Network Robustness

Using the giant-component breakdown criterion, $\frac{\langle k'^2 \rangle_f}{\langle k' \rangle_f} = 2$, and replacing $f$ by $f_c$ in the expressions for the residual moments, derive the relation that expresses the second moment of the original degree distribution, $\langle k^2 \rangle$, in terms of the original first moment, $\langle k \rangle$, and the critical percolation threshold $f_c$.

The derived relation is:

a) $\langle k^2 \rangle = \langle k \rangle \left( 1 + \frac{1}{1 - f_c} \right)$
b) $\langle k^2 \rangle = \langle k \rangle \frac{2 - f_c}{1 - f_c}$
c) $\langle k^2 \rangle = 2 \langle k \rangle (1 - f_c) + \langle k \rangle f_c$
d) $\langle k^2 \rangle = \frac{\langle k \rangle}{(1 - f_c)^2}$
e) None of the above

Original idea by: Matteus Vargas Simão da Silva

Question: Analysis of Degree Correlations in Complex Networks

A network engineer is analyzing the topology of a large technological network. After data collection and a complete analysis, he calculated the Degree Correlation Coefficient $r$ for the network, obtaining the value: $r=-\mathrm{0.19.}$

The Degree Correlation Coefficient ($r$) is defined as:

$$r \;=\; \frac{\sum_{j,k} jk\,\bigl(e_{jk} - q_j q_k\bigr)}{\sigma_r^2}$$

where $e_{jk}$ represents the probability of finding nodes with degrees $j$ and $k$ at the ends of a randomly selected edge; $q_k$ is the probability that the end of an edge has degree $k$$(q_k=k{p}_k\mathrm{/}⟨k⟩);\; and$$\sigma_r^2$ is the normalization term.

Based on this result ($r = -0.19$) and on the theory of degree correlations, mark the correct statement about the topology of this network:

A) The value $r = -0.19$ classifies the network as neutral. Neutral networks are those in which nodes connect to each other with the probabilities expected in random networks, implying that the difference $\sum_{j,k} jk\,\bigl(e_{jk} - q_j q_k\bigr)$is zero. The negative value obtained should be dismissed as a statistical artifact or a “structural cutoff”.

B) The value $r = -0.19$ indicates that the network is disassortative. In disassortative networks, hub nodes tend to avoid linking to each other. This means that, for pairs of high-degree nodes (both $j$ and $\mathrm{k\; large),\; the\; observed\; probability }$$e_{jk}$ is lower than the expected probability $q_j q_k$ of an uncorrelated network.

C) The negative value of $r$ points to an assortative network, since this type of network typically exhibits hubs connecting to low-degree nodes. The condition for $r$ to be positive ($r \ge 0$) is that the magnitude of the correlation captured by $\langle jk\rangle - \langle j\rangle \langle k\rangle$ (the numerator of the formula) is positive.

D) Technological networks are classically assortative. The $r = -0.19$ is atypical, but if it were truly disassortative, the impact would be increased robustness against targeted attacks, since removing a hub would not result in large cascades of disconnections among other hubs.

E) None of the above.

Original idea by: Matteus Vargas Simão da Silva

Question: Degree Dynamics in the BA Model

In the Barabási–Albert (BA) model, which incorporates growth (continuous addition of new nodes) and preferential attachment (new nodes prefer to connect to more connected nodes), the time evolution of a node’s degree, $k_i(t)$, is a central aspect.

The degree growth for a node $i$, which entered the network at time $t_i$ with $m$ links, follows a power law in time $t$, characterized by the dynamic exponent $\beta$.

Which of the following formulas correctly represents the degree growth law $k_i(t)$ for a node $i$ in the BA model?

A.

$$k_i(t) = m \left( \frac{t}{t_i} \right)^{1/2}$$

B.

$$k_i(t) = m \frac{t}{t_i}$$

C.

$$k_i(t) = k^{-\gamma} \quad \text{where} \quad \gamma = 3$$

D.

$$k_i(t) = m \left( \frac{t}{t_i} \right)^{2}$$

E. None of the above

Original idea by: Matteus Vargas Simão da Silva

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