---- > [!theorem] Theorem. ([[degree distribution of the model of Barabasi and Albert]]) > [[The model of Barabasi and Albert for growing undirected graphs|The model of Barabasi and Albert for growing undirected graphs]] is a special case of [[Price's DAG growing model]] when the [[hyperparameter]] $a=c$ is set. In the [[function limit]] of large [[network]] size, it consequently grows a [[network|network]] whose [[degree distribution]] has a [[power law]] tail with exponent $\alpha=3$: $p_{k} \sim k^{-3} \text{ as }k \to \infty .$ > > [!proof]- Proof. ([[degree distribution of the model of Barabasi and Albert]]) > The model generates a [[power law]] [[degree distribution]] because it is equivalent to a special case of [[Price's DAG growing model]] [[in-degree distribution of Price's model is a power law|which yields a power law in-degree distribution]] when we let $a=c$. To see this, suppose we give each edge in our [[network]] a direction, running from the node from which the edge was added to the previously existing node to which it connects. We have converted our [[network]] into a [[network|directed network]] in which each node $i$ has out-degree $c$ and in-degree $q_{i}$ for some $q_{i}$. Then the total degree of the node, in an undirected sense, is $k_{i}=q_{i} + c$. But given that the [[probability]] of an edge attaching to a node is proportional to $k_{i}$, it is proportional to $q_{i}$ as well — which is just [[Price's DAG growing model|Price's model]] when we choose $a=c$. Thus the distribution of in-degrees in our directed [[network]] is the same as for [[Price's DAG growing model]] with $a=c$, which by [[in-degree distribution of Price's model is a power law]] we find to be $p_{q} = \frac{B(q+c, 3)}{B(c,2)},$ > where $B$ is the [[beta function]]. To get the distribution of total (i.e., undirected) [[degree]] we replace $q+c$ with $k$ and find $p_{k}=\begin{cases} > \frac{B(k,3)}{B(c,2)} & \text{for }k \geq c \\ > 0 & \text{for } k < c. > \end{cases}$ Simplifying further using the definition of the [[beta function]] yields $p_{k}=\frac{\Gamma(k)}{\Gamma(k+3)} \frac{\Gamma(c+2)}{\Gamma(c)} \frac{\Gamma(3)}{\Gamma(2)}= \frac{2c(c+1)}{k(k+1)(k+2)},$ > for $k \geq c$, where we have used the property $\frac{\Gamma(x+n)}{\Gamma(x)}=(x+n-1)(x+n-2)\cdots x$ of the [[gamma function]]. In the [[function limit]] of large $k$ this becomes $p_{k} \sim k^{-3}$ which means we have a [[degree distribution]] with a power-law tail and exponent $\alpha=3$. > > > ---- #### ----- #### References > [!backlink] > ```dataview TABLE rows.file.link as "Further Reading" FROM [[]] FLATTEN file.tags GROUP BY file.tags as Tag > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```