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

2025-270

A research group is creating a new social media platform and wants to model its growth using the Barabási–Albert model. They start with a small group of well-connected users. According to the principles of this model, which of the following strategies will most likely lead to the formation of a scale-free network, characteristic of real-world social platforms?

A) Each new user connects to existing users at random, with equal probability, regardless of how many followers those users already have.

B) Each new user connects to existing users with a probability proportional to their current number of followers (popular users are more likely to attract new followers).

C) Each new user connects only to the newest users who joined in the previous step, ensuring recent users stay active and visible.

D) Restrict new users to connecting only with users in their immediate geographical surroundings to create localized clusters.

E) None of the above.

Original idea by: João Medrado Gondim

2025-269

Consider a Barabási-Albert network with parameter \(m = 2\). A node was introduced at time \(t_i = 4\)>. At a later time, this node has degree \(k_i(t) = 100\). What is the expected average clustering coefficient \(\langle C \rangle\) of the network at time \(t\)?

1. \(\langle C \rangle \approx 0.030\)
2. \(\langle C \rangle \approx 0.025\)
3. \(\langle C \rangle \approx 0.010\)
4. \(\langle C \rangle \approx 0.008\)
5. None of the above

Original idea by: Yan Prada.

2025-268

Bitu is an explorer who sets out to visit the mysterious Bara-Al islands — a chain of 90 islands. Each island is connected by a few bridges. Whenever a new island was settled, its bridges were built with a preference for linking to islands that already had many connections. In this way, the Bara-Al islands grew according to Barabási–Albert Model of networks.  Still, as in any graph, there are pairs of islands that maximize the pairwise distance between islands.  These are called extreme islands.

So, he wonders: what is the expected number of bridges he would need to cross, starting from an extreme island and traveling to the farthest one by means of a shortest path?

Note 1: \(90 \approx e^{4.5}\)
Note 2: \(4.5 \approx e^{1.5}\) 

A. 8

B. 6

C. 5

D. 3

E. None of the above

Original idea by: Rodolfo Bitu