A random graph model for massive graphs

Published 1 May 2000

William Aiello, Fan Chung, Linyuan Lü

Citations925

TL;DR

A random graph model is proposed which is a special case of sparse random graphs with given degree sequences which involves only a small number of parameters, called logsize and log-log growth rate, which capture some universal characteristics of massive graphs.

Abstract

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

Keywords

Computer ScienceMathematicsPhysics and Astronomy

ScienceEmergence of Scaling in Random Networks

36,366 Citations1999Albert-Ĺaszló Barabási, Réka Albert

A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.

View PDF

Medical Entomology and ZoologyThe Probabilistic Method

4,356 Citations1991Joel Spencer

A particular set of problems - all dealing with “good” colorings of an underlying set of points relative to a given family of sets - is explored.

NatureDiameter of the World-Wide Web

4,285 Citations1999Réka Albert, Hawoong Jeong +1 more

The World-Wide Web becomes a large directed graph whose vertices are documents and whose edges are links that point from one document to another, which determines the web's connectivity and consequently how effectively the authors can locate information on it.

View PDF

On power-law relationships of the Internet topology

4,222 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more

These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period, and can be used to generate and select realistic topologies for simulation purposes.

View PDF

Random Structures and AlgorithmsA critical point for random graphs with a given degree sequence

2,401 Citations1995Michael Molloy, Bruce Reed

It is shown that if Σ i(i - 2)λi > 0, then such graphs almost surely have a giant component, while if λ0, λ1… which sum to 1, then almost surely all components in such graphs are small.

Physica A Statistical Mechanics and its ApplicationsScale-free characteristics of random networks: the topology of the world-wide web

1,409 Citations2000Albert-Ĺaszló Barabási, Réka Albert +1 more

This work introduces a model that leads to a scale-free network, capturing in a minimal fashion the self-organization processes governing the world-wide web.

Computer NetworksTrawling the Web for emerging cyber-communities

1,010 Citations1999Ravi Kumar, Prabhakar Raghavan +2 more

The subject of this paper is the systematic enumeration of over 100,000 emerging communities from a Web crawl, motivating a graph-theoretic approach to locating such communities, and describing the algorithms and algorithmic engineering necessary to find structures that subscribe to this notion.

Lecture notes in computer scienceThe Web as a Graph: Measurements, Models, and Methods

1,009 Citations1999Jon Kleinberg, Ravi Kumar +3 more

This paper describes two algorithms that operate on the Web graph, addressing problems from Web search and automatic community discovery, and proposes a new family of random graph models that point to a rich new sub-field of the study of random graphs, and raises questions about the analysis of graph algorithms on the Internet.

Combinatorics Probability ComputingThe Size of the Giant Component of a Random Graph with a Given Degree Sequence

828 Citations1998Michael Molloy, Bruce Reed

The size of the giant component in the former case, and the structure of the graph formed by deleting that component is analyzed, which is basically that of a random graph with n′=n−∣C∣ vertices, and with λ′in′ of them of degree i.

View PDF

Cambridge University Press eBooksModels of Random Regular Graphs

610 Citations1999N. C. Wormald

This is a survey of results on properties of random regular graphs, together with an exposition of some of the main methods of obtaining these results.