2022-186

Applying a divisive algorithm on the network below, we obtain the following dendrogram:

Network 

Dendrogram

Looking at the dendrogram, we establish two cuts creating community partitions. Which partition yields better communities and why? (Values are rounded to 2 decimal places).

1. A, because its modularity is equal to 0.36
2. A, because its modularity is equal to 0.45
3. B, because its modularity is equal to 0.36
4. B, because its modularity is equal to 0.45
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

2022-185

The generalized modularity \( M \) of a network with \( L \) links partitioned into \( n_c \) communities can be calculated as:

$$M = \sum_{c=1}^{n_c}\left[\frac{L_c}{L}-\left(\frac{k_c}{2L}\right)^2\right]$$

where \( L_c \) is the total number of links within the community \( C_c \) and \( k_c \) is the total degree of the nodes in this community. Consider the following statements about \( M \):

1. Higher values of \( M \) correspond to better community structures.
2. \( M = 0 \) when the entire network is taken as a single community.
3. \( M \) cannot be negative.
4. \( M \) cannot exceed one.

What is correct to assert:

1. Only I is true
2. I, II, and III are true
3. I, II, and IV are true
4. I and II are true, III and IV are false
5. None of the above

Original idea by: Marcelo Silva

2022-184

 

Given the graph below, where each color represents a different partition, calculate the modularity value. Round it up to two decimals places.

 

 

1. 0.12
2. 0.26
3. 0.37
4. 0.41
5. None of the above.

Original idea by: André Nóbrega

2022-183

Experiments with a random network revealed that its giant component vanishes after random removal of about 70% of its nodes. In this case, what was the average degree of the network?

A. 2.56

B. 4.52

C. 1.98

D. 3.33

E. None of the above

Original idea by: Marcelo Silva

2022-182

Which of the following statements about degree correlations are true:

I. In assortative networks, nodes with small degree tend to connect with other nodes with small degree.

II. In a disassortative network, the probability of connecting a node with degree \( k \) to another of degree \( k' \) is \( k k' / (2L) \).

III. Perfectly assortative networks can only exist with the presence of cycles.

IV. The degree correlation coefficient is negative for assortative networks.

A. Only I

B. I and II

C. I and III

D. III and IV

E. None of the above
    

Original idea by: Victor Sotelo

2022-181

The Kosaraju-Sharir algorithm is an algorithm used to find strongly connected components in a graph.

Applying the algorithm on the graph given above, how many strongly connected components do we find, and what is the size of the biggest component, and the size of the smallest? (respectively)

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

  Original idea by: Pedro Henrique Di Francia Rosso

2022-180

Consider the directed graph given below and select the correct alternative that best decompose the graph into strongly connected components.

A.{P, Q, R, S}, {T}, {U}, {V}

B.{P, Q, S, T, V}, {R}, {U}

C.{P, Q, R, S, T, U, V}

D.{P, Q, R, S, T, V}, {U}

E. None of the above

Original idea by: Muhammad Idrees

2022-179

Consider the following statements about strongly connected components (SCC):

1. The graph \(G'\), obtained by contracting the strongly connected components of \(G\), is necessarily acyclic.
   
2. The strongly connected components of a graph \(G\) and its transpose \(G^T\) are the same.
   
3. It is possible to use the DFS algorithm to find the strongly connected components of a graph. More specifically, two DFS executions must be performed, and the first one is used to find the order of seeds for the second execution.
   

The true statements are:

1. I, II and III
   
2. II and III
   
3. II
   
4. III
   
5. None of the above.

Original idea by: André Nóbrega