Percolation and localisation: Sub-leading eigenvalues of the nonbacktracking matrix

\name James Martin † , Tim Rogers and Luca Zanetti · 2025

Read Percolation and localisation: Sub-leading eigenvalues of the nonbacktracking matrix by \name James Martin † , Tim Rogers and Luca Zanetti (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-17774.txt.

Introduction

James Martin and co-authors look past the top eigenvalue for network breaking points in a 2025 paper. A network's nonbacktracking matrix encodes how failures or infections percolate through it. The inverse of its largest eigenvalue usually estimates the percolation threshold.

In core-periphery networks that estimate fails badly because influence localizes on a few nodes. The authors search deeper into the spectrum for a delocalized eigenvalue. Its inverse often lands much closer to the true threshold. Localization, long a nuisance, becomes a diagnostic in its own right. Better thresholds guide vaccination, hardening, and grid design choices.

Catalog record

CREATOR\name James Martin † , Tim Rogers and Luca Zanetti
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-17774

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Percolation and localisation: Sub-leading eigenvalues of the nonbacktracking matrix \name James Martin † , Tim Rogers and Luca Zanetti Abstract The spectrum of the nonbacktracking matrix associated to a network is known to contain fundamental information regarding percolation properties of the network. Indeed, the inverse of its leading eigenvalue is often used as an estimate for the percolation threshold. However, for many networks with nonbacktracking centrality localised on a few nodes, such as networks with a core-periphery structure, this spectral approach badly underestimates the threshold. In this work, we study networks that exhibit this localisation effect by looking beyond the leading eigenvalue and searching deeper into the spectrum of the nonbacktracking matrix. We identify that, when localisation is present, the threshold often more closely aligns with the inverse of one of the sub-leading real eigenvalues: the largest real eigenvalue with a “delocalised” corresponding eigenvector. We investigate a core-periphery network model and determine, both theoretically and experimentally, a regime of parameters for which our approach closely approximates the threshold, while the estimate derived using the leading eigenvalue does not. We further present experimental results on large scale real-world networks that showcase the usefulness of our approach. percolation; localisation; nonbacktracking spectrum Percolation and localisation \shortauthorlist James Martin et al. 1 Introduction Network percolation is a well-studied process within statistical physics that investigates the connectivity properties of random sub-networks. In bond (or site) percolation, edges (or nodes) are sampled independently at random with some occupation probability p , and the connectivity of the resulting subgraph is assessed. In many real-world networks, there is a sudden transition that separates two distinct regimes: a supercritical regime where the network is likely to contain a giant component that is said to percolate, and a subcritical regime where the network is more likely to be fragmented into many small non-percolating components. This transition has implications in many fields, such as the spread of infectious diseases, the robustness of communication or transport networks to sudden failures, or the permeability of porous materials [ 9 , 15 , 14 , 20 ] . Furthermore, the “critical” value p_{c} that separates the two regimes is analogous to a phase boundary in a physical system, and estimating this percolation threshold is a key research question. For infinite networks, the percolation threshold p_{c} is a well-defined sharp transition that identifies the critical probability where a component of infinite size first emerges. As a percolating component is a component of infinite size, this concept is less meaningful on finite networks. However, when the network is large, a similar, but less distinct transition can often be observed and estimating this transition can provide critical insights into the connectivity of the network. While some networks generated using well-defined models have analytical solutions to the percolation threshold, many real-world networks have complicated topological characteristics and analytical solutions are often absent [ 16 , 21 ] . Instead, direct numerical simulations can precisely model the percolation process, with appropriate metrics to quantify it. To simulate the percolation process, multiple Monte Carlo realisations are sampled and the percolation strength is computed as P(p)=\langle S_{1}\rangle/N , where \langle S_{1}\rangle is the average number of nodes in the largest component when a proportion p of the original number of edges are occupied [ 18 ] . There are several properties of the network that typically exhibit critical behaviour near the percolation threshold and can be computed by directly applying these numerical simulations. For example, the susceptibility \chi(p)=(\langle S_{1}^{2}\rangle-\langle S_{1}\rangle^{2})/\langle S_{1}\rangle of the network is expected to be maximal near the percolation threshold, as demonstrated in Figure 1 , leading to the robust numerical estimate p_{\text{sus}}=\argmax_{p}\;\chi(p) [ 21 ] . Alternatively, near the percolation threshold, we would expect the size of the non-percolating components to be largest, before they connect and form a giant percolating component. Therefore, another estimation of the percolation threshold is the occupation probability where the size of the second largest component is maximal, which we denote p_{\text{slc}}=\argmax_{p}\langle S_{2}\rangle [ 10 ] . Applying similar intuition, we would also expect the mean size of the non-percolating components to peak near the percolation threshold, leading to a further estimate p_{\text{mnp}} . For large networks, however, estimates that require direct simulations can be computationally expensive, and more efficient approaches are often desired. (a) E-R network (b) Core-Periphery network Figure 1: An example of the percolation process for (a) an E-R network and (b) a core-periphery network. The transition in percolation strength P(p) (thick solid black line) aligns with the maximum peak in susceptibility \chi(p) (solid orange line). The estimate p_{\text{nbt}}=1/\lambda_{1}(B) (dotted vertical red line) aligns with the first peak, which is not maximal in a core-periphery network. The estimate 1/\lambda_{2}(B) (dashed vertical blue line) more closely predicts the threshold. In recent literature, message-passing techniques have shown that applying spectral methods to the so-called nonbacktracking matrix can uncover fundamental information about the network regarding properties such as percolation or community structure [ 11 , 7 , 10 , 4 ] . In this approach, the percolation threshold is predicted as p_{\text{nbt}}=1/\lambda_{1}(B) , where B is the non-symmetric nonbacktracking matrix defined on the directed edges of the network such that B_{i\to j,k\to l}=1 if j=k and i\neq l , and zero otherwise [ 8 ] . The leading eigenvalue \lambda_{1}(B) measures the growth rate of the number of nonbacktracking walks, i.e., walks that do not immediately return to the previous node, and reflects the propagation of connections throughout the network. This concept closely relates to the branching number of an infinite tree, which describes the average number of new connections that each node generates, and determines whether the tree will continue to grow or eventually die out [ 23 ] . In infinite locally tree-like networks, the leading eigenvalue of the nonbacktracking matrix captures the average branching factor: in particular, the network will likely contain a giant component if \lambda_{1}(B) is greater than 1. By assigning a weight p to each edge, reflecting the occupation probability, the percolation transition will occur close to where \lambda_{1}(pB)=1 , and the estimate p_{\text{nbt}} is recovered. When the network contains cycles, however, some nonbacktracking walks can revisit edges, and \lambda_{1}(B) overestimates the average branching factor. Then p_{\text{nbt}} gives a lower bound of the actual percolation threshold, which could potentially be much smaller than the observed transition. Nevertheless, p_{\text{nbt}} is an upper bound of the alternative spectral estimate 1/\lambda_{1}(A) , where A denotes the adjacency matrix. However, the latter method is often preferred when the network is dense, as both spectral estimates are close while the computation time is significantly reduced [ 2 ] . To reduce the computational complexity of the nonbacktracking method, the Ihara-Bass determinant formula can be exploited [ 1 ] . Given an undirected network G=(V,E) , the spectrum of the 2|E|\times 2|E| nonbacktracking matrix B contains the entire spectrum of the smaller 2|V|\times 2|V| reduced nonbacktracking matrix H , defined as H=\begin{pmatrix}A&I-D\\ I&0\end{pmatrix}, (1) where A denotes the symmetric adjacency matrix and D denotes the degree matrix, with diagonal entries D_{ii}=\sum_{j}A_{ij} and zeros otherwise. The remaining eigenvalues of B are exactly the trivial eigenvalues -1 and 1 , each with multiplicity |E|-|V| . Then p_{\text{nbt}}=\frac{1}{\lambda_{1}(B)}=\frac{1}{\lambda_{1}(H)}. This estimate closely predicts the percolation threshold

Read the complete text