Redes

Redes Aleatórias

$G_{n,m}$: conjunto dos grafos de $n$ vértices e $m$ arestas (se escolhe aleatoriamente um par de vértices e se conectam ate completar $m$) versão microcanônica (sem flutuação). Existe probabilidade de mais de uma aresta entre vértices, porem probabilidade é $m/n^2$

O relação de arestas/vértices é $m/n$

---

$G_{n,p}$: conjunto dos grafos de $n$ vértices onde cada aresta (das $n(n-1)/2$ possíveis) é estabelecida com probabilidade $p$ - versão canônica (com flutuação). Nesta versão não é possível definir duas vezes a mesma aresta.

O número total esperado de arestas é portanto $m\approx pn(n-1)/2$, que para $n$ grande resulta ser $m=p{n}^2/2$. Assim o a relação arestas/vértices é $m/n=pn/2$

O número de médio de arestas por vértice é $z=<k>=pn$

$G_{n,p}$ tem distribuição de grau binomial: $p_k=\frac{n}{k}{p}^k(1-p{)}^{n-k}$

No limite $n$ grande é a distribuição de Poisson:

$p_k=\frac{z^k{e}^{-z}}{k!}$

O resultado mais notável dos trabalhos de Erdös e Rényi é que quando $n\to \mathrm{\infty }$ para $z=1$ ha uma transição onde aparece uma componente gigante. $z=1\Rightarrow pn=1\Rightarrow p=1/n\Rightarrow m=n/2$

Links

Netlog

--Sebas 15:38, 25 Maio 2008 (BRT)

---

voltar