2026-332

As the average degree \( \langle k \rangle \) of an Erdős-Rényi random network increases, the network's topology undergoes distinct phases of evolution. Which of the following statements accurately characterizes the network exactly at its critical point (\( \langle k \rangle = 1 \) )?

A) The size of the largest component scales as \( N^{2/3} \), containing a vanishing fraction of all nodes, and the cluster size distribution follows a power law. 

B) The network lacks a giant component, and the size of the largest cluster scales logarithmically with the total number of nodes. 

C) A giant component emerges that contains a finite fraction of the network's nodes, and the distribution of cluster sizes is exponential. 

D) The giant component absorbs all isolated nodes and clusters, rendering the network fully connected. 

E) None of the above.

Original idea by: João Vianini

2026-331

Regarding the models G(N, p) and G(N, L), choose the correct alternative:

A) Choosing p = 2L/N(N-1) will guarantee that the graphs generated by G(N, p) and G(N, L) have the same number of edges.

B) If N1 > N2 and L > 0, any graph generated by G(N1, p) will have more edges than any graph generated by G(N2, L).

C) For N1 > N2, and p1 > 0,  G(N1, p1) can generate graphs with an impossible number of edges for any graph generated by G(N2, p2) to reach, regardless of the value of p2.

D) The degree distribution of graphs generated by G(N, p) follow a power-law, as very often real-world graphs do.

E) None of the above.

Original idea by: João Pedro Carolino Morais

2026-330

Consider graphs with \(N = 4\) nodes. Below are three sample outcomes of \( G(N, p) \) at different values of \( p \). Dashed lines show absent edges.

  

Which graph is in the supercritical regime?

(A) All three are supercritical since every node has at least one neighbor

(B) Graph A, because it has at least one edge and \( \langle k\rangle = 0.3 > 0 \)

(C) Graph B, because \(\langle k\rangle = 1 \) satisfies the condition for the giant component

(D) Graph C, because \( \langle k\rangle = 2.4 > 1 \) and \( p = 0.8 > p_c = 1/3 \)

(E) None of the above.

Original idea by: Gustavo P. C. P. da Luz

2026-328

Consider two random graphs, G_a and G_b, where edges are created independently with probabilities p_a and p_b, respectively. Additionally, consider the following binomial degree distribution:

 

Consider N_a = 200 and  N_b = 100 

Evaluate the following statements:

I) The average degree <k> is higher in graph G_b.  

II) The variance of the degree distribution in G_b  is greater than in G_a .  

III) The expected number of edges in G_a is greater than in G_b.  

Select the correct alternative:

A) Only I is correct.  

B) Only I and II are correct.  

C) Only II and III are correct.  

D) I, II, and III are correct. 

E) None of the above.


Original idea by: Gabriel Ukstin Talasso

2026-327

 In a random network with \( N \gg 1 \) and average degree \( \langle k \rangle = 3 \), what is the expected fraction of nodes with degree 0 or 1?

1. \( 1 - e^{-3} \)
2. \( 4 e^{-3} \)
3. \( 3 e^{-3} \)
4. \( 2 e^{-3} \)
5. None of the above

Original idea by: Antonio De Cesare Del Nero

2025-258

A fungal colony, whose hyphae form a network called the mycelium, started growing on a piece of bread left unattended. The colony started small, at an initial number of spores \(N = 5000\). It is known that, although the number of spores remains constant, this species creates hyphae (links) over time, so that at any point in time it looks like a random \(G(N,p)\) network, where \(p\) is given by the function below:

\( p(t) = t/10^{4}\)

where t is the time measured in days.

Given two different intervals:

• A day has passed
• Three days have passed

Assign the correct alternatives with respect to attributes about the mycelium growth.

1. As one day passes, the network is subcritical, and by three days, it remains subcritical.
2. As one day passes, the network is subcritical, and by three days, it’s supercritical.
3. As one day passes, the network is critical, and by three days, it’s supercritical.
4. As one day passes, the network is already supercritical.
5. None of the above.

Original idea by: Alexandre Petrachini

2025-257

\(G_1(N,p_1)\) and \(G_2(N,p_2)\) are two random networks with the same number of nodes \(N\), but different link probabilities, with \(p_1 > p_2\).

Which of the following statements is correct?

1. \(G_1\) will have a lower clustering coefficient than \(G_2\).
2. \(G_2\) will have a larger average degree than \(G_1\).
3. Both \(G_1\) and \(G_2\) must have the same degree distribution, since they share the same number of nodes \(N\).
4. \(G_1\) is more likely to contain a giant component than \(G_2\).
5. None of the above.

Original idea by: Gabriel Sato 

2025-256

Given the following plot for the theoretical binomial distribution of degrees in a random graph created with 250 nodes,

what was the probability (rounded to 2 decimal places) of edge creation used?

A) 0.01

B) 0.05

C) 0.10

D) 0.20

E) None of the above.

Original idea by: João Medrado Gondim

2024-235

Consider a Random Network with N = 2000 nodes and p = 0.0015. In which regime is this network? What is its number of links, in average? Truncate the result if necessary.

A) Supercritical regime and 1499 links.

B) Critical regime and 1499 links.

C) Critical regime and 2998 links.

D) Supercritical regime and  2998 links.

E) None of the above

Original idea by: Cinthia Kleiner

2023-207

Consider an Erdős-Rényi random graph with \(N = 1200\) nodes. If the average degree of the graph is 50, what is the variance of the degree distribution (round to 1 decimal place)?

a) 49.9

b) 7.8

c) 47.9

d) 6.9

e) None of above

Original idea by: João Marcos

2023-206

 

Imagine a Cayley Tree, constructed starting from a central node, where each node has degree \(k\), except the nodes at distance P from the central node, that have degree one, as shown in the figure above. Considering that the number of nodes reachable in \( t \geq 1 \) steps from the central node is \( k(k-1)^{t-1} \), and the number of links is \( L = N-1 \), where \( N \) is the number of nodes, what is the probability of conexion between nodes for \(k=4\) and \(P=4\)?

1. 1/161
2. 2/161
3. 1/41
4. 2/41
5. None of above

Original idea by: Germán Darío Buitrago Salazar