Grafo aleatório

Na teoria dos grafos e na teoria das probabilidades, um grafo aleatório é um grafo gerado por um processo estocástico. A teoria dos grafos aleatórios dedica-se ao estudo das propriedades estatísticas e estruturais de grafos selecionados aleatoriamente dentro de um determinado espaço de probabilidade, focando especialmente no comportamento assintótico à medida que o número de vértices cresce indefinidamente ($n\to \infty$).

Originada no final da década de 1950 com os trabalhos pioneiros de Paul Erdős, Alfréd Rényi e Edgar Gilbert, a teoria tornou-se um dos ramos mais ativos da combinatória e da matemática discreta moderna. Para além da matemática pura, os modelos de grafos aleatórios são amplamente empregados na física estatística, na ciência da computação (como algoritmos probabilísticos e teoria da complexidade) e na análise de redes complexas — tais como redes sociais, redes de telecomunicações, sistemas de transporte e redes biológicas e neuronais.

História e fundamentação

O emprego da aleatoriedade no estudo de problemas combinatórios teve seu primeiro marco significativo em 1947, quando Paul Erdős utilizou o que viria a ser denominado método probabilístico para demonstrar a existência de grafos sem determinados subgrafos completos ou vazios (fornecendo um limite inferior exponencial não construtivo para os números de Ramsey diagonais $R(k,k)$).

No final da década de 1950, o conceito de grafo aleatório como objeto de estudo autônomo foi formulado quase simultaneamente sob duas abordagens distintas:

• Em 1959, Edgar Gilbert introduziu o modelo $G(n,p)$, no qual cada uma das possíveis arestas entre $n$ vértices é selecionada independentemente com probabilidade $p$ fixa.
• No mesmo ano, Paul Erdős e Alfréd Rényi definiram o modelo $G(n,M)$, no qual escolhe-se uniformemente ao acaso um grafo entre todos aqueles que possuem exatamente $n$ vértices e $M$ arestas.

Entre 1959 e 1968, Erdős e Rényi publicaram uma influente série de artigos sobre o tema. O mais célebre deles, On the Evolution of Random Graphs (1960), descreveu a evolução estrutural de um grafo à medida que arestas são gradualmente adicionadas, demonstrando a existência de transições de fase e funções limiar para diversas propriedades topológicas fundamentais, em especial o surgimento do chamado "componente gigante".

Durante as décadas de 1980 e 1990, matemáticos como Béla Bollobás, Svante Janson, Tomasz Łuczak e Andrzej Ruciński consolidaram o tratamento rigoroso da área com ferramentas avançadas de probabilidade e combinatória analítica. Na virada para o século XXI, a constatação de que redes reais (como a World Wide Web e redes metabólicas) apresentavam características não capturadas pelo modelo clássico impulsionou a criação de novos modelos estocásticos, como as redes de mundo pequeno (de Duncan Watts e Steven Strogatz) e as redes livres de escala (de Albert-László Barabási e Réka Albert).

Modelos clássicos fundamentais

Existem duas formulações clássicas intimamente relacionadas para grafos aleatórios finitos, frequentemente agrupadas sob a designação geral de modelo de Erdős–Rényi.

O modelo de Gilbert: $G(n,p)$

No modelo $G(n,p)$, o conjunto de vértices $V=\{1,2,\dots ,n\}$ é fixo. Para cada um dos ${\binom {n}{2}}={\frac {n(n-1)}{2}}$ pares não ordenados de vértices distintos, inclui-se uma aresta com probabilidade $p$, de forma mutuamente independente.

O espaço amostral é composto por todos os $2^{\binom {n}{2}}$ grafos não direcionados simples com $n$ vértices. Se um grafo específico $G_{0}$ possui exatamente $m$ arestas, sua probabilidade é dada por:

$\mathbb {P} (G=G_{0})=p^{m}(1-p)^{{\binom {n}{2}}-m}$

Propriedades básicas

• Número esperado de arestas: A variável aleatória $M$, que conta o número total de arestas de $G$, segue uma distribuição binomial $\mathrm {Bin} \left({\binom {n}{2}},p\right)$. Seu valor esperado e variância são:

$\mathbb {E} [M]={\binom {n}{2}}p$

$\mathrm {Var} (M)={\binom {n}{2}}p(1-p)$

• Distribuição de graus: O grau $D_{v}$ de qualquer vértice fixo $v$ segue uma distribuição binomial $\mathrm {Bin} (n-1,p)$, com média:

