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):
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
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
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 area 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
In a population of size \(, 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) 1.100
E) None of the above
Original idea: Yan Prada
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?
Consider the network below, where each edge is labeled with its edge betweenness centrality.
Using only this two-community partition, what is the modularity of this division? Round your answer to two decimal places.
Original idea by: Luiza Barguil
Given the following graph and the respective dendrogram, mark the correct alternative.
Original idea by: Giorgio Rossa
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?
Original idea by: Aline Azevedo
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 :
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.
Consider a complex network subject to random failures and targeted attacks. Which of the following statements best characterizes network robustness?
Original idea by: Yan Prada Moro
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
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.
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?
Original idea by: Juan Jose Rodriguez Rodriguez
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?
Original idea by: Daniel Gardin
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.
e) None of the above.
Original idea by: Giorgio Rossa
Solve the Travel Salesperson Problem for the following undirected weighted graph and pick the best answer:
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
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: Caio Rhoden
Classify the following statements as true or false, regarding degree correlation properties in networks:
I: For Erd\H{o}s-Rényi, assortative networks, the transition to a giant component takes longer, as hubs preferentially connect to each other.
II: For a disassortative network, the degree correlation function knn (k) increases with k.
III: Structural disassortativity is a phenomenon observed in scale-free networks where γ < 3, which arises because the network lacks a sufficient number of links to connect the large hubs in a neutral way.
IV: Assortative, random networks have a shorter average path length than random neutral networks, but also a larger network diameter.
Now choose the alternative that agrees with the classifications of statements I to IV, in this order:
A) T-F-T-T
B) T-F-F-F
C) F-F-T-T
D) T-F-F-T
E) None of the above
Original idea by: Alexandre Petrachini
Consider networks generated by the following models:
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
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.
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)\)?
Original ideia by: Gabriel Sato
Consider the following well-known pathogens and the following time evolution graph of the fraction of infected individuals using the Suscept...
