Scale-free Networks

The scale-free regime of a network is defined for graphs whose degree distribution is $p(k) \propto k^{-\gamma}$ for $\gamma \in (2, 3)$. Which of the following properties about the resulting networks is true as $\gamma$ approaches $2$ from the right?

a) They become indistinguishable from an Erdős–Rényi random network, because their second moment, $\langle k^2 \rangle$, decreases.

b) Vertices with extremely large degrees become more common.

c) The expected distance between nodes only increases.

d) The tail of $p(k)$ becomes heavy-tailed, indicating a decrease in the average degree, $\langle k \rangle$.

e) None of the above


Original idea: Daniel Gardin

Comments

  1. Joao MeidanisSeptember 21, 2025 at 4:05 PM

    Achei difícil esta questão. A alternativa (A) parece falsa, mas para as demais, achei que ficou dúbio. Acho que muita coisa depende de como se modifica o tamanho da rede.

    ReplyDelete

Post a Comment

Popular posts from this blog

Sierpiński Gasket Graphs

Image
The Sierpiński gasket graphs form one of the most studied examples of self-similar structures in graph theory [1]. They provide a discrete analogue of the classical Sierpiński triangle fractal, preserving both its recursive construction and its combinatorial richness. The sequence begins with the complete graph on three vertices, $S_{1}$, and at each subsequent step, $S_{n+1}$ is obtained from $S_{n}$ by subdividing every triangular face. New vertices are placed at the midpoints of its edges, and these are joined to form a smaller triangle inside. Repeating this process yields a hierarchy of graphs whose geometry captures the recursive pattern of the underlying fractal.   Figure 1. The first 4  Sierpiński gasket graphs. Taken from  Bunimovich et. al (2016) [2] Given this sequence, what is the Global Clustering coefficient of $S_n$, for $n\geq2$ and its limit when $n \to \infty$? $$\textbf{a)}\quad \frac{3^n}{3^{n}-2}, \quad 1$$ $$\textbf{b)}\quad \frac{4\cdot 3^...
Read more

Random Isolated Vertex

Consider a graph consisting of $n$ vertices in which each possible edge is included with probability $p = p(n)$ (a probability that explicitly depends on the size of the graph). This construction provides a probabilistic framework, as described by Gilbert [1], to study typical properties of graphs as $n$ increases. Denote this graph by $G(n, p)$, and consider $p(n) = \frac{1}{\sqrt{n}}$. What is the probability of finding an isolated vertex ( i.e.,  a vertex with no neighbours) in $G(n, p)$ as $n$ increases? Hint: Consider that the probability of finding an isolated vertex in a random graph with $n$ vertices is $P_\mathrm{isolated}(n) = (1-p)^{n-1}$. a) It increases with $n$, approaching $P_\mathrm{isolated}(n) = 1 - \frac{1}{n}$, converging to 1. b)  It increases with $n$, approaching $P_\mathrm{isolated}(n) = 1 - \frac{1}{\sqrt{n}}$, converging to 1. c) It decreases with $n$, approaching $P_\mathrm{isolated}(n) = \frac{\log n}{n}$, converging to 0. d)  It decr...
Read more