Probabilistic methods in massive graphs and Internet computing

To study the power law graph, we propose a new random graph model with given expected degree sequences. In this model, each vertex is assigned to a weight (or the expected degree) and edges are assigned to each pairs independently with probability proportional to the product of their end-vertex-weights. The classical random graph G(n,p) of Erdo&huml;s and Rényi can be viewed as a special case with the equal weights. We show that the distribution of the connected components depending primarily on the average degree d and the second-order average degree d˜. Here d˜ denotes the ratio of the sum of squares of the expected degree and the sum of the expected degrees of vertices. For example, we prove that the giant component exists if the expected average degree d is greater than 1, and there is no giant component if the expected second-order average degree d˜ is at most 1. Examples are given to illustrate that both bounds are best possible. We also obtain the tight upper bound on the size of the second largest connected components when d > 1. The existence of such a bound regardless the weight distribution is a quite amazing fact.; We further identify a family of the random graphs, whose average distance can be determined. These graphs are called “admissible”. The admissible graphs include G(n,p) and the power law graph with the power β > 3, and much more. For the admissible graph, we proved that almost surely the average distance is (1 + o(1)). Similarly we examine the “strongly admissible” graph. We show that almost surely that the diameter of a strongly admissible graph is Θ(). Again, this result applies to G(n,p) and the power law graph with the power β > 3.; The random power law graph is defined as a special random graph with power-law distribution weights. As we point out, the random power law graphs with the power β > 3 are both admissible and strongly admissible.; In the last chapter, we will focus on how the power law graphs are generated. We examine three important aspects of power law graphs, (1) the evolution of power law graphs, (2) the asymmetry of in-degrees and out-degrees, (3) the “scale invariance” of power law graphs. (Abstract shortened by UMI.)...