# 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 ${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$^2$ → ∞ 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$^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 $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:
    $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 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$_2$(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
    $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.

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