Graph spectra and the detectability of community structure in networks
作者： Raj Rao Nadakuditi , M. E. J. Newman
DOI: 10.1103/PHYSREVLETT.108.188701
关键词:
摘要: We study networks that display community structure--groups of nodes within which connections are unusually dense. Using methods from random matrix theory, we calculate the spectra such in limit large size, and hence demonstrate presence a phase transition for detection, as popular modularity maximization method. The separates regime successfully detect structure one is present but not detected. By comparing these results with recent analyses maximum-likelihood methods, able to show spectral an optimal detection method sense no other will succeed where fails.
arxiv.org
harvard.edu
arxiv-vanity.com参考文章(13)
Aurelien Decelle, Florent Krzakala, Cristopher Moore, Lenka Zdeborová, Inference and phase transitions in the detection of modules in sparse networks. Physical Review Letters. ,vol. 107, pp. 065701- 065701 ,(2011) , 10.1103/PHYSREVLETT.107.065701
M. Girvan, M. E. J. Newman, Community structure in social and biological networks Proceedings of the National Academy of Sciences of the United States of America. ,vol. 99, pp. 7821- 7826 ,(2002) , 10.1073/PNAS.122653799
Andrea Lancichinetti, Santo Fortunato, Filippo Radicchi, Benchmark graphs for testing community detection algorithms Physical Review E. ,vol. 78, pp. 046110- ,(2008) , 10.1103/PHYSREVE.78.046110
Anne Condon, Richard M. Karp, Algorithms for graph partitioning on the planted partition model Random Structures and Algorithms. ,vol. 18, pp. 116- 140 ,(2001) , 10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2
Jörg Reichardt, Michele Leone, Un)detectable cluster structure in sparse networks. Physical Review Letters. ,vol. 101, pp. 078701- ,(2008) , 10.1103/PHYSREVLETT.101.078701
Brian Karrer, M. E. J. Newman, Stochastic blockmodels and community structure in networks Physical Review E. ,vol. 83, pp. 016107- ,(2011) , 10.1103/PHYSREVE.83.016107
M. E. J. Newman, Modularity and community structure in networks Proceedings of the National Academy of Sciences of the United States of America. ,vol. 103, pp. 8577- 8582 ,(2006) , 10.1073/PNAS.0601602103
Catherine Donati-Martin, Mireille Capitaine, Delphine Féral, The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations. Annals of Probability. ,vol. 37, pp. 1- 47 ,(2009) , 10.1214/08-AOP394
Santo Fortunato, Community detection in graphs Physics Reports. ,vol. 486, pp. 75- 174 ,(2010) , 10.1016/J.PHYSREP.2009.11.002
Santo Fortunato, Community detection in graphs arXiv: Physics and Society. ,(2009) , 10.1016/J.PHYSREP.2009.11.002