Graph Theory in Practice: Part II
The entire class of random graphs with a power-law degree sequence has been analyzed by Chung, William Aiello of AT&T Laboratories and Linyuan Lu of the University of Pennsylvania. Their model organizes all such graphs according to the values of two parameters, α and β.
When the degree sequence of a power-law graph is plotted on logarithmic scales, it forms a straight line. The parameters α and β specify this line; α is the point where the line intercepts the y axis, and β is the line's slope (or rather the negative of the slope). Thus α is the logarithm of the number of vertices of minimal degree, and β is the rate at which the logarithm of the number of vertices decreases as the degree increases. More formally, if y(k) is the number of vertices of degree k, then the family of graphs defined by the model consists of all those graphs that satisfy the equation y(k)=eα/kβ, subject to the constraint that both k and y(k) must be integers. For any fixed values of α and β, y(k) specifies a finite set of graphs; a random alpha-beta graph is simply one chosen with uniform probability from this set.
The alpha-beta model is somewhat different from the models discussed above in that it does not directly specify the size of the graph in terms of n, the number of vertices. Another difference is that multiple edges between vertices are allowed, and so are "self-loops," or edges that start and end on the same vertex. (Both of these features are present in some natural graphs, such as the Web.)
Aiello, Chung and Lu explore how the properties of alpha-beta graphs vary as a function of β. A larger value of β corresponds to a steeper slope in the power law and hence to fewer nodes of large degree. If β is greater than a threshold value of approximately 3.4785, almost every alpha-beta graph consists of many small, disconnected components; there are not enough edges to hold the graph together. If β is greater than 1 but less than 3.4785, almost every graph has a giant component—a single large, connected piece that includes most of the vertices and edges in the graph. When β is less than 1, high-degree vertices are so abundant that almost every graph consists of one connected piece.
Aiello, Chung and Lu developed their model with a specific family of real-world graphs in mind, namely "call graphs" recording long-distance telephone traffic. As described in Part I, a call graph has telephone numbers as its vertices, and an edge is drawn between two vertices whenever a call is placed between the corresponding numbers. Analysis of an actual call graph shows that the degree sequence is not quite a perfect power law, and yet the model captures important features of the graph. The best approximation has parameter values of roughly α=17 and β=2.1. Since β lies between 1 and 3.4785, the model predicts that the graph is not connected but does have a giant component.