2024-246

Given the networks below, which of the following options is most likely correct about them, where r is the degree correlation coefficient:

a) Network A is disassortative, as the hubs tend to connect with other hubs, while Network B is assortative, with hubs tending to connect to nodes of smaller degree.

b) Network A is assortative, with a positive r, and network B is disassortative, with a negative r.

c) Network A is a perfectly assortative network, where each node links only to nodes with the same degree, while network B is disassortative, with hubs preferring to link to low-degree nodes.

d) Network A is assortative with a negative r, and network B is disassortative with a positive r.

e) None of the above

 Original idea: Matheus C. Lindino

2023-216

Which of the following statements is true about the Kosaraju-Sharir's algorithm?

A) It is used to find the shortest path between two nodes in a graph.

B) It is a greedy algorithm that always finds the optimal solution.

C) It is used to determining the strongly connected components in a directed graph.

D) It is used to computing the minimum spanning tree of a graph

E) None of the above.

Original idea by: Arthur Hendricks.

2025-275

The following image illustrates the Push-Relabel algorithm partially executed on a flow graph, with the respective residual graph displayed on the right. The algorithm repeatedly performs relabel and push operations on a node, trying to push as much flow as possible to neighbors in alphabetical order. A FIFO queue of active nodes (the ones that have excess flow) is used to select the next node to act upon, initialized with the source only.  If a node cannot push all its excess flow, it returns to the FIFO queue.

Based on the process illustrated, mark the correct alternative of the next step in the algorithm:

a) Relabeling of 'a', setting 'h' to 8, and returning the excess flow to 'S' using Push.

b) Relabeling of 'c', setting 'h' to 2, and returning the excess flow to 'b' using Push.

c) Relabeling of 'c', setting 'h' to 8, and returning the excess flow to 'S' using Push.

d) Relabeling of 'e', setting 'h' to 1, and pushing the excess flow to 't'.

e) None of the above 

 

 Original idea  by: Giorgio Rossa

2025-274

Two undirected networks, Network A and Network B, have identical degree distributions \(p_k\)​ but distinct degree correlation patterns.

Regarding the average nearest-neighbor degree function $k_{nn}(k)$ and the degree correlation matrix $e_{jk}$ of each network, we have:

• In Network A, $k_{nn}(k)$ is approximately constant across $k$, and $e_{jk}$ roughly factorizes into $q_j{q}_k$.

• In Network B, $k_{nn}(k)$ decreases systematically with $k$, and the $e_{jk}$ matrix shows high values in the upper-left and lower-right corners rather than along the diagonal.

Consider the following statements:

I. Network A is neutral, while Network B is disassortative.
II. Network B is expected to have a negative Newman correlation coefficient $r$.
III. If a new Network C were highly assortative, its $e_{jk}$ would concentrate along the diagonal, and $k_{nn}(k)$ would increase with $k$.
IV. Because Networks A and B share the same $p_k$, their correlation coefficient $r$ must also be the same.

Which of the statements above are correct?

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

Original idea by: Mateus de Padua Vicente

2025-273

Considering an undirected network with no degree correlation. Let \(e_{jk}\) be the probability to find a node with degree \(j\) and degree \(k\) at the two ends of a randomly selected link and let \(q_k\) be the probability to have a degree \(k\) node at the end of a randomly selected link. You are given the average degree:

\(\langle k\rangle = 10\)

and the following degree-distribution probability masses (all other \(p_k\) can be anything consistent and are not needed):

\(p_{20} = 0.04\)

\(p_{30} = 0.03\)

\(p_{50} = 0.02\)

Using only the information above, compute the 3×3 submatrix of \(e_{jk}\) for degrees 20, 30, and 50. Which option matches this block? Consider the theoretical \(e_{jk}\) for the network with no degree correlation and that the matrix rows and columns correspond to degrees 20, 30, and 50 in that order.

A) \(\left[ \begin{array}{ccc} 0.0064 & 0.0072 & 0.0080\\ 0.0072 & 0.0081 & 0.0090\\ 0.0080 & 0.0090 & 0.0100\end{array}\right]\)

B) \(\left[ \begin{array}{ccc} 0.0032 & 0.0045 & 0.0060\\ 0.0045 & 0.0075 & 0.0080\\ 0.0060 & 0.0080 & 0.0090\end{array}\right]\)

C) \(\left[ \begin{array}{ccc} 0.0080 & 0.0090 & 0.0100\\ 0.0090 & 0.0100 & 0.0110\\ 0.0100 & 0.0110 & 0.0120\end{array}\right]\)

D) \(\left[ \begin{array}{ccc} 0.0064 & 0.0080 & 0.0096\\ 0.0080 & 0.0100 & 0.0120\\ 0.0096 & 0.0120 & 0.0144\end{array}\right]\)

E) None of the above.

Original idea by: Thiago Soares Laitz

2025-272

A friend of yours has published a pioneering research paper in a niche area, and it has gathered several citations from other researchers. The directed graph below shows the citation relationships among papers in this area.

Your friend is extremely happy with the results, given that his Paper A is already the most influent paper in the network, with an incoming degree of 4. Curious, with your knowledge on network science, you want to understand what the probability is of a new paper citing paper A. 

You are happy with rough approximations, so you frame this problem using a copying model for a directed network. With probability \(p = 0.4\) of linking uniformly at random to an existing paper, and probability \(1 - p\) of copying a link from a random paper, what is the probability of a new paper connecting to paper A? Round to two decimal places.

a) 0.10

b) 0.20

c) 0.21

d) 0.29

e) None of the above

Original idea by: Alexandre Petrachini

2025-271

Consider a network generated using the Barabasi-Albert model, whose sequence of node addition is A,B,C,D,E. Consider m=2 and that new nodes always connect to nodes with higher degrees. Which of the alternatives below represents a valid network in this context?

A. 

B.

C.

D.

E. None of the above

Original idea by: Jhessica Silva