Redes livre de escala

Até o momento, os modelos de redes que estudamos (modelo GWS e modelos G(n,m) e G(n, p)) padecem de uma limitação quanto à distribuição do grau. O que ocorre é que, em redes reais, a distribuição do grau segue uma lei de potência (power law) da forma $P(d_i=k)=k^{-\alpha}$ com $2\le \alpha \le 3$. Isto quer dizer que a distribuição do grau é extremamente assimétrica e que os valores mais altos têm boa probabilidade de ocorrer. Em outras palavras, temos um grande número de nós de grau baixo e alguns poucos nós de grau muito elevado. 

Tal comportamento não é exclusivo das redes complexas. Podemos observar este tipo de distribuição com reflexo de outros fenômenos em sistemas complexos como o número de visualizações de vídeos no YouTube ou a distribuição dos tamanhos de fluxos na Internet (um fluxo é o agregado de dados de um conexão TCP, por exemplo).

A principal característica da lei de potência é a cauda pesada, isto significa que a cauda da distribuição lei de potência é mais “pesada” do que a da distribuição exponencial, ou seja, a probabilidade de obtermos valores grandes é muitas vezes maior na distribuição lei de potência do que na distribuição exponencial, conforme mostra o gráfico abaixo.

O gráfico compara uma distribuição lei de potência $P(d_i=k)=k^{-2}$ (curva preta cheia) com a distribuição exponencial com taxa $k$ (curva tracejada e vermelha), cuja função de densidade é dada por $P(d_i=k)=\lambda e^{-\lambda k}$. Como se pode observar os valores da cauda (valores grandes, maiores que 50 ou 100, por exemplo) tem uma probabilidade alta de ocorrência em uma distribuição de lei de potência, o que já não ocorre na distribuição exponencial.

Com este artigo queremos iniciar mais uma série do blog, em que falaremos sobre outro modelo para geração de redes fictícias, cuja principal característica é a geração de redes livre de escala. O modelo de Barabási-Albert (BA) foi proposto no artigo Emergence of scaling in random networks de autoria de Albert-László Barabási* e Réka Albert, publicado em 1999 na Science.

Assim como as redes GWS, as redes BA não são obtidas por um processo puramente aleatório, já que introduzem alguma regularidade no processo de seleção de nós. A regularidade é obtida por meio da anexação preferencial, que dirige a escolha dos nós em direção aos nós mais conectados, ou seja, a escolha continua aleatória, mas usa uma distribuição onde nós mais conectados têm maior chance de serem escolhidos, ao invés de usar uma distribuição uniforme, como nos modelos anteriores.

Além da anexação preferencial, as redes livres de escala introduzem o uso do crescimento. Nos outros modelos, a quantidade de nós na rede é dada inicialmente e não muda ao longo do processo de criação da rede. Já no modelo que veremos, as redes iniciam com um pequeno número de nós e o processo consiste em adicionar nós e arestas à rede inicial.

O modelo BA agrega o crescimento e a anexação preferencial para construir redes livres de escala. Neste modelo, começamos com uma rede inicial de 3 nós conectados entre si. A cada iteração adicionamos um nó e $\Delta m$ enlaces. Os enlaces são ligados ao novo nó e as outras pontas são escolhidas de forma aleatória. A probabilidade de um nó $i$ ser escolhido é dada por $\frac{d_i}{\sum d_i}$. O processo segue até que tenhamos $n$ nós na rede. Ao final do processo, teremos adicionado  $n-3$ nós e aproximadamente $n\Delta m$ enlaces.

Tanto o crescimento quanto a anexação preferencial tentam emular comportamentos existentes em redes complexas reais. Em redes reais (sociais, tecnológicas e biológicas) é comum que mais nós sejam adicionados ao longo do tempo. Assim, um nó adicionado no tempo $t$, pode ter uma visão da rede e fazer sua escolha de conexão com base nisso. Esta escolha tem relação direta com a anexação preferencial. Os nós não escolhem suas conexões aleatoriamente, mas decidem com base em elementos objetivos, sendo a popularidade naquele instante de tempo (medida pelo grau neste caso) um destes fatores. Esta popularidade é o aspecto modelado pela anexação preferencial. Nós populares tem maior probabilidade de ter mais conexões ao longo do tempo.

Em próximos artigos exploraremos uma versão generalizada deste modelo e estudaremos suas propriedades.