2025-272

A friend of yours has published a pioneering research paper in a niche area, and it has gathered several citations from other researchers. The directed graph below shows the citation relationships among papers in this area.

Your friend is extremely happy with the results, given that his Paper A is already the most influent paper in the network, with an incoming degree of 4. Curious, with your knowledge on network science, you want to understand what the probability is of a new paper citing paper A. 

You are happy with rough approximations, so you frame this problem using a copying model for a directed network. With probability \(p = 0.4\) of linking uniformly at random to an existing paper, and probability \(1 - p\) of copying a link from a random paper, what is the probability of a new paper connecting to paper A? Round to two decimal places.

a) 0.10

b) 0.20

c) 0.21

d) 0.29

e) None of the above

Original idea by: Alexandre Petrachini

2025-271

Consider a network generated using the Barabasi-Albert model, whose sequence of node addition is A,B,C,D,E. Consider m=2 and that new nodes always connect to nodes with higher degrees. Which of the alternatives below represents a valid network in this context?

A. 

B.

C.

D.

E. None of the above

Original idea by: Jhessica Silva

2025-270

A research group is creating a new social media platform and wants to model its growth using the Barabási–Albert model. They start with a small group of well-connected users. According to the principles of this model, which of the following strategies will most likely lead to the formation of a scale-free network, characteristic of real-world social platforms?

A) Each new user connects to existing users at random, with equal probability, regardless of how many followers those users already have.

B) Each new user connects to existing users with a probability proportional to their current number of followers (popular users are more likely to attract new followers).

C) Each new user connects only to the newest users who joined in the previous step, ensuring recent users stay active and visible.

D) Restrict new users to connecting only with users in their immediate geographical surroundings to create localized clusters.

E) None of the above.

Original idea by: João Medrado Gondim

2025-269

Consider a Barabási-Albert network with parameter \(m = 2\). A node was introduced at time \(t_i = 4\)>. At a later time, this node has degree \(k_i(t) = 100\). What is the expected average clustering coefficient \(\langle C \rangle\) of the network at time \(t\)?

1. \(\langle C \rangle \approx 0.030\)
2. \(\langle C \rangle \approx 0.025\)
3. \(\langle C \rangle \approx 0.010\)
4. \(\langle C \rangle \approx 0.008\)
5. None of the above

Original idea by: Yan Prada.

2025-268

Bitu is an explorer who sets out to visit the mysterious Bara-Al islands — a chain of 90 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.  Still, as in any graph, there are pairs of islands that maximize the pairwise distance between islands.  These are called extreme islands.

So, he wonders: what is the expected number of bridges he would need to cross, starting from an extreme island and traveling to the farthest one by means of a shortest path?

Note 1: \(90 \approx e^{4.5}\)
Note 2: \(4.5 \approx e^{1.5}\) 

A. 8

B. 6

C. 5

D. 3

E. None of the above

Original idea by: Rodolfo Bitu

2025-267

The contractors for the new Alphaville Barão Geraldo luxury allotment have hired the brilliant students of the MO412 class to design a high-capacity water distribution network. The project's goal is to pump water from the campus lake (Node Lago) through a series of seven interconnected retention dams (Nodes A through G) to the development site (Node Alpha).

The contract specifies that the network must be able to deliver a minimum of 30,000 liters of water per minute. The students have produced the following design, with pipe capacities also measured in thousands of liters per minute:

Analyze the following propositions regarding the network's performance and limitations.

1. Suppose that, due to budget cuts, the pipe from Dam E to Dam G must be downgraded to a capacity of 5,000 L/min. With this hypothetical change, the contractual minimum delivery of 30,000 liters/minute would still be met.
2. To improve performance, a proposal is made to upgrade the pipe from Dam A to Dam D to a capacity of 18,000 L/min. This upgrade alone is sufficient to increase the network's total maximum flow.
3. If a critical failure shuts down the pipe from the Lago to Dam A (capacity becomes 0 L/min), the contractual minimum of 30,000 L/min can still be satisfied by rerouting flow through Dam B.
4. In the original, unmodified network, the pipe connecting Dam D to Dam F must operate at its full capacity of 5,000 L/min in order to achieve the maximum network flow.

Based on your analysis, choose the correct option:

1. Only proposition I is correct.
2. Only proposition II is correct.
3. Only propositions I, III, and IV are correct.
4. Only propositions II and III are correct.
5. None of the above

Original idea by: Eduardo Bouhid

2025-266

In the study of network flows, the residual network plays a key role in maximum flow algorithms such as Ford-Fulkerson, Edmonds–Karp, and Dinitz. Which of the following statements best describes the residual network and its importance?

1. The residual network contains only the edges from the original graph with unchanged capacities, and it is used to verify whether the minimum cut has been reached.
2. The residual network augments the original graph by duplicating every edge, regardless of the current flow, in order to balance the inflow and outflow of intermediate nodes.
3. The residual network includes forward and backward edges that represent the remaining available capacity and the possibility of canceling part of the existing flow, enabling the search for augmenting paths.
4. The residual network is constructed only once at the beginning of the algorithm and remains fixed throughout the process, guaranteeing polynomial complexity.
5. None of the above.

Original idea by: Pedro Pereira