This repository has been archived by the owner on Dec 20, 2022. It is now read-only.
/
p3a_bib.html
613 lines (580 loc) · 54.2 KB
/
p3a_bib.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>p3a.bib</title>
</head>
<body>
<h1>p3a.bib</h1><a name="Aldous1999"></a><pre>
@article{<a href="p3a.html#Aldous1999">Aldous1999</a>,
abstract = {Classical mathematical probability focuses on time-asymptotics, describing what happens if some random process runs for ever. In contrast, the word problems each ask “how long until a chain does something?”, and the focus of this book is on finite-time behavior. More precisely, the word problems ask about hitting times, the time until a state or a set of states is first visited, or until each state in a set is visited; or ask about mixing times, the number of steps until the distribution is approximately the stationary distribution. The card-shuffling problems (section 1.1.4) provide a very intuitive setting for such questions; how many shuffles are needed, as a function of the size of the deck, until the deck is well shuffled? Such size-asymptotic results, of which (1.1) is perhaps the best-known, are one of the themes of this book. Thus in one sense our work is in the spirit of the birthday and coupon-collector's problems in undergraduate probability; in another sense our goals are reminiscent of those of computational complexity (P =? NP and all that), which seeks to relate the time required to solve an algorithmic problem to the size of the problem.},
author = {Aldous, David and Fill, James Allen},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Aldous, Fill - Unknown - Reversible Markov Chains and Random Walks on Graphs.pdf:pdf},
pages = {1--516},
title = {{Reversible Markov Chains and Random Walks on Graphs}},
url = {<a href="http://stat-www.berkeley.edu/users/aldous/RWG/book.html">http://stat-www.berkeley.edu/users/aldous/RWG/book.html</a>},
volume = {2002},
year = {1999}
}
</pre>
<a name="Blondel2008"></a><pre>
@article{<a href="p3a.html#Blondel2008">Blondel2008</a>,
abstract = {We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection method in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2.6 million customers and by analyzing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad-hoc modular networks. .},
archiveprefix = {arXiv},
arxivid = {0803.0476},
author = {Blondel, Vincent D. and Guillaume, Jean-Loup and Lambiotte, Renaud and Lefebvre, Etienne},
doi = {10.1088/1742-5468/2008/10/P10008},
eprint = {0803.0476},
file = {:home/dimitri/cours/3A/p3a/papers/blondel2008.pdf:pdf},
isbn = {1742-5468},
issn = {1742-5468},
keywords = {00,0476,08,0803,12,1742-5468,30,arxiv eprint,c 2008 iop publishing,ltd and sissa,mechanics,networks,new applications of statistical,p10008,random graphs},
pmid = {260529900010},
title = {{Fast unfolding of communities in large networks}},
url = {<a href="http://arxiv.org/abs/0803.0476{\%}0Ahttp://dx.doi.org/10.1088/1742-5468/2008/10/P10008">http://arxiv.org/abs/0803.0476{\%}0Ahttp://dx.doi.org/10.1088/1742-5468/2008/10/P10008</a>},
year = {2008}
}
</pre>
<a name="Decelle2011"></a><pre>
@article{<a href="p3a.html#Decelle2011">Decelle2011</a>,
abstract = {In this paper we extend our previous work on the stochastic block model, a commonly used generative model for social and biological networks, and the problem of inferring functional groups or communities from the topology of the network. We use the cavity method of statistical physics to obtain an asymptotically exact analysis of the phase diagram. We describe in detail properties of the detectability/undetectability phase transition and the easy/hard phase transition for the community detection problem. Our analysis translates naturally into a belief propagation algorithm for inferring the group memberships of the nodes in an optimal way, i.e., that maximizes the overlap with the underlying group memberships, and learning the underlying parameters of the block model. Finally, we apply the algorithm to two examples of real-world networks and discuss its performance.},
archiveprefix = {arXiv},
arxivid = {1109.3041},
author = {Decelle, Aurelien and Krzakala, Florent and Moore, Cristopher and Zdeborov{\'{a}}, Lenka},
doi = {10.1103/PhysRevE.84.066106},
eprint = {1109.3041},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Decelle et al. - 2011 - Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.pdf:pdf},
issn = {15393755},
journal = {Physical Review E - Statistical, Nonlinear, and Soft Matter Physics},
number = {6},
pmid = {22304154},
title = {{Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications}},
volume = {84},
year = {2011}
}
</pre>
<a name="Fortunato2007"></a><pre>
@article{<a href="p3a.html#Fortunato2007">Fortunato2007</a>,
abstract = {Community structure represents the local organization of complex networks and$\backslash$nthe single most important feature to extract functional relationships between$\backslash$nnodes. In the last years, the problem of community detection has been$\backslash$nreformulated in terms of the optimization of a function, the Newman-Girvan$\backslash$nmodularity, that is supposed to express the quality of the partitions of a$\backslash$nnetwork into communities. Starting from a recent critical survey on modularity$\backslash$noptimization, pointing out the existence of a resolution limit that poses$\backslash$nsevere limits to its applicability, we discuss the general issue of the use of$\backslash$nquality functions in community detection. Our main conclusion is that quality$\backslash$nfunctions are useful to compare partitions with the same number of modules,$\backslash$nwhereas the comparison of partitions with different numbers of modules is not$\backslash$nstraightforward and may lead to ambiguities.},
archiveprefix = {arXiv},
arxivid = {0705.4445v1},
author = {Fortunato, Santo},
doi = {10.1117/12.726703},
eprint = {0705.4445v1},
file = {:home/dimitri/cours/3A/p3a/papers/fortunato2007.pdf:pdf},
isbn = {0819467383},
issn = {0277786X},
journal = {Optimization},
keywords = {community structure,complex networks,modularity},
pages = {16--18},
title = {{Quality functions in community detection}},
volume = {6601},
year = {2007}
}
</pre>
<a name="Fortunato2010"></a><pre>
@article{<a href="p3a.html#Fortunato2010">Fortunato2010</a>,
abstract = {The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks. ?? 2009 Elsevier B.V.},
archiveprefix = {arXiv},
arxivid = {0906.0612},
author = {Fortunato, Santo},
doi = {10.1016/j.physrep.2009.11.002},
eprint = {0906.0612},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Fortunato - 2010 - Community detection in graphs.pdf:pdf},
isbn = {0370-1573},
issn = {03701573},
journal = {Physics Reports},
keywords = {Clusters,Graphs,Statistical physics},
number = {3-5},
pages = {75--174},
pmid = {22166104},
title = {{Community detection in graphs}},
volume = {486},
year = {2010}
}
</pre>
<a name="Fortunato2012"></a><pre>
@article{<a href="p3a.html#Fortunato2012">Fortunato2012</a>,
abstract = {Graph vertices are often organized into groups that seem to live fairly independently of the rest of the graph, with which they share but a few edges, whereas the relationships between group members are stronger, as shown by the large number of mutual connections. Such groups of vertices, or communities, can be considered as independent compartments of a graph. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. The task is very hard, though, both conceptually, due to the ambiguity in the definition of community and in the discrimination of different partitions and practically, because algorithms must find ``good'' partitions among an exponentially large number of them. Other complications are represented by the possible occurrence of hierarchies, i.e. communities which are nested inside larger communities, and by the existence of overlaps between communities, due to the presence of nodes belonging to more groups. All these aspects are dealt with in some detail and many methods are described, from traditional approaches used in computer science and sociology to recent techniques developed mostly within statistical physics.},
archiveprefix = {arXiv},
arxivid = {0712.2716v1},
author = {Fortunato, Santo and Castellano, Claudio},
doi = {10.1007/978-1-4614-1800-9_33},
eprint = {0712.2716v1},
file = {:home/dimitri/cours/3A/p3a/papers/fortunato2012.pdf:pdf},
isbn = {9781461418009},
issn = {978-0-387-75888-6},
journal = {Computational Complexity: Theory, Techniques, and Applications},
pages = {490--512},
pmid = {25246403},
title = {{Community structure in graphs}},
volume = {9781461418},
year = {2012}
}
</pre>
<a name="Fortunato2016"></a><pre>
@article{<a href="p3a.html#Fortunato2016">Fortunato2016</a>,
abstract = {Community detection in networks is one of the most popular topics of modern network science. Communities, or clusters, are usually groups of vertices having higher probability of being connected to each other than to members of other groups, though other patterns are possible. Identifying communities is an ill-defined problem. There are no universal protocols on the fundamental ingredients, like the definition of community itself, nor on other crucial issues, like the validation of algorithms and the comparison of their performances. This has generated a number of confusions and misconceptions, which undermine the progress in the field. We offer a guided tour through the main aspects of the problem. We also point out strengths and weaknesses of popular methods, and give directions to their use.},
archiveprefix = {arXiv},
arxivid = {1608.00163},
author = {Fortunato, Santo and Hric, Darko},
doi = {10.1016/j.physrep.2016.09.002},
eprint = {1608.00163},
file = {:home/dimitri/cours/3A/p3a/papers/fortunato2016.pdf:pdf},
issn = {0370-1573},
journal = {Physics Reports},
pages = {1--42},
publisher = {Elsevier B.V.},
title = {{Community detection in networks: A user guide}},
url = {<a href="http://arxiv.org/abs/1608.00163">http://arxiv.org/abs/1608.00163</a>},
volume = {659},
year = {2016}
}
</pre>
<a name="Girvan2002"></a><pre>
@article{<a href="p3a.html#Girvan2002">Girvan2002</a>,
abstract = {A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known--a collaboration network and a food web--and find that it detects significant and informative community divisions in both cases.},
archiveprefix = {arXiv},
arxivid = {cond-mat/0112110},
author = {Girvan, M and Newman, M E J},
doi = {10.1073/pnas.122653799},
eprint = {0112110},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Girvan, Newman - Unknown - Community structure in social and biological networks.pdf:pdf},
isbn = {0027-8424},
issn = {0027-8424},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
keywords = {Algorithms,Animals,Community Networks,Computer Simulation,Humans,Models,Nerve Net,Nerve Net: physiology,Neural Networks (Computer),Social Behavior,Theoretical},
number = {12},
pages = {7821--6},
pmid = {12060727},
primaryclass = {cond-mat},
title = {{Community structure in social and biological networks.}},
url = {<a href="http://arxiv.org/abs/cond-mat/0112110">http://arxiv.org/abs/cond-mat/0112110</a>},
volume = {99},
year = {2002}
}
</pre>
<a name="Gopalan2013"></a><pre>
@article{<a href="p3a.html#Gopalan2013">Gopalan2013</a>,
abstract = {Detecting overlapping communities is essential to analyzing and exploring natural networks such as social networks, biological networks, and citation networks. However, most existing approaches do not scale to the size of networks that we regularly observe in the real world. In this paper, we develop a scalable approach to community detection that discovers overlapping communities in massive real-world networks. Our approach is based on a Bayesian model of networks that allows nodes to participate in multiple communities, and a corresponding algorithm that naturally interleaves subsampling from the network and updating an estimate of its communities. We demonstrate how we can discover the hidden community structure of several real-world networks, including 3.7 million US patents, 575,000 physics articles from the arXiv preprint server, and 875,000 connected Web pages from the Internet. Furthermore, we demonstrate on large simulated networks that our algorithm accurately discovers the true community structure. This paper opens the door to using sophisticated statistical models to analyze massive networks.},
archiveprefix = {arXiv},
arxivid = {arXiv:1408.1149},
author = {Gopalan, Prem K and Blei, David M},
doi = {10.1073/pnas.1221839110},
eprint = {arXiv:1408.1149},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Gopalan, Blei - Unknown - Efficient discovery of overlapping communities in massive networks(2).pdf:pdf},
isbn = {1215421109},
issn = {1091-6490},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
keywords = {Algorithms,Bayes Theorem,Community Networks,Computer Simulation,Humans,Models,Social Behavior,Statistical,Stochastic Processes},
number = {36},
pages = {14534--9},
pmid = {23950224},
title = {{Efficient discovery of overlapping communities in massive networks.}},
url = {<a href="http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=3767539{\&}tool=pmcentrez{\&}rendertype=abstract">http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=3767539{\&}tool=pmcentrez{\&}rendertype=abstract</a>},
volume = {110},
year = {2013}
}
</pre>
<a name="Krzakala2013"></a><pre>
@article{<a href="p3a.html#Krzakala2013">Krzakala2013</a>,
abstract = {Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here, we present a class of spectral algorithms based on a nonbacktracking walk on the directed edges of the graph. The spectrum of this operator is much better-behaved than that of the adjacency matrix or other commonly used matrices, maintaining a strong separation between the bulk eigenvalues and the eigenvalues relevant to community structure even in the sparse case. We show that our algorithm is optimal for graphs generated by the stochastic block model, detecting communities all of the way down to the theoretical limit. We also show the spectrum of the nonbacktracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.},
archiveprefix = {arXiv},
arxivid = {1306.5550},
author = {Krzakala, Florent and Moore, Cristopher and Mossel, Elchanan and Neeman, Joe and Sly, Allan and Zdeborov{\'{a}}, Lenka and Zhang, Pan},
doi = {10.1073/pnas.1312486110},
eprint = {1306.5550},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Krzakala et al. - Unknown - Spectral redemption in clustering sparse networks.pdf:pdf},
isbn = {0027-8424, 1091-6490},
issn = {0027-8424, 1091-6490},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
number = {52},
pages = {20935--20940},
pmid = {24277835},
title = {{Spectral redemption in clustering sparse networks}},
url = {<a href="http://www.pnas.org/content/110/52/20935{\%}5Cnhttp://www.ncbi.nlm.nih.gov/pubmed/24277835{\%}5Cnhttp://www.pnas.org/content/110/52/20935.full.pdf">http://www.pnas.org/content/110/52/20935{\%}5Cnhttp://www.ncbi.nlm.nih.gov/pubmed/24277835{\%}5Cnhttp://www.pnas.org/content/110/52/20935.full.pdf</a>},
volume = {110},
year = {2013}
}
</pre>
<a name="Lovasz1993"></a><pre>
@article{<a href="p3a.html#Lovasz1993">Lovasz1993</a>,
abstract = {This paper we'll formulate the results in terms of random walks, and mostly restrict our attention to the undirected case. 2 L. Lov'asz},
author = {Lov{\'{a}}sz, L},
doi = {10.1.1.39.2847},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lo Asz - 1993 - Random Walks on Graphs A Survey.pdf:pdf},
isbn = {9789638022738},
issn = {03044149},
journal = {Combinatorics Paul Erdos is Eighty},
number = {Volume 2},
pages = {1--46},
title = {{Random walks on graphs: A survey}},
url = {<a href="http://www.cs.yale.edu/publications/techreports/tr1029.pdf">http://www.cs.yale.edu/publications/techreports/tr1029.pdf</a>},
volume = {2},
year = {1993}
}
</pre>
<a name="Luxburg2006"></a><pre>
@article{<a href="p3a.html#Luxburg2006">Luxburg2006</a>,
abstract = {In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. Nevertheless, on the first glance spectral clustering looks a bit mysterious, and it is not obvious to see why it works at all and what it really does. This article is a tutorial introduction to spectral clustering. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed.},
archiveprefix = {arXiv},
arxivid = {arXiv:0711.0189v1},
author = {Luxburg, Ulrike Von},
doi = {10.1007/s11222-007-9033-z},
eprint = {arXiv:0711.0189v1},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Von Luxburg - 2007 - A Tutorial on Spectral Clustering.pdf:pdf},
isbn = {0960-3174},
issn = {09603174},
journal = {Statistics and Computing},
keywords = {graph laplacian,spectral clustering},
number = {March},
pages = {395--416},
pmid = {19784854},
title = {{A Tutorial on Spectral Clustering A Tutorial on Spectral Clustering}},
url = {<a href="http://www.springerlink.com/index/10.1007/s11222-007-9033-z">http://www.springerlink.com/index/10.1007/s11222-007-9033-z</a>},
volume = {17},
year = {2006}
}
</pre>
<a name="Malliaros2013"></a><pre>
@misc{<a href="p3a.html#Malliaros2013">Malliaros2013</a>,
abstract = {Networks (or graphs) appear as dominant structures in diverse domains, including sociology, biology, neuroscience and computer science. In most of the aforementioned cases graphs are directed - in the sense that there is directionality on the edges, making the semantics of the edges nonsymmetric as the source node transmits some property to the target one but not vice versa. An interesting feature that real networks present is the clustering or community structure property, under which the graph topology is organized into modules commonly called communities or clusters. The essence here is that nodes of the same community are highly similar while on the contrary, nodes across communities present low similarity. Revealing the underlying community structure of directed complex networks has become a crucial and interdisciplinary topic with a plethora of relevant application domains. Therefore, naturally there is a recent wealth of research production in the area of mining directed graphs - with clustering being the primary method sought and the primary tool for community detection and evaluation. The goal of this paper is to offer an in-depth comparative review of the methods presented so far for clustering directed networks along with the relevant necessary methodological background and also related applications. The survey commences by offering a concise review of the fundamental concepts and methodological base on which graph clustering algorithms capitalize on. Then we present the relevant work along two orthogonal classifications. The first one is mostly concerned with the methodological principles of the clustering algorithms, while the second one approaches the methods from the viewpoint regarding the properties of a good cluster in a directed network. Further, we present methods and metrics for evaluating graph clustering results, demonstrate interesting application domains and provide promising future research directions. ?? 2013 Elsevier B.V.},
archiveprefix = {arXiv},
arxivid = {1308.0971},
author = {Malliaros, Fragkiskos D. and Vazirgiannis, Michalis},
booktitle = {Physics Reports},
doi = {10.1016/j.physrep.2013.08.002},
eprint = {1308.0971},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Malliaros, Vazirgiannis - 2013 - Clustering and community detection in directed networks A survey(2).pdf:pdf},
isbn = {0370-1573},
issn = {03701573},
keywords = {Community detection,Complex networks,Directed networks,Graph clustering,Graph mining},
number = {4},
pages = {95--142},
title = {{Clustering and community detection in directed networks: A survey}},
volume = {533},
year = {2013}
}
</pre>
<a name="Martin2016"></a><pre>
@article{<a href="p3a.html#Martin2016">Martin2016</a>,
abstract = {In the study of networked systems such as biological, technological, and social networks the available data are often uncertain. Rather than knowing the structure of a network exactly, we know the connections between nodes only with a certain probability. In this paper we develop methods for the analysis of such uncertain data, focusing particularly on the problem of community detection. We give a principled maximum-likelihood method for inferring community structure and demonstrate how the results can be used to make improved estimates of the true structure of the network. Using computer-generated benchmark networks we demonstrate that our methods are able to reconstruct known communities more accurately than previous approaches based on data thresholding. We also give an example application to the detection of communities in a protein-protein interaction network.},
archiveprefix = {arXiv},
arxivid = {1506.05490},
author = {Martin, Travis and Ball, Brian and Newman, M. E J},
doi = {10.1103/PhysRevE.93.012306},
eprint = {1506.05490},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Martin, Ball, Newman - 2016 - Structural inference for uncertain networks(2).pdf:pdf},
issn = {15502376},
journal = {Physical Review E - Statistical, Nonlinear, and Soft Matter Physics},
number = {1},
pmid = {26871091},
title = {{Structural inference for uncertain networks}},
volume = {93},
year = {2016}
}
</pre>
<a name="Mørup2012"></a><pre>
@article{<a href="p3a.html#Mørup2012">Mørup2012</a>,
abstract = {Many networks of scientific interest naturally decompose into clusters or communities with comparatively fewer external than internal links; however, current Bayesian models of network communities do not exert this intuitive notion of communities. We formulate a nonparametric Bayesian model for community detection consistent with an intuitive definition of communities and present a Markov chain Monte Carlo procedure for inferring the community structure. A Matlab toolbox with the proposed inference procedure is available for download. On synthetic and real networks, our model detects communities consistent with ground truth, and on real networks, it outperforms existing approaches in predicting missing links. This suggests that community structure is an important structural property of networks that should be explicitly modeled.},
archiveprefix = {arXiv},
arxivid = {1608.04242},
author = {M{\o}rup, Morten and Schmidt, Mikkel N.},
doi = {10.1162/NECO_a_00314},
eprint = {1608.04242},
file = {:home/dimitri/cours/3A/p3a/papers/morup2012.pdf:pdf},
issn = {0899-7667},
journal = {Neural Computation},
keywords = {community detection,complex networks,infinite relational model,modularity,normalized cut,stochastic block-model},
number = {9},
pages = {2434--2456},
pmid = {22509971},
title = {{Bayesian Community Detection}},
volume = {24},
year = {2012}
}
</pre>
<a name="Newman2003"></a><pre>
@article{<a href="p3a.html#Newman2003">Newman2003</a>,
abstract = {We study assortative mixing in networks, the tendency for vertices in networks to be connected to other vertices that are like (or unlike) them in some way. We consider mixing according to discrete characteristics such as language or race in social networks and scalar characteristics such as age. As a special example of the latter we consider mixing according to vertex degree, i.e., according to the number of connections vertices have to other vertices: do gregarious people tend to associate with other gregarious people? We propose a number of measures of assortative mixing appropriate to the various mixing types, and apply them to a variety of real-world networks, showing that assortative mixing is a pervasive phenomenon found in many networks. We also propose several models of assortatively mixed networks, both analytic ones based on generating function methods, and numerical ones based on Monte Carlo graph generation techniques. We use these models to probe the properties of networks as their level of assortativity is varied. In the particular case of mixing by degree, we find strong variation with assortativity in the connectivity of the network and in the resilience of the network to the removal of vertices.},
archiveprefix = {arXiv},
arxivid = {cond-mat/0209450},
author = {Newman, M E J},
doi = {10.1103/PhysRevE.67.026126},
eprint = {0209450},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Newman - Unknown - Mixing patterns in networks.pdf:pdf},
isbn = {1539-3755},
issn = {1063-651X},
journal = {Physical Review E},
number = {2},
pages = {026126},
pmid = {12636767},
primaryclass = {cond-mat},
title = {{Mixing patterns in networks}},
volume = {67},
year = {2003}
}
</pre>
<a name="Newman2006"></a><pre>
@article{<a href="p3a.html#Newman2006">Newman2006</a>,
abstract = {Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as "modularity" over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets.},
archiveprefix = {arXiv},
arxivid = {physics/0602124},
author = {Newman, M E J},
doi = {10.1073/pnas.0601602103},
eprint = {0602124},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Newman - Unknown - Modularity and community structure in networks.pdf:pdf},
isbn = {0027-8424 (Print)$\backslash$r0027-8424 (Linking)},
issn = {0027-8424},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
number = {23},
pages = {8577--8582},
pmid = {16723398},
primaryclass = {physics},
title = {{Modularity and community structure in networks.}},
url = {<a href="http://www.ncbi.nlm.nih.gov/pubmed/16723398{\%}5Cnhttps://www.ncbi.nlm.nih.gov/pmc/articles/PMC1482622/">http://www.ncbi.nlm.nih.gov/pubmed/16723398{\%}5Cnhttps://www.ncbi.nlm.nih.gov/pmc/articles/PMC1482622/</a>},
volume = {103},
year = {2006}
}
</pre>
<a name="Newman2016a"></a><pre>
@article{<a href="p3a.html#Newman2016a">Newman2016a</a>,
abstract = {For many networks of scientific interest we know both the connections of the network and information about the network nodes, such as the age or gender of individuals in a social network, geographic location of nodes in the Internet, or cellular function of nodes in a gene regulatory network. Here we demonstrate how this "metadata" can be used to improve our analysis and understanding of network structure. We focus in particular on the problem of community detection in networks and develop a mathematically principled approach that combines a network and its metadata to detect communities more accurately than can be done with either alone. Crucially, the method does not assume that the metadata are correlated with the communities we are trying to find. Instead the method learns whether a correlation exists and correctly uses or ignores the metadata depending on whether they contain useful information. The learned correlations are also of interest in their own right, allowing us to make predictions about the community membership of nodes whose network connections are unknown. We demonstrate our method on synthetic networks with known structure and on real-world networks, large and small, drawn from social, biological, and technological domains.},
archiveprefix = {arXiv},
arxivid = {1507.04001},
author = {Newman, M E J and Clauset, Aaron},
doi = {10.1038/ncomms11863},
eprint = {1507.04001},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Newman, Clauset - 2016 - Structure and inference in annotated networks.pdf:pdf},
issn = {2041-1723},
journal = {Nature Communications},
number = {May},
pages = {1--16},
pmid = {27306566},
title = {{Structure and inference in annotated networks}},
url = {<a href="http://arxiv.org/abs/1507.04001">http://arxiv.org/abs/1507.04001</a>},
volume = {7},
year = {2016}
}
</pre>
<a name="Newman2001"></a><pre>
@article{<a href="p3a.html#Newman2001">Newman2001</a>,
abstract = {Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.},
archiveprefix = {arXiv},
arxivid = {cond-mat/0007235},
author = {Newman, M E and Strogatz, S H and Watts, D J},
doi = {10.1103/PhysRevE.64.026118},
eprint = {0007235},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Newman, Strogatz, Watts - Unknown - Random graphs with arbitrary degree distributions and their applications(2).pdf:pdf},
isbn = {1539-3755 (Print)$\backslash$r1539-3755 (Linking)},
issn = {1539-3755},
journal = {Physical review. E, Statistical, nonlinear, and soft matter physics},
number = {2 Pt 2},
pages = {026118},
pmid = {11497662},
primaryclass = {cond-mat},
title = {{Random graphs with arbitrary degree distributions and their applications.}},
url = {<a href="http://www.ncbi.nlm.nih.gov/pubmed/11497662">http://www.ncbi.nlm.nih.gov/pubmed/11497662</a>},
volume = {64},
year = {2001}
}
</pre>
<a name="Newman2006a"></a><pre>
@article{<a href="p3a.html#Newman2006a">Newman2006a</a>,
abstract = {We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks.},
archiveprefix = {arXiv},
arxivid = {physics/0605087},
author = {Newman, M. E J},
doi = {10.1103/PhysRevE.74.036104},
eprint = {0605087},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Newman - 2006 - Finding community structure in networks using the eigenvectors of matrices.pdf:pdf},
isbn = {1539-3755 (Print)$\backslash$r1539-3755 (Linking)},
issn = {15393755},
journal = {Physical Review E - Statistical, Nonlinear, and Soft Matter Physics},
number = {3},
pmid = {17025705},
primaryclass = {physics},
title = {{Finding community structure in networks using the eigenvectors of matrices}},
volume = {74},
year = {2006}
}
</pre>
<a name="Newman2004"></a><pre>
@article{<a href="p3a.html#Newman2004">Newman2004</a>,
abstract = {The connections in many networks are not merely binary entities, either present or not, but have associated weights that record their strengths relative to one another. Recent studies of networks have, by and large, steered clear of such weighted networks, which are often perceived as being harder to analyze than their unweighted counterparts. Here we point out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph, allowing us to apply standard techniques for unweighted graphs to weighted ones as well. We give a number of examples of the method, including an algorithm for detecting community structure in weighted networks and a simple proof of the maximum-flow-minimum-cut theorem.},
archiveprefix = {arXiv},
arxivid = {cond-mat/0407503},
author = {Newman, M. E J},
doi = {10.1103/PhysRevE.70.056131},
eprint = {0407503},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Newman - 2004 - Analysis of weighted networks(2).pdf:pdf},
isbn = {1539-3755$\backslash$r1550-2376},
issn = {15393755},
journal = {Physical Review E - Statistical, Nonlinear, and Soft Matter Physics},
number = {5 2},
pmid = {15600716},
primaryclass = {cond-mat},
title = {{Analysis of weighted networks}},
volume = {70},
year = {2004}
}
</pre>
<a name="Newman2004a"></a><pre>
@article{<a href="p3a.html#Newman2004a">Newman2004a</a>,
abstract = {Many networks display community structure--groups of vertices within which connections are dense but between which they are sparser--and sensitive computer algorithms have in recent years been developed for detecting this structure. These algorithms, however, are computationally demanding, which limits their application to small networks. Here we describe an algorithm which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster, than previous algorithms. We give several example applications, including one to a collaboration network of more than 50,000 physicists.},
archiveprefix = {arXiv},
arxivid = {arXiv:cond-mat/0309508v1},
author = {Newman, M. E J},
doi = {10.1103/PhysRevE.69.066133},
eprint = {0309508v1},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Newman - 2004 - Fast algorithm for detecting community structure in networks.pdf:pdf},
isbn = {1539-3755 (Print)$\backslash$n1539-3755 (Linking)},
issn = {15393755},
journal = {Physical Review E - Statistical, Nonlinear, and Soft Matter Physics},
number = {6 2},
pmid = {15244693},
primaryclass = {arXiv:cond-mat},
title = {{Fast algorithm for detecting community structure in networks}},
volume = {69},
year = {2004}
}
</pre>
<a name="Newman2004b"></a><pre>
@article{<a href="p3a.html#Newman2004b">Newman2004b</a>,
abstract = {We propose and study a set of algorithms for discovering community structure in networks-natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using any one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.},
archiveprefix = {arXiv},
arxivid = {cond-mat/0308217},
author = {Newman, M. E J and Girvan, M.},
doi = {10.1103/PhysRevE.69.026113},
eprint = {0308217},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Newman, Girvan - 2004 - Finding and evaluating community structure in networks.pdf:pdf},
isbn = {1539-3755 (Print)$\backslash$n1539-3755 (Linking)},
issn = {1063651X},
journal = {Physical Review E - Statistical, Nonlinear, and Soft Matter Physics},
number = {2 2},
pmid = {14995526},
primaryclass = {cond-mat},
title = {{Finding and evaluating community structure in networks}},
volume = {69},
year = {2004}
}
</pre>
<a name="Newman2015"></a><pre>
@article{<a href="p3a.html#Newman2015">Newman2015</a>,
abstract = {A substantial volume of research is devoted to studies of community structure in networks, but communities are not the only possible form of large-scale network structure. Here, we describe a broad extension of community structure that encompasses traditional communities but includes a wide range of generalized structural patterns as well. We describe a principled method for detecting this generalized structure in empirical network data and demonstrate with real-world examples how it can be used to learn new things about the shape and meaning of networks.},
archiveprefix = {arXiv},
arxivid = {1505.07478},
author = {Newman, M. E J and Peixoto, Tiago P.},
doi = {10.1103/PhysRevLett.115.088701},
eprint = {1505.07478},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Newman, Peixoto - 2015 - Generalized Communities in Networks(2).pdf:pdf},
issn = {10797114},
journal = {Physical Review Letters},
number = {8},
pmid = {26340218},
title = {{Generalized Communities in Networks}},
volume = {115},
year = {2015}
}
</pre>
<a name="Newman2016"></a><pre>
@article{<a href="p3a.html#Newman2016">Newman2016</a>,
abstract = {Community detection, the division of a network into dense subnetworks with only sparse connections between them, has been a topic of vigorous study in recent years. However, while there exist a range of powerful and flexible methods for dividing a network into a specified number of communities, it is an open question how to determine exactly how many communities one should use. Here we describe a mathematically principled approach for finding the number of communities in a network using a maximum-likelihood method. We demonstrate this approach on a range of real-world examples with known community structure, finding that it is able to determine the number of communities correctly in every case.},
archiveprefix = {arXiv},
arxivid = {1605.02753},
author = {Newman, M. E J and Reinert, Gesine},
doi = {10.1103/PhysRevLett.117.078301},
eprint = {1605.02753},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Newman, Reinert - 2016 - Estimating the Number of Communities in a Network(2).pdf:pdf},
issn = {10797114},
journal = {Physical Review Letters},
number = {7},
pmid = {27564002},
title = {{Estimating the Number of Communities in a Network}},
volume = {117},
year = {2016}
}
</pre>
<a name="Ricci-Tersenghi2016"></a><pre>
@article{<a href="p3a.html#Ricci-Tersenghi2016">Ricci-Tersenghi2016</a>,
abstract = {The problem of detecting communities in a graph is maybe one the most studied inference problems, given its simplicity and widespread diffusion among several disciplines. A very common benchmark for this problem is the stochastic block model or planted partition problem, where a phase transition takes place in the detection of the planted partition by changing the signal-to-noise ratio. Optimal algorithms for the detection exist which are based on spectral methods, but we show these are extremely sensible to slight modification in the generative model. Recently Javanmard, Montanari and Ricci-Tersenghi (arXiv:1511.08769) have used statistical physics arguments, and numerical simulations to show that finding communities in the stochastic block model via semidefinite programming is quasi optimal. Further, the resulting semidefinite relaxation can be solved efficiently, and is very robust with respect to changes in the generative model. In this paper we study in detail several practical aspects of this new algorithm based on semidefinite programming for the detection of the planted partition. The algorithm turns out to be very fast, allowing the solution of problems with {\$}O(10{\^{}}5){\$} variables in few second on a laptop computer.},
archiveprefix = {arXiv},
arxivid = {1603.09045},
author = {Ricci-Tersenghi, Federico and Javanmard, Adel and Montanari, Andrea},
doi = {10.1088/1742-6596/699/1/012015},
eprint = {1603.09045},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Ricci-Tersenghi, Javanmard, Montanari - Unknown - Performance of a community detection algorithm based on semidefinite programming(2).pdf:pdf},
issn = {1742-6588},
journal = {Journal of Physics: Conference Series},
pages = {012015},
title = {{Performance of a community detection algorithm based on semidefinite programming}},
url = {<a href="http://arxiv.org/abs/1603.09045{\%}5Cnhttp://stacks.iop.org/1742-6596/699/i=1/a=012015?key=crossref.252ca19dc33209455e53a35dcdd31edc">http://arxiv.org/abs/1603.09045{\%}5Cnhttp://stacks.iop.org/1742-6596/699/i=1/a=012015?key=crossref.252ca19dc33209455e53a35dcdd31edc</a>},
volume = {699},
year = {2016}
}
</pre>
<a name="Saade2014"></a><pre>
@article{<a href="p3a.html#Saade2014">Saade2014</a>,
abstract = {Spectral clustering is a standard approach to label nodes on a graph by studying the (largest or lowest) eigenvalues of a symmetric real matrix such as e.g. the adjacency or the Laplacian. Recently, it has been argued that using instead a more complicated, non-symmetric and higher dimensional operator, related to the non-backtracking walk on the graph, leads to improved performance in detecting clusters, and even to optimal performance for the stochastic block model. Here, we propose to use instead a simpler object, a symmetric real matrix known as the Bethe Hessian operator, or deformed Laplacian. We show that this approach combines the performances of the non-backtracking operator, thus detecting clusters all the way down to the theoretical limit in the stochastic block model, with the computational, theoretical and memory advantages of real symmetric matrices.},
archiveprefix = {arXiv},
arxivid = {arXiv:1406.1880v1},
author = {Saade, Alaa and Krzakala, Florent and Zdeborov{\'{a}}, Lenka},
eprint = {arXiv:1406.1880v1},
file = {:home/dimitri/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Saade, Krzakala, Zdeborov{\'{a}} - Unknown - Spectral Clustering of Graphs with the Bethe Hessian.pdf:pdf},
issn = {10495258},
journal = {arXiv preprint arXiv:1406.1880},
number = {1},
pages = {1--8},
title = {{Spectral Clustering of Graphs with the Bethe Hessian}},
url = {<a href="http://arxiv.org/abs/1406.1880">http://arxiv.org/abs/1406.1880</a>},
year = {2014}
}
</pre>
<a name="Shi2010"></a><pre>
@article{<a href="p3a.html#Shi2010">Shi2010</a>,
abstract = {Community detection, as an important unsupervised learning problem in social network analysis, has attracted great interests in various research areas. Many objective functions for community detection that can capture the intuition of communities have been introduced from different research fields. Based on the classical single objective optimization framework, this paper compares a variety of these objective functions and explores the characteristics of communities they can identify. Experiments show most objective functions have the resolution limit and their communities structure have many different characteristics.},
author = {Shi, Chuan and Cai, Yanan and Yu, Philip S. and Yan, Zhenyu and Wu, Bin},
doi = {10.1109/ICDMW.2010.107},
file = {:home/dimitri/cours/3A/p3a/papers/shi2010.pdf:pdf},
isbn = {978-0-7695-4257-7},
issn = {15504786},
journal = {2010 IEEE International Conference on Data Mining Workshops},
keywords = {Community detection,multi-objective optimization,objective functions,single-objective optimization},
pages = {1234--1241},
title = {{A Comparison of Objective Functions in Network Community Detection}},
year = {2010}
}
</pre>
<a name="Wierzbicki2016"></a><pre>
@article{<a href="p3a.html#Wierzbicki2016">Wierzbicki2016</a>,
abstract = {Ciencia de las redes es una disciplina emergente se ocupa del estudio de los modelos de red en dominios que van desde la biolog{\'{i}}a y la f{\'{i}}sica con la inform{\'{a}}tica, de los mercados financieros para la integraci{\'{o}}n cultural y de medios de comunicaci{\'{o}}n social a las enfermedades infecciosas. Tambi{\'{e}}n es una herramienta esencial en la comprensi{\'{o}}n de muchos tipos de datos grandes, dando lugar a numerosas aplicaciones pr{\'{a}}cticas. Los modelos de red ayudan a los investigadores y los profesionales tienen sentido de un mundo cada vez m{\'{a}}s complejo, especialmente en relaci{\'{o}}n con los fen{\'{o}}menos sociales mediadas a trav{\'{e}}s de tecnolog{\'{i}}a de la informaci{\'{o}}n. Este volumen contiene varias contribuciones a la investigaci{\'{o}}n en el {\'{a}}rea de la ciencia de las redes, seleccionados de las mejores presentaciones de la conferencia NetSci X-2016. La tasa de aceptaci{\'{o}}n de conferencias para las comunicaciones completas fue del 20{\%}. La Conferencia Internacional y la Facultad de Ciencias de la red (NetSci) es un evento interdisciplinario, reuniendo todos los investigadores interesados en la ciencia de las redes. Despu{\'{e}}s de 11 ediciones, la conferencia es el evento m{\'{a}}s grande y m{\'{a}}s conocida de la zona. Publicado por primera vez en los Lecture Notes in Computer Science serie, el volumen conserva el car{\'{a}}cter interdisciplinario de la ciencia a la red, al tiempo que subraya su conexi{\'{o}}n con la inform{\'{a}}tica. Las obras de los investigadores de diversos or{\'{i}}genes, tales como las ciencias sociales, biolog{\'{i}}a, econom{\'{i}}a y ciencias de la computaci{\'{o}}n, se unen en el objetivo de una mejor comprensi{\'{o}}n de las redes complejas. El desarrollo de mejores modelos de fen{\'{o}}menos complejos, como las redes complejas, es en s{\'{i}} mismo una importante contribuci{\'{o}}n a la inform{\'{a}}tica. El uso de tales modelos computacionales puede mejorar la tecnolog{\'{i}}a de la informaci{\'{o}}n existente, as{\'{i}} como ampliar el alcance de las aplicaciones de la tecnolog{\'{i}}a de la informaci{\'{o}}n en nuevas {\'{a}}reas. Por esta raz{\'{o}}n, el estudio de la ciencia de las redes puede ser beneficioso para los inform{\'{a}}ticos, y los avances en la ciencia de las redes puede ser considerado como los avances en la inform{\'{a}}tica.},
author = {Wierzbicki, Adam and Brandes, Ulrik and Schweitzer, Frank and Pedreschi, Dino},
doi = {10.1007/978-3-319-28361-6},
file = {:home/dimitri/cours/3A/p3a/papers/creusefond2016.pdf:pdf},
isbn = {9783319283609},
issn = {16113349},
journal = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
keywords = {community detection,quality functions,social networks},
pages = {111--125},
title = {{Advances in network science: 12th international conference and school, NetSci-X 2016 Wroclaw, Poland, January 11–13, 2016 proceedings}},
volume = {9564},
year = {2016}
}
</pre>
<a name="Yang2015"></a><pre>
@article{<a href="p3a.html#Yang2015">Yang2015</a>,
abstract = {Nodes in real-world networks organize into densely linked communities where edges appear with high concentration among the members of the community. Identifying such communities of nodes has proven to be a challenging task due to a plethora of defin-itions of network communities, intractability of methods for detecting them, and the issues with evaluation which stem from the lack of a reliable gold-standard ground-truth. In this paper, we distinguish between structural and functional definitions of network communities. Structural definitions of communities are based on connectivity patterns, like the density of connections between the community members, while functional definitions are based on (often unobserved) common function or role of the community members in the network. We argue that the goal of network community detection is to extract functional commu-nities based on the connectivity structure of the nodes in the network. We then identify networks with explicitly labeled functional communities to which we refer as ground-truth communities. In particular, we study a set of 230 large real-world social, collaboration, and information networks where nodes explicitly state their community memberships. For exam-ple, in social networks, nodes explicitly join various interest-based social groups. We use such social groups to define a reliable and robust notion of ground-truth communities. We then propose a methodology, which allows us to compare and quantitatively evaluate how different structural definitions of communities correspond to ground-truth functional com-munities. We study 13 commonly used structural definitions of communities and examine their sensitivity, robustness and performance in identifying the ground-truth. We show that the 13 structural definitions are heavily correlated and naturally group into four classes. We find that two of these definitions, Conductance and Triad participation ratio, consistently give the best performance in identifying ground-truth communities. We also investigate a task of detecting communities given a single seed node. We extend the local spectral cluster-ing algorithm into a heuristic parameter-free community detection method that easily scales to networks with more than 100 million nodes. The proposed method achieves 30 {\%} relative improvement over current local clustering methods.},
archiveprefix = {arXiv},
arxivid = {1205.6233},
author = {Yang, Jaewon and Leskovec, Jure},
doi = {10.1007/s10115-013-0693-z},
eprint = {1205.6233},
file = {:home/dimitri/cours/3A/p3a/papers/yang2013.pdf:pdf},
isbn = {9780769549057},
issn = {02193116},
journal = {Knowledge and Information Systems},
title = {{Defining and evaluating network communities based on ground-truth}},
year = {2015}
}
</pre>
</body>
</html>