Um grafo aleatório é obtido a partir de um conjunto de n [[vértices]] e adicionando arestas entre elas de forma aleatória. O objetivo do estudo netsnesta área é detrminardeterminar em que fase, uma propriedade particular do grafo, poderá ocorrer. Diferentes modelos de grafos aleatórios produzem diferentes [[distribuições]] de [[probabilidade]] nos grafos. Mais comummentecomumente estudada é o proposto de Edgar Gilbert, denotado G (n, p), em que cada aresta possível ocorre de forma independente com probabilidade p. A probabilidade de um grafo aleatótioaleatório com m arestas é <math>p^m(1-p)^{N-m},</math>. Um modelo relacionado, o modelo de Erdős-Rényi denotado G (n, F), atribui a probabilidade igual a todos os grafos de arestas exactamenteexatamente M. Com a notação <math>N = \begin{bmatrix} n\\2 \end{bmatrix},</math> com 0 ≤ ''M'' ≤ ''N'', ''G''(''n'',''p'') tem <math>\begin{bmatrix} N\\M \end{bmatrix}</math> e cada elemento ocorre com probabilidade <math>\begin{bmatrix} N \\ M \\ \end{bmatrix}^{-1}.</math>.
O mais rápido algoritmo conhecido por gerar a ex-modelo é proposto por Nobari et al.<ref name="refname2"></ref> O último modelo pode ser visto como uma imagem num determinado momento (M) do '''processo gráfico aleatório''' ɞ̃(n) o que é um processo estocástico que começa com n vértices e sem arestas, e em cada etapa adiciona uma nova aresta escolhida de modo uniforme a partir do conjunto de bordas desaparecidas.
