Random Networks

You were hired to audit a router backbone. The team claims the topology is well modeled by an Erdős–Rényi network $G(N,p)$ with $N=10^6$ and mean degree $\langle k\rangle=6$. Based only on this model, choose the option that simultaneously describes:

(i) the structural regime and the expected global connectivity;
(ii) the clustering coefficient $C$;
(iii) the order of magnitude of the average distance $\langle d\rangle$; and
(iv) the minimum fraction $q_c$ of random node removals needed to eliminate the giant component.

Conventions: “connected” = a single component; $\ln$ is the natural logarithm; round $\langle d\rangle$ to the hundredth and $q_c$ to three decimals.

Useful data: $\ln 10 \approx 2.3026$, $\ln 6 \approx 1.7918$, $\ln 10^6 = 6\ln 10 \approx 13.8155$.

a) Supercritical, with a giant component (network not necessarily connected); $C\approx p\approx 6.0\times10^{-6}$; $\langle d\rangle \approx \dfrac{\ln N}{\ln\langle k\rangle}\approx 7.71$; $q_c\approx 1-\dfrac{1}{\langle k\rangle}\approx 0.833$.

b) Connected with high probability; $C\approx 6.0\times10^{-3}$; $\langle d\rangle\approx \ln N\approx 13.82$; $q_c\approx 0.500$.

c) Subcritical, no giant component; $C\approx 6.0\times10^{-6}$; $\langle d\rangle\approx \dfrac{\ln N}{\ln 6}\approx 7.71$; $q_c\approx 0.833$.

d) Critical; $C\approx p\approx 6.0\times10^{-6}$; $\langle d\rangle$ grows as $N^{1/3}$; $q_c\approx 1.000$.

e) None of the above.


Original idea by: Matteus Vargas