Heterogeneous message passing for heterogeneous networks

Abstract

Message passing (MP) is a computational technique used to find approximate solutions to a variety of problems defined on networks. MP approximations are generally accurate in locally tree-like networks but require corrections to maintain their accuracy level in networks rich with short cycles. However, MP may already be computationally challenging on very large networks and additional costs incurred by correcting for cycles could be prohibitive. We show how the issue can be addressed. By allowing each node in the network to have its own level of approximation, one can focus on improving the accuracy of MP approaches in a targeted manner. We perform a systematic analysis of 109 real-world networks and show that our node-based MP approximation is able to increase both the accuracy and speed of traditional MP approaches. We find that, compared to conventional MP, a heterogeneous approach based on a simple heuristic is more accurate in 81% of tested networks, faster in 64% of cases, and both more accurate and faster in 49% of cases.

arXiv comment12 pages, 8 figures, 3 tables

References in corpus (40)

• Emergence of scaling in random networks
• Community structure in social and biological networks
• Lethality and centrality in protein networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• The structure of scientific collaboration networks
• The diameter of the world wide web
• The Dynamics of Viral Marketing
• Self-similar community structure in organisations
• Community Structure in Jazz
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• What's in a crowd? Analysis of face-to-face behavioral networks
• Random graphs with clustering
• Phase transition in the detection of modules in sparse networks
• A message passing approach for general epidemic models
• Inferring the origin of an epidemic with a dynamic message-passing algorithm
• Contact patterns among high school students
• Percolation on sparse networks
• Spectra of complex networks
• Who is the best player ever? A complex network analysis of the history of professional tennis
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Containing epidemic outbreaks by message-passing techniques
• The unreasonable effectiveness of tree-based theory for networks with clustering
• Message passing on networks with loops
• Predicting percolation thresholds in networks
• Directed network modules
• Loops of any size and Hamilton cycles in random scale-free networks
• Optimizing spread dynamics on graphs by message passing
• Dynamic message-passing equations for models with unidirectional dynamics
• Breaking of the site-bond percolation universality in networks
• Fundamental statistical features and self-similar properties of tagged networks
• Rare events and discontinuous percolation transitions
• Tight lower bound for percolation threshold on a quasi-regular graph
• Beyond the locally tree-like approximation for percolation on real networks
• Belief propagation for networks with loops
• Fluctuations in percolation of sparse complex networks
• A message-passing approach to epidemic tracing and mitigation with apps
• Message passing methods on complex networks
• Uncertainty Reduction for Stochastic Processes on Complex Networks
• Decoding communities in networks

Cited by in corpus (4)

• The theory of percolation on hypergraphs
• The nature of hypergraph $k$-core percolation problems
• General theory for extended-range percolation on simple and multiplex networks
• An approximation for return time distributions of random walks on sparse networks