Mathematical results on scale-free random graphs.pdf

Mathematical results on scale-free random graphs B. Bolloba?s January 16, 2003 1 Introduction Recently there has been much interest in studying large-scale real-world net- works and attempting to model their properties using random graphs. Although the study of real-world networks as graphs goes back some time, recent activity perhaps started with the paper of Watts and Strogatz [55] about the ‘small- world phenomenon’. Since then the main focus of attention has shifted to the ‘scale-free’ nature of the networks concerned, evidenced by, for example, power- law degree distributions. It was quickly observed that the classical models of random graphs introduced by Erdo?s and Re?nyi [28] and Gilbert [33] are not appropriate for studying these networks, so many new models have been intro- duced. The work in this field falls very roughly into the following categories. 1. Direct studies of the real-world networks themselves, measuring various properties such as degree-distribution, diameter, clustering, etc. 2. Suggestions for new random graph models motivated by this study. 3. Computer simulations of the new models, measuring their properties. 4. Heuristic analysis of the new models to predict their properties. 5. Rigorous mathematical study of the new models, to prove theorems about their properties. Although many hundreds of interesting papers have been written in this area (see, for example, the surveys [2, 27]), so far almost all of this work comes under 1-4; to date there has been very little rigorous mathematical work in the field. Our main aim in this article is to present some of this mathematical work, including several new results. Even an overview of the work in 1-4 lies outside our scope, so we shall present only those models which have been made mathematically precise and for which results have been proved, and mention only a few heuristic results for comparison with the theorems we present. For similar reasons, we cannot even survey the ‘classical’ theory of