TOPICS
Search

Random Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
RandomGraphs

A random graph is a graph in which properties such as the number of graph vertices, graph edges, and connections between them are determined in some random way. The graphs illustrated above are random graphs on 10 vertices with edge probabilities distributed uniformly in [0,1].

Erdős and Rényi (1960) 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 graph edges are almost certain to have it. This is known as a phase transition (Janson et al. 2000, p. 103). Almost all graphs are connected and nonplanar (Skiena 1990, p. 156).

The Wolfram Language command RandomGraph[{n, m}] gives a pseudorandom graph with n vertices and m edges.

See also

Graph, Graph Theory, Phase Transition

Explore with Wolfram|Alpha

References

Bollobás, B. Graph Theory: An Introductory Course. New York: Springer-Verlag, 1979.Bollobás, B. Random Graphs. London: Academic Press, 1985.Erdős, P. and Rényi, A. "On the Evolution of Random Graphs." Publ. Math. Inst. Hungar. Acad. Sci. 5, 17-61, 1960.Erdős, P. and Spencer, J. Probabilistic Methods in Combinatorics. New York: Academic Press, 1974.Janson, S.; Łuczak, T.; and Ruciński, A. Random Graphs. New York: Wiley, 2000.Kolchin, V. F. Random Graphs. New York: Cambridge University Press, 1998.Newman, M. E. J. Strogatz, S. H.; and Watts, D. J. "Random Graphs with Arbitrary Degree Distributions and Their Applications. Phys. Rev. E 64, 026118, 2001.Palmer, E. M. Graphical Evolution: An Introduction to the Theory of Random Graphs. New York: Wiley, 1985.Skiena, S. "Random Graphs." Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 154-160, 1990.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.

Referenced on Wolfram|Alpha

Random Graph

Cite this as:

Weisstein, Eric W. "Random Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RandomGraph.html

Subject classifications