Message passing on networks with loops

Abstract

In this paper we offer a solution to a long-standing problem in the study of networks. Message passing is a fundamental technique for calculations on networks and graphs. The first versions of the method appeared in the 1930s and over the decades it has been applied to a wide range of foundational problems in mathematics, physics, computer science, statistics, and machine learning, including Bayesian inference, spin models, coloring, satisfiability, graph partitioning, network epidemiology, and the calculation of matrix eigenvalues. Despite its wide use, however, it has long been recognized that the method has a fundamental flaw: it only works on networks that are free of short loops. Loops introduce correlations that cause the method to give inaccurate answers at best, and to fail completely in the worst cases. Unfortunately, almost all real-world networks contain many short loops, which limits the usefulness of the message passing approach. In this paper we demonstrate how to rectify this shortcoming and create message passing methods that work on any network. We give two example applications, one to the percolation properties of networks and the other to the calculation of the spectra of sparse matrices.

References in corpus (12)

• The structure of scientific collaboration networks
• The Kernel Polynomial Method
• Random graphs with clustering
• Efficient Monte Carlo algorithm and high-precision results for percolation
• Phase transition in the detection of modules in sparse networks
• A message passing approach for general epidemic models
• Percolation on sparse networks
• Random graphs containing arbitrary distributions of subgraphs
• Spectra of random graphs with arbitrary expected degrees
• Loop Calculus in Statistical Physics and Information Science
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Spectra of networks containing short loops

Cited by in corpus (29)

• Belief propagation for networks with loops
• Cavity and replica methods for the spectral density of sparse symmetric random matrices
• The theory of percolation on hypergraphs
• A message-passing approach to epidemic tracing and mitigation with apps
• Message-passing theory for cooperative epidemics
• Message passing methods on complex networks
• Tensor Networks contraction and the Belief Propagation algorithm
• Gauging tensor networks with belief propagation
• Percolation on feature-enriched interconnected systems
• Random graphs with arbitrary clustering and their applications
• Targeted influence maximization in complex networks
• Block belief propagation algorithm for two-dimensional tensor networks
• The characteristics of cycle-nodes-ratio and its application to network classification
• Percolation in random graphs with higher-order clustering
• 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
• Belief propagation on networks with cliques and chordless cycles
• Effects of clustering heterogeneity on the spectral density of sparse networks
• Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
• Coordination problems on networks revisited: statics and dynamics
• Scaling and universality for percolation in random networks: A unified view
• Generating functions for message-passing on weighted networks: directed bond percolation and SIR epidemics
• Distributed Cooperative Positioning in Dense Wireless Networks: A Neural Network Enhanced Fast Convergent Parametric Message Passing Method
• An approximation for return time distributions of random walks on sparse networks
• Forest expansion of two-body partition functions for sparse interaction graphs
• How universal is the mean-field universality class for percolation in complex networks?
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks
• Exact statistical mechanics of the Ising model on networks