Yoon S, Goltsev A V, Dorogovtsev S N, Mendes J F F
Departamento de Física da Universidade de Aveiro, I3N, 3810-193 Aveiro, Portugal.
Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Oct;84(4 Pt 1):041144. doi: 10.1103/PhysRevE.84.041144. Epub 2011 Oct 31.
We generalize the belief-propagation algorithm to sparse random networks with arbitrary distributions of motifs (triangles, loops, etc.). Each vertex in these networks belongs to a given set of motifs (generalization of the configuration model). These networks can be treated as sparse uncorrelated hypergraphs in which hyperedges represent motifs. Here a hypergraph is a generalization of a graph, where a hyperedge can connect any number of vertices. These uncorrelated hypergraphs are treelike (hypertrees), which crucially simplifies the problem and allows us to apply the belief-propagation algorithm to these loopy networks with arbitrary motifs. As natural examples, we consider motifs in the form of finite loops and cliques. We apply the belief-propagation algorithm to the ferromagnetic Ising model with pairwise interactions on the resulting random networks and obtain an exact solution of this model. We find an exact critical temperature of the ferromagnetic phase transition and demonstrate that with increasing the clustering coefficient and the loop size, the critical temperature increases compared to ordinary treelike complex networks. However, weak clustering does not change the critical behavior qualitatively. Our solution also gives the birth point of the giant connected component in these loopy networks.
我们将置信传播算法推广到具有任意基序（三角形、环等）分布的稀疏随机网络。这些网络中的每个顶点都属于给定的一组基序（配置模型的推广）。这些网络可被视为稀疏不相关超图，其中超边代表基序。这里的超图是图的一种推广，其中超边可以连接任意数量的顶点。这些不相关超图是树状的（超树），这极大地简化了问题，并使我们能够将置信传播算法应用于这些具有任意基序的循环网络。作为自然示例，我们考虑有限环和团形式的基序。我们将置信传播算法应用于所得随机网络上具有成对相互作用的铁磁伊辛模型，并得到该模型的精确解。我们找到了铁磁相变的精确临界温度，并证明随着聚类系数和环大小的增加，与普通树状复杂网络相比，临界温度会升高。然而，弱聚类不会在定性上改变临界行为。我们的解还给出了这些循环网络中巨型连通分量的诞生点。
