Gráfico aleatório - Random graph

Em matemática , gráfico aleatório é o termo geral para se referir a distribuições de probabilidade sobre gráficos . Os gráficos aleatórios podem ser descritos simplesmente por uma distribuição de probabilidade ou por um processo aleatório que os gera. A teoria dos gráficos aleatórios encontra-se na interseção entre a teoria dos grafos e a teoria da probabilidade . De uma perspectiva matemática, gráficos aleatórios são usados para responder a perguntas sobre as propriedades de gráficos típicos . Suas aplicações práticas são encontradas em todas as áreas nas quais redes complexas precisam ser modeladas - muitos modelos de grafos aleatórios são, portanto, conhecidos, espelhando os diversos tipos de redes complexas encontradas em diferentes áreas. Em um contexto matemático, gráfico aleatório refere-se quase exclusivamente ao modelo de gráfico aleatório Erdős – Rényi . Em outros contextos, qualquer modelo de gráfico pode ser referido como um gráfico aleatório .

Modelos

Um grafo aleatório é obtido começando com um conjunto de n vértices isolados e adicionando arestas sucessivas entre eles aleatoriamente. O objetivo do estudo neste campo é determinar em que estágio uma propriedade particular do gráfico pode surgir. Diferentes modelos de gráficos aleatórios produzem diferentes distribuições de probabilidade nos gráficos. O mais comumente estudado é aquele proposto por Edgar Gilbert , denotado G ( n , p ), em que toda aresta possível ocorre independentemente com probabilidade 0 < p <1. A probabilidade de obter qualquer gráfico aleatório particular com m arestas é com a notação . ${\ displaystyle p ^ {m} (1-p) ^ {Nm}}$ ${\ displaystyle N = {\ tbinom {n} {2}}}$

Um modelo intimamente relacionado, o modelo Erdős – Rényi denotado G ( n , M ), atribui probabilidade igual a todos os gráficos com exatamente M arestas. Com 0 ≤ M ≤ N , G ( n , M ) possui elementos e cada elemento ocorre com probabilidade . O último modelo pode ser visto como um instantâneo em um determinado momento ( M ) do processo de gráfico aleatório , que é um processo estocástico que começa com n vértices e sem arestas, e em cada etapa adiciona uma nova aresta escolhida uniformemente a partir do conjunto de bordas ausentes. ${\ displaystyle {\ tbinom {N} {M}}}$ ${\ displaystyle 1 / {\ tbinom {N} {M}}}$ ${\ displaystyle {\ tilde {G}} _ {n}}$

Se, em vez disso, começarmos com um conjunto infinito de vértices e, novamente, deixarmos cada aresta possível ocorrer independentemente com probabilidade 0 < p <1, obteremos um objeto G chamado de gráfico aleatório infinito . Exceto nos casos triviais quando p é 0 ou 1, tal G quase certamente tem a seguinte propriedade:

Dados quaisquer n + m elementos , há um vértice c em V que é adjacente a cada um e não é adjacente a nenhum deles . ${\ displaystyle a_ {1}, \ ldots, a_ {n}, b_ {1}, \ ldots, b_ {m} \ in V}$ ${\ displaystyle a_ {1}, \ ldots, a_ {n}}$ ${\ displaystyle b_ {1}, \ ldots, b_ {m}}$

Acontece que se o conjunto de vértices é contável então existe, até o isomorfismo , apenas um único grafo com esta propriedade, ou seja, o grafo Rado . Assim, qualquer gráfico aleatório infinito contável é quase certamente o gráfico Rado, que por essa razão às vezes é chamado simplesmente de gráfico aleatório . No entanto, o resultado análogo não é verdadeiro para gráficos incontáveis, dos quais existem muitos gráficos (não isomórficos) que satisfazem a propriedade acima.

Outro modelo, que generaliza o modelo de gráfico aleatório de Gilbert, é o modelo de produto escalar aleatório . Um gráfico de produto escalar aleatório associa a cada vértice um vetor real . A probabilidade de uma aresta uv entre quaisquer vértices u e v é alguma função do produto escalar u • v dos respectivos vetores.

A matriz de probabilidade da rede modela gráficos aleatórios por meio de probabilidades de borda, que representam a probabilidade de que uma determinada borda exista por um período de tempo especificado. Este modelo é extensível para direcionado e não direcionado; ponderado e não ponderado; e estrutura de gráficos estáticos ou dinâmicos. ${\ displaystyle p_ {i, j}}$ ${\ displaystyle e_ {i, j}}$

