Modelo Erdős–Rényi

Na teoria de grafos, o modelo Erdõs-Rényi é um dos dois modelos estritamente relacionados para gerar grafos aleatórios, que inclui o limite entre cada par de nós com igual probabilidade, independentemente das extremidades. O nome do modelo surgiu dos matemáticos Paul Erdős e Alfréd Rényi, que primeiro introduziram um dos dois modelos em 1959, o outro modelo foi introduzido de forma independente e contemporânea por Edgar Gilbert. Estes modelos podem ser utilizados nos métodos probabilísticos para provar a existência dos grafos de forma a satisfazer várias propriedades, ou fornecer definição rigorosa do que significa uma propriedade manter-se para quase todos os grafos.

Hoje em dia existe um grande número de modelos para estruturar redes. Alguns desses modelos são mecanismos, significando que codificam uma série de regras matemáticas e consegue-se produzir certo tipo de redes. A finalidade destes modelos é frequentemente representada por certas relações de causa e efeito. Normalmente, esses modelos têm um único mecanismo dominante, projetado para produzir certos tipos específicos de topologias padrão.O tipo mais comum de modelo grafo aleatório é o modelo Erdős-Rényi (muitas vezes designado por grafo de Poisson aleatório ou grafo aleatório Binomial).^[1]

Definição

Existem duas variantes relacionados do modelo de grafos aleatórios Erdős-Rényi (ER).

No modelo o $G(n,M)$ grafo é escolhido de forma uniforme aleatória da coleção de todos os grafos o qual tem nós e extremidades. Por exemplo, no modelo $G(3,2)$ cada uma das três possibilidades de grafos de três vértices e duas extremidades são incluídos com uma probabilidade ${1 \over 3}$ .
No modelo $G(n,p)$ , o grafo é construído por nós ligados aleatoriamente. Cada extremidade é incluída no grafo com a probabilidade independentemente de todas as outras extremidades. De forma equivalente, todos os grafos com nós e extremidades têm probabilidade igual a

$p^{M}(1-p)^{({n \choose 2}-M)}$

O parâmetro $p$ neste modelo pode ser pensado como a função ponderada; como $p$ aumenta de $0$ até $1$ o modelo torna-se muito mais susceptível a incluir grafos com mais extremidades e muito menos susceptível de incluir com menos extremidades. Em particular, o caso $p=0{,}5$ corresponde ao caso onde todos $2^{\binom {n}{2}}$ grafos nos vértices são escolhidos com igual probabilidades. O comportamento dos grafos aleatórios são muitas vezes desproporcionados no caso o $n$ é número de vértices, que tende para infinito. Apesar $p$ e $M$ poderem ser fixos neste caso, também podem ser funções dependentes de $n$ . Quase todos os grafos com $G(n,2ln(n)/n)$ estão interligados.

Significa que,

como $n$ tende para infinito, a probabilidade deste grafo nos $n$ vértices com extremidades e probabilidade $2\ln(n)/n$ é ligada, tende para $1$ .

Comparação entre os dois modelos

O número esperado de extremidades em $G(n,p)$ é ${n \choose 2}p$ demonstrada pela lei dos grandes números em que qualquer grafo $G(n,p)$ tem aproximadamente muitas extremidades (desde que o número esperado de extremidades tenda para infinito). Por conseguinte, uma heurística se pn² → ∞ deve comportar-se de forma semelhante a $G(n,M)$ com o $M={n \choose 2}p$ como $n$ aumenta. Para muitas propriedades do grafo. Se P é qualquer propriedade que é função monótona de um grafo em relação ao sub grafo ordenado (significa que, se A é um sub grafo de B e A satisfaz P então B satisfará P), então na afirmação “ P vale para quase todos os grafos na $G(n,p)$ ” e “ P vale para quase todos os grafos em que $G(n,{n \choose 2}p)$ ” são equivalentes (previsto Pn²→ ∞). Por exemplo, se P é a propriedade de ser ligado, ou se P contém propriedade de um ciclo Hamiltoniano. No entanto, isto não é necessariamente para assegurar as propriedades de funções não-monótonas (por exemplo, a propriedade de possuir um número par de extremidades). Na prática, o modelo $G(n,p)$ é mais vulgarmente utilizado nos dias de hoje, em parte, devido à facilidade de análise autorizado pela independência das arestas.

Propriedades do G(n, p)

Com a notação abaixo, a representação gráfica no $G(n,p)$ tem em média ${n \choose 2}p$ arestas. A distribuição do grau de qualquer vértice é binomial:^[2]

