2023-227

Consider a flow network for the company "A", which needs to deliver products from the capital to 10 cities. Three of these cities are small and don't have direct delivery routes from the capital. However, each of these small cities can receive products from the other 7 cities.

Due to a special event, City "T", one of the three small cities, requires a delivery of 650 products. The flow capacities of the network are defined as follows:

• Company "A" can send a maximum of 150 products to each city that has a direct connection from the capital.
• Two of the 7 cities that can receive products directly from the capital can forward a maximum of 200 products each to City "T".
• The remaining 5 of the 7 cities can forward a maximum of 50 products each to City "T".
• The other two small cities don't require any products.

Given these conditions, how many of the 650 requested products can be delivered to City "T" for the event?

1. 500
2. 550
3. 600
4. 650
5. None of the above

Original idea by: Thaysa Bello

2023-226

 

Imagine a Cayley Tree, constructed starting from a central node of degree \( k \). Each node at distance \( d \) from the central node has degree \( k \), until the nodes reachable at distance \( P \) that have degree one, as shown in figure above. Consider \( k+1 \) communities, with communities corresponding to the subtrees rooted at the children of the central node, and the central node by itself being a community. What is the modularity of this partition if \( k=3 \) and \( P=4 \)? Round it up to three decimal places.

1. 0.523
2. 0.621
3. 0.785
4. 0.891
5. None of the above.

Original idea by: Germán Darío Buitrago Salazar

2023-225

Agglomerative hierarchical clustering can be applied to community detection in graphs. By using dendrograms, one can visualize the order in which nodes merged. This visualization enables the extraction of the underlying community organization.

Which of the presented dendrograms and respective cuts would faithfully represent the given graph and its three colored communities?

1. IV;
2. III;
3. II;
4. I;
5. None of the above.

Original idea by: Fillipi Valadares

2023-224

Consider the following network. The fuchsia nodes are all part of a weak community.

Which option presents a modification that makes this community a strong one?

1. Remove node 8 from the community.
2. Add node 9 to the community.
3. Add node 5 to the community.
4. Remove node 6 from the community.
5. None of the above

Original idea by: Christian Konishi

2023-223

Considering the following undirected graph:

I. {1, 2, 3, 4} is a clique.

II. {1, 2, 3, 4} is a strong community.

III. {5, 6, 7} is a weak community.

IV. {5, 6, 7} is a clique.

V. {4, 5, 6, 7} is a weak community.

Which statements from the options above are correct?

1. I, III and V
2. II, III and V
3. II, IV and V
4. II, III, IV and V
5. none of above

Original idea by: Anderson Nogueira Cotrim

2023-222

Consider a scale-free network with average degree 2.9, second moment of the degree distribution 32.3, and degree exponent 2.89. It is correct to state that:

1. The preferential attachment assumption is valid, with a probability Π(k) that a link of a new node links to another node of degree k proportional to the square of k.
2. This network is perfectly assortative, with a degree correlation coefficient equal to 1.
3. This network displays enhanced robustness, since its breakdown threshold is greater than the breakdown threshold of a random network with the same average degree.
4. This network is in a random network regime, since the degree exponent is close to 3.
5. None of the above.

Original idea by: Vitoria D. M. Pinho

2023-221

Which of the following statements correctly describes the robustness of scale-free networks?

1. Scale-free networks are highly robust against random node removal but vulnerable to targeted attacks.
2. Scale-free networks are equally robust against random node removal and targeted attacks.
3. Scale-free networks are highly robust against targeted attacks but vulnerable to random node removal.
4. Scale-free networks are vulnerable to both random node removal and targeted attacks.
5. None of the above.

Original idea by: Arthur Hendricks.