2022-118

Consider the flow from S to T in the network below. Flow and capacity (F:C) are defined for each link. 

Which alternative represents possible values of flow/capacity for the variables x, y, w, z:

1. x=3, y=4, w=2, z=5
2. x=2, y=4, w=2, z=6
3. x=3, y=5, w=2, z=4
4. x=3, y=5, w=1, z=5
5. None of the above

Original Idea by: Iury Cleveston

2022-117

The push-relabel algorithm is one of many known algorithms used to find maximum flows. Consider the following statements about the push-relabel algorithm:

1. The push–relabel algorithm is one of the most efficient maximum flow algorithms. It allows the flow to exceed the edge's flow capacity, except from the source. It pushes as much flow as possible, and in the end, it saturates all edges from the source.
2. The push-relabel algorithm first steps are: Start with initial flow as zero, and then find augmenting paths and add them to the flow. When no more augmenting paths exist, return the resulting flow.
3. The push-relabel algorithm uses a labeling function to assign heights to the nodes, determining which ones should be selected for the push operation.
4. There is an implementation of the push-relabel algorithm that is called Edmonds-Karp algorithm. This implementation uses Breadth-First Search, which reduces the time complexity of the original algorithm.
5. Another differential from the push-relabel algorithm is that it also requires the construction of the level graph of the residual network.
   

Select the option that exactly list the correct statements:

1. I, II and III are correct.
2. I, III, IV and V are correct.
3. I and IV are correct.
4. I and III are correct.
5. None of the above.

Original idea by: Heitor Mattosinho

2022-116

Considers the following characteristics of algorithms that find the maximum flow in a flow network:

1. Uses a combination of BFS and DFS;
2. Uses BFS to find the shortest augmenting path (in terms of number of edges used);
3. Finds augmenting paths in an unspecified manner;
4. Maintains a "preflow" instead of finding augmenting paths.

Which algorithms below fit these characteristics, respectively?

1. Ford-Fulkerson, Edmonds-Karp, Dinitz, Push-Relabel;
2. Dinitz, Ford-Fulkerson, Edmonds-Karp, Push-Relabel;
3. Dinitz, Edmonds-Karp, Ford-Fulkerson, Push-Relabel;
4. Push-Relabel, Edmonds-Karp, Ford-Fulkerson, Dinitz;
5. None of the above.

Original idea by: Filipe Roberto.

2022-115

Consider the following statements, regarding the Bianconi-Barabási model.

1. The preferential attachment is driven by the product of a node's fitness, η, and its degree \( k \).
2. A node with a higher fitness will increase its degree faster. 
3. When all fitnesses are equal, the Bianconi-Barabási model reduces to the Barabási-Albert model.
4. The earlier a node joins the network, the larger is its degree at any time.

Choose the best answer.

1. I - True; II - True; III - False; IV - False.
2. I - True; II - False; III - False; IV - True.
3. I - False; II - True; III - True; IV - False.
4. I - True; II - True; III - True; IV - False.
5. None of the above.

Original idea by: Diogo Souza

2022-114

Analyze the following statements and select the correct alternative.

1. The Barabási-Albert model describes a network where a new node is twice as likely to connect to a degree-four node than a degree-two node;
2. When the dynamical exponent is β=1/2 in a BA network, the first-mover advantage might emerge over time, making hubs larger because they arrived earlier. But in real networks, that is not always the case. BA is a minimum model and does not account for nodes' intrinsic properties;
3. The Barabási-Albert model predicts networks that result in rich-gets-richer dynamics which can be replicated in a real network regardless of the intrinsic properties of its nodes.

1. Statements I and III are true.
2. Statements I and II are true.
3. Statements II and III are true.
4. Only statement III is true.
5. None of the above.

Original idea by: André Portela

2022-113

 

Non-Linear Barabási-Albert Model

  Analyze the scaling regimes based on the non-linear Barabási-Albert model. To aid with this analysis, use the image below.

Image extracted from http://networksciencebook.com/chapter/5#non-linear

1. In the sublinear regime, the degrees follow the stretched exponential distribution
2. The Barabási-Albert Model corresponds to the linear regime and follows a power law distribution
3. In the superlinear regime, one can observe the formation of a hub-and-spoke network in which most nodes connect directly to a few central nodes
4. The rich-gets-richer process takes place in the linear regime where all nodes connect to super-hubs

Now select the true statements:

    A. 1, 2, and 3

    B. 2, 3, and 4

    C. 2 and 4

    D. All the statements

    E. None of the above

Original idea by: Márcia Jacobina

2022-112

The network below was generated using the Barabasi-Albert model:

Which alternative represents a possible order of node addition:

1. ECABD
2. DACBE
3. CABDE
4. BACDE
5. None of the above

Original Idea by Iury Cleveston

2022-110

Consider the following statements about the Barabási-Albert model.

1. The degree exponent is dependent of m.
2. Growth and preferential attachment are simultaneously needed for the emergence of the scale-free property.
3. When deriving the degree distribution, we assume that, at any moment, the total number of nodes equals the number of timesteps, that is, \( N(t) = t \).
4. If a new node has a choice between a degree-two and a degree-four node, it is twice as likely that it connects to the degree-four node.

Select the correct alternative.

