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).

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 $\frac{1}{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{)}^{((\genfrac{}{}{0ex}{}{n}{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^{(\genfrac{}{}{0ex}{}{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

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)$ é $(\genfrac{}{}{0ex}{}{n}{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=(\genfrac{}{}{0ex}{}{n}{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,(\genfrac{}{}{0ex}{}{n}{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 $(\genfrac{}{}{0ex}{}{n}{2})p$ arestas. A distribuição do grau de qualquer vértice é binomial:

$P(\mathrm{deg}(v)=k)=(\genfrac{}{}{0ex}{}{n-1}{k})p^k(1-p{)}^{n-1-k},$

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

$P(\mathrm{deg}(v)=k)\to \frac{(np{)}^k{\mathrm{e}}^{-np}}{k!}\text{ as }n\to \mathrm{\infty }\text{ and }np=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t},$

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

Num artigo de 1960, Erdős e Rényi 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<\frac{(1-ϵ)\ln n}{n}$, então o grafo em $G(n,p)$ certamente contem vértices isolados, e, assim, ser desligada.

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

$\frac{\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^{\prime }$ a partir da rede. Existe um limiar de percolação crítico $p{\text{'}}_c=\frac{1}{⟨k⟩}$ abaixo do qual a rede torna-se fragmentada enquanto acima de $p{\text{'}}_c$ um componente ligado de grandes dimensões de ordem $n$ existe. O tamanho relativo do componente gigante, P ∞, é dada pela

$P_{\mathrm{\infty }}=p^{\prime }[1-\exp (-⟨k⟩P_{\mathrm{\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.

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{E}\mathrm{i}\mathrm{g}\mathrm{e}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}\mathrm{s}\mathrm{o}\mathrm{f}𝐜\}>1$,

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

$\det (\mathrm{𝟏}\mathbf{-}𝐜)=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.

Predefinição:Referências