---- - $\langle k \rangle=c_{1}=c$ all denote [[expectation|expected degree]] throughout. - $g_{0}(u)=\sum_{k}p_{k}u^{k}$ and $g_{1}(u)=\sum_{k}q_{k}u^{k}=\frac{g_{0}'(u)}{g_{0}'(1)}$ are [[probability generating function]]s for the [[degree distribution]] and [[excess degree distribution]]. > [!theorem] Theorem. ([[characterization of giant component in the configuration model]]) > The following are equivalent: > 1. The [[configuration model]] has a [[giant component]]; > 2. (Intuitive) The [[expectation|expected]] [[excess degree]] $\frac{c_{2}}{c_{1}}$ exceeds $1$ (see below); > 3. $\frac{c_{2}}{c_{1}}>1$, where $c_{1}$ resp. $c_{2}$ are the [[expectation|expected]] number of first resp. second neighbors of a node; > 4. $g_{1}'(1)>1$ (since $g_{1}'(u)$ is the [[expectation|expected]] [[excess degree]] of a node); > 5. $\langle k^{2} \rangle - 2 \langle k \rangle > 0$; > 6. $\sum_{i}k_{i} (k_{i}-2) > 0$. > 7. The equation $u=g_{1}(u)$ has a solution other than $u=1$. > If a [[giant component]] does exist, its size is given by $S=1-g_{0}(u_{*})$, where $u_{*}$ is the (it's often unique) non-unity solution to $u=g_{1}(u).$ > [!note] Remark. > Interestingly enough, notice from $(5)$ that nodes of degree zero or two have no say in whether or not a [[giant component]] exists. > [!proof]- Proof. ([[characterization of giant component in the configuration model]]) > **Existence of giant component.** [[configuration model#^443b4f|We showed here]] that the expected number of neighbors a distance $d$ away from some node follows the equation $c_{d}= \left( \frac{c_{2}}{c_{1}} \right)^{d-1} c_{1},$ > showing that it either grows or falls off exponentially depending on whether $c_{2} / c_{1} > 1$. Now we can argue as in the [[characterization of giant component in Erdos-Renyi random graph model]] to show that when $\frac{c_{2}}{c_{1}}>1$ the component to which our start node belongs grows with $n$ and is thus [[giant component|giant]], and if $\frac{c_{2}}{c_{1}}\leq_{}1$ this cannot happen. > > The other equivalencies are just rewriting $\frac{c_{2}}{c_{1}}$. [[configuration model|We know that]], as the average excess degree, $\frac{c_{2}}{c_{1}}= \frac{\langle k^{2} \rangle - \langle k \rangle}{\langle k \rangle}$, so $\frac{c_{2}}{c_{1}} \iff \langle k^{2} \rangle - \langle k \rangle > \langle k \rangle$, i.e., $\langle k^{2} \rangle - 2 \langle k \rangle >0 .$ > And then expanding $\langle k \rangle= \frac{1}{n}\sum_{i}k_{i}$ and $\langle k^{2} \rangle=\frac{1}{n} \sum_{i}k_{i}^{2}$ we get $\langle k^{2} \rangle - 2 \langle k \rangle = \frac{1}{n} \sum k_{i} (k_{i} - 2) $ > from which the last equivalency follows. > > **Size of giant component, when it exists.** We proceed somewhat similarly to [[characterization of giant component in the configuration model]]. Suppose a [[giant component]] exists. We calculate its size as $n \to \infty$. Consider any node in the [[network]] with nontrivial degree, choose one of its edges, and follow that edge. Denote by $u$ the probability that the edge's destination does not belong to the [[giant component]], and let $X$ be the [[indicator random variable]] that equals $1$ with [[probability]] $u$. A node having $k$ neighbors does not belong to the [[giant component]] with probability $u^{k}$ (the probabilities are all [[independent random variables|independent]] because [[the configuration model is locally tree-like]] guarantees that none of the neighbors connect to one another). The [[expectation]] of $u^{X}$ is given by the [[probability generating function]] $g_{0}(u):= \mathbb{E}[u^{X}]= \sum_{k}p_{k}u^{k}$ > and represents the probability, averaged over $k$, that a node does not belong to the [[giant component]]. Then $S=1-g_{0}(u)$ > is the average probability that a node *does* belong to the [[giant component]], or equivalently, the size of the [[giant component]] as a fraction of [[network]] size. > > Thus, our task is to find $u$. The probability that a node is not connected to the [[giant component]] via a particular neighboring node is equal to the probability that *that* node is not connected to the [[giant component]], which if it has [[degree]] $k$ is $u^{k}$. Notice, however, that we are dealing with the [[excess degree distribution]] here, such that the averaged probability over $k$ that a node is not connected to the giant component via a particular other node is $\sum_{k}q_{k}u^{k}$. But this probability is just $u$, by definition, hence $u=\sum_{k}q_{k}u^{k}.$ > Setting $g_{1}(u):= \sum_{k}q_{k}u^{k}$ we are thus have the following self-consistent equation for $u$ $u=g_{1}(u). (*)$ > Note that we do not need to calculate the [[excess degree distribution]] itself, for one can verify that $g_{1}(u)=\frac{g_{0}'(u)}{g_{0}'(u)}$. > > Usually we cannot solve $g_{1}(u)$ exactly for $u$. Since $g_{1}(1)=1$, $u=1$ is always a solution. Clearly it corresponds to a case where there is no [[giant component]]. $g_{1}(u)$ is defined as a [[power series]] with nonnegative coefficients (probabilities) when $u \geq 0$, hence it is generally positive, increasing, and [[convex function|concave-up]] (so [[derivative]] is increasing) ([[characterization of extrema for differentiable convex functions|see]]). ![[CleanShot 2023-11-06 at [email protected]|400]] > The figure shows we have a nontrivial solution when $g'_{1}(1)>1$. But properties of [[probability generating function]]s tell us $g'_{1}(1)$ is just the [[expectation|expected]] [[excess degree]]! So the following are equivalent: > - $u=g_{1}(u)$ has a solution with $u<1$ > - the average [[excess degree]] is greater than 1 > - the [[network]] has a [[giant component]]. > ---- #### ----- #### References > [!backlink] > ```dataview TABLE rows.file.link as "Further Reading" FROM [[]] FLATTEN file.tags GROUP BY file.tags as 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 > ```