info prev up next book cdrom email home

Random Graph

A random graph is a Graph in which properties such as the number of Nodes, Edges, and connections between them are determined in some random way. Erdös and Rényi showed that for many monotone-increasing properties of random graphs, graphs of a size slightly less than a certain threshold are very unlikely to have the property, whereas graphs with a few more Edges are almost certain to have it. This is known as a Phase Transition.

See also Graph (Graph Theory), Graph Theory


Bollobás, B. Random Graphs. London: Academic Press, 1985.

Steele, J. M. ``Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of Random Trees.'' Prob. Eng. Inform. Sci. 1, 47-59, 1987.

© 1996-9 Eric W. Weisstein