P(\operatorname {deg} (v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},

Onde $n$ é o número total de vértices na representação do grafo. Desde

P(\operatorname {deg} (v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!}}\quad {\mbox{ as }}n\to \infty {\mbox{ and }}np=\mathrm {const} ,

Esta distribuição é designada por distribuição Poisson para $n$ grande e $np=const.$

Num artigo de 1960, Erdős e Rényi^[3] descreveram o comportamento de $G(n,p)$ muito preciso para vários valores de $p.$ Estes resultados incluíam:

Se $np<1$ então o grafo em $G(n,p)$ certamente não têm componentes ligados de tamanho maior do que $O(log(n))$ .

Se $np=1$ então o grafo em $G(n,p)$ certamente têm um maior componente cujo tamanho é da ordem n^2/3.

Se np → c > 1, onde $c$ é a constante, então o grafo no $G(n,p)$ certamente tem um único componente gigante que contem uma fracção positiva dos vértices. Nenhum outro componente irá conter mais de $O(log(n))$ vértices.

Se $p<{\tfrac {(1-\epsilon )\ln n}{n}}$ , então o grafo em $G(n,p)$ certamente contem vértices isolados, e, assim, ser desligada.

Se $p>{\tfrac {(1+\epsilon )\ln n}{n}}$ , então o grafo em $G(n,p)$ praticamente certo que será ligado.

${\tfrac {\ln n}{n}}$ trata-se de um limiar para a ligação acentuada de $G(n,p)$ .

Outras propriedades do grafo podem ser descritas com precisão com $n$ a tender para o infinito. Por exemplo, existe um $k(n)$ (aproximadamente igual a 2 log₂(n)) de tal modo que o maior clique em $G(n{,}0.5)$ tem quase certamente qualquer tamanho $k(n)$ ou $k(n)+1$ .

Teoria da Percolação

A teoria de percolação examina um grafo finito ou infinito e elimina extremidades (ou ligações) de forma aleatória. Assim, o processo "Erdős-Rényi" é, de facto, uma ligação não ponderada de percolação no grafo completo. (Um refere-se à percolação em que os nós e/ou ligações são eliminados com pesos heterogéneos como percolação ponderada). Como a teoria de percolação tem muito das suas origens na física, grande parte da pesquisa feita foi sobre malhas em espaços euclidianos. A transição a partir do qual $np=1$ os grafos com componente de maiores dimensões é análogo ao componente de pequenas dimensões, mas para malhas o ponto de transição é difícil de determinar. Os físicos muitas vezes referem-se ao estudo da grafo completo como uma teoria de campo médio. Assim, o processo Erdős-Rényi é o caso mean-field de percolação. Alguns trabalhos significativos também foram feitos sobre percolação em grafos aleatórios. De um ponto de vista físico este ainda seria um modelo de mean-field, de modo a justificação da pesquisa ser muitas vezes formulada em termos da robustez do grafo, visto como uma rede de comunicação. Dado um grafo aleatório de n ≫ 1 os nós com um grau médio <k>. Elimina aleatoriamente uma fracção 1 − p′ de nós e deixar apenas uma fracção $p'$ a partir da rede. Existe um limiar de percolação crítico $p'_{c}={\tfrac {1}{\langle k\rangle }}$ abaixo do qual a rede torna-se fragmentada enquanto acima de $p'_{c}$ um componente ligado de grandes dimensões de ordem $n$ existe. O tamanho relativo do componente gigante, P ∞, é dada pela^[4] ^[5]^[6]^[7]

P_{\infty }=p'[1-\exp(-\langle k\rangle P_{\infty })].\,

Pressupostos

Ambas hipóteses principais do modelo (extremidades que são independentes e cada lado que é igual probabilidade) pode ser inadequado para a modelação de fenómenos reais. Em particular, um grafo Erdős-Rényi não tem pontas pesadas, como acontece em muitas redes reais. Além disso, tem baixo agrupamento, ao contrário de muitas redes sociais. Para obter alternativas a modelação populares, existe Barabási-Albert e modelo Watts e Strogatz . Note-se que estes modelos alternativos não são processos de percolação, mas representam um modelo de crescimento e de interligação, respetivamente.^[8]

História

O modelo G(n,p) foi introduzido por Edgar Gilbert num artigo em 1959, que estudou o limite de ligação mencionado acima. O modelo G(n,M) foi introduzido por Erdős e Rényi no seu artigo em 1959. Tal como acontece com Gilbert, as suas primeiras investigações foram como a ligação de G(n,M), com análise seguinte mais detalhada, em 1960.

Interação Erdős-Rényi Modelo Grafos Aleatórios (comunidades de redes ER)

Uma simples generalização do modelo (ER) de grafo aleatório aplica-se como apresentado a seguir. Deixe o conjunto de nós n ser dividido em comunidades q, composto por $n^{(1)},...,n^{(q)}$ cada nó, com $\sum _{l}n^{(l)}=n$ , e deixar que seja dada a seguinte matriz q x q de probabilidades $p^{(l,m)}$ de ligação entre qualquer nó da comunidade l com qualquer outro nó da comunidade m (possivelmente com l = m)

p^{(l,m)}={\frac {c^{(l,m)}}{n}}

,

onde $c^{(l,m)}$ é por sua vez uma matriz q x q não negativa que satisfaz o equilíbrio detalhado

n^{(l)}c^{(l,m)}=c^{(l,m)}n^{(m)}

.

Ao usar essa construção percebe-se uma generalização do grafo aleatório ER onde $c^{(l,m)}$ representa a matriz de ligações médias entre a comunidade l e a comunidade m, as auto-casos l = m sendo aqueles onde nós recuperamos a rede ER único (q=1). É possível provar que tal comunidade de redes de ER está a filtrar quando satisfaz a matriz $c^{(l,m)}$

\max\{\mathrm {Eigenvalues~of~} \mathbf {c} \}>1

,

que, em particular, significa que a percolação "limiar" é realmente agora uma superfície dada pela seguinte equação.

\det(\mathbf {1-c} )=0

.

Ao contrário do caso q = 1 (onde nós recuperamos o limiar de percolação c = 1, ver acima) esta equação pode ter várias soluções e, em geral, o número de soluções podem crescer mais rapidamente do que n.

Referências

↑ Aaron Clauset, Inference, Models and Simulation for Complex Systems,Lecture 13, CSCI 7000-001, 18 October 2011
↑ Newman, Mark. E. J.; S. H. Strogatz and D. J. Watts (2001). «Random graphs with arbitrary degree distributions and their applications». Physical Review E. 64 (026118). doi:10.1103/PhysRevE.64.026118 ,
↑ Erdős, Paul; A. Rényi (1960). «On the evolution of random graphs» (PDF). Publications of the Mathematical Institute of the Hungarian Academy of Sciences. 5: 17–61 The probability p used here refers there to $N(n)={n \choose 2}p$
↑ Bollobás, B. (2001). Random Graphs 2nd ed. [S.l.]: Cambridge University Press. ISBN 0-521-79722-5
↑ Bollobás, B.; Erdős, P. (1976). «Cliques in Random Graphs». Math. Proc. Cambridge Phil. Soc. 80 (3): 419–427. doi:10.1017/S0305004100053056
↑ Erdős, P.; Rényi, A. (1959). «On Random Graphs. I» (PDF). Publicationes Mathematicae. 6: 290–297
↑ Erdős, P.; Rényi, A. (1960). «The Evolution of Random Graphs». Magyar Tud. Akad. Mat. Kutató Int. Közl. 5: 17–61
↑ S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin (2010). «Catastrophic cascade of failures in interdependent networks». Nature. 464 (7291): 1025–8. doi:10.1038/nature08932

[1] Aaron Clauset, Inference, Models and Simulation for Complex Systems,Lecture 13, CSCI 7000-001, 18 October 2011

[2] Newman, Mark. E. J.; S. H. Strogatz and D. J. Watts (2001). «Random graphs with arbitrary degree distributions and their applications». Physical Review E. 64 (026118). doi:10.1103/PhysRevE.64.026118 ,

[3] Erdős, Paul; A. Rényi (1960). «On the evolution of random graphs» (PDF). Publications of the Mathematical Institute of the Hungarian Academy of Sciences. 5: 17–61 The probability p used here refers there to $N(n)={n \choose 2}p$

[4] Bollobás, B. (2001). Random Graphs 2nd ed. [S.l.]: Cambridge University Press. ISBN 0-521-79722-5

[5] Bollobás, B.; Erdős, P. (1976). «Cliques in Random Graphs». Math. Proc. Cambridge Phil. Soc. 80 (3): 419–427. doi:10.1017/S0305004100053056

[6] Erdős, P.; Rényi, A. (1959). «On Random Graphs. I» (PDF). Publicationes Mathematicae. 6: 290–297

[7] Erdős, P.; Rényi, A. (1960). «The Evolution of Random Graphs». Magyar Tud. Akad. Mat. Kutató Int. Közl. 5: 17–61

[8] S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin (2010). «Catastrophic cascade of failures in interdependent networks». Nature. 464 (7291): 1025–8. doi:10.1038/nature08932

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]