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

2025-294

You are a systems analyst at a major data center, and you are tasked with evaluating the robustness of your facility's network infrastructure against random node failures.

Your analysis of the network topology reveals that the average degree <k> of the nodes is 6.25. Based on your understanding of robustness, what breakdown threshold does the network at the datacenter need to have to display enhanced robustness?

a) 0.85

b) 0.84

c) 0.17

d) 0.16

e) None of the above

Original idea by: Alexandre Petrachini

2025-303

In the context of the classic SI, SIS, and SIR epidemiological models, which of the following statements is incorrect?

A. All three models predict that the epidemic ends only after every individual has been infected at least once.

B. In the Susceptible-Infected (SI) model, each individual in the population is assumed to be either healthy or infected.

C. In the Susceptible-Infected-Susceptible (SIS) model, an individual who becomes infected with the disease can recover and return to the susceptible state, allowing reinfection.

D. In the Susceptible-Infected-Recovered (SIR) model, individuals who have been infected acquire immunity or die from the disease and therefore do not become susceptible again.

E. None of the above

Original idea by: Mylena Roberta

2025-302

Consider the SI model (Susceptible-Infected) under the homogeneous mixing assumption. In this model, the spread of the virus is driven by random contacts between individuals.

You are given the following data for a specific population at time \(t\):

• Total Population (\(N\)): 10,000 individuals

• Current Susceptible individuals (\(S\)): 9,500

• Current Infected individuals (\(I\)): 500

• Average degree (contacts per individual per unit time, \(\langle k\rangle\)): 12

• Transmission probability (\(\beta\)): 0.05

At this specific moment, what is the average rate of new infections?

A) 275

B) 285

C) 570

D) 600

E) None of the above

Original idea by: Alexandre Petrachini

2025-301

Consider the following well-known pathogens and the following time evolution graph of the fraction of infected individuals using the Susceptible-Infected-Susceptible Model (SIS):

Disease	Transmission	R0
SARS	Airborne droplet	2-5
Polio	Fecal-oral route	5-7
Measles	Airborne	12-18

Which of the curves could represent the pathogens presented?

A. f1 - SARS,  f2 - Polio,  f3 - Measles

B. f1 - Measles,  f2 - SARS,  f3 - Polio

C. f1 - Polio,  f2 - SARS,  f3 - Measles

D. f1 - Measles,  f2 - Polio,  f3 - SARS

E. None of the above

Original idea by: Jhessica Silva

2025-300

In the homogeneous-mixing SI model, which statement correctly describes the analytical solution for the time required to reach a fraction \(i(t) = 0.5\) of infected invividuals?

a) It depends only on the total population size and not on the infection rate \(\beta\)

b) It always occurs at the same time, regardless of the initial condition

c) It is inversely proportional to the contact density but not to \(\beta\)

d) It increases linearly with the initial number of infected individuals

e) None of the above. 

Original idea by: Gabriel Sato

2025-299

Under the Homogenous Mixing hypothesis, why are early quarantines one of the recommendations for the slow down of infection spreading?

A) For the Susceptible-Infected-Removed Model, quarantines are a good tool to maintain \(R_0\) above 1, reaching the "Disease-free State", where epidemics die out due to the negative \(\tau\).

B) The quarantine decreases the likelihood of a disease being transmitted, which accelerates the "Disease-free State", indicating that the infection will die exponentially.

C) In the Susceptible-Infected Model, individuals are prone to be infected again after recuperation, therefore quarantines are paramount to avoid new infections on the same individual.

D) By restricting the number of connections between individuals, the characteristic time will be greater, giving researchers more time to discover new vaccines and medicines.

E) None of the above.

Original idea by: João Medrado Gondim

2025-298

In a population of size \(N=10000\), a disease spreads according to the SI model.
The average degree is \(\langle k\rangle= 20\), the transmission probability per contact is  \(\beta = 0.04\), and initially one individual is infected.

Using the SI model solution with the homogeneous mixing hypothesis, compute the expected number of infected individuals after \(t=5\) time units.

Round to the closest integer.

A) 54

B) 350

C) 850

D) 1100

E) None of the above

Original idea by: Yan Prada 

2025-297

