----- > [!proposition] Proposition. ([[percolation by uniform removal in the configuration model]]) > Consider a [[network percolation|site percolation process]] on [[configuration model]] in which each node remains functioning with uniform **occupation probability** $\phi$. > \ After percolation, the fraction $S$ of nodes in the [[giant cluster]] out of nodes in the original [[network]] is $\begin{align} S= & \phi[1- g_{0}(u)], \text{ where} \\ u = & 1 - \phi + \phi g_{1}(u) \\ g_{0}(z) = & \sum_{k=0}^{\infty} p_{k}z^{k} \\ g_{1}(z)= & \sum_{k=0}^{\infty} q_{k}z^{k} = \frac{1}{\langle k \rangle } \sum_{k=0}^{\infty}{(k+1)p_{k+1}} z^{k} \end{align}$ where $g_{1}$ is the [[probability generating function|PGF]] of [[configuration model]]'s [[excess degree distribution]], and we only consider the solution $u$ with smallest value. \ Often it is not possible to solve for $u$ directly; graphically, however, (see proof) we see that the **critical phase transition value of $\phi$** beyond which a [[giant cluster]] appears (**percolation** occurs) is $\phi_{c}= \frac{1}{g_{1}'(u)}=\frac{1}{\mathbb{E}[q_{k}]}= \frac{\langle k \rangle }{\langle k^{2} \rangle - \langle k \rangle}.$ A [[network]] for which $\phi > \phi_{c}$ is said to be **robust to random failure**. > [!basicexample] > - [[site percolation on 4-regular configuration model]] > - [[percolation on sparse configuration model]] > - [[uniform bond percolation with Poisson degree distribution]] > - > [!proposition] Corollary. > [[scale-free network|Scale-free networks]] such as the internet are robust to random failure. > [!proof] Proof of Corollary. > We know that [[power-law probability distribution|Power laws with exponents]] in the range $2<\alpha<3$ have diverging $\langle k^{2}\rangle$, which means $\phi_{c} \to 0$ in the [[function limit]] of large [[network]] size. So any nontrivial choice of $\phi$ will yield a [[giant cluster]]. > [!proof]- Proof. ([[percolation by uniform removal in the configuration model]]) > Let $u$ be the average [[probability]] that a node is not connected to the [[giant cluster]] via a particular neighbor. A node with [[degree]] $k$ that didn't get removed due to the percolation is thus not attached to the [[giant cluster]] if none of its neighbors are, which happens with probability $u^{k}$. Thus the [[expectation|average probability]] of not being in the cluster is $\sum_{k=0}^{\infty}p_{k}u^{k}=g_{0}(u),$ > where $g_{0}$ is the relevant [[probability generating function]]. Then the average probability a node *does* belong to the [[giant cluster]] is $1-g_{0}(u)$. Thus, out of all the original nodes in the [[network]], the total fraction $S$ that are in the [[giant cluster]] is $S=\phi[1-g_{0}(u)].$ > Now we need to calculate $u$. In order for a node not to be connected to the [[giant cluster]] via a particular neighbor, either > 1. The neighbor got removed due to percolation > 1. Happens with probability $1-\phi$ > 2. The neighbor did not get removed, but never belonged in the first place > 1. Happens with probability $\phi u^{k}$, where $k$ is its [[excess degree]] obeying the [[configuration model]] [[excess degree distribution]] $q_{k}=\frac{(k+1)p_{k+1}}{\langle k \rangle}$. > > So the probability of a node not being connected to the [[giant cluster]] via a particular neighbor $i$ is $1-\phi + \phi u^{k}$. Averaging over $q_{k}$ we arrive at the following expression for the [[law of total probability]] $u$ of not being connected to the [[giant cluster]] via a particular neighbor $i$: $\begin{align} > u = & \mathbb{P}(\text{not being connected via }i) \\ > = & \sum_{k=0}^{\infty} \mathbb{P}(\text{not being connected via }i | k_{i}=k) \overbrace{\mathbb{P}(k_{i}=k)}^{q_{k}} \\ > = & \sum_{k=0}^{\infty} q_{k}(1-\phi + \phi u^{k}) \\ > = & 1 - \phi + \phi g_{1}(u), > \end{align}$ > where $g_{1}(z)=\sum_{k=0}^{\infty}q_{k}z^{k}$ is the [[probability generating function]] for the [[excess degree distribution]]. > > Of course, $u$ is not generally possible to solve for. But there is an elegant graphical representation of the solution as follows. $g_{1}(u)$ and all its [[derivative|derivatives]] are [[polynomial|polynomials]] in $u$ with nonnegative coefficients, thus in general for $u \geq 0$ $g_{1}$ will look like an [[increasing]] function [[curvature form|curving]] upward. Then to obtain $1-\phi+\phi g_{1}(u)$ we compress this curve by a factor $\phi \in [0,1]$ and translate upward by a factor $(1-\phi) \in [0,1]$. The point(s) at which the resulting curve intersects the line $y=u$ are then the desired solutions. The trivial solution $u=1$ (giving $S=0$) always exists due to normalization requirements of PGF. Only when we have a solution $u<1$ can there be a [[giant cluster]]. As seen in Prof. Newman's figure below: ![[CleanShot 2023-12-01 at [email protected]|400]] > the transition occurs when $\left[ \frac{d}{du}(1-\phi + \phi g_{1}(u)) \right]_{u=1}=1$. Performing the [[derivative]] and rearranging we get the **critical value** $\phi_{c}$ as $\phi_{c}=\frac{1}{g_{1}'(1)}=\frac{1}{\mathbb{E}[q_{k}]}.$ > Using facts we've derived regarding the [[configuration model]], we can compute $\begin{align} > g_{1}'(1) = & \frac{1}{\langle k \rangle } \sum_{k=1}^{\infty} k(k+1)p_{k+1} \\ > = & \frac{1}{\langle k \rangle } \sum_{k=0}^{\infty} k(k-1)p_{k} \\ > = & \frac{ \langle k^{2} \rangle - \langle k \rangle }{ \langle k \rangle } > \end{align}$ > and hence $\phi_{c}= \frac{\langle k^{2} \rangle - \langle k \rangle}{\langle k \rangle}$. ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```