Connected components in random graphs with given expected degree sequences
We consider a family of random graphs with a given expected degree sequence. Each edge
is chosen independently with probability proportional to the product of the expected degrees
of its endpoints. We examine the distribution of the sizes/volumes of the connected
components which turns out depending primarily on the average degree d and the second-
order average degree d~. Here d~ denotes the weighted average of squares of the expected
degrees. For example, we prove that the giant component exists if the expected average …
is chosen independently with probability proportional to the product of the expected degrees
of its endpoints. We examine the distribution of the sizes/volumes of the connected
components which turns out depending primarily on the average degree d and the second-
order average degree d~. Here d~ denotes the weighted average of squares of the expected
degrees. For example, we prove that the giant component exists if the expected average …
Abstract
We consider a family of random graphs with a given expected degree sequence. Each edge is chosen independently with probability proportional to the product of the expected degrees of its endpoints. We examine the distribution of the sizes/volumes of the connected components which turns out depending primarily on the average degree d and the second-order average degree d~. Here d~ denotes the weighted average of squares of the expected degrees. For example, we prove that the giant component exists if the expected average degree d is at least 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.
Springer