Em artigos anteriores, nós mostramos características muito próprias das redes complexas reais: são esparsas, são livres de escala, possuem grupos, são conexas e os caminhos são tipicamente curtos. Conduzimos este estudo com dados de redes complexas publicamente disponíveis na Internet e demonstramos o que cada uma destas características significa.
Além das métricas e da observação destas características em redes dos mais diferentes domínios, a ciência das redes também procura explicar o motivo do aparecimento destas características. Para isso, foram desenvolvidos modelos que, a partir de algoritmos estocásticos, produzem redes que apresentam uma ou mais das características próprias das redes complexas.
As redes aleatórias estão entre os primeiros modelos de redes complexas estudados e já falamos brevemente delas anteriormente.
Embora estas redes não sejam tão representativas de fenômenos encontrados nos sistemas reais, seu estudo é importante porque com uma abordagem simples conseguem capturar algumas das propriedades das redes complexas, servindo de referência para outros modelos de redes. Além disso, estes modelos introduzem o conceito da aleatoriedade, o qual, como será demonstrado neste artigo, é imprescindível aos demais modelos.
O primeiro modelo de rede aleatória que estudaremos é o modelo de Gilbert, que apareceu no trabalho Random Graphs de Edgar N. Gilbert publicado em 1959 no periódico The Annals of Mathematical Statistics.
Neste modelo começamos com uma rede de $n$ nós e nenhum enlace. Em seguida, enumeramos todos os $\frac{n(n-1)}{2}$ enlaces possíveis nesta rede e selecionamos cada um com probabilidade $p$. Cada vez que um enlace é selecionado, ele é adicionado à rede. O processo contrário pode ser feito também, iniciando o grafo com todos os enlaces possíveis e removendo-os com probabilidade $q=1-p$. Os resultados das duas formas são equivalentes.
Vamos então resumir os passos para geração deste modelo. Dado $n$ e $p$
- Inicialmente: geramos $n$ nós, numerados de $0$ a $n-1$.
- Defina $U \sim Uniform(0,1)$ (variável aleatória $U$ uniformemente distribuída)
- Para $i = 0, 1,...,(n-2)$ faça:
- Para $j = (i+1),...,(n-1)$ faça:
- Se U < p, crie a aresta entre $i$ e $j$ (U tem novo valor aleatório a cada iteração)
Considerando o procedimento acima, o número médio de enlaces na rede é $m=p\frac{n(n-1)}{2}$. Desta equação derivamos a densidade média, que é $\frac{2m}{n(n-1)}=\frac{2p\frac{n(n-1)}{2}}{n(n-1)}= p$.
No entanto, a quantidade exata de enlaces em um grafo de Gilbert é incerta. Este fato dificulta a comparação deste tipo de rede com outros modelos, já que se costuma usar a densidade como parâmetro para se produzir redes equivalentes. Assim, as redes de Gilbert não costumam ser utilizadas, sendo preferível o uso de redes de Erdos-Rényi (ER) que possuem uma quantidade de enlaces ajustável e certa, que é o que veremos a seguir.
Diferentemente do Modelo de Gilbert, Erdös e Rényi propuseram em seu trabalho On the evolution of random graphs, publicado em 1960, um modelo de geração de redes que consegue produzir uma rede de densidade especificada, i.e., com um número de enlaces controlado. Assim teremos um número de nós $n$ e um número de enlaces $m$. Por conta de seus parâmetros, o modelo de Gilbert é chamado também de G(n,p) e o modelo ER é chamado de G(n,m).
No modelo ER iniciamos com uma rede de $n$ nós e nenhum enlace. A seguir, adicionamos um enlace ao grafo escolhendo aleatoriamente dois nós diferentes do grafo. Note que no momento da escolha aleatória, cada nó deve possuir igual probabilidade de ser escolhido. Repetimos o processo de adição de enlaces até que a quantidade de enlaces na rede seja igual à $m$.
Observe que apesar dos processos de geração dos modelos serem diferentes, os modelos G(n,p) e G(n,m) são diretamente correlacionados. Dado um modelo G(n,p), um modelo G(n,m) de grau médio e densidade equivalentes pode ser obtido usando o mesmo valor de $n$ e com $m$ dado por $\frac{p(n-1)n}{2}$, arredondado para cima. Por outro lado, dado um modelo G(n,m), pode-se obter um modelo G(n,p) equivalente com o mesmo número de nós e $p$ dado pela densidade da G(n,m). Por conta dessa equivalência, os resultados de análises de um modelo podem ser aplicadas ao outro.
Em um próximo artigo, pretendemos analisar algumas propriedades interessantes destas redes.
Comentários
Postar um comentário