A Random Graph Model for Power Law Graphs

Top Cited Papers

1 January 2001

journal article
research article
Published by Taylor & Francis in Experimental Mathematics

Vol. 10 (1) , 53-66
https://doi.org/10.1080/10586458.2001.10504428

Abstract

We propose a random graph model which is a special case of sparserandom graphs with given degree sequences which satisfy a power law. This model involves only a small number of paramo eters, called logsize and log-log growth rate. These parameters capture some universal characteristics of massive graphs. From these parameters, various properties of the graph can be derived. For example, for certai n ranges of the parameters, we wi II compute the expected distribution of the sizes of the connected components which almost surely occur with high probability. We illustrate the consistency of our model with the behavior of some massive graphs derived from data in telecommunications. We also discuss the threshold function, the giant component, and the evolution of random graphs in this model.

Keywords

This publication has 13 references indexed in Scilit:

Scale-free characteristics of random networks: the topology of the world-wide web
Physica A: Statistical Mechanics and its Applications, 2000
A random graph model for massive graphs
Published by Association for Computing Machinery (ACM) ,2000
Graph Theory in Practice: Part II
American Scientist, 2000
Emergence of Scaling in Random Networks
Science, 1999
Diameter of the World-Wide Web
Nature, 1999
On power-law relationships of the Internet topology
ACM SIGCOMM Computer Communication Review, 1999
The Web as a Graph: Measurements, Models, and Methods
Published by Springer Nature ,1999
Trawling the Web for emerging cyber-communities
Computer Networks, 1999
A critical point for random graphs with a given degree sequence
Random Structures & Algorithms, 1995
On the strength of connectedness of a random graph
Acta Mathematica Hungarica, 1964