Quiz Question – Strongly Connected Components (SCC) – Kosaraju-Sharir’s algorithm

2022-010

Discovering the strongly connected components in a graph is an important task in many applications for real problems. Kosaraju-Sharir’s algorithm is one of the algorithms that produce these important components on graphs and uses the DFS (depth-first search) algorithm in some of its phases.

Consider the figures below, where Figure (a) is the original directed graph, and Figure (b) is the same graph in reverse order.

Using the Kosaraju-Sharir’s algorithm, analyze the statements about the Strongly Connected Components (SCC) extracted from the graph:

1. There are only the three SCC: 7,8 – 11,12,9,10 – 0,5,4,2,3

2. There are only the three SCC: 6,11,12,9,10 – 0,1,5,4,2,3 – 7,8

3. Single node is always a SCC, and in the graph, they are the nodes 1 and 6

4. There are five SCC: 1 – 7,8 – 11,12,9,10 – 6 – 0,5,4,2,3

Select the correct alternative:

$$

1. Only statements 1, 3, 4 are correct.
2. Only statement 3 is correct.
3. Only statements 2, 3, and 4 are correct.
4. Only statements 3 and 4 are correct.
5. None of the above.

Original idea by: Rubens de Castro Pereira

Quiz Question – Evolving Networks

2022-009

$$

In many real networks, node deletion can occur at any moment of the network lifecycle. Depending on the number of nodes and links removed, this can impact some network properties. To explore the impact of node deletion, consider a Barabási-Albert model where in each time step, we add a new node with m links, and with rate r, we remove a node. 

Analyze the following statements about node deletion:

1. If r < 1, the number of removed nodes will be greater than the number of new nodes, and the network will be into a random network regime.
2. If r = 1, nodes arrive and are removed at the same rate, and the network has a fixed size and remains scale-free.
3. If r > 1, the number of removed nodes will be less than the number of new nodes, and the network continues to grow and remain with its scale-free properties.
4. The rate r of node deletion does not affect the network topology because the topology is independent of adding and deletion nodes.

Select the correct alternative:

$$

1. Only statements 1, 2, and 3 are correct.
2. Only statements 2, 3, and 4 are correct.
3. Only statements 1, 3, and 4 are correct.
4. Only statement 4 is correct.
5. None of the above.

Original idea by: Rubens de Castro Pereira

Quiz Question - The Barabási-Albert Model

$$

2022-008

The sequence of images below shows some steps for generating the network based on the Barabási-Albert model. Consider that starting with \(m_0\) nodes, the empty circles mark the newly added node to the network in each timestep \(t\), and the new node's number of links \(m\) is \(2\).

Analyze the following statements about the network:

1. Choosing which node will be connected uses the preferential attachment criteria.

2. After \(t\) timesteps, this model generates a network with \(N = t + m_0\) nodes.

3. The degree distribution of this network follows the Poisson distribution.

4. This network has scale-free property.

5. The diameter of this network with N nodes can be estimated by the equation \(D \sim \frac {(log N)}{ (log log N)} \).

Select the correct alternative:

$$

1. All statements are correct. 
2. Only statements 1, 2, and 3 are correct.  
3. Only statements 3, 4, and 5 are correct.
4. Only statements 1, 2, 4, and 5 are correct. 
5. None of the above.

Original idea by: Rubens de Castro Pereira