1. Only statements I and IV are true.
2. Only statements I, II and III are true.
3. Only statements II, III and IV are true.
4. Only statements II and IV are true.
5. None of the above.

Original idea by: Diogo Souza

2022-109

Consider a non-oriented network that follows the Barabási-Albert with \( m = 3 \). After 2000 time-steps, what is the probability that a new node will link to a node with degree \( k=50 \) (round to 0.01%)?

1. around 0.83%
2. around 0.37%
3. around 0.91%
4. around 0.42%
5. None of the above

Original idea by: Athyrson Machado Ribeiro

2022-108

Analyze the graph below and choose the best answer regarding strongly connected components.

1. There are three strongly connected components
2. The subgraph with the single node 7 cannot be considered a strongly connected component because it has only one node
3. One of the strongly connected components is {3, 5, 6, 4}

Now select the true statements:

1. I and II
2. I and III
3. II and III
4. All the statements
5. None of the above

Original idea by: Márcia Jacobina

2022-107

Consider the network below:

Which edges when reversed yield a network with only 2 strongly connected components?

1. L1, L8
2. L2, L4, L8
3. L2, L3, L7
4. L3, L4, L8
5. None of the above

Original Idea by: Iury Cleveston

2022-106

Look at the network below.

Choose the alternative that correctly identifies its strongly connected components.

1. (C,D,G,H) and (A, B, E, F);
2. (A, B, C, D) and (E, F, G, H);
3. (A, B, E, F), (C, G), (D) and (H);
4. (A, E, F), (B, C, G), (D) and (H);
5. None of the above.

Original idea by: Filipe Maciel

2022-105

Identify the number of strongly connected components in the graph below:

1. 5
   
2. 4
   
3. 3
   
4. 2
   
5. None of the above

Original idea by: Felipe Crispim da Rocha Salvagnini

2022-104

Consider the following integral:

$$ \int \cos^2 x dx $$

Which of the alternatives has a correct intermediate step and the solution, using Euler's formulas below, where \( i \) represents the imaginary unit?

$$ \cos \theta = \frac{e^{\theta i} + e^{-\theta i}}{2} $$ $$ \sin \theta = \frac{e^{\theta i} - e^{-\theta i}}{2i} $$

1. $$ \frac{1}{2} \int (e^{2ix} + 2 - e^{-2ix}) dx = \frac{1}{2}(\frac{e^{2ix}}{2i} + 2x - \frac{e^{-2ix}}{2i}) + c $$
2. $$ \frac{1}{4} \int (e^{2ix} + 2 + e^{-2ix}) dx = \frac{1}{4}(\frac{e^{2ix}}{2i} + 2x - \frac{e^{-2ix}}{2i}) + c $$
3. $$ \frac{1}{4} \int (e^{2ix} + e^{-2ix}) dx = \frac{1}{4}(\frac{e^{2ix}}{2i} + \frac{e^{-2ix}}{2i}) + c $$
4. $$ \frac{1}{4} \int (e^{2x} + 2 + e^{-2x}) dx = \frac{1}{4}(\frac{e^{2x}}{2} + 2x + \frac{e^{-2x}}{2}) + c $$
5. None of the above
   

Original idea by: Diogo Souza

2022-103

Consider the following statements about strongly connected components (SCC):

1. All strongly connected components in a bipartite, directed network have an even number of nodes.
   
2. The Kosaraju-Sharir algorithm uses the BFS-algorithm two times in order to get the SCCs of a network.
3. A single node may be classified as a strongly connected component in a network.

The only statements above that are correct are:

1. I and III
2. II and III
3. I and II
4. Only III
5. None of the above

Original idea by: Athyrson M. Ribeiro

2022-102

Select the correct alternative based on the following statements:

1. A very large network in the scale-free regime should have \( \langle k^3 \rangle \) much larger than \( \langle k \rangle \).
2. A very large network in the scale-free regime should have \( \langle k^2 \rangle \) always smaller than \( \langle k \rangle \).
3. Hubs are expected on large exponentially bounded networks;
4. Hubs are expected on large networks in the scale-free regime.

1. Only I and IV are true;
2. Only II and III are true;
3. Only II and IV are false;
4. Only I and III are false;
5. None of the above

Original idea by: André Portela

2022-101

You are asked to analyze a Scale-Free network and calculate its number of nodes, however you perceived that counting every node of this network would take days. You were able to collect the following information:

• The largest hub has size 500
• The minimum degree is 1
• γ = 3

With that in hand, you are ready to estimate the number of nodes. Round your best guess to the nearest integer:

1. 500
2. 550
3. 250000
4. 302500
5. None of the above

Original idea by: Victória Pedrazzoli

2022-099

Which of the following is a characteristic of scale-free networks?

1. Their degree distribution exhibits a power-law behavior at the tail end
2. They are the only ones that contain hubs
3. All real networks are scale-free
4. Scale-free networks are very similar to random networks
5. None of the above

Original idea by: Júlio César Martins

2022-119

Starting from the node indicated as 'start', use DFS and label the nodes with their ending times. Which of the alternatives below corresponds to a possible answer?

Tip: the reverse order of finishing DFS times in a directed acyclic graph is a topological order.

1. 
   

2. 
   

3. 
   

4. 
   

5. None of the above.

Original ideia by: Filipe Maciel Roberto