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} Continuar lendo