Em nosso último artigo sobre redes aleatórias, vimos que a probabilidade de termos uma rede conexa é muito próxima de 1 mesmo em redes pouco densas (menos de 1%, em redes grandes), e vimos um fenômeno de transição de fase nestas redes quando seu grau médio é próximo de 1. Estes são resultados animadores porque mostram que este modelo, a despeito de sua simplicidade, captura uma propriedade de redes complexas reais que costumam ser conexas mesmo sendo esparsas.
Dando continuidade ao nosso estudo, agora verificaremos se as redes aleatórias também capturam uma outra propriedade das redes complexas reais. Nós sabemos que estas redes são livres de escala, o que significa que a distribuição do grau nestas redes segue uma lei de potência. Isso quer dizer que há uma profunda assimetria entre os graus dos nós que pertencem a estas redes, com muitos nós de grau baixo e poucos nós de grau muito alto. Será que isso também acontece nas redes aleatórias? Será que a simples disposição aleatória de enlaces permite a geração de redes livres de escala?
Primeiramente, é importante estabelecer que em uma rede G(n,m), como $n$ e $m$ são parâmetros para formação da rede fictícia, podemos calcular o grau médio nesta rede diretamente por $\lambda = \frac{2m}{n}$. Já nas redes G(n,p), o grau médio da rede é dado por $\lambda = p(n-1)$.
Este último resultado para redes G(n,p) pode ser obtido considerando que a distribuição do grau na rede G(n,p) se comporta como uma distribuição binomial. Isto é diretamente compreendido, se observarmos o processo de geração desta rede. A adição de cada um dos enlaces à rede é um processo de Bernoulli com probabilidade de sucesso $p$. Como é uma rede G(n,p), podemos perceber que para cada nó da rede testaremos a criação de $n-1$ enlaces, que é a quantidade máxima de enlaces possível para cada nó. Desta forma, a distribuição do grau $P_{GNP}(d_i = k)$ de um nó é dada pela soma de $n-1$ processos de Bernoulli independentes com probabilidade $p$. Esta soma sabemos que seguirá uma distribuição Binomial com parâmetros $n-1$ e $p$. Assim, o grau médio será a média da binomial e a distribuição do grau é dada por
$P_{GNP}(d_i = k) = {n-1\choose k}p^k(1-p)^{n-1-k}$
A figura abaixo demonstra como esta distribuição se ajusta bem à distribuição do grau de uma rede G(n,p). As barras azuis do gráfico são a distribuição do grau de uma rede G(n,p) com 4000 nós e $p=0.01$. Já a linha vermelha é a função de densidade de probabilidade da distribuição binomial com $n=4000$ e $p=0.01$.
Da mesma forma que fizemos para redes G(n,p), podemos obter a distribuição do grau em redes G(n,m) por meio de um procedimento semelhante. Cada vez que uma aresta é adicionada, selecionamos um par de nós aleatoriamente. Sendo assim, podemos dizer que fazemos duas tentativas de escolher um nó, logo há uma probabilidade de $\frac{2}{n}$ (processo de Bernoulli com probabilidade de sucesso $\frac{2}{n}$) de que um determinado nó seja escolhido em uma das tentativas. Este processo é repetido $m$ vezes, e assim podemos observar que obtemos uma Binomial com parâmetros $m$ e $\frac{2}{n}$. Este resultado corrobora o valor do grau médio $\lambda = \frac{2m}{n}$ e mostra que a distribuição do grau é dada por
$P_{GNM}(d_i = k) = {m\choose k}(\frac{2}{n})^k(1-\frac{2}{n})^{m-k}$
Para valores de $n$ muito grandes e grau médio baixo ($n>100$ e $\lambda < 10$), ambas as redes podem ainda ser modeladas por uma distribuição de Poisson, onde $\lambda$ é o grau médio. Assim temos
$P(d_i = k) = \frac{\lambda^k e^{-\lambda}}{k!}$
Como se pode ver, tanto a distribuição binomial como a de Poisson (para as condições solicitadas) são simétricas e não seguem uma lei de potência. Na cauda esquerda temos poucos nós com grau baixo e na cauda da direita os valores do grau são relativamente baixos se comparados aos obtidos nas redes complexas reais. Você deve se lembrar que, em nosso estudo anterior, o grau do Hub em redes reais chegou a ser de 7 a 30 vezes maior do que a média. Enquanto que na rede aleatória mostrada no gráfico, o Hub não chega a ser nem o dobro da média.
Assim, é possível concluir que redes aleatórias não capturam bem a distribuição do grau livre de escala presente em redes reais. Note que isto não implica que estes modelos sejam inúteis. Pelo contrário, os modelos indicam que, do ponto de vista macroscópico, o mecanismo da aleatoriedade não é suficiente para explicar a formação de grandes Hubs em redes complexas e que deve existir um outro mecanismo para explicar este fenômeno. Mas, veremos isso em outro momento.
Comentários
Postar um comentário