Mathematical results on scale-free random graphs

Mathematical results on scale-free random graphsB. Bollob´asJanuary 16, 20031 IntroductionRecently there has been much interest in studying large-scale real-world net-works and attempting to model their properties using random graphs. Althoughthe study of real-world networks as graphs goes back some time, recent activityperhaps 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 ofrandom graphs introduced by Erd˝os and R´enyi [28] and Gilbert [33] are notappropriate 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 variousproperties 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 abouttheir 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 comesunder 1-4; to date there ...