On the degree properties of generalized random graphs

A generalization of the classical Erdös and Rényi (ER) random graph is introduced and investigated. A generalized random graph (GRG) admits different values of probabilities for its edges rather than a single probability uniformly for all edges as in the ER model. In probabilistic terms, the vertices of a GRG are no longer statistically identical in general, giving rise to the pos- sibility of complex network topology. Depending on their surrounding edge probabilities, vertices of a GRG can be either "homogeneous" or "heterogeneous". We study the statistical properties of the degree of a single vertex, as well as the degree distribution over the whole GRG. We distinguish the degree distribution for the entire random graph ensemble and the degree frequency for a particular graph realization, and study the mathematical relationship between them. Finally, the connectivity of a GRG, a property which is highly related to the degree distribution, is briefly discussed and some useful results are derived.

Keywords

Random graph, degree distribution, connectivity, giant component

2010 Mathematics Subject Classification

05C40, 05C80

Full Text (PDF format)

Published 1 January 2009