| Table of contents |
|
2 Properties of random graphs 3 History 4 References |
A random graph is obtained by starting with a set of n vertices and adding edges between them at random. Different random graph models produce different probability distributions on graphs.
The most commonly studied model, called G(n,p), includes each possible edge independently with probability p. A closely related model, G(n,M) assigns equal probability to all graphs with exactly M edges. Both models can be viewed as snapshots at a particular time of the random graph process , which is a stochastic process that starts with n vertices and no edges and at each time unit adds one new edge chosen uniformly from the set of missing edges.
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 n and p what the probability is that G(n,p) is connected, meaning that it has a path between any two vertices. In studying such questions, random graph theorists often concentrate on the limit behavior of random graphs—the values that various probabilities converge to as n grows very large.
(threshold functions, evolution of G~)Random graph models
Properties of random graphs