REVIEW
k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
Statistical Mechanics · Submitted 26 Feb 2006 · 34 references
Pith's verdict: A mostly exact and important theory of the hybrid k-core transition; the only real gap is an unproved factorization assumption that a referee should ask to see.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
A network's k-core collapses when its corona of weakest vertices percolates, making the transition simultaneously discontinuous and square-root singular.
The reading
What carries the argument
The central object is the corona: the subset of vertices in the k-core with exactly k neighbors in the k-core—the 'weakest' vertices whose removal triggers a domino-like pruning cascade. The argument is carried by the generating functions $H_{1k}(x)$ for corona clusters seen from a randomly chosen edge end and $H_{0k}(x)$ for clusters attached to a vertex, together with the order parameter $R$, the probability that an edge end is not the root of an infinite $(k-1)$-ary subtree. The critical condition $k(k-1)P_k(k)/z_{1k}=1$, where $P_k(k)$ is the corona fraction and $z_{1k}$ the mean k-core degree, is exactly the point where the denominator of $N_{\rm crn}=kP_k(k)/(1-k(k-1)P_k(k)/z_{1k})$ vanishes, so corona clusters percolate precisely at the k-core threshold.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that the k-core percolation threshold $p_c(k)$ for $k\ge3$ is exactly the percolation threshold of the corona, the set of k-core vertices that have degree k inside the k-core. At $p>p_c(k)$ corona clusters are finite, and their mean size, defined through the generating functions $H_{1k}(x)$ and $H_{0k}(x)$, diverges as $N_{\rm crn}\propto[p-p_c(k)]^{-1/2}$. This divergence feeds through the exact relation $d\ln M_k/d\ln p=1+N_{\rm crn}$ into the order parameter, so that $M_k(p)-M_k(p_c(k))\propto[p-p_c(k)]^{1/2}$, explaining both the jump and the continuous singularity of the hybrid transition. The mean intervertex distance in corona clusters acts as a diverging correlation length, and a single removed vertex can prune a region whose mean size diverges at the threshold.
Load-bearing premise
The load-bearing assumption is that the k-core of an uncorrelated network is itself uncorrelated, so a vertex's degree in the k-core is independent of its neighbors' degrees and the corona-cluster generating functions factorize as written; the paper cites a proof in footnote [27] but does not present it.
Editorial extensions
If this is right
- Removing a single vertex at $p$ slightly above $p_c(k)$ can prune a region of mean size diverging as $[p-p_c(k)]^{-1/2}$; near the threshold the k-core is extremely fragile to localized damage.
- The k-core phase transition is hybrid: $M_k$ jumps discontinuously at $p_c(k)$ yet carries a square-root singular term above the threshold, and the derivative $dR/dp$ diverges.
- Corona cluster sizes obey a power-law distribution $\Pi_k(s)\propto s^{-3/2}$ at the critical point, with the largest corona cluster growing as $N^{2/3}$.
- The destruction of the k-core is equivalent to a cooperative relaxation process whose rate $r$ diverges as $[t_c-t]^{-1/2}$ approaching a critical time $t_c=\ln(1/p_c(k))$, opposite to the critical slowing down of ordinary continuous transitions.
Reading between the lines
- If this corona mechanism is right, the same square-root singularity should appear in any system whose stable phase is held together by a minimal-connectivity skeleton, such as rigidity percolation or jamming, whenever the weakly connected elements form a percolating set at the instability.
- The claim suggests a practical diagnostic: measuring only the corona fraction $P_k(k)$ and mean k-core degree $z_{1k}$ of a network's k-core gives the combination $k(k-1)P_k(k)/z_{1k}$ that reports how close the network is to k-core collapse, independent of the rest of the degree distribution.
- A testable extension is to plant a known degree-degree correlation inside the k-core of a finite random graph; the theory predicts the factorization of $H_{1k}$ and the $1/2$ exponent should fail in a measurable way as correlations grow.
Original abstract
We develop the theory of the k-core (bootstrap) percolation on uncorrelated random networks with arbitrary degree distributions. We show that the k-core percolation is an unusual, hybrid phase transition with a jump emergence of the k-core as at a first order phase transition but also with a critical singularity as at a continuous transition. We describe the properties of the k-core, explain the meaning of the order parameter for the k-core percolation, and reveal the origin of the specific critical phenomena. We demonstrate that a so-called ``corona'' of the k-core plays a crucial role (corona is a subset of vertices in the k-core which have exactly k neighbors in the k-core). It turns out that the k-core percolation threshold is at the same time the percolation threshold of finite corona clusters. The mean separation of vertices in corona clusters plays the role of the correlation length and diverges at the critical point. We show that a random removal of even one vertex from the k-core may result in the collapse of a vast region of the k-core around the removed vertex. The mean size of this region diverges at the critical point. We find an exact mapping of the k-core percolation to a model of cooperative relaxation. This model undergoes critical relaxation with a divergent rate at some critical moment.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
We develop the theory of the k-core (bootstrap) percolation on uncorrelated random networks with arbitrary degree distributions. We show that the k-core percolation is an unusual, hybrid phase transition with a jump emergence of the k-core as at a first order phase transition but also with a critical singularity as at a continuous transition. We describe the properties of the k-core, explain the meaning of the order parameter for the k-core percolation, and reveal the origin of the specific critical phenomena. We demonstrate that a so-called ``corona'' of the k-core plays a crucial role (corona is a subset of vertices in the k-core which have exactly k neighbors in the k-core). It turns out that the k-core percolation threshold is at the same time the percolation threshold of finite corona clusters. The mean separation of vertices in corona clusters plays the role of the correlation length and diverges at the critical point. We show that a random removal of even one vertex from the k-core may result in the collapse of a vast region of the k-core around the removed vertex. The mean size of this region diverges at the critical point. We find an exact mapping of the k-core percolation to a model of cooperative relaxation. This model undergoes critical relaxation with a divergent rate at some critical moment.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We develop the theory of the k-core (bootstrap) percolation on uncorrelated random networks with arbitrary degree distributions. | contribution 0.99 | 0.95 | 0.05 | asserted 0.97 |
| s1 | We show that the k-core percolation is an unusual, hybrid phase transition with a jump emergence of the k-core as at a first order phase transition but also with a critical singularity as at a continuous transition. | result 0.99 | 0.94 | 0.59 | asserted 1.00 |
| s2 | We describe the properties of the k-core, explain the meaning of the order parameter for the k-core percolation, and reveal the origin of the specific critical phenomena. | contribution 0.96 | 0.92 | 0.11 | asserted 1.00 |
| s3 | We demonstrate that a so-called ``corona'' of the k-core plays a crucial role (corona is a subset of vertices in the k-core which have exactly k neighbors in the k-core). | result 0.57 | 0.84 | 0.11 | asserted 1.00 |
| s4 | It turns out that the k-core percolation threshold is at the same time the percolation threshold of finite corona clusters. | result 1.00 | 0.88 | 0.17 | asserted 1.00 |
| s5 | The mean separation of vertices in corona clusters plays the role of the correlation length and diverges at the critical point. | result 0.67 | 0.85 | 0.10 | asserted 1.00 |
| s6 | We show that a random removal of even one vertex from the k-core may result in the collapse of a vast region of the k-core around the removed vertex. | result 1.00 | 0.88 | 0.15 | hedged possibility 0.79 |
| s7 | The mean size of this region diverges at the critical point. | result 1.00 | 0.81 | 0.10 | asserted 1.00 |
| s8 | We find an exact mapping of the k-core percolation to a model of cooperative relaxation. | contribution 0.52 | 0.95 | 0.13 | asserted 1.00 |
| s9 | This model undergoes critical relaxation with a divergent rate at some critical moment. | result 0.91 | 0.79 | 0.12 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:cond-mat/0602611 by the authors.
References
How the literature uses it
Papers whose main result relates to this one's
States the same result 1 paper
-
We show that in networks with a finite mean number z_2 of the second-nearest neighbors, the emergence of a k-core is a hybrid phase transition.
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.