Percolation on random graphs
Remco van der Hofstad · 2025
Read Percolation on random graphs by Remco van der Hofstad (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-2512-15673.txt.
Introduction
Remco van der Hofstad reviews recent progress on percolation on random graphs in a 2025 paper. Percolation models random damage to a network: heavy damage shatters it into small pieces, while light damage barely affects connectivity. The sharp change between those regimes is a phase transition, and its location and nature are the focus.
Near or below criticality, components show intricate scaling, with typical components bounded but average and largest sizes growing as powers of network size. Two settings behave rather differently: rank one like graphs, including the configuration model, and dynamic graphs that grow over time, such as preferential attachment models. Inhomogeneity of the underlying graph proves crucial throughout.
Catalog record
| CREATOR | Remco van der Hofstad |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-15673
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Percolation on random graphs Thanks: The full version of the paper can be accessed at https://arxiv.org/abs/0000.00000 Remco van der Hofstad Abstract Percolation is a model for random damage to a network. It is one of the simplest models that displays a phase transition : when the network is severely damaged, it falls apart in many small connected components, while if the damage is light, connectivity is hardly affected. We study the location and nature of the phase transition on random graphs. In particular, we focus on the connectivity structure close to, or below, criticality, where components display intricate scaling behaviour such that a typical connected component has bounded size, while the average and maximal connected component sizes grow like powers of the network size. We review the recent progress that has been made in two important settings: random graphs whose expected adjacency matrix is close to being rank-1 , the most prominent examples being the configuration model and rank-1 inhomogeneous random graphs, and dynamic random graphs , i.e., random graphs that grow with time, such as uniform and preferential attachment models. Remarkably, these two settings behave rather differently. In all cases, the inhomogeneity of the underlying random graph on which we perform percolation is of crucial importance. 1 Introduction. In percolation, edges and/or vertices are randomly removed from a connected graph G=(V(G),E(G)) . Often, percolation is studied on infinite connected graphs, such as the hypercubic lattice or infinite trees. See the books by Grimmett [ 38 ] , Bollobás and Riordan [ 22 ] and Kesten [ 49 ] for background. Percolation on infinite graphs is the simplest imaginable model that displays a phase transition . Suppose edges in the graph are removed independently with some probability \pi\in[0,1] . 1 1 1 Traditionally, p is used as the edge-retention probability. Due to the potential conflicts with other usages of p here, we choose for \pi instead. We think of the retention probability \pi as the proportion of edges that escapes being damaged. When \pi is small, the damage is substantial, and the graph falls apart into many small and finite components. In particular, while G had an infinite connected component, after percolation, for \pi small, no infinite connected component remains. On the other hand, when the damage is very little and \pi is close to 1, the graph remains to have an infinite connected component even after the damage is inflicted. By monotonicity in the edge-retention probability, there is a unique \pi_{c} above which infinite structures remain, while below it, no infinite connected component exists. Throughout the remainder of this paper, we will write ‘component’ to mean ‘connected component’. Motivation for percolation on finite graphs. Real-world networks are finite, yet very large, graphs. Such networks can be affected by vertices and edges being down or attacked, rendering them out of service. This is sometimes called attack or failure vulnerability . Such a failure process could arise from vertices or edges randomly failing. Then, the key question is how much connectivity is preserved while vertices or edges are randomly knocked out. We will often assume that this is a truly random process, in the sense that the edges or vertices fail with equal probabilities independently of one another. Such an attack is sometimes called a random attack . Real-world networks are generally sparse (see e.g. [ 41 , 44 , 51 ] ), meaning that their number of edges grows linearly with the network size. The relevant notion of convergence for sparse graphs is the highly powerful theory of local convergence [ 6 , 10 , 43 ] , which investigates the structure of finite graphs from the perspective of a uniformly chosen vertex called a root . The space of locally-finite rooted graphs, apart from isomorphisms, can be equipped with a local topology that turns it into a Polish space . Graph sequences converge locally when expectations of bounded and continuous functions of these rooted graphs converge to expectations with respect to a limiting probability distribution on rooted graphs. While this may seem a weak notion, it has proven to be very effective in analysing structural properties of large random graphs. For example, while the maximal component size is not described by the local limit, under one additional assumption, it is [ 42 ] , and we therefore refer to it as ‘almost local’. Percolation on finite graphs. Let G=(V(G),E(G)) be a finite graph. For convenience, we denote the vertex set as V(G)=[n]=\{1,\ldots,n\} , while the edge set E(G) can be general. Let \pi be the edge-retention probability. For u,v\in[n] , we write that u\longleftrightarrow v when there exists a path of edges that are retained in percolation, and let \mathscr{C}_{v}^{\pi}=\{u\in[n]\colon u\longleftrightarrow v\} be the collection of vertices that are connected to v in percolation on G with percolation parameter \pi . Percolation on finite graphs is inherently different from percolation on infinite transitive graphs in that a unique critical value , such as present on many infinite transitive graphs, cannot exist. Indeed, let \mathbb{P}_{\pi} denote the percolation measure on the finite graph G . Then, the dependence on the edge-retention probability \pi is smooth, and \mathbb{P}_{\pi}(\mathcal{E}) is a polynomial of finite degree for every event \mathcal{E} . As a result, there cannot be a sharp phase transition, in the sense that if \pi is close to critical and \delta very small, then also \pi+\delta will be close to critical. Further, on a finite graph, no infinite components can exist. This means that we have to redefine the notion of a critical value. A local way of quantifying the critical behaviour is to take a uniform vertex U , and to investigate the component \mathscr{C}_{U}^{\pi} of that vertex after percolating with percolation parameter \pi . When \limsup_{k\rightarrow\infty}\limsup_{n\rightarrow\infty}\mathbb{P}_{\pi_{n}}(|\mathscr{C}_{U}^{\pi_{n}}|\geq k)=0, the components in the percolated graph are small and we can think of (\pi_{n})_{n\geq 1} as being subcritical, while when \liminf_{k\rightarrow\infty}\liminf_{n\rightarrow\infty}\mathbb{P}_{\pi_{n}}(|\mathscr{C}_{U}^{\pi_{n}}|\geq k)>0, the sequence (\pi_{n})_{n\geq 1} is supercritical. Of course, the boundary between these two settings may not be sharp, and are generally referred to as finite-size corrections . Percolation on random graphs. In this paper, we focus on percolation on random graphs, which poses an additional difficulty due to the fact that the graphs are random , and thus we deal with double randomness due to percolation and the random graph on which it acts. As a result, we can think of the stochastic models on random graphs as processes in a disordered medium. Especially for percolation, this is somewhat paradoxical, since percolation often provides the random medium on which other processes, in particular random walks, act. For a more extended overview of percolation on random graphs, we refer to [ 44 , Part III] . The largest components in percolation on random graphs. We let \big(|\mathscr{C}_{\scriptscriptstyle(i)}^{\pi}|\big)_{i\geq 1} denote the ordered collection of components, where we break ties (if they exist) arbitrarily. Thus, in particular, (1.1) |\mathscr{C}_{\rm max}^{\pi}|=|\mathscr{C}_{\scriptscriptstyle(1)}^{\pi}|=\max_{i\geq 1}|\mathscr{C}_{\scriptscriptstyle(i)}^{\pi}| denotes the largest or maximal component size, and we write |\mathscr{C}_{\rm sec}^{\pi}|=|\mathscr{C}_{\scriptscriptstyle(2)}^{\pi}| for the second largest component size. Note that the vector \big(|\mathscr{C}_{\scriptscriptstyle(i)}^{\pi}|\big)_{i\geq 1} has a random number of coordinates, which equals the number of disjoint components, and it will be convenient to extend this finite vector to an infinite vector by