Modelo Erdős–Rényi

Ciência da Rede
Teoria
Grafo Rede complexa Contágio Redes de pequeno mundo Scale-free Estrutura comunitária Percolação Evolução Difusão de inovações (redes sociais) Controlabilidade Desenho grafo Capital social Análise de links Otimização Reciprocidade Transitividade Ligação preferencial Teoria do equilíbrio Efeito de rede Influência social
Tipos de Rede
Rede de computadores Telecomunicação Rede social Neural Artificial Interdependente Semântico Dependência Fluxo
Grafos
Caraterísticas Clique Componente Corte Ciclo Estrutura de dados Aresta Laço Vizinhança Caminho Vértice Lista de adjacência / matriz Incidência Lista / matrix Tipos Grafo bipartido Grafo completo Grafo orientado Hipergrafo Multigrafo Aleatórios Ponderado
Métricas & Algoritmos
Centralidade Grau Betweenness Proximidade PageRank Clustering Centralidades Baseadas na Dissimilaridades Distribuição de Graus Correlação de Graus Assortatividade Distância Modularidade
Modelos
Grafo Aleatório Erdös–Rényi Barabási–Albert Watts–Strogatz Exponencial Aleatório (ERGM) Epidemia Hierárquica
Categorias
Teoria dos grafos Teoria das redes complexas
v d e

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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle {1 \over 3}}$.
• No modelo ${\displaystyle 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

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

O parâmetro ${\displaystyle p}$ neste modelo pode ser pensado como a função ponderada; como ${\displaystyle p}$ aumenta de ${\displaystyle 0}$ até ${\displaystyle 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 ${\displaystyle p=0{,}5}$ corresponde ao caso onde todos ${\displaystyle 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 ${\displaystyle n}$ é número de vértices, que tende para infinito. Apesar ${\displaystyle p}$ e ${\displaystyle M}$ poderem ser fixos neste caso, também podem ser funções dependentes de ${\displaystyle n}$. Quase todos os grafos com ${\displaystyle G(n,2ln(n)/n)}$ estão interligados.

Significa que,

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

Comparação entre os dois modelos

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

O número esperado de extremidades em ${\displaystyle G(n,p)}$ é ${\displaystyle {n \choose 2}p}$ demonstrada pela lei dos grandes números em que qualquer grafo ${\displaystyle 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^2 → ∞ deve comportar-se de forma semelhante a ${\displaystyle G(n,M)}$ com o ${\displaystyle M={n \choose 2}p}$ como ${\displaystyle 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 ${\displaystyle G(n,p)}$ ” e “ P vale para quase todos os grafos em que ${\displaystyle G(n,{n \choose 2}p)}$” são equivalentes (previsto Pn^2→ ∞). 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 ${\displaystyle 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 ${\displaystyle G(n,p)}$ tem em média ${\displaystyle {n \choose 2}p}$ arestas. A distribuição do grau de qualquer vértice é binomial:[2]

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

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

${\displaystyle 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 ${\displaystyle n}$ grande e ${\displaystyle np=const.}$

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

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

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

• Se np → c > 1, onde ${\displaystyle c}$ é a constante, então o grafo no ${\displaystyle 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 ${\displaystyle O(log(n))}$ vértices.

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

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

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

Outras propriedades do grafo podem ser descritas com precisão com ${\displaystyle n}$ a tender para o infinito. Por exemplo, existe um ${\displaystyle k(n)}$ (aproximadamente igual a 2 log₂(n)) de tal modo que o maior clique em ${\displaystyle G(n{,}0.5)}$ tem quase certamente qualquer tamanho ${\displaystyle k(n)}$ ou ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle p'}$ a partir da rede. Existe um limiar de percolação crítico ${\displaystyle p'_{c}={\tfrac {1}{\langle k\rangle }}}$ abaixo do qual a rede torna-se fragmentada enquanto acima de ${\displaystyle p'_{c}}$ um componente ligado de grandes dimensões de ordem ${\displaystyle n}$ existe. O tamanho relativo do componente gigante, P ∞, é dada pela[4] [5][6][7]

${\displaystyle 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 ${\displaystyle n^{(1)},...,n^{(q)}}$ cada nó, com ${\displaystyle \sum _{l}n^{(l)}=n}$, e deixar que seja dada a seguinte matriz q x q de probabilidades ${\displaystyle p^{(l,m)}}$ de ligação entre qualquer nó da comunidade l com qualquer outro nó da comunidade m (possivelmente com l = m)

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

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

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle c^{(l,m)}}$

${\displaystyle \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.

${\displaystyle \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

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  A referência emprega parâmetros obsoletos |coautor= (ajuda),
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  A referência emprega parâmetros obsoletos |coautor= (ajuda) The probability p used here refers there to ${\displaystyle 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  A referência emprega parâmetros obsoletos |coautor= (ajuda)
6. Erdős, P.; Rényi, A. (1959). «On Random Graphs. I» (PDF). Publicationes Mathematicae. 6: 290–297  A referência emprega parâmetros obsoletos |coautor= (ajuda)
7. Erdős, P.; Rényi, A. (1960). «The Evolution of Random Graphs». Magyar Tud. Akad. Mat. Kutató Int. Közl. 5: 17–61  A referência emprega parâmetros obsoletos |coautor= (ajuda)
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  !CS1 manut: Nomes múltiplos: lista de autores (link)