Scale-Free Networks

A group of explorers is mapping the connections between caves on a mysterious island. Each cave is a node, and the tunnels connecting them are edges. Studies indicate that the cave network follows a scale-free distribution with N = 20000 caves. The minimum number of tunnels from a cave (kmin) is 3, and the network follows a power-law with exponent \(\gamma = 2.6\).

The most valuable treasure is hidden in the most connected cave ("biggest hub"). The explorers want to estimate how many tunnels this cave has to plan their expedition. Based on this information, which statement is correct?

A) The biggest hub has approximately \(k_{\max} \approx 3000\) tunnels. Since the network follows the small-world property, explorers will need many steps to reach most caves, as the average distance between two caves grows as \(\ln N\).

B) The biggest hub has about \(k_{\max} \approx 500\) tunnels, and the average distance between two caves grows as \(\ln \ln N\), showing the ultra-small property, so the treasure can be reached quickly from almost any cave.

C) The average distance between caves does not depend on \(\gamma\), and hubs do not influence the journey — the network behaves like a random network.

D) The mean degree \(\langle k \rangle\) diverges, but the variance \(\langle k^2 \rangle\) is finite, making the most connected caves irrelevant.

E) None of the above

Original idea by: Aline Azevedo

Comments

  1. Joao MeidanisSeptember 21, 2025 at 11:00 AM

    Tem potencial, mas não chei o k_max = 1463 que calculei. Algumas das alternativas acabaram sendo muito obviamente erradas, como (c) e (d), aumentando a facilidade da questão.

    ReplyDelete

Post a Comment

Popular posts from this blog

Dogs, Friends, and Paths at Praça da Paz

Image
Six dogs are happily playing at Praça da Paz, Barão Geraldo . Each dog is a node , and each friendship (two dogs playing together) is an edge .   Considering the above  undirected network of dog friendships, which of the following statements is correct ? A)  The clustering coefficient of node Violeta is 0 B)  Ginger is very social and her clustering coefficient is 0.5, participating in more than one triangle C) The shortest path from Mindú to Violeta has length 4 D)  The average degree of the nodes ⟨k⟩  is 2.375, and the degree distribution shows that three nodes have degree 1 E)   None of the above   Original idea by: Aline Azevedo
Read more

Barabási–Albert Model

You are an analyst for a streaming platform called StreamWorld , which works like a social network: each movie is a node, and connections between movies represent users who watched both. StreamWorld grows following a pattern similar to the Barabási–Albert model : Each new movie connects to m = 3 existing movies. The probability of a movie receiving a new connection is proportional to the number of connections it already has (preferential attachment). At the start ( t = 0 ), there are m₀ = 5 fully connected movies. At time t = 12000 , the network has N = 12000 + m₀ movies, and three movies were released: - Movie A at t A = 100 - Movie B at t B = 1000 - Movie C at t C = 4000 Which of the following is the correct ranking of their expected degrees k i (t) from largest to smallest , what is the approximate ratio between the larges...
Read more

Random Graph - Erdős-Rényi

Consider a connected Erdős-Rényi random graph \( G(n, p) \) with \( n = 100 \) nodes and edge probability \( p = 0.1 \). The average degree is \( \langle k \rangle = 10 \). Which of the following statements is correct? The degree distribution is concentrated around the mean, the average distance scales linearly with \( n \), and the clustering coefficient is \( 0.05 \). The degree distribution is approximately Poisson, the average distance is 2, and the clustering coefficient is roughly equal to \( p \). The degree distribution is uniform, the average distance is independent of \( n \), and the clustering coefficient grows with \( n \). The degree distribution is Poisson, the average distance is 3, and the clustering coefficient is zero. None of the above Original idea by: Aline Azevedo
Read more