In the context of community detection in complex networks, which of the following statements most accurately describes the "resolution limit" inherent in modularity (M) maximization?

A. The resolution limit refers to the inability of the Girvan-Newman algorithm to effciently recalculate edge betweenness in large-scale networks, thus preventing its practical application.

B. The resolution limit refers exclusively to divisive methods, indicating that iterative edge removal always fragments the network into individual components before a maximum of modularity can be achieved.

C. The resolution limit is an artifact of the modularity formula, favoring the merging of small communities, even if they are strongly internally connected (such as cliques), into larger communities, to maximize the overall M.

D. The resolution limitation states that modularity (M) will always assign a negative value to any partition that is not a perfect clique, making it difficult to identify dense but incomplete community structures.

E. None of the above

Original idea by: Juan Jose Rodriguez Rodriguez

2025-296

Consider the network below, where each edge is labeled with its edge betweenness centrality.

After applying a divisive community detection algorithm based on edge betweenness, the first split of the network yields the two communities shown below:

Using only this two-community partition, what is the modularity of this division? Round your answer to two decimal places.

1. 0.16
2. 0.20
3. 0.24
4. 0.28
5. None of the above

Original idea by: Luiza Barguil

2025-295

Given the following graph and the respective dendrogram, mark the correct alternative.

a) All division lines produce some weak community.

b) Division line 3 produces 2 weak communities and 2 strong communities.

c) Division line 1 produces one strong and one weak community. 

d) Division line 2 produces at least 2 strong communities.

e) None of the above.

 

 Original idea by: Giorgio Rossa

2025-293

The Galactic Federation maintains an interplanetary communication network connecting \(N = 1000\) colonies through hyperspace routes. Scientists from the Central Observatory have estimated:

\(\langle k \rangle = 4\), \(\langle k^2 \rangle = 100\)

During a cosmic particle storm, 800 colonies lost communication with the network.  Does the Galactic Federation’s network still maintain a giant component or has it collapsed?

1. The network remains connected, since the critical threshold is \(f_c = 0.96\).
2. The network has collapsed, since the critical threshold is \(f_c = 0.96\).
3. Communication has collapsed, since the critical threshold is \(f_c = 0.67\).
4. Communication is still possible, since the critical threshold is \(f_c = 0.67\).
5. None of the above

Original idea by: Aline Azevedo

2025-292

You are the team leader in your firm’s Cybersecurity Department, responsible for maintaining four critical corporate networks: AegisNet, MercuryGrid, HeliosCloud and VanguardLink 

Early one morning, you notice that several nodes across all four networks have been unexpectedly shut down. A quick inspection of the system logs (graphically depicted below) reveals the exact sequence in which each node went offline. Your mission is to determine whether this incident represents a coordinated cyberattack targeting multiple systems simultaneously, or if it is merely the result of random hardware failures in aging equipment.

Time 0 : 

Time 1:  

Time 2: 

Based on the logs, your best assessment is:

A) It was an attack on all networks

B) It was an attack only on VanguardLink

C) It was an attack only on AegisNet and VanguardLink

D) It was an attack only on AegisNet, MercuryGrid, and VanguardLink

E) None of the above.

Original idea by: Carolina Albuquerque

2025-291

The image below shows the probability that a node belongs to the giant component of an Erdos–Rényi network, estimated as the ratio between the size of the largest connected component and the number of the remaining nodes after the removal of a fraction f of nodes, with the red vertical line representing the breakdown threshold for the created network.

Which of the following alternatives best approximates the number of nodes (N) of the network and the probability for edge creation (p), respectively:

A) N = 500 and p = 0.015

B) N = 750 and p = 0.02

C) N = 1000 and p = 0.005

D) N = 1500 and p = 0.002
E) None of the above.

Original idea by: João Medrado Gondim

2025-290

Consider a complex network subject to random failures and targeted attacks. Which of the following statements best characterizes network robustness?

1. Scale-free networks are equally robust against both random failures and targeted attacks due to their heavy-tailed degree distribution.
2. Random networks (Erdős–Rényi type) typically remain connected longer under random attacks than scale-free networks with the same average degree.
3. The robustness of a network is maximized when the degree distribution follows a power law with exponent close to 5.
4. In scale-free networks, robustness to random node removal arises because most nodes have low degree, while vulnerability to targeted attacks results from dependence on high-degree hubs.
5. None of the above.

