Graph Spectra and the Detectability of Community Structure in Networks
Graph Spectra and the Detectability of Community Structure in Networks
复制标题
DOI：
10.1103/physrevlett.108.188701
复制
发表时间：
2012-05-01
影响因子：
8.6
通讯作者：
Newman, M. E. J.
中科院分区：
文献类型：
--
作者：
Nadakuditi, Raj Rao;Newman, M. E. J.
我们研究了显示社区结构的网络--其中连接异常密集的节点组。利用随机矩阵理论的方法，我们计算了这类网络在大尺寸限制下的谱，从而证明了用于社区检测的矩阵方法，如流行的模块化最大化方法，存在相变。该转换将这样的方法成功地检测到社区结构的制度与结构存在但未被检测到的制度分开。通过将这些结果与最近的最大似然方法的分析相比较，我们能够表明谱模数最大化是一种最优的检测方法，因为在模数方法失效的情况下没有其他方法能够成功。
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 of such networks in the limit of large size, and hence demonstrate the presence of a phase transition in matrix methods for community detection, such as the popular modularity maximization method. The transition separates a regime in which such methods successfully detect the community structure from one in which the structure is present but is not detected. By comparing these results with recent analyses of maximum-likelihood methods, we are able to show that spectral modularity maximization is an optimal detection method in the sense that no other method will succeed in the regime where the modularity method fails.