On the evolution of scale-free graphs

Abstract

We study the evolution of random graphs where edges are added one by one between pairs of weighted vertices so that resulting graphs are scale-free with the degree exponent $γ$. We use the branching process approach to obtain scaling forms for the cluster size distribution and the largest cluster size as functions of the number of edges $L$ and vertices $N$. We find that the process of forming a spanning cluster is qualitatively different between the cases of $γ>3$ and $2<γ<3$. While for the former, a spanning cluster forms abruptly at a critical number of edges $L_c$, generating a single peak in the mean cluster size $<s>$ as a function of $L$, for the latter, however, the formation of a spanning cluster occurs in a broad range of $L$, generating double peaks in $<s>$.

revised version, 4 pages, 6 figures, 1 table