----- (Newman 15.6) > [!proposition] Proposition. ([[uniform bond percolation with Poisson degree distribution]]) > Consider a (uniform) bond percolation process with *edge* occupation probability $\phi$ on a random graph with Poisson degree distribution and mean degree $c$, in the limit of large network size $n$. > > **a.** Write down an equation whose solution gives the probability $u$ that a node is not connected to the giant percolation cluster via a particular one of its edges. > > A node is not connected to the [[giant cluster]] via a particular one of its edges if one of the following hold: > - the edge got removed during percolation > - happens with probability $1-\phi$ > - the edge didn't get removed during percolation but does not lead to the [[giant cluster]] > - happens with probability $\phi u^{k}$ if the edge leads to a node with [[excess degree]] $k$ > > > Thus our expression is $u = 1-\phi + \phi u^{k}$. Now using [[law of total probability]] we get $u= \sum_{k} q_{k} (1-\phi + \phi u^{k})$ which we know is $u=1-\phi+\phi g_{1}(u)$. We know our [[network]] has a [[Poisson random variable|Poisson degree distribution]] (and recall that for an [[Erdos-Renyi random graph model|Poisson random graph]] the [[excess degree distribution]] equals the [[degree distribution]]), so we may further write $u=1 - \phi + \phi \sum_{k=0}^{\infty} \frac{c^{k}e ^{-c}}{k!} u^{k }=1 - \phi + \phi e ^{-c} \sum_{k=0}^{\infty} \frac{(cu)^{k}}{k!} $ > but using the [[power series]] representation for $\exp$ this is just $1-\phi + \phi e^{-c }e^{cu}$ and so we ultimately have $u= 1 - \phi + \phi e^{c(u-1)}.$ > > **b.**  In terms of $u$ write down an expression for the probability that a node is not in the giant cluster given that it has degree $k$. > > This is the probability that it is not connected via any of its $k$ edges, i.e., $\mathbb{P}(\text{not in Gcluster} | \text{deg }k)= u^{k}= [1-\phi + e ^{c(u-1)}]^{k}.$ > > **c.**  Hence, or otherwise, write down an expression in terms of $u$, $c$, and $k$ for the probability that a node has degree $k$ given that it is not in the giant cluster (and has not been removed from the network). > > Apply [[Bayes' Theorem]] thus: $\begin{align} > \mathbb{P}(k | \text{not in G.Cl})= & \mathbb{P}(\text{not in G.Cl}| k) \frac{\mathbb{P}(k)}{\mathbb{P}(\text{not in G.Cl})} \\ > = & u^{k} c^{k} \frac{e^{-c}}{k!} \frac{1}{1-S} \\ > = & \frac{u^{k}c^{k}e^{-c}}{k! g_{0}(u)}. > \end{align}$ > > **d.**  Thus, show that the mean degree of nodes not in the giant cluster is $cu$. > > Compute $\begin{align} > \sum_{k=0}^{\infty} k \frac{u^{k}c^{k}e^{-c}}{k! g_{0}(u)}= & \sum_{k=0}^{\infty} \frac{k p_{k} u^{k}}{g_{0}(u)} \\ > = & \sum_{k=0}^{\infty} u \frac{g_{0}'(u)}{g_{0}(u)} \\ > = & u \cdot \frac{ce^{c(u-1)}}{e^{c(u-1)}} \\ > = & cu. > \end{align}$ > > > ----- #### ---- #### 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 > ```