Modelo Erdős – Rényi - Erdős–Rényi model
Ciência da rede | ||||
---|---|---|---|---|
Tipos de rede | ||||
Gráficos | ||||
|
||||
Modelos | ||||
|
||||
| ||||
No campo matemático da teoria dos grafos , o modelo Erdős – Rényi é um de dois modelos intimamente relacionados para gerar gráficos aleatórios ou a evolução de uma rede aleatória . Eles foram nomeados em homenagem aos matemáticos húngaros Paul Erdős e Alfréd Rényi , que primeiro introduziram um dos modelos em 1959, enquanto Edgar Gilbert introduziu o outro modelo contemporaneamente e independentemente de Erdős e Rényi. No modelo de Erdős e Rényi, todos os gráficos em um conjunto de vértices fixo com um número fixo de arestas são igualmente prováveis; no modelo introduzido por Gilbert, também chamado de modelo Erdős – Rényi – Gilbert , cada aresta tem uma probabilidade fixa de estar presente ou ausente, independentemente das outras arestas. Esses modelos podem ser usados no método probabilístico para provar a existência de gráficos que satisfazem várias propriedades ou para fornecer uma definição rigorosa do que significa uma propriedade ser válida para quase todos os gráficos.
Definição
Existem duas variantes intimamente relacionadas do modelo de gráfico aleatório Erdős – Rényi.
- No modelo, um grafo é escolhido uniformemente ao acaso a partir da coleção de todos os grafos que possuem nós e arestas. Os nós são considerados rotulados, o que significa que os grafos obtidos entre si pela permutação dos vértices são considerados distintos. Por exemplo, no modelo, há três gráficos de duas arestas em três vértices rotulados (um para cada escolha do vértice do meio em um caminho de duas arestas) e cada um desses três gráficos é incluído com probabilidade .
- No modelo, um gráfico é construído conectando nós rotulados aleatoriamente. Cada aresta é incluída no gráfico com probabilidade , independentemente de todas as outras arestas. De forma equivalente, a probabilidade de gerar cada gráfico que possui nós e arestas é
O comportamento de gráficos aleatórios é frequentemente estudado no caso em que , o número de vértices, tende ao infinito. Embora e possam ser corrigidos neste caso, eles também podem ser funções dependendo de . Por exemplo, a afirmação de que quase todo gráfico em está conectado significa que, conforme tende para o infinito, tende a probabilidade de que um gráfico em vértices com probabilidade de borda esteja conectado .
Comparação entre os dois modelos
O número esperado de arestas em G ( n , p ) é , e pela lei dos grandes números, qualquer gráfico em G ( n , p ) quase certamente terá aproximadamente essas arestas (desde que o número esperado de arestas tenda ao infinito). Portanto, uma heurística aproximada é que se pn 2 → ∞, então G ( n , p ) deve se comportar de forma semelhante a G ( n , M ) à medida que n aumenta.
Para muitas propriedades de gráfico, esse é o caso. Se P é qualquer propriedade de gráfico que é monótona em relação à ordem do subgrafo (o que significa que se A é um subgrafo de B e A satisfaz P , então B irá satisfazer P também), então as afirmações " P vale para quase todos os gráficos em G ( n , p ) "e" P vale para quase todos os gráficos em "são equivalentes (desde que pn 2 → ∞). Por exemplo, isso é válido se P for a propriedade de estar conectado ou se P for a propriedade de conter um ciclo hamiltoniano . No entanto, isso não será necessariamente válido para propriedades não monótonas (por exemplo, a propriedade de ter um número par de arestas).
Na prática, o modelo G ( n , p ) é o mais utilizado atualmente, em parte pela facilidade de análise permitida pela independência das arestas.
Propriedades de G ( n , p )
Com a notação acima, um gráfico em G ( n , p ) tem arestas médias . A distribuição do grau de qualquer vértice particular é binomial :
onde n é o número total de vértices no gráfico. Desde a
esta distribuição é Poisson para grandes n e np = const.
Em um artigo de 1960, Erdős e Rényi descreveram o comportamento de G ( n , p ) muito precisamente para vários valores de p . Seus resultados incluíram:
- Se np <1, então um gráfico em G ( n , p ) quase certamente não terá componentes conectados de tamanho maior do que O (log ( n )).
- Se np = 1, então um gráfico em G ( n , p ) quase certamente terá um maior componente cujo tamanho é da ordem n 2/3 .
- Se np → c > 1, onde c é uma constante, então um gráfico em G ( n , p ) quase certamente terá um componente gigante único contendo uma fração positiva dos vértices. Nenhum outro componente conterá mais do que O (log ( n )) vértices.
- Se , então, um gráfico em G ( n , p ) quase certamente conterá vértices isolados e, portanto, será desconectado.
- Se , então, um gráfico em G ( n , p ) será quase com certeza conectado.
Portanto, é um limite agudo para a conexão de G ( n , p ).
Outras propriedades do gráfico podem ser descritas quase precisamente, já que n tende para o infinito. Por exemplo, existe um k ( n ) (aproximadamente igual a 2log 2 ( n )) tal que o maior clique em G ( n , 0,5) tem quase com certeza o tamanho k ( n ) ou k ( n ) + 1.
Assim, embora encontrar o tamanho do maior clique em um grafo seja NP-completo , o tamanho do maior clique em um grafo "típico" (de acordo com este modelo) é muito bem compreendido.
Os gráficos de borda dupla de gráficos Erdos-Renyi são gráficos com quase a mesma distribuição de grau, mas com correlações de grau e um coeficiente de agrupamento significativamente maior .
Relação com percolação
Na teoria da percolação, examina-se um grafo finito ou infinito e remove arestas (ou links) aleatoriamente. Assim, o processo Erdős – Rényi é, na verdade, uma percolação de elos não ponderada no gráfico completo . (Um se refere à percolação na qual nós e / ou elos são removidos com pesos heterogêneos como percolação ponderada). Como a teoria da percolação tem muitas de suas raízes na física , grande parte da pesquisa feita foi nas redes dos espaços euclidianos. A transição em np = 1 do componente gigante para o componente pequeno tem análogos para esses gráficos, mas para reticulados o ponto de transição é difícil de determinar. Os físicos freqüentemente se referem ao estudo do gráfico completo como uma teoria de campo médio . Assim, o processo Erdős – Rényi é o caso do campo médio da percolação.
Algum trabalho significativo também foi feito na percolação em gráficos aleatórios. Do ponto de vista do físico, ainda seria um modelo de campo médio, de modo que a justificativa da pesquisa costuma ser formulada em termos da robustez do gráfico, visto como uma rede de comunicação. Dado um gráfico aleatório de n ≫ 1 nós com um grau médio . Remova aleatoriamente uma fração de nós e deixe apenas uma fração da rede. Existe um limite crítico de percolação abaixo do qual a rede se torna fragmentada, enquanto acima existe um componente conectado gigante de ordem n . O tamanho relativo do componente gigante, P ∞ , é dado por
Ressalvas
Ambas as duas principais suposições do modelo G ( n , p ) (que as arestas são independentes e que cada aresta é igualmente provável) podem ser inadequadas para modelar certos fenômenos da vida real. Os gráficos Erdős – Rényi têm baixo agrupamento, ao contrário de muitas redes sociais. Algumas alternativas de modelagem incluem o modelo Barabási – Albert e o modelo Watts e Strogatz . Esses modelos alternativos não são processos de percolação, mas representam um modelo de crescimento e religação, respectivamente. Um modelo para interagir com redes Erdős – Rényi foi desenvolvido recentemente por Buldyrev et al.
História
O modelo G ( n , p ) foi introduzido pela primeira vez por Edgar Gilbert em um artigo de 1959 estudando o limite de conectividade mencionado acima. O modelo G ( n , M ) foi introduzido por Erdős e Rényi em seu artigo de 1959. Como com Gilbert, suas primeiras investigações foram quanto à conectividade de G ( n , M ), com a análise mais detalhada seguindo em 1960.
Veja também
- Gráfico Rado - gráfico infinito contendo todos os gráficos contáveis, o gráfico formado pela extensão do modelo G ( n , p ) para gráficos com um número infinito contável de vértices. Ao contrário do caso finito, o resultado desse processo infinito é (com probabilidade 1 ) o mesmo gráfico, até o isomorfismo.
- Evolução de fase dupla - o processo que conduz a auto-organização em sistemas adaptativos complexos descreve as maneiras pelas quais as propriedades associadas ao modelo Erdős – Rényi contribuem para o surgimento de ordem nos sistemas.
- Os modelos de gráfico aleatório exponencial descrevem uma distribuição de probabilidade geral de gráficos em "n" nós dados um conjunto de estatísticas de rede e vários parâmetros associados a eles.
- Modelo de bloco estocástico , uma generalização do modelo Erdős – Rényi para gráficos com estrutura de comunidade latente
- Modelo Watts-Strogatz
- Modelo Barabási-Albert
Referências
Literatura
- West, Douglas B. (2001). Introdução à Teoria de Grafos (2ª ed.). Prentice Hall. ISBN 0-13-014400-2.
- Newman, MEJ (2010). Redes: uma introdução . Oxford.
- Reuven Cohen e Shlomo Havlin (2010). Redes Complexas: Estrutura, Robustez e Função . Cambridge University Press.