Blog de Grafos do Daniel

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

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...