Quiz Question – Network Flow

2022-013

Consider the graph below and the flow from 1 to 10, where the capacity value is defined in each link.

Select the correct alternative with the maximum flow of the network and the possible flow values from node 1 to nodes 2, 3, and 4.

$$

1. The maximum flow of the network is 19 and the flow values from node 1 are 8, 5, and 9.
2. The maximum flow of the network is 18 and the flow values from node 1 are 7, 5, and 6.
3. The maximum flow of the network is 20 and the flow values from node 1 are 7, 5, and 8.
4. The maximum flow of the network is 19 and the flow values from node 1 are 7, 5, and 7.
5. None of the above.

Original idea by: Rubens de Castro Pereira

Quiz Question – Communities

2022-012

$$

To uncover the community structure of networks, we can use hierarchical clustering algorithms, and dendrograms help us to extract the underlying community organization. Analyze the figure below, observing the colored lines (A, B, and C) that cut the dendrogram to define communities.

Select the correct alternative:

$$

1. Line A (red) produces three communities: (c1): 6, 9, 13; (c2): 1, 8, 3, 14, 7, 2, 11, 15; (c3): 5, 16, 10, 4, 12, 17. 
2. Line B (green) produces six communities: (c1): 6, 9, 13; (c2): 1, 8; (c3):  3, 14, 7; (c4): 2, 11, 15; (c5): 5, 16, 10; (c6): 4, 12, 17.
3. Line C (brown) produces eleven communities: (c1): 6, 9, 13; (c2): 1; (c3): 8; (c4): 3; (c5): 14; (c6): 7; (c7): 2; (c8): 11; (c9): 15; (c10): 5, 16, 10; (c11): 4, 12, 17.
4. All statements are correct.
5. None of the above.

Original idea by: Rubens de Castro Pereira

Quiz Question – Network Robustness

 2022-011

 

Related to the Percolation Theory and Cascading Failures, analyze the statements below: 

1. Percolation theory shows that the percolating cluster occurs when it is possible to observe a phase transition from many small clusters to a percolating cluster that percolates the whole lattice.

2. The branching model is one of the cascading failures where the node whose initial failure triggers the avalanche of the tree's root and its branches are the nodes whose failure was triggered by this initial failure.

3. The failure propagation model is frequently used to describe cascading failures in networks where a healthy node i changes its state if a φ fraction of its neighbors have failed.

4. The failure propagation models predict the existence of a critical state in which the avalanche sizes follow a power law, and the avalanche exponent α is uniquely determined by the degree exponent of the network on which the avalanche propagates.

Select the correct alternative:

$$

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

Original idea by: Rubens de Castro Pereira

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

Quiz Question - Calculus and Differential Equations

$$

2022-007

The Fermat Teorem defines that if f had a local maximum or minimum in c, and if f'(c) exists, then f'(c) = 0. A critical number of the function f is a number c in the domain of f where f'(c) = 0 or f'(c) does not exist.

Choose the statement that presents the critical numbers of \(f(x)=x^{3/5}(4-x)\).

$$

1. 0 and \({2/3}\)
2. \({2/3}\) and \({4/3}\) 
3. \({4/3}\) and \({3/2}\)
4. 0 and \({3/2}\)
5. None of the above.

Original idea by: Rubens de Castro Pereira