On the accuracy of message-passing approaches to percolation in complex networks

Abstract

The Message-Passing Approach (MPA) is the state-of-the-art technique to obtain quasi-analytical predictions for percolation on real complex networks. Besides being intuitive and straightforward, it has the advantage of being mathematically principled: it is exact on trees, while yielding generally good predictions on networks containing cycles as do most real complex networks. Here we show that the MPA does not perform its calculations on some ill-defined tree-like approximation of the network, as its formulation leads to believe, but rather considers a random network ensemble in which the original network is cloned and shuffled an infinite number of times. We conclude that the fact that the MPA is exact on trees does not imply that it is nearly exact on tree-like networks. In fact we find that the closer a non-tree network is to a tree, the worse the MPA accuracy becomes.

arXiv comment7 pages, 4 figures

References in corpus (26)

• Random graphs with arbitrary degree distributions and their applications
• Influence maximization in complex networks through optimal percolation
• Statistical physics of inference: Thresholds and algorithms
• A message passing approach for general epidemic models
• Inferring the origin of an epidemic with a dynamic message-passing algorithm
• Percolation on sparse networks
• Resilience to damage of graphs with degree correlations
• Percolation in real interdependent networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Containing epidemic outbreaks by message-passing techniques
• Message passing theory for percolation models on multiplex networks with link overlap
• A message-passing approach for recurrent-state epidemic models on networks
• Dynamic message-passing equations for models with unidirectional dynamics
• Mapping the Structure of Directed Networks: Beyond the "Bow-tie" Diagram
• Rare events and discontinuous percolation transitions
• Beyond the locally tree-like approximation for percolation on real networks
• Spectra of networks containing short loops
• Spectra of random networks with arbitrary degrees
• A message-passing approach for threshold models of behavior in networks
• Fluctuations in percolation of sparse complex networks
• Network cloning unfolds the effect of clustering on dynamical processes
• Percolation in real multiplex networks
• Message passing and moment closure for susceptible-infected-recovered epidemics on finite networks
• Heterogeneous micro-structure of percolation in sparse networks
• Unsupervised feature learning from finite data by message passing: discontinuous versus continuous phase transition
• Message-Passing Methods for Complex Contagions