Decelle Aurelien, Krzakala Florent, Moore Cristopher, Zdeborová Lenka
Université Paris-Sud & CNRS, LPTMS, UMR8626, Bât 100, Université Paris-Sud, F-91405 Orsay, France.
Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Dec;84(6 Pt 2):066106. doi: 10.1103/PhysRevE.84.066106. Epub 2011 Dec 12.
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.
在本文中，我们扩展了之前关于随机块模型的工作。随机块模型是一种常用于社会和生物网络的生成模型，以及从网络拓扑结构推断功能组或社区的问题。我们使用统计物理学的腔方法来获得相图的渐近精确分析。我们详细描述了社区检测问题中可检测性 - 不可检测性相变和易 - 难相变的性质。我们的分析自然地转化为一种信念传播算法，用于以最优方式推断节点的组成员身份，即最大化与潜在组成员身份的重叠，并学习块模型的潜在参数。最后，我们将该算法应用于两个真实世界网络的示例，并讨论其性能。