Original idea by: Yan Prada Moro

2025-289

Considering the impact of degree correlations on the emergence of a giant component in random networks, which of the following statements is correct?

A. The phase transition point is the same for assortative and disassortative networks

B. The phase transition occurs at higher ⟨k⟩ in assortative networks and at lower ⟨k⟩ in disassortative networks

C. For large ⟨k⟩, the giant component is smaller in assortative networks than in disassortative networks

D. Regardless of ⟨k⟩, the giant component is always larger in neutral networks than in assortative or disassortative networks

E. None of the above

Original idea by: Mylena Roberta

2025-288

A Flamengo fan living in Campinas made a promise that if their team reached the final of the 2025 Libertadores de America Cup, they would visit all the stadiums where Flamengo played during the knockout stages. Now that Flamengo has indeed made it to the final, the fan must fulfill their promise before returning home to Campinas to catch a flight to Lima for the final.

To plan the most efficient route, the fan created a simplified map in the form of a graph, where each node represents a stadium and each edge is weighted by the distance between stadiums. Using the Cheapest Insertion heuristic, they determined their itinerary.

What is the total distance to be covered on this journey?

A) 4085 Km

B) 4135 Km

C) 4140 Km

D) 5815 Km

E) None of the above

Original idea by: Eduardo Bouhid

2025-287

Considering the Traveling Salesman Problem (TSP) in a complete graph where the triangular inequality holds, which of the following statements most accurately describes the fundamental difference in tour construction and performance guarantee between the Rosenkrantz-Stearns-Lewis algorithm and the Christofides algorithm?

1. Both algorithms are based on the "Farthest Insertion" heuristic, but Christofides applies additional optimization using dynamic programming to achieve a 1.5 x optimal cost guarantee, while Rosenkrantz-Stearns-Lewis does not.


2. Christofides' algorithm uses minimum perfect matching over the odd degree nodes of the minimum spanning tree (MST) to construct an Eulerian graph, achieving an approximation guarantee of 1.5 x optimal cost. In contrast, the Rosenkrantz-Stearns-Lewis algorithm duplicates all edges of the MST, resulting in a guarantee of 2 x optimal cost.


3. The Rosenkrantz-Stearns-Lewis algorithm duplicates the edges of the MST to form an Eulerian tour, and the Christofides algorithm improves on this by finding a minimum perfect match on all nodes in the graph (not just those of odd degree), but both algorithms share the same 2 x cost-optimal performance guarantee.


4. The Rosenkrantz-Stearns-Lewis algorithm uses a minimum perfect match over the odd degree nodes of the MST, achieving a 1.5 x optimal cost guarantee, while the Christofides algorithm duplicates all MST edges, achieving a 2 x optimal cost guarantee.


5. None of the above.

Original idea by: Juan Jose Rodriguez Rodriguez

2025-286

The Euclidean Traveling Salesman Problem (Euclidean TSP) is a special case of the symmetric TSP where each city corresponds to a point in \(\mathbb{R}^d\) and costs equal the Euclidean distance between points. As the Euclidean distance is symmetric and satisfies the triangle inequality, Euclidean TSP is a special case of Metric TSP, allowing approximation algorithms to be used for a solution.

Consider the Euclidean TSP on 5 cities, located in \(\mathbb{R}^2\) at

A (0, 0); B (2, 0); C (2, 1); D (0, 1); E (1, 1).

Which of the following statements is true?

1. The Nearest Neighbor heuristic starting from any node always yields a tour of cost 6.
2. Any Euclidean TSP can be solved in polynomial time using the ILP formulation.
3. The optimal tour is achieved by ABCED, costing 5.
4. The Cheapest Insertion heuristic is better than the Nearest Neighbor for any starting single-node cycle. 
5. None of the above

Original idea by: Daniel Gardin

2025-285

The graph below is an input instance for the Traveling Salesperson Problem showing the weight of each link between nodes. Considering that links not shown have infinite weight, find the correct alternative.

