Reichardt Jörg, Bornholdt Stefan
Institute for Theoretical Physics, University of Bremen, Otto-Hahn-Allee, D-28359 Bremen, Germany.
Phys Rev E Stat Nonlin Soft Matter Phys. 2006 Jul;74(1 Pt 2):016110. doi: 10.1103/PhysRevE.74.016110. Epub 2006 Jul 18.
Starting from a general ansatz, we show how community detection can be interpreted as finding the ground state of an infinite range spin glass. Our approach applies to weighted and directed networks alike. It contains the ad hoc introduced quality function from [J. Reichardt and S. Bornholdt, Phys. Rev. Lett. 93, 218701 (2004)] and the modularity Q as defined by Newman and Girvan [Phys. Rev. E 69, 026113 (2004)] as special cases. The community structure of the network is interpreted as the spin configuration that minimizes the energy of the spin glass with the spin states being the community indices. We elucidate the properties of the ground state configuration to give a concise definition of communities as cohesive subgroups in networks that is adaptive to the specific class of network under study. Further, we show how hierarchies and overlap in the community structure can be detected. Computationally efficient local update rules for optimization procedures to find the ground state are given. We show how the ansatz may be used to discover the community around a given node without detecting all communities in the full network and we give benchmarks for the performance of this extension. Finally, we give expectation values for the modularity of random graphs, which can be used in the assessment of statistical significance of community structure.
从一个通用假设出发，我们展示了如何将社区检测解释为寻找无限范围自旋玻璃的基态。我们的方法同样适用于加权网络和有向网络。它包含了[J. Reichardt和S. Bornholdt，《物理评论快报》93，218701 (2004)]中临时引入的质量函数以及纽曼和吉尔万[《物理评论E》69，026113 (2004)]所定义的模块度Q作为特殊情况。网络的社区结构被解释为使自旋玻璃能量最小化的自旋构型，其中自旋态为社区索引。我们阐明基态构型的性质，以便给出社区作为网络中凝聚子群的简洁定义，该定义适用于所研究的特定网络类别。此外，我们展示了如何检测社区结构中的层次结构和重叠。给出了用于寻找基态的优化过程的计算高效的局部更新规则。我们展示了如何在不检测完整网络中的所有社区的情况下，使用该假设来发现给定节点周围的社区，并给出了此扩展性能的基准。最后，我们给出了随机图模块度的期望值，可用于评估社区结构的统计显著性。
