General and exact approach to percolation on random graphs

Antoine Allard, Laurent Hébert-Dufresne, Jean-Gabriel Young, and Louis J. Dubé

Phys. Rev. E 92, 062807 – Published 7 December 2015

Abstract

We present a comprehensive and versatile theoretical framework to study site and bond percolation on clustered and correlated random graphs. Our contribution can be summarized in three main points. (i) We introduce a set of iterative equations that solve the exact distribution of the size and composition of components in finite-size quenched or random multitype graphs. (ii) We define a very general random graph ensemble that encompasses most of the models published to this day and also makes it possible to model structural properties not yet included in a theoretical framework. Site and bond percolation on this ensemble is solved exactly in the infinite-size limit using probability generating functions [i.e., the percolation threshold, the size, and the composition of the giant (extensive) and small components]. Several examples and applications are also provided. (iii) Our approach can be adapted to model interdependent graphs—whose most striking feature is the emergence of an extensive component via a discontinuous phase transition—in an equally general fashion. We show how a graph can successively undergo a continuous then a discontinuous phase transition, and preliminary results suggest that clustering increases the amplitude of the discontinuity at the transition.

Received 8 April 2015

DOI:https://doi.org/10.1103/PhysRevE.92.062807

Authors & Affiliations

Antoine Allard^*, Laurent Hébert-Dufresne^†, Jean-Gabriel Young, and Louis J. Dubé

Département de physique, de génie physique, et d'optique, Université Laval, Québec, Québec, Canada G1V 0A6

^*Now at Departament de Física Fonamental, Universitat de Barcelona, Carrer de Martí i Franquès 1, 08028 Barcelona, Spain.
^†Now at Santa Fe Institute, Santa Fe, New Mexico 87501, USA.

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 92, Iss. 6 — December 2015

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
(a) Example of an arbitrary graph that can be handled by our framework. Red and blue represent vertex types 1 and 2, respectively. There are ten vertices of each type. (b) Distribution of the number of vertices of type $j$ in components reached from an initial vertex chosen at random for the graph shown in (a). Symbols are the results of $2.5 \times 10^{8}$ numerical simulations, and lines are the predictions of Eqs. (3a)–(3d). The distributions are discrete; lines have been added to guide the eye. Triangles $(▵)$ correspond to pure site percolation, with ${{\tilde{r}}_{s}^{'}} \equiv {{\tilde{r}}_{1}^{'}, {\tilde{r}}_{2}^{'}} = {0.40, 0.70}$ and ${{\tilde{p}}_{i j}^{'}} \equiv {{\tilde{p}}_{11}^{'}, {\tilde{p}}_{12}^{'}, {\tilde{p}}_{21}^{'}, {\tilde{p}}_{22}^{'}} = {1.00, 1.00, 1.00, 1.00}$ . Circles $(\circ)$ correspond to hybrid percolation (site and bond) with ${{\tilde{r}}_{s}^{'}} \equiv {{\tilde{r}}_{1}^{'}, {\tilde{r}}_{2}^{'}} = {0.95, 0.90}$ and ${{\tilde{p}}_{i j}^{'}} \equiv {{\tilde{p}}_{11}^{'}, {\tilde{p}}_{12}^{'}, {\tilde{p}}_{21}^{'}, {\tilde{p}}_{22}^{'}} = {1.00, 0.90, 0.85, 0.95}$ . These probabilities are given in terms of the original vertex types to lighten the presentation (thus the use of a prime). To use the mapping described in Sec. 2b, a probability for each individual vertex and each individual edge must be defined. For instance, if vertex 8 is of type 1, we set $r_{8} = {\tilde{r}}_{1}^{'}$ . Similarly, if vertex 5 is of type 2 and shares three undirected edges with vertex 8, we set $p_{58} = 1 - {(1 - {\tilde{p}}_{21}^{'})}^{3}$ and $p_{85} = 1 - {(1 - {\tilde{p}}_{12}^{'})}^{3}$ .
Reuse & Permissions
Figure 2
Illustration of the stub matching scheme. (a) Vertices are attributed a type according to the distribution ${w_{i}}$ , and are given a number of stubs of each type according to the distribution ${P_{i} (k)}$ . There are $N = 12$ vertices, $| N | = 3$ types of vertices (four vertices of type 1 in red, four vertices of type 2 in green, and four vertices of type 3 in blue), and $| E | = 2$ types of stubs (light blue and dark red). Stubs are then randomly matched according to a set of rules, $R$ , to create hyperedges. For example, a light blue stub and a dark red stub that both stem from vertices of type 2 can be matched to create a directed edge, or three light blue stubs stemming from three vertices of types 1, 2, and 3 can be matched to create a triangle. More complex hyperedges are possible and can be handled by our mathematical approach. (b) Example of a graph obtained with the stub matching scheme which can reproduce a great variety of nontrivial correlations and clustering patterns. In the infinite-size limit $(N \to \infty)$ , the resulting graphs have an underlying treelike structure: There are no closed paths other than within clustered hyperedges.
Reuse & Permissions
Figure 3
(a), (b) Effective treelike structure of an hyperedge from the point of view of a vertex of type 2 before and after projection, respectively. There exists an effective edge between the initial vertex of type 2 and any vertices that are directly or indirectly reachable from it. The probability for an effective edge to exist corresponds to the probability that a direct or indirect path exists. (c) Schematic representation of the pgf $f_{μ i} (x)$ . Knowing that a vertex of type $i$ has been reached from one of its stubs of type $μ$ [i.e., a pair $(μ, i)$ ], this pgf generates the distribution of the number of vertices of each type in its neighborhood, as well as the type of stubs from which they have been reached. The types of the vertices and of the stubs are identified with the subscripts of the variables $x = {x_{ν i}}$ .
Reuse & Permissions
Figure 4
Comparison of the emergence of the giant component in a clustered graph ensemble that qualifies for the strong clustering regime with its unclustered counterpart. We see that the latter has a lower percolation threshold. Details on the graphs used are given in Sec. 4e.
Reuse & Permissions
Figure 5
Comparison of the size of the extensive (functional) components as a function of the vertex existence probability $r_{1}$ in four related graph ensembles. The details of each graph ensemble are given in the main text of Sec. 5. The curves $S_{(c, i)}$ and $S_{(u, i)}$ were obtained with Eq. (14) and the curves $S_{(c, d)}^{A}, S_{(c, d)}^{B}, S_{(u, d)}^{A}$ , and $S_{(u, d)}^{B}$ were obtained with Eq. (36). Symbols show the results of numerical simulations on these graph ensembles with $N = 10^{6}$ vertices. (Inset) Comparison between the curve $S_{(u, d)}^{A}$ and the curve $S_{(u, i)}$ rescaled according to ${\tilde{S}}_{(u, i)} [r_{1}] = {\bar{q}}_{1}^{A B} S_{(u, i)} [r_{1} {\bar{q}}_{1}^{A B}]$ (the dependence to $r_{1}$ in shown in brackets).
Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics