Belief propagation for networks with loops

Abstract

Belief propagation is a widely used message passing method for the solution of probabilistic models on networks such as epidemic models, spin models, and Bayesian graphical models, but it suffers from the serious shortcoming that it works poorly in the common case of networks that contain short loops. Here we provide a solution to this long-standing problem, deriving a belief propagation method that allows for fast calculation of probability distributions in systems with short loops, potentially with high density, as well as giving expressions for the entropy and partition function, which are notoriously difficult quantities to compute. Using the Ising model as an example, we show that our approach gives excellent results on both real and synthetic networks, improving significantly on standard message passing methods. We also discuss potential applications of our method to a variety of other problems.

References in corpus (25)

• Critical phenomena in complex networks
• Stochastic blockmodels and community structure in networks
• Weak pairwise correlations imply strongly correlated network states in a neural population
• Direct-coupling analysis of residue co-evolution captures native contacts across many protein families
• Why social networks are different from other types of networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Random graphs with clustering
• Ising Model on Networks with an Arbitrary Distribution of Connections
• Localization and centrality in networks
• Percolation on sparse networks
• Inverse statistical problems: from the inverse Ising problem to data science
• Rational Group Decision Making. A random field Ising model at T=0
• Self-fulfilling Ising Model of Financial Markets
• Cluster Variation Method in Statistical Physics and Probabilistic Graphical Models
• Ising, Schelling and Self-Organising Segregation
• Message passing on networks with loops
• Social applications of two-dimensional Ising models
• Loop Calculus in Statistical Physics and Information Science
• How to Compute Loop Corrections to Bethe Approximation
• Hopping on the Bethe lattice: Exact results for densities of states and dynamical mean-field theory
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Market structure explained by pairwise interactions
• Spectra of sparse regular graphs with loops
• Equations of motion approach to the spin-1/2 Ising model on the Bethe lattice

Cited by in corpus (15)

• Message passing methods on complex networks
• Gauging tensor networks with belief propagation
• Hypergraph assortativity: a dynamical systems perspective
• The nature of hypergraph $k$-core percolation problems
• Targeted influence maximization in complex networks
• Block belief propagation algorithm for two-dimensional tensor networks
• Heterogeneous message passing for heterogeneous networks
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Simulating quantum dynamics in two-dimensional lattices with tensor network influence functional belief propagation
• General theory for extended-range percolation on simple and multiplex networks
• Belief propagation on networks with cliques and chordless cycles
• Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
• Distributed Cooperative Positioning in Dense Wireless Networks: A Neural Network Enhanced Fast Convergent Parametric Message Passing Method
• Mean-field theory of vector spin models on networks with arbitrary degree distributions
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks