Modelo Erdős–Rényi

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

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)}$

A graph generated by the binomial model of Erdős and Rényi (p = 0.01)

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

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:

$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₂(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.