Para M ≃ pN , onde N é o número máximo de arestas possíveis, os dois modelos mais usados, G ( n , M ) e G ( n , p ), são quase intercambiáveis.

Os gráficos regulares aleatórios formam um caso especial, com propriedades que podem diferir dos gráficos aleatórios em geral.

Uma vez que temos um modelo de gráficos aleatórios, cada função nos gráficos torna-se uma variável aleatória . O estudo desse modelo é determinar se, ou pelo menos estimar a probabilidade de que uma propriedade possa ocorrer.

Terminologia

O termo 'quase todos' no contexto de gráficos aleatórios refere-se a uma sequência de espaços e probabilidades, de modo que as probabilidades de erro tendem a zero.

Propriedades

A teoria dos gráficos aleatórios estuda as propriedades típicas dos gráficos aleatórios, aquelas que se mantêm com alta probabilidade para gráficos desenhados a partir de uma distribuição particular. Por exemplo, podemos pedir um determinado valor de e qual é a probabilidade de que esteja conectado . Ao estudar essas questões, os pesquisadores muitas vezes se concentram no comportamento assintótico de gráficos aleatórios - os valores para os quais as várias probabilidades convergem à medida que aumentam muito. A teoria da percolação caracteriza a conexão de gráficos aleatórios, especialmente os infinitamente grandes. ${\ displaystyle n}$ ${\ displaystyle p}$ ${\ displaystyle G (n, p)}$ ${\ displaystyle n}$

A percolação está relacionada à robustez do grafo (também chamada de rede). Dado um gráfico aleatório de nós e um grau médio . Em seguida, removemos aleatoriamente uma fração de nós e deixamos apenas uma fração . Existe um limite crítico de percolação abaixo do qual a rede se torna fragmentada, enquanto acima existe um componente conectado gigante. ${\ displaystyle n}$ ${\ displaystyle \ langle k \ rangle}$ ${\ displaystyle 1-p}$ ${\ displaystyle p}$ ${\ displaystyle p_ {c} = {\ tfrac {1} {\ langle k \ rangle}}}$ ${\ displaystyle p_ {c}}$

A percolação localizada refere-se à remoção de um nó de seus vizinhos, vizinhos próximos mais próximos etc. até que uma fração de nós da rede seja removida. Foi mostrado que para o gráfico aleatório com distribuição de graus de Poisson exatamente como para a remoção aleatória. Para outros tipos de distribuições de grau para ataque localizado é diferente de ataque aleatório (funções de limiar, evolução de ) ${\ displaystyle 1-p}$ ${\ displaystyle p_ {c} = {\ tfrac {1} {\ langle k \ rangle}}}$ ${\ displaystyle p_ {c}}$ ${\ displaystyle {\ tilde {G}}}$

Grafos aleatórios são amplamente utilizados no método probabilístico , onde se tenta provar a existência de grafos com certas propriedades. A existência de uma propriedade em um gráfico aleatório pode muitas vezes implicar, por meio do lema de regularidade de Szemerédi , a existência dessa propriedade em quase todos os gráficos.

Em gráficos regulares aleatórios , são o conjunto de gráficos -regulares com tais que e são os números naturais , e são pares. ${\ displaystyle G (n, r-reg)}$ ${\ displaystyle r}$ ${\ displaystyle r = r (n)}$ ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle 3 \ leq r <n}$ ${\ displaystyle rn = 2m}$

A sequência de grau de um gráfico em depende apenas do número de arestas nos conjuntos ${\ displaystyle G}$ ${\ displaystyle G ^ {n}}$

{\ displaystyle V_ {n} ^ {(2)} = \ left \ {ij \: \ 1 \ leq j \ leq n, i \ neq j \ right \} \ subset V ^ {(2)}, \ qquad i = 1, \ cdots, n.}

Se as arestas, em um gráfico aleatório, forem grandes o suficiente para garantir que quase todos tenham grau mínimo de pelo menos 1, então quase todos estão conectados e, se forem pares, quase todos têm uma correspondência perfeita. Em particular, no momento em que o último vértice isolado desaparece em quase todos os gráficos aleatórios, o gráfico torna-se conectado. ${\ displaystyle M}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle n}$ ${\ displaystyle G_ {M}}$

Quase todo grafo processa em um número par de vértices com a aresta elevando o grau mínimo para 1 ou um grafo aleatório com um pouco mais que arestas e com probabilidade próxima de 1 garante que o grafo tenha uma correspondência completa, com exceção de no máximo um vértice . ${\ displaystyle {\ tfrac {n} {4}} \ log (n)}$

