Message passing on networks with loops

DOI10.1073/PNAS.1914893116zbMATH Open1431.94214arXiv1907.08252OpenAlexW2963092996WikidataQ91104834 ScholiaQ91104834MaRDI QIDQ5218487FDOQ5218487

Authors: George T. Cantwell, M. E. J. Newman 

Publication date: 4 March 2020

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1907.08252

Recommendations

• On the interconnection of message passing systems
• Loopy belief propagation: convergence and effects of message errors
• Message-Passing Algorithms: Reparameterizations and Splittings
• An optimal message routing algorithm for double-loop networks
• A random network model of message transmission
• The logic of message-passing
• Multiplicative circulant networks. Topological properties and communication algorithms

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Applications of graph theory to circuits and networks (94C15)

Cited In (9)

• Coordination problems on networks revisited: statics and dynamics
• On forest expansions for two-body partition functions on tree-like interaction graphs
• Ranking edges by their impact on the spectral complexity of information diffusion over networks
• Gauging tensor networks with belief propagation
• The characteristics of cycle-nodes-ratio and its application to network classification
• Targeted influence maximization in complex networks
• Message-passing on hypergraphs: detectability, phase transitions and higher-order information
• Message-passing theory for cooperative epidemics
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks

This page was built for publication: Message passing on networks with loops

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5218487)