a) Using the Closest Neighbor heuristic, starting from node 'a' will result in the cycle a-c-d-f-e-b-a, with a total cost of 19.

b) Using the Closest Neighbor heuristic, any starting node will result in a total cost of 16.

c) Using the Cheapest Insertion heuristic, starting from the cycle a-b-c-a will result in a final cost of 16.

d) Using the Closest Neighbor heuristic, starting from node 'a' will result in the cycle a-b-e-c-d-f-a, with a total cost of 16.

e) None of the above.

 

 Original idea by: Giorgio Rossa

2025-284

Solve the Travel Salesperson Problem for the following undirected weighted graph and pick the best answer:

A) Cycle ABCDEA with weight 24

B) Cycle ABCEDA with weight 20

C) Cycle ADEBCA with weight 18

D) Cycle AEBCDA with weight 19

E) None of the above

Original idea by: Raphael Adamski

2025-283

A post office must plan a route to visit five cities (A, B, C, D, E) and return to the start. Distances (cost units) are given in the graph below. The graph satisfies the triangle inequality and is undirected. Apply the cheapest insertion heuristic (from the traveling salesperson problem), starting with triangle ABC (initial cycle: A → B → C → A). At each step, insert the vertex that yields the smallest cost increase according to the cheapest insertion heuristic. Which final cycle is obtained and what is its total cost?

A) A → C → B → D → E → A, total cost 29

B) A → B → E → D → C → A, total cost 27

C) A → B → D → C → E → A, total cost 25

D) A → D → B → E → C → A, total cost 27

E) None of the above

Original idea by: Thiago Soares Laitz

2025-282

A large, undirected network, with no self-loops or multi-links, is analyzed. It exhibits a scale-free degree distribution described by the formula \(p(k) = k^\gamma\) with an exponent \(\gamma=2.5\). Empirical measurement yields a degree correlation coefficient \(r = -0.15\). A plot of the average nearest-neighbor degree \(k_{nn}(k)\) shows relatively independency of the degree \(k\) for small \(k\), but it begins to decay for nodes with \(k > \sqrt{\langle k\rangle N}\), where \(N\) is the network size. What is the most precise classification of this network's degree correlations?

A)  The network is intrinsically disassortative;

B) The network exhibits structural disassortativity, a phenomenon affecting scale-free networks with exponent \(\gamma < 3\) and the network's nature;

C) The network is neutral, as the average nearest-neighbor degree is independent of \(k\) for most nodes and \(r\) is close to 0;

D) The network is assortative, but the measurement is skewed by the high variance of high-degree nodes;

E)  None of the above.

Original idea by: Caio Rhoden

2025-280

Consider networks generated by the following models:

• Barabási-Albert model
• Erdős-Rényi model

With regard to the degree correlations, the generated networks are, with high probability, respectively:

A. Disassortative and Disassortative

B. Disassortative and Neutral

C. Neutral and Disassortative

D. Neutral and Neutral

E. None of the above

Original idea by: Jhessica Silva

2025-279

Consider that the following network obeys the Barabási–Albert model, assess each statement from I to V regarding probabilities of receiving a link, and then mark the correct alternative. Round probability values to two decimal places.

I) Node M is the node with the highest probability of receiving a link from a new node, of 0.13.

II) Node D is the node with the second highest probability of receiving a link from a new node, of 0.10.

III) Nodes A, C, L, P, and I have the same probability of receiving a new link, of 0.02.

IV) Nodes N and E have the same probability of receiving a new link, of 0.08.

V) Nodes H and D have different probabilities of receiving a new link, of 0.08 and 0.09 respectively.

Which alternative contains the truth values of the above statements in the correct order?

A) F F T T F

B) T F T T F

C) T T F F T

D) T F T F T

E) None of the above

Original idea by: Carolina Albuquerque

2025-278

Consider a network with 4 nodes (1, 2, 3, 4) and the following 5 edges: (1, 2), (1, 3), (2, 3), (2, 4), (3, 4). What is the average nearest neighbor degree for nodes of degree \(k=3\), denoted by \(k_{nn}(3)\)?

1. 2.5
2. 3.0
3. 2.67
4. 2.33
5. None of the above

Original idea by: Gabriel Sato