Chapter 7 - Network Robustness

Imagine a tree standing tall in the forest. Its structure can be represented as a tree graph: the node labeled R stands for the roots, the nodes labeled L represent the leaves, and every other node, labeled by numbers, marks a branching point where the trunk or branches split.

Consider the graph representation of this tree displayed on the following figure.

One afternoon, a sudden whirlwind sweeps through the forest. The strong gusts break some of the branching nodes, tearing off sections of the tree. To survive, the tree’s roots must still maintain at least half of its original leaf nodes after the storm.

From the options below, which set of branching nodes could be destroyed by the whirlwind — while still allowing the tree to remain alive?

A. 2, 11, 22, 23

B. 5, 7, 12, 16, 18, 19, 22, 24 

C. 2, 12, 17, 20

D. 6, 7, 14, 24 

E. None of the above.

Original idea by: Rodolfo Bitu

Chapter 7 - Degree Correlations

Rodolfo was studying ant colonies. He keeps several ant farms of Brazilian species in his house. For each colony, he mapped every contact between ants, representing these interactions as a network. Even when two ants interacted multiple times, he recorded that relationship only once.

He noticed that these networks follow the Scale-Free Network Model with k_min=1, and that the queen ant consistently has the highest number of connections.

His summarized results are as follows

• “Formigas carpinteiras” farm: 1,000,000 ants; queen has 100 connections.
• “Formigas de fogo” farm: 1,000,000 ants; queen has 10,000 connections.
• “Formigas faraó” farm: 10,000 ants; queen has 1,000 connections.
• “Formigas louca” farm: 10,000 ants; queen has 10 connections.

Select the correct statement: 🐜

A. The “Formigas carpinteiras” farm is a disassortative network because the high number of queen’s connections indicates a hub-dominated topology.
B. Both the “Formigas de fogo” and “Formigas faraó” farms are disassortative networks because their degree exponent values are less than 3.
C. The “Formigas louca” farm is disassortative because its degree exponent is greater than 3.
D. All farms are assortative networks because larger populations tend to promote connections between similar-degree nodes.
E. None of the above.

Original idea by: Rodolfo Bitu

Chapter 5 - Barabási-Albert Model

Bitu is an explorer who sets out to visit the mysterious Bara-Al islands — a chain of 96 islands. Each island is connected by a few bridges. Whenever a new island was settled, its bridges were built with a preference for linking to islands that already had many connections. In this way, the Bara-Al islands grew according to Barabási–Albert Model of networks.

So, he wonders: what is the expected maximum number of bridges he would need to cross, starting from one island and traveling to the farthest one?

Note 1: 96 ≈ e^4.5 
Note 2: 4.5 ≈ e^1.5 

A. 3

B. 5

C. 6

D. 8

E. None of the above

Original idea by: Rodolfo Bitu

Chapter 4 - Scale-Free Property

Consider the Scale-Free Network Model with minimum degree k_min​ = 1.

Define f(N,γ) as the function that computes the second moment of the degree distribution, ⟨k²⟩ , for a finite network with N nodes and degree exponent γ. Use the Continuum Formalism.

Compute the following ratios:

1. f(10⁴, 7/3) / f(10⁴, 5)

2. f(10⁸, 7/3) / f(10⁸, 5)

3. f(10¹², 7/3) / f(10¹², 5)

The values for (1), (2), and (3) are approximately, respectively:

A. 1, 10_000,  1_000_000_000
B. 1, 100_000_000, 1_000_000
C. 100, 10_000, 1_000_000
D. 100, 100_000_000, 1_000_000_000
E. None of the above

Note: underscores are used only for readability of large numbers.

Original idea by: Rodolfo Bitu

Chapter 3 - Random Networks

Consider networks following the Random Network Model with N=10,000 nodes and probability p of a pair of nodes to be connected.

Choose the WRONG alternative.
Hint: ln⁡(10,000) ≅ 10

A. When p = 1/20,000​, the network is in the subcritical regime, which means it does not have a giant component.
B. When p = 1/10,000​, the network is in the critical regime, which means it has a giant component.
C. When p = 1/4,000​, the network is in the connected regime, which means the giant component absorbs all nodes and components.
D. When p = 1/5,000​, the network is in the supercritical regime, which means the giant component contains a considerable fraction of the nodes.
E. None of the above.

Original idea by: Rodolfo Bitu

Chapter 2 - Graph Theory

 

G is a bipartite graph with vertex partition:

U = {1,2,3,4,5,6}

V = {7,8,9}

Consider the projections of G onto the sets U and V and the following graphs. 

Select the alternative that contains only true statements:

A. The projection of G onto U is graphs II and IV.

B. By removing one edge from graph IV, it becomes the projection of G onto V.

C. The projection of G onto U is graph III.

D. The projection of G onto V is graph II.

E. None of the above.

Original idea by: Rodolfo Bitu