Spectral estimation of the percolation transition in clustered networks

Abstract

There have been several spectral bounds for the percolation transition in networks, using spectrum of matrices associated with the network such as the adjacency matrix and the non-backtracking matrix. However they are far from being tight when the network is sparse and displays clustering or transitivity, which is represented by existence of short loops e.g. triangles. In this work, for the bond percolation, we first propose a message passing algorithm for calculating size of percolating clusters considering effects of triangles, then relate the percolation transition to the leading eigenvalue of a matrix that we name the triangle-non-backtracking matrix, by analyzing stability of the message passing equations. We establish that our method gives a tighter lower-bound to the bond percolation transition than previous spectral bounds, and it becomes exact for an infinite network with no loops longer than 3. We evaluate numerically our methods on synthetic and real-world networks, and discuss further generalizations of our approach to include higher-order sub-structures.

13 pages, 3 figures

References in corpus (11)

• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Random graphs with clustering
• Phase transition in the detection of modules in sparse networks
• Percolation on sparse networks
• Percolation and Epidemic Thresholds in Clustered Networks
• Percolation on correlated networks
• Clustering in complex networks. II. Percolation properties
• Bond percolation on a class of clustered random networks
• Tight lower bound for percolation threshold on a quasi-regular graph

Cited by in corpus (2)

• Percolation on complex networks: Theory and application
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling