Scale-Free Networks

A network is defined as scale-free if the probability $P(k)$ of a node having $k$ links (degree) follows a power law, $P(k) \sim k^{-\gamma}$.

This peculiar distribution, which strongly contrasts with the Poisson distribution found in random networks, is responsible for the emergence of hubs (high-degree nodes) and for the "Ultra Small World" property.

Based on these characteristics and on the role of the exponent $\gamma$, which of the following statements about scale-free networks is CORRECT?

a) The main distinction between a scale-free network (power law) and a random (Poisson) network of similar size is that the scale-free network does not have extremely high-degree nodes (hubs), while the random network has a longer-tailed distribution.

b) In real scale-free networks, which are finite (size $N$), the expected maximum degree ($k_{\max}$) is always independent of the network size $N$, since the divergence of the power law in the infinite limit is completely suppressed in practice.

c) The Ultra Small World property is a consequence of the central role of hubs, which ensure that the average path length in a scale-free network grows more slowly than the logarithmic growth that is typical of random networks.

d) The degree exponent $\gamma$ does not influence the finiteness of the distribution’s moments. For any value of $\gamma$, the second moment ($\langle k^2 \rangle$) of a scale-free network (in the limit $N \to \infty$) will always be finite, which is a prerequisite for the network to be modelable.

e) None of the above.

Original idea by: Matteus Vargas

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

Chapter 2 - Graph Theory

Consider the undirected graph above, representing an interaction network. 

Analyze: (i) the shortest path between nodes C and J; (ii) whether edge E–F is a bridge; (iii) the clustering coefficient of node B.

Select the correct alternative bellow:

A - $d(C,J)=4$; E–F is a bridge; $C_B = 5/6$
B - $d(C,J)=5$; E–F is a bridge; $C_B = 1/2$
C - $d(C,J)=4$; E–F is not a bridge; $C_B = 2/3$
D - $d(C,J)=3$; E–F is a bridge; $C_B = 5/6$
E - None of the above

Original idea by: Matteus Vargas Simão