----- > [!proposition] Proposition. ([[the configuration model is locally tree-like]]) > Any local [[neighborhood]] in the [[configuration model]] is a [[tree]] if for $n$ large enough. Put precisely, if you start at any node in the [[network]] and form the set of all nodes a distance $d$ or less from it, the set will [[almost-everywhere|almost-surely]] take the form of a [[tree]] as $n \to \infty$. > [!proof]- Proof. ([[the configuration model is locally tree-like]]) > We proceed similarly to [[small components of Erdos-Renyi random graph model are trees]]. Choose a starting node and form a [[neighborhood]] $A$ of nodes around it a distance $d$ or less away. Suppose $A$ has $s$ nodes in total. $A$ has at least $s-1$ edges (else it would not be [[connected|connected]]). We claim it almost-surely does not have more than $s-1$ edges as $n \to \infty$. Let $X=\text{number of additional edges in }A$; we want to show $\mathbb{E}[X] \to 0$. For each pair of nodes $i,j \in A$ define $X_{ij}=\begin{cases} > 1 & \text{ an `additional' edge exists between }i \text{ and } j \text{ in }A \\ > 0 & \text{ else,} > \end{cases}$ > note that $X=\sum_{i,j}X_{ij}$. $\mathbb{P}(X_{ij}=1)=\frac{k_{i}k_{j}}{2m}$ as shown [[configuration model#^443b4f|here]]. So $2\mathbb{E}[X]=2\sum_{i,j} \mathbb{E}[X_{ij}]=2\sum_{i,j} \frac{k_{i}k_{j}}{2m},$ > as $n$ and hence $m$ tend to infinity, each term above tends to $0$ supposing that the average values of $k_{i}$ and $k_{j}$ (which are average values of [[excess degree distribution]]) remain fixed. The average excess degree is $\frac{\langle k ^{2}\rangle - \langle k \rangle}{\langle k \rangle}$ and so provided this values does not grow faster than $n$ the network is locally tree-like. > ----- #### ---- #### 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 > ```