Message passing methods on complex networks

Abstract

Networks and network computations have become a primary mathematical tool for analyzing the structure of many kinds of complex systems, ranging from the Internet and transportation networks to biochemical interactions and social networks. A common task in network analysis is the calculation of quantities that reside on the nodes of a network, such as centrality measures, probabilities, or model states. In this review article we discuss message passing methods, a family of techniques for performing such calculations, based on the propagation of information between the nodes of a network. We introduce the message passing approach with a series of examples, give some illustrative applications and results, and discuss the deep connections between message passing and phase transitions in networks. We also point out some limitations of the message passing approach and describe some recently-introduced methods that address these limitations.

arXiv comment16 pages and 16 figures

References in corpus (19)

• Community detection in graphs
• Error and attack tolerance of complex networks
• Random graphs with arbitrary degree distributions and their applications
• Resilience of the Internet to random breakdowns
• Stochastic blockmodels and community structure in networks
• Mixed membership stochastic blockmodels
• Spectral redemption: clustering sparse networks
• Phase transition in the detection of modules in sparse networks
• Localization and centrality in networks
• Percolation on sparse networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Message passing on networks with loops
• Loop Calculus in Statistical Physics and Information Science
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Tight lower bound for percolation threshold on a quasi-regular graph
• Belief propagation for networks with loops
• Spectra of random networks with arbitrary degrees
• Equitable random graphs

Cited by in corpus (12)

• Robustness and resilience of complex networks
• The theory of percolation on hypergraphs
• The nature of hypergraph $k$-core percolation problems
• Heterogeneous message passing for heterogeneous networks
• General theory for extended-range percolation on simple and multiplex networks
• Homophily Within and Across Groups
• Strength and weakness of disease-induced herd immunity in networks
• Connected components in networks with higher-order interactions
• Larger holes as narrower degree distributions in complex networks
• Fast convergence to an approximate solution by message-passing for complex optimizations
• Shortest-path percolation on scale-free networks
• The Spectral Topology of Global Imbalances:A Graph-Theoretic Framework for Systemic Risk in the Balance of Payments