User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

The many facets of community detection in complex networks

Primary tabs

download
  • Open access
  • PDF
  • 538.42 K
Schaub, Michael [UCL] Delvenne, Jean-Charles [UCL] Rosvall, Martin Lambiotte, Renaud [UNamur]
Document type Article de périodique (Journal article) – Article de recherche
Access type Accès libre
Publication date 2017
Language Anglais
Journal information "Applied Network Science" - Vol. 2, no.1 (2017)
Peer reviewed yes
issn 2364-8228
e-issn 2364-8228
Publication status Publié
Affiliations UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique
UCL - SSH/LIDAM/CORE - Center for operations research and econometrics
Links
  1. Ahn Yong-Yeol, Bagrow James P., Lehmann Sune, Link communities reveal multiscale complexity in networks, 10.1038/nature09182
  2. Aicher C., Jacobs A. Z., Clauset A., Learning latent block structure in weighted networks, 10.1093/comnet/cnu026
  3. Alpert Charles J, Kahng Andrew B, Recent directions in netlist partitioning: a survey, 10.1016/0167-9260(95)00008-4
  4. Andersen Reid, Chung Fan, Lang Kevin, Local Graph Partitioning using PageRank Vectors, 10.1109/focs.2006.44
  5. Anderson Carolyn J, Wasserman Stanley, Faust Katherine, Building stochastic blockmodels, 10.1016/0378-8733(92)90017-2
  6. Arenas Alex, Díaz-Guilera Albert, Pérez-Vicente Conrad J., Synchronization Reveals Topological Scales in Complex Networks, 10.1103/physrevlett.96.114102
  7. Bacik Karol A., Schaub Michael T., Beguerisse-Díaz Mariano, Billeh Yazan N., Barahona Mauricio, Flow-Based Network Analysis of the Caenorhabditis elegans Connectome, 10.1371/journal.pcbi.1005055
  8. Benson A. R., Gleich D. F., Leskovec J., Higher-order organization of complex networks, 10.1126/science.aad9029
  9. Bickel Peter J., Sarkar Purnamrita, Hypothesis testing for automated community detection in networks, 10.1111/rssb.12117
  10. Blondel Vincent D, Guillaume Jean-Loup, Lambiotte Renaud, Lefebvre Etienne, Fast unfolding of communities in large networks, 10.1088/1742-5468/2008/10/p10008
  11. Boccaletti S., Bianconi G., Criado R., del Genio C.I., Gómez-Gardeñes J., Romance M., Sendiña-Nadal I., Wang Z., Zanin M., The structure and dynamics of multilayer networks, 10.1016/j.physrep.2014.07.001
  12. Browet A, Hendrickx JM, Sarlette A (2016) Incompatibility boundaries for properties of community partitions. arXiv:160300621. https://arxiv.org/abs/1603.00621 .
  13. Chen Mingming, Kuzmin Konstantin, Szymanski Boleslaw K., Community Detection via Maximization of Modularity and Its Variants, 10.1109/tcss.2014.2307458
  14. Chen M, Nguyen T, Szymanski BK (2015) A new metric for quality of network community structure. arXiv:150704308.
  15. Coscia Michele, Giannotti Fosca, Pedreschi Dino, A classification for community discovery methods in complex networks, 10.1002/sam.10133
  16. Decelle Aurelien, Krzakala Florent, Moore Cristopher, Zdeborová Lenka, Inference and Phase Transitions in the Detection of Modules in Sparse Networks, 10.1103/physrevlett.107.065701
  17. Delvenne J.- C., Yaliraki S. N., Barahona M., Stability of graph communities across time scales, 10.1073/pnas.0903215107
  18. Delvenne Jean-Charles, Schaub Michael T., Yaliraki Sophia N., Barahona Mauricio, The Stability of a Graph Partition: A Dynamics-Based Framework for Community Detection, Dynamics On and Of Complex Networks, Volume 2 (2013) ISBN:9781461467281 p.221-242, 10.1007/978-1-4614-6729-8_11
  19. Donath WE, Hoffman AJ (1972) Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices. IBM Tech Discl Bull 15(3): 938–944.
  20. Donath W. E., Hoffman A. J., Lower Bounds for the Partitioning of Graphs, 10.1147/rd.175.0420
  21. Everett Martin G., Borgatti Stephen P., Regular equivalence: General theory, 10.1080/0022250x.1994.9990134
  22. Fiedler M (1973) Algebraic connectivity of graphs. Czechoslov Math J 23(2): 298–305.
  23. Fiedler M (1975) A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslov Math J 25(4): 619–633.
  24. Fortunato Santo, Community detection in graphs, 10.1016/j.physrep.2009.11.002
  25. Fortunato S., Barthelemy M., Resolution limit in community detection, 10.1073/pnas.0605965104
  26. Fortunato Santo, Hric Darko, Community detection in networks: A user guide, 10.1016/j.physrep.2016.09.002
  27. Good Benjamin H., de Montjoye Yves-Alexandre, Clauset Aaron, Performance of modularity maximization in practical contexts, 10.1103/physreve.81.046106
  28. Guimerà Roger, Sales-Pardo Marta, Amaral Luís A. Nunes, Modularity from fluctuations in random graphs and complex networks, 10.1103/physreve.70.025101
  29. Hagen L., Kahng A.B., New spectral methods for ratio cut partitioning and clustering, 10.1109/43.159993
  30. Hanneman RA, Riddle M (2005) Introduction to social network methods, University of California Riverside.
  31. Holland Paul W., Laskey Kathryn Blackmond, Leinhardt Samuel, Stochastic blockmodels: First steps, 10.1016/0378-8733(83)90021-7
  32. Holme Petter, Saramäki Jari, Temporal networks, 10.1016/j.physrep.2012.03.001
  33. Kannan Ravi, Vempala Santosh, Vetta Adrian, On clusterings : Good, bad and spectral, 10.1145/990308.990313
  34. Karrer Brian, Newman M. E. J., Stochastic blockmodels and community structure in networks, 10.1103/physreve.83.016107
  35. Kernighan B. W., Lin S., An Efficient Heuristic Procedure for Partitioning Graphs, 10.1002/j.1538-7305.1970.tb01770.x
  36. Kleinberg J (2003) An impossibility theorem for clustering. In: Becker S, Thrun S, Obermayer K (eds)Advances in neural information processing systems 15, 463–470.. MIT Press. http://papers.nips.cc/paper/2340-an-impossibility-theorem-for-clustering.pdf .
  37. Kloster Kyle, Gleich David F., Heat kernel based community detection, 10.1145/2623330.2623706
  38. Krzakala F., Moore C., Mossel E., Neeman J., Sly A., Zdeborova L., Zhang P., Spectral redemption in clustering sparse networks, 10.1073/pnas.1312486110
  39. Lambiotte Renaud, Delvenne Jean-Charles, Barahona Mauricio, Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks, 10.1109/tnse.2015.2391998
  40. Lancichinetti Andrea, Fortunato Santo, Limits of modularity maximization in community detection, 10.1103/physreve.84.066122
  41. Lancichinetti Andrea, Fortunato Santo, Radicchi Filippo, Benchmark graphs for testing community detection algorithms, 10.1103/physreve.78.046110
  42. Malliaros Fragkiskos D., Vazirgiannis Michalis, Clustering and community detection in directed networks: A survey, 10.1016/j.physrep.2013.08.002
  43. Massoulié Laurent, Community detection thresholds and the weak Ramanujan property, 10.1145/2591796.2591857
  44. Mossel E, Neeman J, Sly A (2013) A proof of the block model threshold conjecture. arXiv:13114115. https://arxiv.org/abs/1311.4115 .
  45. Newman M. E. J., Equivalence between modularity optimization and maximum likelihood methods for community detection, 10.1103/physreve.94.052315
  46. Newman M. E. J., Finding community structure in networks using the eigenvectors of matrices, 10.1103/physreve.74.036104
  47. Newman MEJ (2006b) Modularity and community structure in networks. Proc Natl Acad Sci 103(23): 8577–8582. doi: 10.1073/pnas.0601602103 http://www.pnas.org/content/103/23/8577.abstract .
  48. Newman M. E. J., Communities, modules and large-scale structure in networks, 10.1038/nphys2162
  49. Newman M. E. J., Girvan M., Finding and evaluating community structure in networks, 10.1103/physreve.69.026113
  50. Nicosia V., Vertes P. E., Schafer W. R., Latora V., Bullmore E. T., Phase transition in the economically modeled growth of a cellular nervous system, 10.1073/pnas.1300753110
  51. Nowicki Krzysztof, Snijders Tom A. B, Estimation and Prediction for Stochastic Blockstructures, 10.1198/016214501753208735
  52. Parthasarathy, S, Ruan Y, Satuluri V (2011) Community discovery in social networks: Applications, methods and emerging trends In: Social network data analytics, 79–113.. Springer.
  53. Peel L, Larremore DB, Clauset A (2016) The ground truth about metadata and community detection in networks. arXiv:160805878 http://arxiv.org/abs/1608.05878 .
  54. Peixoto Tiago P., Parsimonious Module Inference in Large Networks, 10.1103/physrevlett.110.148701
  55. Peixoto Tiago P., Inferring the mesoscale structure of layered, edge-valued, and time-varying networks, 10.1103/physreve.92.042807
  56. Peixoto TP, Rosvall M (2015) Modeling sequences and temporal networks with dynamic community structures. arXiv:150904740. https://arxiv.org/abs/1509.04740 .
  57. Persson C, Bohlin L, Edler D, Rosvall M (2016) Maps of sparse markov chains efficiently reveal community structure in network flows with memory. arXiv preprint arXiv:160608328. https://arxiv.org/abs/1606.08328 .
  58. Pothen Alex, Graph Partitioning Algorithms with Applications to Scientific Computing, ICASE/LaRC Interdisciplinary Series in Science and Engineering (1997) ISBN:9789401062770 p.323-368, 10.1007/978-94-011-5412-3_12
  59. Rosvall M., Bergstrom C. T., Maps of random walks on complex networks reveal community structure, 10.1073/pnas.0706851105
  60. Rosvall M, Esquivel AV, Lancichinetti A, West JD, Lambiotte R (2014) Memory in network flows and its effects on spreading dynamics and community detection. Nat Commun4630: 5. doi: 10.1038/ncomms5630 .
  61. Saade A, Krzakala F, Zdeborová L (2014) Spectral clustering of graphs with the bethe hessian. In: Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ (eds)Advances in Neural Information Processing Systems 27, 406–414.. Curran Associates, Inc. http://papers.nips.cc/paper/5520-spectral-clustering-of-graphs-with-the-bethe-hessian.pdf .
  62. Salnikov V, Schaub MT, Lambiotte R (2016) Using higher-order Markov models to reveal flow-based communities in networks. Sci Rep: 6:23194. doi: 10.1038/srep23194 .
  63. Schaeffer Satu Elisa, Graph clustering, 10.1016/j.cosrev.2007.05.001
  64. Schaub Michael T., Delvenne Jean-Charles, Yaliraki Sophia N., Barahona Mauricio, Markov Dynamics as a Zooming Lens for Multiscale Community Detection: Non Clique-Like Communities and the Field-of-View Limit, 10.1371/journal.pone.0032210
  65. Sekara Vedran, Stopczynski Arkadiusz, Lehmann Sune, Fundamental structures of dynamic social networks, 10.1073/pnas.1602803113
  66. Jianbo Shi, Malik J., Normalized cuts and image segmentation, 10.1109/34.868688
  67. Spielman DA, Teng SH (1996) Spectral partitioning works: Planar graphs and finite element meshes In: Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, 96–105.. IEEE. doi: 10.1109/SFCS.1996.548468 .
  68. Spielman Daniel A., Teng Shang-Hua, A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning, 10.1137/080744888
  69. von Luxburg Ulrike, A tutorial on spectral clustering, 10.1007/s11222-007-9033-z
  70. Von Luxburg U, Williamson RC, Guyon I (2012) Clustering: Science or art?, Vol. 27. http://www.jmlr.org/proceedings/papers/v27/luxburg12a/luxburg12a.pdf .
  71. Xie J, Kelley S, Szymanski BK (2013) Overlapping community detection in networks: The state-of-the-art and comparative study. ACM Comput Surv (csur) 45(4): 43.
  72. Yan, X (2016) Bayesian Model Selection of Stochastic Block Models. arXiv:160507057. https://arxiv.org/abs/1605.07057 .
  73. Yang Jaewon, Leskovec Jure, Defining and evaluating network communities based on ground-truth, 10.1007/s10115-013-0693-z
Bibliographic reference Schaub, Michael ; Delvenne, Jean-Charles ; Rosvall, Martin ; Lambiotte, Renaud. The many facets of community detection in complex networks. In: Applied Network Science, Vol. 2, no.1 (2017)
Permanent URL http://hdl.handle.net/2078.1/182948