On the evolution of scale-free graphs

Original · EN

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