---- > [!theorem] Theorem. ([[the small-world effect in the Erdos-Renyi random graph model]]) > The [[expectation|expected]] [[diameter of a network|diameter]] of $G(n,p)$ varies as $\ln n$ provided $n$ is large. > [!proof]- Proof. ([[the small-world effect in the Erdos-Renyi random graph model]]) > Consider two different starting nodes $i$ and $j$ in $G(n,p)$. As seen in the [[characterization of giant component in Erdos-Renyi random graph model]], for $n$ large we have that the [[expectation|expected]] number of nodes $s$ and $t$ steps from these starting codes will be $c^{s}$ and $c^{t}$ respectively so long as we stay in the regime where both of these are much less than $n$. We assume this condition is satisfied. Now, we proceed as follows. > ![[CleanShot 2023-11-06 at [email protected]|500]] > We have balls of radius $s$ and $t$ around nodes $i$ and $j$ respectively. If a connection exists between said balls then the [[geodesic distance in networks|shortest path]] from $i$ to $j$ has length $d_{ij}$ less than or equal to $\ell:=s+t+1$. Conversely, if no such edge exists than the balls have not met yet and hence the shortest path has length greater than $s+t+1$. That is, $\mathbb{P}(d_{ij} > s+t+1)=\mathbb{P}(d_{ij}>\ell)$ is equal to the probability that no edge exists between the balls. > > We compute this probability. There are on average $c^{t} \times c^{s}=c^{s+t}$ pairs of nodes such that one lies on each surface, and each is not-connected with probability $1-p=1-\frac{c}{n-1} \approx 1- \frac{c}{n}$. So the probability of no connections is $\mathbb{P}(d_{ij}> \ell)=(1-p)^{c^{s+t}}=(1-p)^{c^{\ell-1}} \approx \left( 1-\frac{c}{n} ^{} \right)^{c^{\ell-1}},$where the $\approx$ becomes $=$ as $n \to \infty$. Now we find $\ln \mathbb{P}(d_{ij} > \ell)= c^{\ell-1} \ln \left( 1-\frac{c}{n} \right) \approx -\frac{c^{\ell}}{n},$ > where again $\approx \to =$ as $n \to \infty$ (we used a [[power series]] expansion $\ln(1-x) \approx -x$). So now exponentiation yields $\mathbb{P}(d_{ij}>\ell)= e^{-c^{\ell}/n}.$ > The [[network]] [[diameter of a network|diameter]] is the smallest $\ell$ such that $\mathbb{P}(d_{ij} > \ell)=0$. In the [[function limit]] of large $n$, the above equation tends to 0 only if $c^{\ell}$ grows faster than $n$, meaning that our smallest value of $\ell$ is the value such that $c^{\ell}=an^{1+\varepsilon}$ with $a$ constant and $\varepsilon \to 0$ from above. Rearranging that equation we find $\ell=\ln a /\ln c + \lim_{ \varepsilon \to 0 } \frac{(1+\varepsilon) \ln n}{\ln c} =A+\ln n / \ln c$ > where $A,c$ are constant and so the result is shown. ---- #### ----- #### 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 > ```