$\mathbb {E} [D_{v}]=(n-1)p$

Se $p={\frac {c}{n}}$ para alguma constante $c>0$, à medida que $n\to \infty$, a distribuição do grau de qualquer vértice converge pontualmente para uma distribuição de Poisson de média $\lambda =c$:

$\lim _{n\to \infty }\mathbb {P} (D_{v}=k)={\frac {c^{k}e^{-c}}{k!}}$

O modelo de Erdős–Rényi: $G(n,M)$

No modelo $G(n,M)$, fixa-se o número de vértices $n$ e o número exato de arestas $M$, com $0\leq M\leq {\binom {n}{2}}$. O espaço amostral consiste em todos os grafos simples que possuem precisamente $M$ arestas, distribuídos sob a probabilidade uniforme:

$\mathbb {P} (G=G_{0})={\binom {\binom {n}{2}}{M}}^{-1}$

Equivalência assintótica

Os modelos $G(n,p)$ e $G(n,M)$ são assintoticamente equivalentes na maioria das situações práticas quando $M\approx {\binom {n}{2}}p$. Especificamente, se ${\mathcal {P}}$ é uma propriedade monótona de grafos (isto é, a adição de arestas não destrói a propriedade, como conexidade ou existência de subgrafos) e $M={\binom {n}{2}}p\to \infty$ e ${\binom {n}{2}}-M\to \infty$, o comportamento limite de $\mathbb {P} (G(n,p)\in {\mathcal {P}})$ coincide com o de $\mathbb {P} (G(n,M)\in {\mathcal {P}})$.

O modelo $G(n,p)$ costuma ser matematicamente mais tratável em demonstrações devido à independência estocástica entre a presença das diferentes arestas, enquanto $G(n,M)$ é um modelo microcanônico com volume de arestas estritamente fixado.

O processo de grafo aleatório

Um processo de grafo aleatório é uma cadeia estocástica discreta $\{G_{t}\}_{t=0}^{N}$, onde $N={\binom {n}{2}}$. O processo inicia-se com $G_{0}$ consistindo em $n$ vértices isolados e nenhuma aresta. Em cada passo $t\in \{1,\dots ,N\}$, uma aresta é selecionada uniformemente ao acaso dentre as arestas ainda não inseridas e adicionada ao grafo, de modo que $G_{t}$ é um grafo distribuído de acordo com $G(n,t)$.

Esse processo permite analisar "tempos de parada" (hitting times) estocásticos. Por exemplo, pode-se comparar o momento exato em que o grau mínimo atinge 1 com o instante em que o grafo torna-se conexo.

Propriedades assintóticas e funções limiar

No estudo de grafos aleatórios, interessa investigar o comportamento estrutural quando $n$ tende ao infinito. Diz-se que uma propriedade ${\mathcal {P}}$ ocorre assintoticamente quase certamente (frequentemente abreviado como a.a.s., do inglês asymptotically almost surely, ou quase certamente) se:

$\lim _{n\to \infty }\mathbb {P} (G_{n}\in {\mathcal {P}})=1$

Definição de função limiar

Uma função $r(n)$ é dita uma função limiar (ou limiar de probabilidade) para uma propriedade monótona crescente ${\mathcal {P}}$ se a probabilidade satisfaz:

$\lim _{n\to \infty }\mathbb {P} (G(n,p(n))\in {\mathcal {P}})={\begin{cases}0,&{\text{se }}{\frac {p(n)}{r(n)}}\to 0\\1,&{\text{se }}{\frac {p(n)}{r(n)}}\to \infty \end{cases}}$

Diz-se que um limiar é agudo (sharp threshold) se a transição entre 0 e 1 ocorre em uma faixa estreita $p(n)=(1\pm o(1))r(n)$. Pelo teorema de Friedgut e Kalai (1996), toda propriedade monótona invariante por automorfismos possui um limiar agudo ou grosseiro bem caracterizado por sua sensibilidade a permutações.

Limiares notáveis no modelo $G(n,p)$

A tabela a seguir resume os limiares probabilísticos para algumas das propriedades mais estudadas:

