Properties of Random Graphs
The theory of random graphs studies typical properties of random graphs, those that hold with high probability for graphs drawn from a particular distribution. For example, we might ask for a given value of and what the probability is that is connected. In studying such questions, researchers often concentrate on the asymptotic behavior of random graphs—the values that various probabilities converge to as grows very large. Percolation theory characterizes the connectedness of random graphs, especially infinitely large ones.
Percolation is related to the robustness of the graph (called also network). Given a random graph of n nodes and an average degree . Next we remove randomly a fraction of nodes and leave only a fraction . There exists a critical percolation threshold below which the network becomes fragmented while above a giant connected component exists .
(threshold functions, evolution of G~)
Random graphs are widely used in the probabilistic method, where one tries to prove the existence of graphs with certain properties. The existence of a property on a random graph can often imply, via the famous Szemerédi regularity lemma, the existence of that property on almost all graphs.
Read more about this topic: Random Graph
Famous quotes containing the words properties of, properties and/or random:
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)
“Assemble, first, all casual bits and scraps
That may shake down into a world perhaps;
People this world, by chance created so,
With random persons whom you do not know—”
—Robert Graves (1895–1985)