Barabási–Albert model

Ciência da Rede
Teoria
Grafo Rede complexa Contágio Redes de pequeno mundo Scale-free Estrutura comunitária Percolação Evolução Difusão de inovações (redes sociais) Controlabilidade Desenho grafo Capital social Análise de links Otimização Reciprocidade Transitividade Ligação preferencial Teoria do equilíbrio Efeito de rede Influência social
Tipos de Rede
Rede de computadores Telecomunicação Rede social Neural Artificial Interdependente Semântico Dependência Fluxo
Grafos
Caraterísticas Clique Componente Corte Ciclo Estrutura de dados Aresta Laço Vizinhança Caminho Vértice Lista de adjacência / matriz Incidência Lista / matrix Tipos Grafo bipartido Grafo completo Grafo orientado Hipergrafo Multigrafo Aleatórios Ponderado
Métricas & Algoritmos
Centralidade Grau Betweenness Proximidade PageRank Clustering Centralidades Baseadas na Dissimilaridades Distribuição de Graus Correlação de Graus Assortatividade Distância Modularidade
Modelos
Grafo Aleatório Erdös–Rényi Barabási–Albert Watts–Strogatz Exponencial Aleatório (ERGM) Epidemia Hierárquica
Categorias
Teoria dos grafos Teoria das redes complexas

O modelo de Barabási–Albert (BA) é um algoritmo para gerar redes sem escala de forma aleatória: a rede cresce através da inclusão de novos nós no decorrer do tempo, e esses novos nós se ligam aos nós já existentes na rede com probabilidade proporcional ao grau. Esse modelo gera redes com distribuição de grau do tipo lei de potência, propriedade amplamente observada em vários sistemas naturais e artificiais, incluindo a internet, redes de citação e em algumas redes sociais.

Conceitos

Muitas das redes naturais observadas enquadram-se na classe denominada de redes sem escala, esta declaração quer dizer que as suas distribuições de grau seguem leis de potência: a probabilidade $p(k)$ de um nó escolhido ao acaso ter grau $k$ é proporcional a $k^{-\gamma }$, onde $\gamma$ é um número real positivo. Entretanto, os modelos de redes aleatórias conhecidos anteriormente, como o modelo de Erdös-Rényi (ER) e de Watts-Strogatz (WS) não apresentam essa característica. A distribuição de grau $p(k)$ para tais modelos apresenta um decaimento exponencial para grandes valores de $k$.

O modelo de Barabási-Albert é um dos que foram propostos para a produção de redes sem escala. Ele incorpora dois conceitos gerais: crescimento e anexação preferencial. Estes dois conceitos podem ser aplicados para certos tipos de redes naturais, como a redes de citações.

Na teoria de redes, a propriedade de crescimento significa que ao longo do tempo novos nós são adicionados a rede. Já anexação preferencial significa que quanto mais conectado é um nó, maior é a sua probabilidade de receber novas ligações a partir dos nós recém adicionados. Os nós com maior grau têm maior capacidade para agarrar links adicionados à rede.

Anexação preferencial é um exemplo de um ciclo de feedback positivo, em que as variações aleatórias (inicialmente um nó ter mais ligações ou tendo começado a acumular ligações mais cedo do que o outro) são automaticamente reforçadas, ampliando assim as diferenças, gerando alguns poucos nós com grau elevado, os chamados hubs, e muitos outros nós com grau baixo.

O mecanismo de anexação preferencial às vezes é proverbialmente chamado de efeito Mateus, "os ricos ficam mais ricos".

Intuitivamente, a anexação preferencial pode ser entendida se pensarmos em termos de redes sociais conectando pessoas. Aqui um link entre as pessoas A e B significa que a pessoa A "sabe" ou "está familiarizada com" a pessoa B. Uma pessoa fortemente conectada, ou seja, com um grau elevado, representa uma pessoa com muitas relações com outros membros da comunidade. Assim, um novato ao entrar na comunidade tem mais chance de se familiarizar com uma dessas pessoas de maior visibilidade do que com uma pessoa desconhecida. Da mesma forma, na web, novas páginas vinculam-se preferencialmente aos hubs como o Google ou a Wikipédia, ao invés de páginas que quase ninguém conhece.

Algoritmo

Rede gerada pelo algoritmo do modelo Barabasi Albert.

O processo de crescimento inicia-se com uma rede arbitrária de $n_{0}$ nós. Novos nós são adicionados a rede, um a um, e cada um desses novos nós faz conexões com outros $c$ nós já existentes, onde $c$ é uma variável do modelo. A probabilidade do novo nó se conectar a um outro nó $i$ qualquer já presente na rede é proporcional ao número de ligações que o nó $i$ possui. Formalmente, a probabilidade $p_{i}$ de que o novo nó irá se conectar a um vértice $i$ já presente é:

$p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}},$

em que $k_{i}$ é o grau do nó $i$ e a soma no denominador, realizada sobre todos os nós $j$ já existentes na rede, é a normalização da probabilidade. Esse processo de escolha de conexão é repetido então para cada uma das $c$ ligações que o novo nó irá fazer.