Propriedade	Função limiar $p(n)$	Comportamento assintótico
Surgimento de ao menos uma aresta	$n^{-2}$	Limiar grosseiro
Surgimento de um subgrafo isomorfo a $H$	$n^{-1/m(H)}$	Onde $m(H)=\max _{H'\subseteq H}{\frac {|E(H')|}{|V(H')|}}$ é a densidade máxima
Existência de ao menos um ciclo (de qualquer ordem)	$n^{-1}$	O número de ciclos converge para uma distribuição de Poisson
Surgimento do componente gigante	$n^{-1}$	Transição crítica em $p=c/n$ para $c=1$
Desaparecimento do último vértice isolado	${\frac {\ln n}{n}}$	Limiar agudo: $p(n)={\frac {\ln n+c}{n}}$
Conexidade do grafo	${\frac {\ln n}{n}}$	Coincide assintoticamente com o desaparecimento dos vértices isolados
Existência de um ciclo hamiltoniano	${\frac {\ln n+\ln \ln n}{n}}$	Limiar agudo (Komlós e Szemerédi, 1983)
Grafo planar	${\frac {1}{2n}}$	Quase certamente não planar para $p>{\frac {1}{2n}}$

Evolução do grafo e o componente gigante

O estudo da evolução de $G(n,p)$ quando $p={\frac {c}{n}}$ (para $c>0$ constante) é um dos resultados mais profundos de Erdős e Rényi (1960). Conforme a constante $c$ varia em torno de 1, o grafo exibe uma marcante transição de fase de segunda ordem, análoga à teoria da percolação:

Fase subcrítica ($c<1$)

Quando $c<1$:

• O grafo é quase certamente composto por uma coleção disjunta de pequenos componentes conexos (árvores simples e componentes unicíclicos).
• O maior componente conexo possui no máximo ordem logarítmica:

$|C_{\max }|=O(\log n)$

• Não há componentes com mais de um ciclo.

Janela crítica ($c=1$)

Na vizinhança de $c=1$, parametrizada por $p={\frac {1+\lambda n^{-1/3}}{n}}$ com $\lambda \in \mathbb {R}$ (conhecida como a scaling window de Bollobás e Łuczak):

• Vários componentes de tamanho intermediário fundem-se gradualmente.
• O maior componente conexo atinge uma ordem de grandeza fracionária:

$|C_{\max }|=\Theta (n^{2/3})$

• A distribuição de tamanhos e o número de ciclos nos componentes relacionam-se formalmente a passeios aleatórios e excursões do movimento browniano.

Fase supercrítica ($c>1$)

Quando $c>1$:

• Surge quase certamente um único componente dominante, denominado componente gigante, cuja ordem é linear no número de vértices:

$|C_{\max }|\sim y(c)n$

em que a fração $y(c)\in (0,1)$ é a única raiz positiva da equação transcendente:

$1-y=e^{-cy}$

• Todos os demais componentes conexos permanecem pequenos, com tamanho limitado por $O(\log n)$.
• A estrutura do componente gigante torna-se complexa, contendo múltiplos ciclos interligados.

Fase de conexidade ($p\approx {\frac {\ln n}{n}}$)

Para $p(n)={\frac {\ln n+c+o(1)}{n}}$, todos os componentes pequenos restantes são progressivamente absorvidos pelo componente gigante. A probabilidade de o grafo ser completamente conexo converge assintoticamente para uma distribuição de Gumbel:

$\lim _{n\to \infty }\mathbb {P} (G(n,p){\text{ é conexo}})=e^{-e^{-c}}$

Esse resultado decorre do fato de que o número de vértices isolados converge assintoticamente para uma distribuição de Poisson de média $e^{-c}$.

O método probabilístico e aplicações em combinatória

Os grafos aleatórios são o alicerce do método probabilístico, técnica introduzida principalmente por Paul Erdős para demonstrar a existência de objetos combinatórios com propriedades incomuns sem a necessidade de construí-los explicitamente.

O raciocínio baseia-se na constatação de que, se definirmos um espaço de probabilidade sobre uma família de grafos e mostrarmos que a probabilidade de um elemento satisfazer uma determinada propriedade ${\mathcal {A}}$ é estritamente positiva:

$\mathbb {P} (G\in {\mathcal {A}})>0$

então necessariamente deve existir ao menos um grafo com a propriedade ${\mathcal {A}}$.

Um dos exemplos mais célebres é a demonstração de Erdős (1959) sobre a existência de grafos com cintura (comprimento do menor ciclo) arbitrariamente grande e número cromático arbitrariamente grande. Até então, acreditava-se que um número cromático elevado exigia necessariamente a presença de pequenos ciclos (como triângulos ou subgrafos densos). Avaliando $G(n,p)$ com $p=n^{\epsilon -1}$ e eliminando um vértice de cada ciclo curto, Erdős provou a existência de grafos com cintura superior a $k$ e número cromático superior a $r$, para quaisquer inteiros $k,r\geq 3$.

Lógica e leis zero-um

No final da década de 1960, pesquisadores da União Soviética liderados por Glebskii et al. (1969) e, de forma independente, Ronald Fagin (1976) nos Estados Unidos, descobriram que os grafos aleatórios satisfazem uma notável lei zero-um para a lógica de primeira ordem.

Seja $\phi$ qualquer sentença formulada na linguagem de primeira ordem da teoria dos grafos (utilizando quantificadores $\forall ,\exists$, conectivos booleanos e o predicado binário de adjacência $\sim$). Se a probabilidade $p\in (0,1)$ for constante e independente de $n$, então:

$\lim _{n\to \infty }\mathbb {P} (G(n,p)\models \phi )\in \{0,1\}$

Em outras palavras, qualquer afirmação de primeira ordem ou é assintoticamente quase certamente verdadeira, ou quase certamente falsa. Essa lei deixa de valer se permitirmos que $p(n)$ decresça em certas taxas (como $p(n)=n^{-\alpha }$ com $\alpha \in (0,1)$ racional, investigado por Shelah e Spencer em 1988) ou se considerarmos linguagens mais expressivas, como a lógica de segunda ordem monádica (com a qual se pode expressar conectividade ou colorabilidade).

Grafos aleatórios infinitos: o grafo de Rado

Quando se estende o conceito de grafo aleatório para uma quantidade enumerável e infinita de vértices ($V=\mathbb {N}$) e define-se que cada par de vértices possui uma aresta com probabilidade independente $p\in (0,1)$, ocorre um fenômeno de unicidade surpreendente: com probabilidade 1, o grafo resultante é isomorfo a um único objeto matemático, conhecido como o grafo de Rado (ou grafo aleatório infinito).

Esse grafo caracteriza-se pela propriedade de extensão: para quaisquer dois subconjuntos finitos e disjuntos de vértices $U$ e $W$, existe um vértice $z\notin U\cup W$ que é adjacente a todos os vértices de $U$ e a nenhum vértice de $W$. O grafo de Rado é altamente simétrico (ultrahomogêneo) e universal, no sentido de que contém qualquer grafo enumerável finito ou infinito como subgrafo induzido.

Outros modelos de grafos aleatórios

Embora o modelo de Erdős–Rényi seja a base teórica histórica, sua distribuição de graus de Poisson e seu coeficiente de agrupamento convergindo a zero ($C\approx p\to 0$) o tornam inadequado para descrever a maioria das redes empíricas do mundo real. Diversos outros modelos foram propostos para suprir essas características.

Grafos regulares aleatórios

Um grafo $d$-regular aleatório, denotado por $G(n,d{\text{-reg}})$, é um grafo escolhido uniformemente entre todos os grafos simples $d$-regulares sobre $n$ vértices (exigindo que $nd$ seja par).

O estudo desse modelo baseia-se amplamente no modelo de emparelhamento (ou configuration model) de Bollobás (1980): cada vértice recebe $d$ "meias-arestas", que são emparelhadas aleatoriamente sob uma permutação uniforme. Grafos regulares aleatórios destacam-se como excelentes exemplos de grafos expansores (grafos altamente conectados com baixa densidade de arestas), de suma relevância para a teoria de códigos corretores de erro e comunicação em redes.

Modelo Watts–Strogatz (redes de mundo pequeno)

Ver artigo principal: Modelo Watts–Strogatz

Proposto por Duncan Watts e Steven Strogatz em 1998, este modelo interpola entre uma rede regular em anel (com alto coeficiente de agrupamento local e grande distância média) e um grafo puramente aleatório (com pequeno diâmetro e baixo agrupamento).

A partir de uma grade regular unidimensional onde cada nó está conectado aos seus $k$ vizinhos mais próximos, cada aresta é reconectada aleatoriamente com probabilidade $\beta$. Para valores intermediários de $\beta$, a rede exibe simultaneamente:

• Um coeficiente de agrupamento elevado (vizinhos de um nó têm alta chance de serem vizinhos entre si);
• Uma distância média entre nós logarítmica ou sublogarítmica (o fenômeno do mundo pequeno ou dos "seis graus de separação").

Modelo Barabási–Albert (redes livres de escala)

Ver artigo principal: Modelo Barabási–Albert

Formulado por Albert-László Barabási e Réka Albert em 1999, este modelo incorpora dois princípios fundamentais observados em redes dinâmicas reais:

1. Crescimento contínuo: Novos vértices entram progressivamente na rede ao longo do tempo.
2. Ligação preferencial (preferential attachment ou efeito "o rico fica mais rico"): A probabilidade $\Pi (v_{i})$ de um novo vértice ligar-se a um vértice existente $v_{i}$ é proporcional ao grau atual $k_{i}$ deste último:

$\Pi (v_{i})={\frac {k_{i}}{\sum _{j}k_{j}}}$

Como consequência, a rede atinge um estado estacionário no qual a distribuição dos graus segue assintoticamente uma lei de potência:

$P(k)\propto k^{-\gamma }$

com expoente livre de escala $\gamma =3$. Redes dessa natureza contam com a existência de hubs (nós com grau desproporcionalmente elevado).

Modelo de blocos estocásticos (SBM)

Ver artigo principal: Modelo de blocos estocásticos

O modelo de blocos estocásticos (Stochastic Block Model) particiona os $n$ vértices em $k$ classes ou comunidades predeterminadas. A probabilidade de uma aresta existir entre o vértice $u$ (pertencente ao bloco $r$) e o vértice $v$ (pertencente ao bloco $s$) é dada por uma entrada fixa $B_{rs}$ de uma matriz de probabilidade $B\in [0,1]^{k\times k}$.

O SBM é uma das principais ferramentas de referência estatística e aprendizado não supervisionado para problemas de detecção de comunidades em sociologia computacional, biologia de sistemas e aprendizado de máquina.

Grafos geométricos aleatórios

Em um grafo geométrico aleatório $G(n,r)$, $n$ vértices são distribuídos aleatoriamente (segundo uma distribuição uniforme ou um processo pontual de Poisson) dentro de um espaço métrico, como o quadrado unitário $[0,1]^{d}$ em $\mathbb {R} ^{d}$. Dois vértices conectam-se por uma aresta se, e somente se, a distância euclidiana entre eles for menor ou igual a um determinado raio de corte $r>0$.

Tais grafos modelam naturalmente redes ad hoc móveis, redes de sensores sem fio e estruturas espaciais em física da matéria condensada.

Aplicações

A teoria dos grafos aleatórios possui uma vasta gama de aplicações teóricas e práticas:

• Modelagem de epidemias e processos de contato: A propagação de agentes infecciosos em populações é descrita por modelos estocásticos (como os modelos SIR ou SIS) sobrepostas a redes com diferentes distribuições de conectividade, permitindo calcular o limiar epidêmico.
• Ciência da computação e algoritmos: O teste de algoritmos em instâncias geradas por grafos aleatórios é utilizado na análise de complexidade média. Grafos aleatórios também auxiliam no projeto de redes de interconexão robustas, sistemas tolerantes a falhas e estruturas de dados probabilísticas.
• Física estatística e matéria condensada: Há uma correspondência direta entre a formação do componente gigante e a transição de gelificação em polímeros ou a teoria da percolação. Os grafos aleatórios também servem como substrato para modelos de vidros de spin e para o estudo do modelo de Ising.
• Bioinformática e neurociência: Análise de redes de interação proteína-proteína, redes de regulação gênica e mapeamento de redes neurais estruturais e funcionais no cérebro (conectômica).

Ver também

• Teoria dos grafos
• Modelo de Erdős–Rényi
• Modelo Watts–Strogatz
• Modelo Barabási–Albert
• Método probabilístico
• Teoria da percolação
• Grafo de Rado
• Ciência das redes

Bibliografia

• Alon, Noga; Spencer, Joel H. (2016). The Probabilistic Method 4.ª ed. Hoboken: John Wiley & Sons. ISBN 978-1119061953 
• Bollobás, Béla (2001). Random Graphs 2.ª ed. Cambridge: Cambridge University Press. ISBN 978-0521797221 
• Frieze, Alan; Karoński, Michał (2015). Introduction to Random Graphs. Cambridge: Cambridge University Press. ISBN 978-1107118508 
• Janson, Svante; Łuczak, Tomasz; Ruciński, Andrzej (2000). Random Graphs. Nova Iorque: John Wiley & Sons. ISBN 978-0471175414 
• Newman, Mark (2018). Networks 2.ª ed. Oxford: Oxford University Press. ISBN 978-0198805090 
• Penrose, Mathew (2003). Random Geometric Graphs. Oxford: Oxford University Press. ISBN 978-0198506263