Would like to have some hints on solving the following proofs related to network data.
- Let $z_{m}$ be the average number of neighbours at distance $m$ from a randomly selected node in a network $G_{n}$ with $n$ nodes. By considering the degree distribution of a node reached by following a randomly chosen edge, show that the following recurrence relationship holds.
$$z_{m} = \bigg( \dfrac{E(k^{2}) - E(k)}{E(k)}\bigg) z_{m-1}, m > 1 \text{ and } z_{1} = E(k),$$
where $k$ is a random variable of the degree of a randomly selected node in the network.
- The diameter $\ell$ of the network can be estimated when the total number of neighbours of a randomly selected node at distance $\leq \ell$ equals the number of nodes in the network. Using this argument, show that
$$\ell = 1+\dfrac{\log(n/z_{1})}{\log(z_{2}/z{1})}.$$
- When a fraction $f$ of nodes and their corresponding edges in the network are randomly removed, the degree distribution is changed from $p_{k}$ to $p_{k'}$, where
$$p_{k'} = \sum_{k=k'}^{\infty} p_{k} \begin{bmatrix} k\\k'\end{bmatrix} f^{k-k'} (1-f)^{k'}.$$
Show that the first and second moment of the new degree distribution become
$$ \begin{aligned} E(k') &= (1-f)E(k) \\ E(k'^{2}) &= (1-f)^{2}E(k^{2}) + f(1-f)E(k). \end{aligned} $$
Using Molloy-Reed criterion, show that the network dismantles when $f > f_{c}$, where
$$f_{c} = 1 - \dfrac{E(k)}{E(k^{2}) - E(k)}.$$
- Suppose that $p_{k} \propto k^{-\gamma}, \gamma > 0$. Let $k_{min}$ and $k_{max}$ be the observed minimum degree and the observed maximum degree respectively. Find $f_{c}$ in terms of $\gamma$, $k_{min}$ and $k_{max}$. Demonstrate that, when $2 < \gamma < 3$, $f_{c}$ tends to one and, when $\gamma > 3$, $f_{c}$ is a constant independent of the network size. Furthermore, argue that we cannot dismantle a scale-free network by random removel of nodes when $2 < \gamma < 3$.