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=pn^{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\rightarrow \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