2025-310

Which of the following alternatives contains a graph with only one Strongly Connected Component (SCC)? 

a)

b)

c) 

d)

 

e) None of the above


Original idea by: Pedro Zaffalon da Silva

2025-309

The Kosaraju–Sharir's algorithm is used to identify strongly connected components (SCCs) in directed graphs. It runs in O(V + E) time, since it performs two depth-first searches (DFS) and uses the transposed graph.

Consider the directed graph with vertices {0, 1, 2, 3, 4, 5, 6, 7} and edges:

(0 → 1), (1 → 2), (2 → 0), (2 → 3), (3 → 4), (4 → 5), (4 → 6), (5 → 6), (6 → 7), (7 → 4)

Regarding the application of the Kosaraju–Sharir's algorithm to this graph, select the correct alternative:

a) The algorithm finds three strongly connected components: {0,1,2}, {3} and {4,5,6,7}.

b) The algorithm finds four strongly connected components: {0,1,2}, {3}, {4,5,6} and {7}.

c) The algorithm cannot be applied to directed graphs, only to undirected graphs.

d) The algorithm finds eight strongly connected components, each vertex being isolated.

e) None of the above.

Original idea by: Pedro Pereira

2025-308

Consider a pathogen spreading on a highly heterogeneous contact network whose degree distribution follows a power law with exponent between 2 and 3.  Based on network epidemic theory and immunization strategies, which of the statements below is correct ?

A) In networks of this type, the epidemic threshold is positive. Therefore, random immunization is sufficient to stop the epidemic if at least 30% of the population is vaccinated.

B) Strategies that immunize the acquaintances of randomly selected individuals tend to target high-degree nodes, increasing the epidemic threshold.

C) The strategy of immunizing acquaintances of random individuals does not improve epidemic control in real networks, because there is no correlation between the degree of a node and the degree of its neighbors.

D) For networks with diverging second moment in their degree distribution, SI and SIS models have the same epidemic threshold, since hubs do not influence their dynamics.

E) None of the above.

 Original idea by: Pedro Zaffalon da Silva 

2025-307

Which of the following statements correctly describes the relationship between network structure and the spread of pathogens, ideas, or computer viruses?

A) The structure of the underlying network is irrelevant to the spreading process; the only factor that matters is the inherent contagiousness of the agent (virus or idea). 

B) Biological diseases spread through contact networks, whereas digital viruses and social phenomena spread randomly without following any specific network topology. 

C) The contact network serves as the transmission medium for spreading processes, meaning that the network's topology significantly determines the speed, reach, and pattern of the diffusion. 

D) Spreading phenomena are strictly limited to biological systems (like the SARS outbreak), and network science concepts cannot be effectively applied to digital or social contexts.

E) None of the above.

Original idea by: Augusto Cruz

2025-306

Consider the propagation of a virus modeled by the SIS (Susceptible-Infected-Susceptible) system in two distinct networks:

• A Random Network (Erdős-Rényi).
• A Scale-Free Network.

Both networks have the same number of nodes and the same average degree.

Given that the epidemic threshold is defined by the critical spreading rate, below which the virus dies out exponentially, select the correct statement regarding the behavior of this threshold and immunization strategies:

1. Since both networks have the same average degree , the epidemic threshold will be identical for both, as the average connection density determines the initial spreading speed in any topology.
2. The Random Immunization strategy is equally effective in both types of networks, meaning that the same fraction of nodes have to be immunized in both networks to stop the epidemic.
3. In Scale-Free Networks, with degree exponent \(\gamma\) between 2 and 3, the hubs are less relevant, and the network behaves similarly to a random network.
4. In the Scale-Free Network, the epidemic threshold is given by \(\langle k \rangle / \langle k^2 \rangle\).
5. None of the above.

Original idea by: Giancarlo Maldonado Cárdenas

2025-305

Consider immunization strategies discussed in the context of network epidemics. Which of the following statements is incorrect?

1. Random immunization performs poorly in scale-free networks because it rarely targets highly connected hubs.
2. Targeted immunization raises the epidemic threshold by removing the hubs responsible for rapid spreading.
3. Random immunization always outperforms targeted immunization in networks where \(\langle k^2\rangle\) is finite.
4. Immunizing a randomly selected neighbor of a randomly chosen individual tends to target high-degree nodes due to the friendship paradox.
5. None of the above

Original idea by: Jhonatan Cléto

2025-304

In the context of epidemic spreading on networks, which statement correctly explains why scale-free networks allow epidemics to spread more easily than random networks?

1. Because scale-free networks have a lower average degree \(\langle k\rangle\), making it harder to contain infections.,/li>
2. Because scale-free networks follow homogeneous mixing, allowing each node the same chance to infect others.
3. Because scale-free networks contain hubs with very high degree, causing \(\langle k^2\rangle\) to diverge and making the epidemic threshold \(\lambda_c\) approach zero.
4. Because scale-free networks have stronger community structure, slowing down infection and increasing the epidemic threshold. 
5. None of the above.

Original idea by: Thiago Soares Laitz