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 idea by: Filipe Maciel Roberto

2022-098

Which of the following statements is true, regarding the scale-free property?

1. The scale-free property depends on the formalism used.
2. Nodes with widely different degrees cannot coexist in a network that has the scale-free property.
3. The exponent value γ = 3 is called a critical point, as it marks a separation between divergent and convergent second moments of the degree distribution.
4. A log-log plot of the scale-free property results in an exponential graph.
5. None of the above.

Original idea by: Diogo Souza

2022-097

Consider scale-free networks with 50000 nodes and \( k_{max} = 50 \).  When \( k_{min} \) is changed from 1 to 3, what is the percent increase on the exponent \( \gamma \)?  Round your answer to the nearest 1% multiple.

1. 7%
2. 29%
3. 47%
4. 86%
5. None of the above

Original idea by: Athyrson M. Ribeiro