Com esse mecanismo, os nós com grau elevado, aqueles com muitas conexões, tendem a acumular rapidamente ainda mais ligações, enquanto nós com grau baixo, contendo apenas algumas poucas ligações, tem probabilidade muito pequena de serem escolhidos como o destino para um novo link. Assim, os novos nós tem uma preferência para unir-se aos nós já fortemente ligadas. Note também que há um valor mínimo para o grau de um nó, sendo ele igual ao parâmetro $c$. O grau médio $\langle k\rangle$ da rede pode ser calculado analiticamente, sendo $\langle k\rangle =2c$.

Propriedades

Distribuição de grau

A distribuição de grau $p(k)$ para uma rede construída com o modelo de BA, com N = 150000 nós e grau médio $\langle k\rangle =6$. A linha contínua representa o resultado analítico, enquanto os círculos azuis são o resultado numérico. Note que ambos os eixos estão em escala logarítmica.

A distribuição de grau para redes construídas com o modelo de Barabasi-Albert pode ser obtida analiticamente :

$p(k)={\frac {2c(c+1)}{k(k+1)(k+2)}}$

Assintoticamente, quando $k\gg 1$, essa distribuição segue uma lei de potência, $p(k)\propto k^{-3}$.

Distância média do menor caminho

O distância média do menor caminho no modelo BA aumenta aproximadamente logaritmicamente com o tamanho da rede. A forma real tem uma correção logarítmica dupla e vai como

$\ell \sim {\frac {\ln N}{\ln \ln N}}.$

O modelo BA tem um comprimento de caminho médio sistematicamente menor do que um grafo aleatório.

Correlação de grau

As correlações entre os níveis de nós ligados desenvolvem espontaneamente o modelo de BA por causa da forma como a rede se desenvolve. A probabilidade $n_{kl}$ de encontrar uma ligação entre os nós de graus k e l no modelo BA, quando $m=1$ é dada por

$n_{k\ell }={\frac {4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}+{\frac {12\left(\ell -1\right)}{k\left(k+\ell -1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}.$

Isso certamente não é o resultado esperado se as distribuições forem correlacionados, $n_{k\ell }=k^{-3}\ell ^{-3}$

Coeficiente de agrupamento ou clustering

Embora não haja um resultado analítico para o coeficiente de clustering do modelo BA, os coeficientes de agrupamento empiricamente determinados são geralmente mais elevados para o modelo de BA para as redes aleatórias. O coeficiente de clustering também dimensiona com o tamanho da rede após uma lei de potência aproximadamente.

$C\sim N^{-0.75}.\,$

Este comportamento ainda é distinto do comportamento de redes de pequeno mundo onde o clustering é independente do tamanho do sistema. No caso de redes hierárquicas, clustering em função do grau de nó também segue uma lei de potência,

$C(k)=k^{-1}.\,$

Este resultado foi obtido analiticamente por Dorogovtsev, Goltsev e Mendes.

Propriedades espectrais

A densidade espectral de modelo BA tem uma forma diferente da densidade espectral semicircular do grafo aleatória. Ele tem um triângulo como forma com a parte superior deitado bem acima do semicírculo e arestas em decomposição como uma lei de potência.

Casos limites

Modelo A

Modelo A mantém o crescimento, mas não inclui a fixação preferencial. A probabilidade de um novo nó de ligação para qualquer nó preexistente é igual. A distribuição resultante do grau neste limite é geométrica, indicando que o crescimento por si só não é suficiente para produzir uma estrutura livre de escala.

Modelo B

Modelo B mantém a fixação preferencial, mas elimina o crescimento. O modelo começa com um número fixo de nós desligados e adiciona links, preferencialmente escolhendo nós com um alto grau, como destinos. Embora o grau de distribuição no início da simulação pareça sem escala, a distribuição não é estável, e ele acaba tornando-se quase Gaussian com a rede a aproximar-se da saturação. Então a fixação preferencial por si só não é suficiente para produzir uma estrutura livre de escala.

O fracasso dos modelos A e B para conduzir a uma distribuição livre de escala indica que o crescimento e a fixação preferencial são necessários simultaneamente para reproduzir a distribuição do poder-lei estacionário observado em redes reais.

História

O primeiro uso de um mecanismo de anexação preferencial para explicar as distribuições de energia de lei parece ter sido por Yule em 1925, embora o tratamento matemático de Yule é opaco para os padrões modernos, devido à falta de ferramentas apropriadas para a análise de processos estocásticos. O método da equação mestre moderno, que produz uma derivação mais transparente, foi aplicado para o problema por Herbert A. Simon, em 1955, no decurso de estudos sobre o tamanho das cidades e outros fenómenos. Foi aplicado pela primeira vez para o crescimento das redes de Derek de Solla Price, em 1976, que estava interessado em redes de citação entre artigos científicos. O nome "anexação preferencial", e a atual popularidade dos modelos de redes sem escala, é devido ao trabalho de Albert-László Barabási e Réka Albert, que redescobriu o processo de forma independente em 1999 e aplicou-a a distribuições de grau na web.

Ver também

• Modelo Erdős–Rényi
• Modelo Watts–Strogatz
• Redes de pequeno mundo
• Teoria dos Grafos