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 ().
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 ).
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 , no qual cada uma das possíveis arestas entre vértices é selecionada independentemente com probabilidade fixa. No mesmo ano, Paul Erdős e Alfréd Rényi definiram o modelo , no qual escolhe-se uniformemente ao acaso um grafo entre todos aqueles que possuem exatamente vértices e 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: No modelo , o conjunto de vértices é fixo. Para cada um dos pares não ordenados de vértices distintos, inclui-se uma aresta com probabilidade , de forma mutuamente independente.
O espaço amostral é composto por todos os grafos não direcionados simples com vértices. Se um grafo específico possui exatamente arestas, sua probabilidade é dada por:
Propriedades básicas Número esperado de arestas: A variável aleatória , que conta o número total de arestas de , segue uma distribuição binomial . Seu valor esperado e variância são:
Distribuição de graus: O grau de qualquer vértice fixo segue uma distribuição binomial , com média:
Se para alguma constante , à medida que , a distribuição do grau de qualquer vértice converge pontualmente para uma distribuição de Poisson de média :
O modelo de Erdős–Rényi: No modelo , fixa-se o número de vértices e o número exato de arestas , com . O espaço amostral consiste em todos os grafos simples que possuem precisamente arestas, distribuídos sob a probabilidade uniforme:
Equivalência assintótica Os modelos e são assintoticamente equivalentes na maioria das situações práticas quando . Especificamente, se é 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 e , o comportamento limite de coincide com o de .
O modelo costuma ser matematicamente mais tratável em demonstrações devido à independência estocástica entre a presença das diferentes arestas, enquanto é 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 , onde . O processo inicia-se com consistindo em vértices isolados e nenhuma aresta. Em cada passo , uma aresta é selecionada uniformemente ao acaso dentre as arestas ainda não inseridas e adicionada ao grafo, de modo que é um grafo distribuído de acordo com .
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 tende ao infinito. Diz-se que uma propriedade ocorre assintoticamente quase certamente (frequentemente abreviado como a.a.s., do inglês asymptotically almost surely, ou quase certamente) se:
Definição de função limiar Uma função é dita uma função limiar (ou limiar de probabilidade) para uma propriedade monótona crescente se a probabilidade satisfaz:
Diz-se que um limiar é agudo (sharp threshold) se a transição entre 0 e 1 ocorre em uma faixa estreita . 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 A tabela a seguir resume os limiares probabilísticos para algumas das propriedades mais estudadas:
Propriedade Função limiar Comportamento assintótico Surgimento de ao menos uma aresta Limiar grosseiro Surgimento de um subgrafo isomorfo a Onde é a densidade máxima Existência de ao menos um ciclo (de qualquer ordem) O número de ciclos converge para uma distribuição de Poisson Surgimento do componente gigante Transição crítica em para Desaparecimento do último vértice isolado Limiar agudo: Conexidade do grafo Coincide assintoticamente com o desaparecimento dos vértices isolados Existência de um ciclo hamiltoniano Limiar agudo (Komlós e Szemerédi, 1983) Grafo planar Quase certamente não planar para
Evolução do grafo e o componente gigante O estudo da evolução de quando (para constante) é um dos resultados mais profundos de Erdős e Rényi (1960). Conforme a constante 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 () Quando : 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:
Não há componentes com mais de um ciclo.
Janela crítica () Na vizinhança de , parametrizada por com (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:
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 () Quando : Surge quase certamente um único componente dominante, denominado componente gigante, cuja ordem é linear no número de vértices:
em que a fração é a única raiz positiva da equação transcendente:
Todos os demais componentes conexos permanecem pequenos, com tamanho limitado por . A estrutura do componente gigante torna-se complexa, contendo múltiplos ciclos interligados.
Fase de conexidade () Para , 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:
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 .
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 é estritamente positiva:
então necessariamente deve existir ao menos um grafo com a propriedade .
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 com e eliminando um vértice de cada ciclo curto, Erdős provou a existência de grafos com cintura superior a e número cromático superior a , para quaisquer inteiros .
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 qualquer sentença formulada na linguagem de primeira ordem da teoria dos grafos (utilizando quantificadores , conectivos booleanos e o predicado binário de adjacência ). Se a probabilidade for constante e independente de , então:
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 decresça em certas taxas (como com 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 () e define-se que cada par de vértices possui uma aresta com probabilidade independente , 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 e , existe um vértice que é adjacente a todos os vértices de e a nenhum vértice de . 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 () 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 -regular aleatório, denotado por , é um grafo escolhido uniformemente entre todos os grafos simples -regulares sobre vértices (exigindo que seja par).