2023-222

Consider a scale-free network with average degree 2.9, second moment of the degree distribution 32.3, and degree exponent 2.89. It is correct to state that:

1. The preferential attachment assumption is valid, with a probability Π(k) that a link of a new node links to another node of degree k proportional to the square of k.
2. This network is perfectly assortative, with a degree correlation coefficient equal to 1.
3. This network displays enhanced robustness, since its breakdown threshold is greater than the breakdown threshold of a random network with the same average degree.
4. This network is in a random network regime, since the degree exponent is close to 3.
5. None of the above.

Original idea by: Vitoria D. M. Pinho

2023-221

Which of the following statements correctly describes the robustness of scale-free networks?

1. Scale-free networks are highly robust against random node removal but vulnerable to targeted attacks.
2. Scale-free networks are equally robust against random node removal and targeted attacks.
3. Scale-free networks are highly robust against targeted attacks but vulnerable to random node removal.
4. Scale-free networks are vulnerable to both random node removal and targeted attacks.
5. None of the above.

Original idea by: Arthur Hendricks.

2023-220

Consider a simple scale-free network with \( k_\min = 1\), \( \langle k \rangle = 10 \), and \( N \) nodes. For which values of \( N \) we expect to observe the structural cutoff phenomenon? Tip: establish a relationship between \( k_S(N) \)  and \( k_\max \).

1. \( N > 2500 \)
2. \( N < 2500 \)
3. \( N > 1000 \)
4. \( N < 1000 \)
5. None of the above

Original idea by: Christian Konishi

2023-219

The degree correlation function depicted in the following figure (shown in purple) is derived from a Bianconi-Barabási model with parameters N = 10,000, m = 3, and a uniform fitness distribution:

(Extracted from Albert-László Barabási book "Network Science")

Please choose the accurate statement regarding this figure:

1. This network exhibits a neutral nature due to the presence of structural cutoff phenomena.
2. The network cannot be classified as disassortative since randomizing the network while maintaining the same degree distribution produces a similar behavior, as the orange dots (Randomized R-S).
3. While this network displays some disassortativity, it is not pronounced primarily due to structural cutoff.
4. This network does not exhibit any structural cutoff phenomena. 
5. none of above

Original idea by: Anderson Nogueira Cotrim

2023-218

The network below, shown at t=0 with each node and its respective fitness η, follows the Bianconi-Barabasi model and grows by adding a new node at each subsequent time unit, accompanied by two new links (m=2). All new nodes have a fitness of 1. Which node is expected to have the most links at t=1 and at t going to infinity?

1. node 1 at t=1; node 3 at t=infinity.
2. node 2 at t=1; node 3 at t=infinity.
3. node 2 at t=1; node 5 at t=infinity.
4. node 3 at t=1; node 5 at t=infinity.
5. None of the above

Original idea by: Thaysa Bello

2023-217

Taking into consideration the directed graph below, in the context of Strongly Connected Components (SSCs), choose the most appropriate alternative:

a) This graph has an even number of SCCs and not all the components' numbers of nodes are prime numbers.

b) The largest SCC (with the greatest number of nodes) is precisely the first SCC found by Kosaraju-Sharir's algorithm.

c) More than half of the SCCs in the graph have 3 nodes.

d) This graph has 5 SCCs, the smallest of which is formed by 'k' alone.

e) None of the above. 

Original idea by: João Marcos

2023-215

Given the following directed graph, if we executed Kosaraju-Sharir’s algorithm to detect its strongly connected components (SCCs) starting at node A and assuming the adjacency lists are sorted in descending order (Z to A), what would the SCCs be and in which order they would be returned?

1. 2 SCCs returned: BDCA first and then FGH;
2. 2 SCCs returned: FGH first and then BDCA;
3. 4 SCCs returned: H first, then G, F, and BDCA;
4. 4 SCCs returned: BDCA first, then F, G, and H;
5. None of the above.

Original idea by: Fillipi Valadares

2023-214

Consider the following directed graph:

In order to apply the Kosaraju-Sharir algorithm, a DFS was performed and the following start and end times were computed:

What will be the first strongly connected component detected in this graph?

1. {7}.
2. {4, 5, 6}.
3. {2, 3, 4}.
4. {1, 2, 3}.
5. None of the above

Original idea by: Christian Konishi

2023-213

 Considering the following directed graph:

I. Since this is a strongly connected graph, it does not have a topological sort.

II. We can easily find a topological sort for this graph using the reverse order of finishing times from DFS.  

III. By applying Kosaraju-Sharir’s algorithm to this graph, we will obtain a set of strongly connected components in the order [{C}, {D, E, F}, {A}, {B}].

IV. Kosaraju-Sharir’s algorithm can find the topological sort of any directed graph even if it has cycles, in this case treating each strongly connected component as a single node. In this particular graph, the last node in the topological sort could be either A or B.

What statements from the options above are correct?

1. I and III
2. II and IV
3. III
4. III and IV
5. none of above

Original idea by: Anderson Nogueira Cotrim