2022-136

Based on the Failure Propagation Model used to describe cascading failures, analyze this network. Consider that each node has the same breakdown threshold \( \varphi = 0.4 \).

1. If a failure starts at node 0, it will not propagate to any other nodes.
2. A failure at node 9 will cascade to nodes 10, 11, and 12.
3. If all nodes have their breakdown threshold changed to \( \varphi = 0.3 \), a failure in any of the network nodes will trigger an avalanche.

Now select the option that contains exactly the true statements:

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

Original idea by: Márcia Jacobina

2022-135

Consider the following graph. What can be said about its clustering coefficient?

A. The graph has 3 nodes with clustering coefficient equal to 1/3.

B. The average clustering coefficient of the graph is equal to 4/3.
C. There are no nodes with clustering coefficient equal to 1.
D. The global clustering coefficient of the graph is equal to 3/8.
E. None of the above.

Original idea by: Diogo Souza

2022-134

Not all networks display the expected behavior of hubs linking to other hubs. They do so on some networks, but not on others. These patterns manifest a common feature, degree correlations, which allow us to detect the presence or lack of correlations in a real network. Analyze the degree correlation function knn(k) which expresses the average degree of the neighbors of all degree-k-nodes, and, then, classify the sentences below as true or false.

                                                     

 Inspired by http://networksciencebook.com/chapter/7measuring-degree; purple: knn(k), horizontal line: prediction, green: fit to knn(k)=akμ

1) In a disassortative network hubs prefer to link to high-degree nodes and the best representation for this network is Image A.

2) In a neutral network, there is a lack of degree correlations. Plotting knn(k) in function of k results in a horizontal line as shown in Image C, which demonstrates that the average degree of a node's neighbors is independent of the node's degree k.

3) Image A is a good representation of an assortative network where hubs tend to connect to other hubs. Thus, the higher the degree k of a node, the higher the average degree of its nearest neighbors.

4) In a disassortative network, as shown in Image B, the degree correlation function decreases with k, indicating hubs prefer to link to low-degree nodes.

Now select the option that contains exactly the true statements:

    A. Only 1 and 3

    B. Only 1, 2 and 3

    C. Only 2, 3 and 4

    D. All the statements

    E. None of the above

Original idea by: Márcia Jacobina

2022-133

Regarding Strongly Connected Components (SCC), which of the following assertions are true:

i) Any SCC with two or more nodes has a cycle

ii) SCC's are only possible in undirected graphs

iii) Kosaraju-Sharir's algorithm for finding SCC's runs in linear time

1. Only i) and iii) are true
2. Only ii) and iii) are true
3. Only i) is true
4. Only ii) is true
5. None of the above

Original idea by: Júlio César Martins

2022-132

Scale-free networks are robust to random node failures but vulnerable to attacks. Consider that the telecom network in the country below is under attack, and the attacker knows the topology.

What region is the most likely to entirely lose communication with the rest of the country:

1. South
2. Northeast
3. Southeast
4. North
5. None of the above

Original idea by: Iury Cleveston

2022-131

Given the network below, extracted from "Networks by Mark Newman", which of the following sequences of node removals represents an attack against largest hubs that break s the network into three components?

 

Options:

1. n5, n8, n9
2. n13, n4, n8
   
3. n13, n9, n5
   
4. n9, n13, n5
   
5. None of the above.

Original idea by: Filipe Maciel