Modelo Erdős–Rényi

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


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 o que significa a propriedade para manter quase todos estes 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[editar | editar código-fonte]

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

  • No modelo o G ( n , p ) 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[editar | editar código-fonte]

Um grafo gerado pelo modelo binomial de Erdős e Rényi (p = 0.01)

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 pn2 → ∞ 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 Pn2→ ∞). Por exemplo, se P é a propriedade de ser ligado, ou se P contém propriedade de um ciclo Hamiltiano. 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 extremidades.

Propriedades do G(n, p)[editar | editar código-fonte]

Com a notação abaixo, a representação gráfica no G ( n , p ) tem em média {n \choose 2}p extremidades. 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 n2/3.
  • Se npc > 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 log2(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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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)[editar | editar código-fonte]

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~} \bold{c} \}>1 ,

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

 \det (\bold{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

  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". 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.. Random Graphs. 2nd ed. [S.l.]: Cambridge University Press, 2001. 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". 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.