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.

16 pages and 16 figures

References in corpus (8)

• Stochastic blockmodels and community structure in networks
• Phase transition in the detection of modules in sparse networks
• Percolation on sparse networks
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• 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