----- > [!proposition] Proposition. ([[the friendship paradox]]) > In the [[configuration model]], the [[probability]] that a node reached by following an edge from a chosen node has [[degree]] $k$ is $\frac{k}{2m} n p_{k} = \frac{kp_{k}}{\langle k \rangle }$ > where $\langle k \rangle$ is the average/[[expectation|expected]] [[degree]] over the whole [[network]] and [[mean degree|we have used]] $\langle k \rangle=\frac{2m}{n}$. > \ > From this we can derive that the [[mean degree|expected degree]] of a neighbor is $\frac{\langle k^{2} \rangle}{\langle k \rangle}$. Moreover, $\frac{\langle k^{2} \rangle}{\langle k \rangle}> \langle k \rangle$ almost surely: "your friends have more friends than you do." > [!proof]- Proof. ([[the friendship paradox]]) > There are $2m-1$ places to which a stub can lead, we assumed $m$ large so we'll just write $2m$ sometimes. If a node $i$ has [[degree]] $k$, then the stub connects to node $i$ with [[probability]] $\frac{k}{2m-1} \approx \frac{k}{2m}$. We [[expectation|expect]] $np_{k}$ nodes to have [[degree]] $k$. Thus $\sum_{np_{k}\text{ terms}} \frac{k}{2m}= \frac{knp_{k}}{\langle k \rangle}$ is the [[law of total probability|probability]] that the stub leads to *any* node having [[degree]] $k$. > > Or we could use [[law of total probability|law of total probability]]: $\begin{align} > \sum_{i=1}^{n} & \mathbb{P}(\text{stub connects to }i | i \text{ has degree }k) \mathbb{P}(i \text{ has degree }k) \\ > = & \sum_{i=1}^{n} \frac{k}{2m} p_{k} \\ > = & \frac{k}{2m} n p_{k}=k p_{k} / \langle k \rangle. > \end{align}$ > > Now consider a [[random variable|randomly]] chosen node in the [[configuration model]] and let $K$ denote the [[degree]] of one of its neighbors. We calculate > $\mathbb{E}[K]=\sum_{k=1}^{n-1} k\mathbb{P}(K==k)=\sum_{k=1}^{n-1}k^{2}p_{k}/\langle k \rangle = \frac{\langle k^{2} \rangle }{\langle k \rangle }.$ > (Recall $n$ is large.) > > Note that the average degree of a neighbor is thus different than the average degree $\langle k \rangle$ of a typical node in the [[network]]. In fact, it is usually larger, which we show now by calculating the difference $\langle k^{2} \rangle/ \langle k \rangle - \langle k \rangle = \frac{1}{\langle k \rangle }(\langle k^{2} \rangle - \langle k \rangle ^{2})=\sigma_{k}^{2} / \langle k \rangle, $ > where $\sigma_{k}^{2}$ is the [[variance|variance]] of the [[degree distribution]] which is positive so long as the [[network]] is not [[regular graph|regular]] which happens with probability $0$ as $n \to \infty$. Thus $\frac{\sigma_{k}^{2}}{\langle k \rangle}$ is almost surely greater than $0$, hence $\langle k^{2} \rangle / k > \langle k \rangle $ > with [[probability]] $1$. This is the friendship paradox. ----- #### ---- #### 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 > ```