Phys. Rev. E 83, 051134 (2011) - Heterogeneous $k$-core versus bootstrap percolation on complex networks

k

Go Mobile »
Access by Staats- und Universitaetsbibliothek Bremen

Heterogeneous k $k$ -core versus bootstrap percolation on complex networks

G. J. Baxter, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes

Phys. Rev. E 83, 051134 – Published 31 May 2011

Abstract

We introduce the heterogeneous k $k$ -core, which generalizes the k $k$ -core, and contrast it with bootstrap percolation. Vertices have a threshold ri $r_{i}$ , that may be different at each vertex. If a vertex has fewer than ri $r_{i}$ neighbors it is pruned from the network. The heterogeneous k $k$ -core is the subgraph remaining after no further vertices can be pruned. If the thresholds ri $r_{i}$ are 1 with probability f $f$ , or k⩾3 $k ⩾ 3$ with probability 1−f $1 - f$ , the process can be thought of as a pruning process counterpart to ordinary bootstrap percolation, which is an activation process. We show that there are two types of transitions in this heterogeneous k $k$ -core process: the giant heterogeneous k $k$ -core may appear with a continuous transition and there may be a second discontinuous hybrid transition. We compare critical phenomena, critical clusters, and avalanches at the heterogeneous k $k$ -core and bootstrap percolation transitions. We also show that the network structure has a crucial effect on these processes, with the giant heterogeneous k $k$ -core appearing immediately at a finite value for any f>0 $f > 0$ when the degree distribution tends to a power law P(q)~q−γ $P (q) ~ q^{- γ}$ with γ<3 $γ < 3$ .

Received 20 December 2010

DOI:

©2011 American Physical Society

Authors & Affiliations

G. J. Baxter^1,*, S. N. Dorogovtsev^1,2, A. V. Goltsev^1,2, and J. F. F. Mendes¹

¹Departamento de Física, I3N, Universidade de Aveiro, Campus Universitário de Santiago, PT-3810-193 Aveiro, Portugal
²A. F. Ioffe Physico-Technical Institute, RU-194021 St. Petersburg, Russia

^*gjbaxter@ua.pt

Article Text

Click to Expand

References

Click to Expand

Issue

Vol. 83, Iss. 5 — May 2011

Reuse & Permissions

International Year Of Light

The Physical Review Journals Celebrate the International Year of Light

The editors of the Physical Review journals revisit papers that represent important breakthroughs in the field of optics. The articles covered are free to read throughout 2015. Read more.

Images

Figure 1
(a) Relative size of the heterogeneous k $k$ -core, Sk $S_{k}$ (solid curves), which is the subgraph that includes all vertices that meet the threshold requirements of Eq. (1), and the fraction of active vertices in bootstrap percolation, Sb $S_{b}$ (dashed curves) as a function of f $f$ for the same network—an Erdős-Rényi graph of mean degree five—with the same k=3 $k = 3$ at three different values of p $p$ corresponding to different regions of the phase diagrams (see Fig. 2): (1) p=0.5 $p = 0.5$ , which is between pc $p_{c}$ and ps $p_{s}$ for both models, (2) p=0.61 $p = 0.61$ , which is above ps-k $p_{s-k}$ but still below ps-b $p_{s-b}$ , and (3) p=0.91 $p = 0.91$ , which is above pf-k $p_{f-k}$ and ps-b $p_{s-b}$ . Each numbered pair indicates the same choice of parameters p $p$ and k $k$ with the activation process of bootstrap percolation indicated by arrows to the right and the pruning process of the heterogeneous k $k$ -core by arrows to the left. (b) Size Sgc-k $S_{gc-k}$ of the giant heterogeneous k $k$ -core (solid) and the size Sgc-b $S_{gc-b}$ of the giant BPC (dashed) as a function of f $f$ for the same network and the same values of p $p$ .Reuse & Permissions
Figure 2
(a) Phase diagram for the heterogeneous k $k$ -core in the f $f$ -p $p$ plane. The giant HKC is absent in region I. In region II the giant HKC is present but vertices with threshold k $k$ do not form a giant component within it. In region III the vertices with threshold k $k$ in the HKC form a giant connected component. The giant HKC appears continuously at the threshold marked by the thin black curve. The hybrid discontinuous transition occurs at the points marked by the heavy black line beginning from ps−k $p_{s - k}$ . The giant component of threshold vertices appears with a continuous transition marked by a thin dashed curve. Above pt−k $p_{t - k}$ the first appearance of the giant HKC is with a discontinuous transition. Above pf−k $p_{f - k}$ the giant HKC appears discontinuously for any f>0 $f > 0$ . (b) Phase diagram for boostrap percolation. The giant BPC is absent in region I. The giant BPC is present in region II. In region III the giant BPC is present and the active vertices with threshold $k$ form a giant connected component. The continuous appearance of the giant BPC is marked by the thin solid curve and the hybrid transition (beginning at $p_{s - b}$ ) by a heavy solid curve. These diagrams are for a Bethe lattice with degree five and for $k = 3$ , but the diagram for any network with finite second moment of the degree distribution will be qualitatively the same. Note that the locations of the continuous transitions from region I to II and from II to III for BPC with $k \to k - 1$ coincide (up to the point where the discontinuous transition is encountered) with those for the heterogeneous $k$ -core. The special critical point, $p_{s - b}$ , with $k$ reduced by $1$ also coincides with $p_{s - k}$ (see also Appendix ).Reuse & Permissions
Figure 3
(a) Subcritical clusters of different sizes in bootstrap percolation. Left: Because they start in an inactive state two connected vertices (shaded area) cannot become active if each has $k - 1$ active neighbors (in this example $k = 3$ ). The same follows for clusters of three (center) or more vertices (right). If any member of a subcritical cluster gains another active neighbor, an avalanche of activations encompasses the whole cluster. (b) Similar clusters would be included in the heterogeneous $k$ -core.Reuse & Permissions
Figure 4
Corona clusters of different sizes in heterogeneous $k$ -core. Left: Because they are included unless pruned, two connected vertices (whose threshold is $k$ ) form part of the heterogeneous $k$ -core if each has $k - 1$ other neighbors in the core, as each is “assisted” by the other. Right: In general, a corona cluster consists of vertices (with threshold $k$ ) that each have exactly $k$ active neighbors, either inside or outside the cluster. If one neighbor of any of the cluster vertices is removed from the core (for example, the one indicated by the arrow), an avalanche is caused as the entire cluster is pruned.Reuse & Permissions
Figure 5
Symbols used in graphical representations of self-consistency equations for the heterogeneous $k$ -core.Reuse & Permissions

1 of 5