Erdős–Rényi model

From Wikipedia, the free encyclopedia

In graph theory, the Erdős-Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges. It can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for "almost all" graphs.

Contents

[edit] Definition

There are two closely related variants of the Erdős-Rényi random graph model.

A graph generated by the binomial model of Erdos and Renyi (p=0.01)
A graph generated by the binomial model of Erdos and Renyi (p=0.01)
  • In the G(n, M) model a graph is chosen uniformly at random from the collection of all graphs which have n nodes and M edges. For example, in the G(3,2) model, each of the three possible graphs on three vertices and two edges are included with probability 1/3.
  • In the G(n, p) model, a graph is thought to be constructed by connecting nodes randomly. Each edge is included in the graph with probability p, with the presence or absence of any two distinct edges in the graph being independent. Equivalently, all graphs with n nodes and M edges have equal probability of p^M (1-p)^{{n \choose 2}-M}. The parameter p in this model can be thought of as a weighting function; as p increases from 0 to 1, the model becomes more and more likely to include graphs with more edges and less and less likely to include graphs with fewer edges. In particular, the case p = 0.5 corresponds to the case where all 2^\tbinom{n}{2} graphs on n vertices are chosen with equal probability.

The behavior of random graphs are often studied in the case where n, the number of vertices, tends to infinity. Although p and M can be fixed in this case, they can also be functions depending on n. For example, the statement "almost every graph in G(n, \tfrac{2 \ln n}{n}) is connected" means "as n tends to infinity, the probability that a graph on n vertices with edge probability \tfrac{2 \ln n}{n} is connected tends to 1".

[edit] Comparison between the two models

The expected number of edges in G(n,p) is \tbinom{n}{2}p, and by the law of large numbers any graph in G(n,p) will almost surely have approximately this many edges (provided the expected number of edges tends to infinity). Therefore a rough heuristic is that if pn2 tends to infinity, then G(n,p) should behave similarly to G(n,M) with M=\tbinom{n}{2} p as n increases.

For many graph properties, this is the case. If P is any graph property which is Monotone with respect to the subgraph ordering (meaning that if A is a subgraph of B and A satisfies P, then B will satisfy P as well), then the statements " P holds for almost all graphs in G(n,p) " and "P holds for almost all graphs in G(n, \tbinom{n}{2} p) are equivalent (provided np2 tends to infinity). For example, this holds if P is the property of being connected, or if P is the property of containing a Hamiltonian cycle. However, this will not necessarily hold for non-monotone properties (e.g. the property of having an even number of edges).

In practice, the G(n, p) model is the one more commonly used today, in part due to the ease of analysis allowed by the independence of the edges.

[edit] Properties of G(n, p)

As mentioned above, a graph from G(n, p) has on average \tbinom{n}{2} p edges. The distribution of the degree of any particular vertex is binomial:

P(\operatorname{deg}(v) = k) = {n-1\choose k}p^k(1-p)^{n-1-k},

where n is the total number of vertices in the graph.

In a 1960 paper, Erdős and Rényi described the behavior of G(n,p) very precisely for various values of p. Their results included that:

  • If np < 1, then a graph in G(n,p) will almost surely have no connected components of size larger than O(logn)
  • If np = 1, then a graph in G(n,p) will almost surely have largest component whose size is of order n2 / 3
  • If np tends to a constant c > 1, then a graph in G(n, p) will almost surely have a unique "giant" component containing a positive fraction of the vertices. No other component will contain more than O(logn) vertices.
  • If p<\tfrac{(1-\epsilon)\ln n}{n}, then a graph in G(n, p) will almost surely not be connected.
  • If p>\tfrac{(1+\epsilon) \ln n}{n}, then a graph in G(n, p) will almost surely be connected.

Thus \tfrac{\ln n}{n} is a sharp threshold for the connectivity of G(n, p).

Other properties of the graph can be described almost precisely as n tends to infinity. For example

  • There is a k(n) (approximately equal to 2log2n) such that the largest clique in G(n, 0.5) is almost surely either k(n) or k(n) + 1.

Thus even though finding the size of the largest clique in a graph is NP-complete, the size of the largest clique in a "typical" graph (according to this model) is very well understood.

[edit] Weaknesses

Both of the two major assumptions of the G(n, p) model (that edges are independent and that each edge is equally likely) may be unrealistic in modeling real situations. In particular, an Erdős-Rényi graph will likely not be scale-free like many real networks.

[edit] History

The G(n, p) model was first introduced by Edgar Gilbert in a 1959 paper which studied the connectivity threshold mentioned above. The G(n, M) model was introduced by Erdős and Rényi in their 1959 paper. As with Gilbert, their first investigations were as to the connectivity of G(n,M), with the more detailed analysis following in 1960.

[edit] References

  • Bollobás, B. (2001), Random Graphs (2nd ed.), Cambridge University Press, ISBN 0521797225 
  • Bollobás, B.; Erdős, P. (1976). "Cliques in Random Graphs". Math. Proc. Cambridge Phil. Soc. 80 (3): 419–427. 
  • Erdős, P.; Rényi, A. (1959). "On Random Graphs. I.". Publicationes Mathematicae 6: 290–297. 
  • Erdős, P.; Rényi, A. (1960). "The Evolution of Random Graphs". Magyar Tud. Akad. Mat. Kutató Int. Közl. 5: 17–61. 
  • Gilbert, E.N. (1959). "Random Graphs". Annals of Mathematical Statistics 30: 1141–1144. doi:10.1214/aoms/1177706098. 
  • West, Douglas B. (2001), Introduction to Graph Theory (2nd ed.), Prentice Hall, ISBN 0-13-014400-2 
Languages