Nonbacktracking expansion of finite graphs

Abstract

Message passing equations yield a sharp percolation transition in finite graphs, as an artifact of the locally treelike approximation. For an arbitrary finite, connected, undirected graph we construct an infinite tree having the same local structural properties as this finite graph, when observed by a nonbacktracking walker. Formally excluding the boundary, this infinite tree is a generalization of the Bethe lattice. We indicate an infinite, locally treelike, random network whose local structure is exactly given by this infinite tree. Message passing equations for various cooperative models on this construction are the same as for the original finite graph, but here they provide the exact solutions of the corresponding cooperative problems. These solutions are good approximations to observables for the models on the original graph when it is sufficiently large and not strongly correlated. We show how to express these solutions in the critical region in terms of the principal eigenvector components of the nonbacktracking matrix. As representative examples we formulate the problems of the random and optimal destruction of a connected graph in terms of our construction, the nonbacktracking expansion. We analyze the limitations and the accuracy of the message passing algorithms for different classes of networks and compare the complexity of the message passing calculations to that of direct numerical simulations. Notably, in a range of important cases, simulations turn out to be more efficient computationally than the message passing.

arXiv comment13 pages, 7 figures

References in corpus (25)

• Finding and evaluating community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Catastrophic cascade of failures in interdependent networks
• Random graphs with arbitrary degree distributions and their applications
• Multilayer Networks
• The structure and dynamics of multilayer networks
• Influence maximization in complex networks through optimal percolation
• Scale-Free Networks are Ultrasmall
• Spectral redemption: clustering sparse networks
• Localization and Spreading of Diseases in Complex Networks
• Localization and centrality in networks
• Percolation on sparse networks
• Network dismantling
• Percolation in real interdependent networks
• Multiple percolation transitions in a configuration model of network of networks
• Fast and simple decycling and dismantling of networks
• Percolation on correlated networks
• Redundant interdependencies boost the robustness of multilayer networks
• Correlated Edge Overlaps in Multiplex Networks
• Metric structure of random networks
• Tight lower bound for percolation threshold on a quasi-regular graph
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Beyond the locally tree-like approximation for percolation on real networks
• Network cloning unfolds the effect of clustering on dynamical processes
• Emergence of coexisting percolating clusters in networks

Cited by in corpus (7)

• Percolation on complex networks: Theory and application
• The localization of non-backtracking centrality in networks and its physical consequences
• Heterogeneous micro-structure of percolation in sparse networks
• Localization of nonbacktracking centrality on dense subgraphs of sparse networks
• Numerical assessment of the percolation threshold using complement networks
• Fault Tolerance of Random Graphs with respect to Connectivity: Mean-field Approximation for Semi-dense Random Graphs
• Approximating nonbacktracking centrality and localization phenomena in large networks