2022-077

Consider the following graph, that lists the requirements for subjects in a Computer Science course. Which of the alternatives represent an acceptable topological ordering?

1. ProgI → ProgII → SO → ArqComp → CompAlg → EstDados → IA → ProbEst
2. ProbEst → IA → ProgI → ArqComp → SO → ProgII → CompAlg → EstDados
3. ArqComp → SO → ProgI → ProgII → CompAlg → EstDados → ProbEst → IA
4. ProgI → ArqComp → ProgII → SO → CompAlg → EstDados → ProbEst → IA
5. None of the above.

Original idea by: Diogo Souza

2022-076

Your classmate is having trouble identifying hubs of a network. You as a good colleague decided to help her. Which of the following alternatives contains the larger hub on the network below?

1. Node E
2. Nodes A, B and C
3. Node F
4. Node D
5. None of the above

Original idea by: Victória Pedrazzoli

2022-075

What are the partitions of this bipartite graph?

1. P1={a, c, f, h, i, k}    P2={b, d, e, g, j, l}
2. P1={a, d, f, g, i, l}    P2={b, c, e, h, j, k}
3. P1={a, d, f, h, j, k}    P2={b, c, e, g, i, l}
4. P1={a, d, e, h, i, l}    P2={f, g, b, c, j, k}
5. None of the above

Original idea by: Márcia Jacobina

2022-074

Pedro and Sofia are brothers, and they argue pretty often. Their mother is a lovely and calm person, but today she is stressed out because of her work and has decided to ground them for arguing so often. She left them an exercise to solve to get out of detention. Their mother drew a graph (image below) and asked her children if the following statements about the graph are true or false: 

1. The edge between nodes BD is a bridge
2. The shortest path between the nodes E and C is 3
3. The graph diameter is 6 
4. The graph is disconnected
5. By removing the edges BD and EA the resulting graph has two connected components

Your task is to help the kids find the true alternative in the following list. Consider that the graph is undirected.

1. Only I, II, V are correct
2. Only I, III, and IV are correct
3. Only III, and V are correct
4. Only II, III, and V are correct
5. None of the above

Original idea by: Levy Chaves

2022-073

While performing a routine check on a power grid network, an employee noticed that the adjacency matrix could be rearranged into a block diagonal form, as shown in the figure below.

It is correct to affirm that the network:

1. Forms a complete graph.
2. Contains a bridge connecting two components.
3. Consists of two disconnected components.
4. Is a bipartite network.
5. None of the above.

Original idea by: Heitor Mattosinho

2022-072

In a bipartite network, we can generate a different projection for each disjoint set of nodes. Consider the following bipartite network:

The average clustering coefficient, <C>, for each projection, rounded to two decimal places, would be:

1. <C> = 0,33 for projection on set A, <C> = 0,33 for projection on set B
2. <C> = 0,47 for projection on set A, <C> = 0,25 for projection on set B
3. <C> = 0,67 for projection on set A, <C> = 0,60 for projection on set B
4. <C> = 0,33 for projection on set A, <C> = 0,60 for projection on set B
5. None of the above

Original idea by: Athyrson M. Ribeiro

2022-071

 

Cherepnalkoski and Mozetič published the community structure evaluation of retweet networks related to European Parliament (EP) members in 2016 [1]. They collected one year of data from the behavior of EP members on Twitter. For the record, Tweets are posts on Twitter and retweets are re-posts, or in other words: a retweet is a quick way to share (in a rather public way) something another person said to people that follow you. So the researchers were analyzing on a community level how EP members had behaved on Twitter by sharing posts of each other.

The so-called core retweet network (composed only by EP members) has 459 nodes, 4,441 edges, is represented in the figure below, and has the following structure: 

1. Each node represents one EP member; 
2. Links represent retweets between EP members (when an EP shared something that another EP member posted on Twitter);
3. Node colors represent the political groups of the EP members;
4. Node sizes are proportional to the total number of times that an EP member has been retweeted by other members;
5. Link colors represented the EP member that has been retweeted by the respective colleague.

The core retweet network of the EP members [1]

Evaluate the following statements:

1. This is an undirected network;
2. This is not a weighted network;
3. The graph formed by this network is a complete graph;
4. The average degree is very close to 458.

Select the best answer:

1. 1 - True, 2 - False, 3 - True, 4 - False
2. 1 - False, 2 - True, 3 - False, 4 - True
3. 1 - False, 2 - False, 3 - True, 4 - True
4. 1 - False, 2 - True, 3 - False, 4 - False
5. None of the above

Reference

[1] Cherepnalkoski, D., Mozetič, I. Retweet networks of the European Parliament: evaluation of the community structure. Appl Netw Sci 1, 2 (2016). https://doi.org/10.1007/s41109-016-0001-4

Original idea by: André Portela