On the degree properties of generalized random graphs. (English) Zbl 1173.05042

Shi, Yi Y.; Qian, Hong

Commun. Math. Sci. 7, No. 1, 175-187 (2009).

Summary: 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 possibility 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.

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C40	Connectivity

Keywords:

random graph; degree distribution; connectivity; giant component