Grafos aleatórios G(n, p) e o limiar de conexidade

Grafos aleatórios G(n, p)

O modelo G(n, p) cria um grafo com n vértices em que cada par de vértices vira uma aresta independentemente, com probabilidade p. Com p = 0 o grafo não tem arestas; com p = 1 é o grafo completo. Entre esses extremos, cada sorteio dá um grafo diferente, e o interesse está nas propriedades que aparecem com alta probabilidade.

Conexidade e o limiar

Um fenômeno importante é que a probabilidade de o grafo ser conexo passa de quase 0 para quase 1 numa faixa estreita de valores de p. Essa faixa é aproximadamente em torno de ln(n)/n: abaixo dela, quase sempre sobram vértices isolados; acima dela, quase sempre não sobra nenhum.

A aula estima essa probabilidade sorteando R grafos para cada p. Como R é finito, a curva tem ruído: aumente R para ver a transição mais limpa. A cada mudança a estimativa é recalculada com as mesmas sementes, então o resultado é reproduzível.

Distribuição de graus

Como as arestas são independentes, o grau de um vértice segue uma binomial de parâmetros n − 1 e p, com média (n − 1)p. O gráfico de graus da aula compara a média dos sorteios com essa distribuição teórica. Quando n é grande e p é pequeno, a binomial se aproxima de uma Poisson.

Cuidado com a leitura

• Estimativas com poucos sorteios variam. Compare sempre com R grande antes de concluir algo.
• O limiar ln(n)/n é uma aproximação assintótica; para n pequeno ele é só uma referência.
• Um grafo aleatório conexo não é necessariamente "bonito": o layout automático mostra apenas uma amostra.