A random graph model for power law graphs

Citation
W. Aiello et al., A random graph model for power law graphs, EXP MATH, 10(1), 2001, pp. 53-66
Citations number
20
Categorie Soggetti
Mathematics
Journal title
EXPERIMENTAL MATHEMATICS
ISSN journal
10586458 → ACNP
Volume
10
Issue
1
Year of publication
2001
Pages
53 - 66
Database
ISI
SICI code
1058-6458(2001)10:1<53:ARGMFP>2.0.ZU;2-V
Abstract
We propose a random graph model which is a special case of sparse random gr aphs with given degree sequences which satisfy a power law. This model invo lves only a small number of parameters, called logsize and log-log growth r ate. These parameters capture some universal characteristics of massive gra phs. From these parameters, various properties of the graph can be derived. For example, for certain ranges of the parameters, we will compute the exp ected distribution of the sizes of the connected components which almost su rely occur with high probability. We illustrate the consistency of our mode l with the behavior of some massive graphs derived from data in telecommuni cations. We also discuss the threshold function, the giant component, and t he evolution of random graphs in this model.