----- > [!proposition] Proposition. ([[size of small components in the configuration model]]) > The average/expected size $\langle s \rangle$ of the [[small component]] in the [[configuration model]] to which a node belongs is $\langle s \rangle= 1 + \frac{u^{2}g_{0}'(1)}{g_{0}(u)[1-g_{1}'(u)]} . (1)$ > If there is no [[giant component]], then $u=1$ ([[characterization of giant component in the configuration model|see here]]) and so $\langle s \rangle= 1 + \frac{g_{0}'(1)}{1-g_{1}'(1)} \text{ when } u=1.$ > $(1)$ may also be expressed in the following forms: $\langle s \rangle=1 + \frac{c_{1}^{2}}{c_{1}-c_{2}} \text{ and } \langle s \rangle= 1 + \frac{\langle k \rangle^{2}}{2\langle k \rangle-\langle k^{2} \rangle }, $ > so we see $\langle s \rangle$ is specified entirely by the first and second [[moment of a measurable function|moments]] of the [[degree distribution]]. > \ > Using [[probability generating function|PGF]] techniques we can infer exactly how [[small component]] sizes are [[distribution|distributed]]. Letting $\pi_{s}$ denote the [[probability]] that a randomly chosen node belongs to a small (not [[giant component|giant]]) [[component of a graph|component]] of size $s$, we have $\pi_{s}=\begin{cases} \frac{\langle k \rangle }{(s-1)!} \left[ \frac{d^{s-2}}{dz^{s-2}}[g_{1}(z)]^{s} \right] |_{z=0} & s > 1 \\ p_{0} & s=1. \end{cases}$ > [!proof]- Proof. ([[size of small components in the configuration model]]) > Because [[the configuration model is locally tree-like]], we begin as we did in [[size of small components in Erdos-Renyi random graph model]]: we consider a random node $i$ and notice that the size of the [[component of a graph|component]] to which it belongs is just $1$ plus the size of shaded [[subgraph|subnetworks]]; see below. > > ![[CleanShot 2023-11-06 at 17.15.05@2x 1.jpg|500]] > > Then we follow the exact same argument as in the [[size of small components in the configuration model]] proof, the [[expectation|expected]] size $\langle s \rangle$ of the [[small component]] to which $i$ belongs is $\langle s \rangle= 1 + \langle k \rangle_{\text{small}} \langle t \rangle ,$ > where $\langle k \rangle_{\text{small}}$ is the [[expectation|expected degree]] of a node in the [[small component]] and $\langle t \rangle$ is the [[expectation|expected]] size of the set of nodes reached by following an edge from $i$. Our task hereon will therefore be to find $\langle k \rangle_{\text{small}}$ and $\langle t \rangle$. This is an exercise (or read the book). ----- #### ---- #### 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 > ```