A Random Graph Model for Massive Graphs

A Random Graph Model for Massive Graphs

2000 | William Aiello, Fan Chung, Linyuan Lu
This paper introduces a random graph model for massive graphs with a power law degree sequence. The model is defined by two parameters, logsize (α) and log-log growth rate (β), which capture universal characteristics of such graphs. The model allows for the derivation of various graph properties, including the sizes of connected components. For certain ranges of β, the model predicts the existence of a giant component (a large connected component) and the sizes of smaller components. The paper also compares the model's predictions with empirical data from real-world graphs, such as call graphs derived from telecommunications data. The model is based on a power law degree distribution, where the number of nodes with degree x is proportional to x^(-β). The paper analyzes the connectivity properties of the graph as a function of β. For β < 1, the graph is almost surely connected. For 1 < β < 2, there is a giant component of size Θ(n), and all smaller components are of size O(1). For 2 < β < β₀ (approximately 3.4785), there is a giant component, and all smaller components are of size O(log n). For β = 2, smaller components are of size O(log n / log log n). For β > β₀, there is no giant component. The paper also discusses the sizes of the second largest components and shows that for β > 4, the number of components of given sizes follows a power law distribution. The paper compares the model's predictions with empirical data from call graphs, showing that the model accurately captures the structure of these graphs. The model is shown to be robust, as it applies to a wide range of real-world graphs with power law degree sequences. The paper also discusses the limitations of the model and the need for further research to understand the structural properties of massive graphs.This paper introduces a random graph model for massive graphs with a power law degree sequence. The model is defined by two parameters, logsize (α) and log-log growth rate (β), which capture universal characteristics of such graphs. The model allows for the derivation of various graph properties, including the sizes of connected components. For certain ranges of β, the model predicts the existence of a giant component (a large connected component) and the sizes of smaller components. The paper also compares the model's predictions with empirical data from real-world graphs, such as call graphs derived from telecommunications data. The model is based on a power law degree distribution, where the number of nodes with degree x is proportional to x^(-β). The paper analyzes the connectivity properties of the graph as a function of β. For β < 1, the graph is almost surely connected. For 1 < β < 2, there is a giant component of size Θ(n), and all smaller components are of size O(1). For 2 < β < β₀ (approximately 3.4785), there is a giant component, and all smaller components are of size O(log n). For β = 2, smaller components are of size O(log n / log log n). For β > β₀, there is no giant component. The paper also discusses the sizes of the second largest components and shows that for β > 4, the number of components of given sizes follows a power law distribution. The paper compares the model's predictions with empirical data from call graphs, showing that the model accurately captures the structure of these graphs. The model is shown to be robust, as it applies to a wide range of real-world graphs with power law degree sequences. The paper also discusses the limitations of the model and the need for further research to understand the structural properties of massive graphs.
Reach us at info@study.space