Spectral estimation of the percolation transition in clustered networks

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 nonbacktracking 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 paper, 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-nonbacktracking 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 substructures.

Figure 1

(a) A graph with no loop longer than 3. (b) One way to decompose a graph containing loops longer than 3 to triangles (red) and single edges (blue).

Figure 2

(a) Illustration of the computation of BP messages along a single edge $i\to j$, using messages from triangles and single edges to $i$, except $j\to i$. (b) Illustration of computation of messages from a triangle $a$ to node $i$, as a function of messages from other triangles and from single edges.

Figure 3

(a) Comparison of size of the giant clusters of simulations (averaged over ten realizations), BP without triangles [20] and our message-passing algorithm on a network generated by the clustered random graph model [28]. The network has number of nodes $n={10}^5$, average degree $c=3$, and fraction of edges belonging to triangles $\rho =0.5$. The inset shows the size of the second-largest cluster in simulations, which has a peak at the percolation transition. Three vertical lines, from left to right, in the inset are the estimates of percolation transition given using the adjacency matrix, the nonbacktracking matrix and the triangle-nonbacktracking matrix respectively. (b) From bottom to top, percolation transition given by the adjacency matrix $A$, the nonbacktracking matrix $B$, the triangle-nonbacktracking matrix $C$, and exact theory for $n\to \infty$ CRG networks in Ref. [28]. Networks have a Poisson degree distribution with average degree $c=3$. Number of nodes $n={10}^6, \rho$ denotes fraction of edges belonging to triangles. Each point of simulation is averaged over five random realizations of edges' open-closed states.