Source-linked AI summary
Percolation on sparse networks
Brian Karrer, M. E. J. Newman, Lenka Zdeborová
TL;DR
Estimating percolation thresholds on networks requires alternatives to lattice-spanning criteria, so the paper compares cluster-based estimates with eigenvalue bounds. The non-backtracking matrix gives the exact threshold for locally tree-like networks and a better lower bound than the adjacency matrix more generally.
Problem
Because networks have no lattice edges, the percolation threshold cannot be identified by locating a cluster spanning from edge to edge.
Method
The paper estimates thresholds from the peak size of the second-largest cluster and compares simulations with bounds from adjacency and non-backtracking matrix leading eigenvalues.
Results
On locally tree-like networks, the inverse leading eigenvalue of the non-backtracking matrix gives the exact threshold; otherwise it consistently provides a better lower bound than the adjacency matrix.
Takeaways & Limitations
The non-backtracking matrix is the preferred eigenvalue-based estimator of percolation thresholds on sparse networks.
Takeaways & Limitations
Exact agreement is not expected on networks that are not tree-like, and the degree of disagreement varies across networks.
Abstract
from arXiv · showhide
We study percolation on networks, which is used as a model of the resilience of networked systems such as the Internet to attack or failure and as a simple model of the spread of disease over human contact networks. We reformulate percolation as a message passing process and demonstrate how the resulting equations can be used to calculate, among other things, the size of the percolating cluster and the average cluster size. The calculations are exact for sparse networks when the number of short loops in the network is small, but even on networks with many short loops we find them to be highly accurate when compared with direct numerical simulations. By considering the fixed points of the message passing process, we also show that the percolation threshold on a network with few loops is given by the inverse of the leading eigenvalue of the so-called non-backtracking matrix.
Numerical calculation of the leading eigenvalue
The Ihara–Bass determinant formula replaces the 2m × 2m non-backtracking matrix with a sparser 2n × 2n matrix for computing its leading eigenvalue.
- Numerical calculation of the leading eigenvalue: The Ihara–Bass determinant formula shows that the leading eigenvalue of the non-backtracking matrix is also the leading eigenvalue of a 2n × 2n matrix.This provides an alternative to directly calculating the eigenvalue of the 2m × 2m non-backtracking matrix.
- Numerical calculation of the leading eigenvalue: For a sparse network, the alternative matrix has 2m + 2n nonzero elements, fewer than the non-backtracking matrix itself.Its sparsity permits rapid numerical calculation of the leading eigenvalue.
- Numerical calculation of the leading eigenvalue: The alternative matrix uses D, the diagonal matrix whose entries are the node degrees.The resulting method was used to calculate the values reported in the following section.
Percolation thresholds
The non-backtracking matrix provides the exact percolation threshold on locally tree-like networks and a lower bound on sparse networks with loops, where it is at least as accurate as the adjacency-matrix bound.
- Percolation thresholds: The inverse leading eigenvalues of both the adjacency and non-backtracking matrices provide lower bounds on the percolation threshold of a sparse network.The non-backtracking matrix always gives a better bound, or at least no worse, than the adjacency matrix.
- Percolation thresholds: On locally tree-like networks, the non-backtracking matrix gives the exact percolation threshold.The threshold is obtained from the inverse of its leading eigenvalue.
- Percolation thresholds: The numerical threshold estimate is the point where the second-largest cluster reaches its maximum size.The largest cluster grows with p, whereas the second-largest cluster peaks at the threshold and then decreases.
- Percolation thresholds: For four non-tree-like networks, the non-backtracking matrix gives a lower bound on the true threshold and a better bound than the adjacency matrix.The degree of disagreement with measured thresholds varies across networks.
- Percolation thresholds: For the random graph and block model, estimated thresholds agree well with results because these computer-generated networks are genuinely tree-like.Table I compares eigenvalue-based estimates with repeated numerical simulations, or an exact value for the random graph.