Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs

Abstract

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 tree-like (hypertrees), which crucially simplify the problem and allow 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 on the resulting random networks. We obtain an exact solution of this model on networks with finite loops or cliques as motifs. 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 tree-like complex networks. Our solution also gives the birth point of the giant connected component in these loopy networks.

9 pages, 4 figures

References in corpus (13)

• Critical phenomena in complex networks
• Random graphs with clustering
• A message passing approach for general epidemic models
• The entropy of network ensembles
• Random graphs containing arbitrary distributions of subgraphs
• Percolation and Epidemic Thresholds in Clustered Networks
• Loop series for discrete statistical models on graphs
• Clustering in complex networks. I. General formalism
• Percolation on correlated networks
• Clustering in complex networks. II. Percolation properties
• Cavity analysis on the robustness of random networks against targeted attacks: Influences of degree-degree correlations
• Algorithm for counting large directed loops
• Belief propagation for graph partitioning

Cited by in corpus (19)

• Message passing on networks with loops
• Spectra of networks containing short loops
• Belief propagation for networks with loops
• The theory of percolation on hypergraphs
• Message passing methods on complex networks
• Nonbacktracking expansion of finite graphs
• Ising model in clustered scale-free networks
• The nature of hypergraph $k$-core percolation problems
• Homophily-based social group formation in a spin-glass self-assembly framework
• Block belief propagation algorithm for two-dimensional tensor networks
• Tweaking Synchronisation by Link Addition
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Spectra of random networks in the weak clustering regime
• Self-avoiding walks and connective constants in clustered scale-free networks
• Weighted projected networks: mapping hypergraphs to networks
• Belief propagation on networks with cliques and chordless cycles
• Loop Series Expansions for Tensor Networks
• Ferromagnetic transition in a simple variant of the Ising model on multiplex networks
• Spin-glass transition in the Ising model on multiplex networks