The random graph model generates a graph that has a fixed number of nodes which are connected randomly by undirected edges, see image to the left below. The number of edges depend on a specified probability. The edge probability is chosen based on the number of nodes in the graph. The model most commonly used for this purpose was introduced by Gilbert. This is known as the G(n,p) model. "n" being the number of vertices and "p" the linking probability. The number of edges created according to this model is not known in advance. Erd?s-Rényi introduced a similar model where all the graphs with "m" edges are equally probable and "m" varies between 0 and n(n-1)/2. This is known as the G(n,m) model. The degree distribution is Poissonian in both the generating mechanisms, see image to the right below.
Pros & Cons
It is a mathematically well understood model and has been studied in detail. It can be used to generate networks of any size. It does not generate networks with high clustering coefficient and scale free structure.
- Gilbert, E. N. (1959). Random Graphs. Ann. Math. Stat. 30:1141.
- Erd?s, P. and Rényi, A. (1959). On Random Graphs I. Publicationes Mathematicae Debrecen, 6:290--297.
- Batagelj, V. and Brandes, U.(2005). Efficient generation of large random networks.
Physical Review E 71:036113-036118.
(Access restricted to APS subscribers.)