Teorema do dia: #1 – Caso especial para Grafos Aleatórios Generalizados

A demonstração de hoje é a resolução do exercício 6.1 do livro Random Graphs and Complex Networks.

No modelo para geração de grafos aleatórios generalizados cada vértice tem um peso definido e as arestas são inseridas de maneira independente de acordo com o peso dos vértices. Assim, vértices com pesos maiores tem mais probabilidade de possuir mais vizinhos do que os vértices de menor peso num grafo onde todos os pesos são distribuídos de modo que sejam diferentes.

Neste modelo a probabilidade de existir uma aresta entre dois vértices u e v, para u \neq v, é

p_{uv} = \frac{w_u w_v}{\ell_n + w_u w_v}

onde w é o peso de cada vértice e

\displaystyle \ell_n = \sum_{v \in V}w_v

Em muitos casos, os pesos dos vértices dependem de {n} (o número de vértices). Mas um caso especial de grafos aleatórios generalizados é quando consideramos que {w_u \equiv \frac{n\lambda}{n - \lambda}}, neste caso {p_{uv} = \frac{\lambda}{n}} para todo {u, v \in V}

Seja {G = (V,E)} um grafo aleatório de {n} véritces do modelo de Érdos e Renyi. A probabilidade da aresta {\{u,v\} \in E} é {p_{uv} = \frac{\lambda}{n}}, quando {w_u = \frac{n\lambda}{n - \lambda}} para todo {u \in V}.

Prova: Sabendo que p_{uv} = \frac{w_u w_v}{\ell_n + w_u w_v} e que neste caso {w_u = \frac{n \lambda}{n - \lambda}} para todo {u \in V} . Temos que

\displaystyle \ell_n = \sum_{u \in V} w_u = n \frac{n\lambda}{n - \lambda}.

Assim, podemos substituir {w_u} na formula

\displaystyle p_{ij} = \frac{w_u w_v}{\ell_n + w_u w_v} \\ = \left( \, \frac{n \lambda}{n - \lambda} w_v \, \right) / \left( \, n \frac{n\lambda}{n - \lambda} + \frac{n\lambda}{n - \lambda} w_v \, \right) \\ = \left( \, \frac{n \lambda}{n - \lambda} w_v \, \right) / \left( \, \frac{n \dot n \lambda + nw_v}{n - \lambda} \, \right) \\ = \left( \frac{n \lambda w_v}{n\lambda (n + w_v)}\right) \\ = \frac{w_v}{n + w_v} \text{ (substituindo novamente)} \\ = \left( \frac{n \lambda}{n\lambda (n - \lambda)}\right) / \left( n + \frac{n \lambda}{n\lambda (n - \lambda)} \right) \\ = \left( \frac{n \lambda}{n\lambda (n - \lambda)}\right) / \left( \frac{n(n - \lambda)n \lambda}{n\lambda (n - \lambda)} \right) \\ = \left( \frac{n \lambda}{n(n - \lambda)n \lambda} \right) \\ = \left( \frac{n \lambda}{n n - n\lambda + n \lambda} \right) \\ = \left( \frac{n \lambda}{n n} \right) \\ = \frac{\lambda}{n}

\square

Comentar

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s