Para alguma constante , quase todo gráfico rotulado com vértices e pelo menos arestas é hamiltoniano . Com a probabilidade tendendo para 1, a aresta particular que aumenta o grau mínimo para 2 torna o gráfico Hamiltoniano. ${\ displaystyle c}$ ${\ displaystyle n}$ ${\ displaystyle cn \ log (n)}$

As propriedades do gráfico aleatório podem mudar ou permanecer invariáveis sob as transformações do gráfico. Mashaghi A. et al., Por exemplo, demonstrou que uma transformação que converte gráficos aleatórios em seus gráficos de borda dupla (ou gráficos de linha) produz um conjunto de gráficos com quase a mesma distribuição de grau, mas com correlações de grau e um agrupamento significativamente maior coeficiente.

Coloração

Dado um grafo aleatório G de ordem n com o vértice V ( G ) = {1, ..., n }, pelo algoritmo guloso sobre o número de cores, os vértices podem ser coloridos com as cores 1, 2, ... (o vértice 1 tem a cor 1, o vértice 2 tem a cor 1 se não for adjacente ao vértice 1, caso contrário, tem a cor 2, etc.). O número de cores adequadas de gráficos aleatórios dado um número de cores q , chamado de polinômio cromático , permanece desconhecido até agora. O escalonamento de zeros do polinômio cromático de gráficos aleatórios com parâmetros ne o número de arestas m ou a probabilidade de conexão p foi estudado empiricamente usando um algoritmo baseado em casamento de padrões simbólicos.

Árvores aleatórias

Uma árvore aleatória é uma árvore ou arborescência formada por um processo estocástico . Em uma grande variedade de gráficos aleatórios de ordem ne tamanho M ( n ), a distribuição do número de componentes da árvore de ordem k é assintoticamente Poisson . Tipos de árvores aleatórias incluem árvore uniforme spanning , árvore de extensão mínima aleatório , árvore binária aleatória , Treap , rapidamente explorar árvore aleatório , árvore browniano , e Floresta aleatória .

Gráficos aleatórios condicionais

Considere um dado modelo de gráfico aleatório definido no espaço de probabilidade e seja uma função de valor real que atribui a cada gráfico em um vetor de m propriedades. Para um gráfico aleatório condicional fixo , são modelos nos quais a medida de probabilidade atribui probabilidade zero a todos os gráficos de tal forma que ' . ${\ displaystyle (\ Omega, {\ mathcal {F}}, P)}$ ${\ displaystyle {\ mathcal {P}} (G): \ Omega \ rightarrow R ^ {m}}$ ${\ displaystyle \ Omega}$ ${\ displaystyle \ mathbf {p} \ in R ^ {m}}$ ${\ displaystyle P}$ ${\ displaystyle {\ mathcal {P}} (G) \ neq \ mathbf {p}}$

Casos especiais são gráficos aleatórios condicionalmente uniformes , onde atribui probabilidade igual a todos os gráficos com propriedades especificadas. Eles podem ser vistos como uma generalização do modelo Erdős – Rényi G ( n , M ), quando a informação condicionante não é necessariamente o número de arestas M , mas qualquer outra propriedade arbitrária do grafo . Neste caso, poucos resultados analíticos estão disponíveis e a simulação é necessária para obter distribuições empíricas das propriedades médias. ${\ displaystyle P}$ ${\ displaystyle {\ mathcal {P}} (G)}$

Gráficos interdependentes

Em gráficos interdependentes, os nós de uma rede (gráfico) dependem de outras redes para funcionar. Portanto, falhas em um ou vários gráficos induzem falhas em cascata entre os gráficos, o que pode levar a um colapso abrupto.

História

O primeiro uso de um modelo de gráfico aleatório foi por Helen Hall Jennings e Jacob Moreno em 1938, onde um "sociograma casual" (um modelo Erdős-Rényi direcionado) foi considerado no estudo de comparação da fração de links recíprocos em seus dados de rede com o modelo aleatório . Outro uso, sob o nome de "rede aleatória", foi por Solomonoff e Rapoport em 1951, usando um modelo de grafos direcionados com grau de saída fixo e anexos escolhidos aleatoriamente a outros vértices.

O modelo Erdős – Rényi de gráficos aleatórios foi definido pela primeira vez por Paul Erdős e Alfréd Rényi em seu artigo de 1959 "On Random Graphs" e independentemente por Gilbert em seu artigo "Random graphs".

Languages

In other projects