Barabási–Albert model
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.
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 ) {\displaystyle p(k)} de um nó escolhido ao acaso ter grau k {\displaystyle k} é proporcional a k − γ {\displaystyle k^{-\gamma }} , onde γ {\displaystyle \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 ) {\displaystyle p(k)} para tais modelos apresenta um decaimento exponencial para grandes valores de k {\displaystyle 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.
O processo de crescimento inicia-se com uma rede arbitrária de n 0 {\displaystyle 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 {\displaystyle c} nós já existentes, onde c {\displaystyle c} é uma variável do modelo. A probabilidade do novo nó se conectar a um outro nó i {\displaystyle i} qualquer já presente na rede é proporcional ao número de ligações que o nó i {\displaystyle i} possui. Formalmente, a probabilidade p i {\displaystyle p_{i}} de que o novo nó irá se conectar a um vértice i {\displaystyle i} já presente é: em que k i {\displaystyle k_{i}} é o grau do nó i {\displaystyle i} e a soma no denominador, realizada sobre todos os nós j {\displaystyle 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 {\displaystyle c} ligações que o novo nó irá fazer.
Distribuição de grau
A distribuição de grau para redes construídas com o modelo de Barabasi-Albert pode ser obtida analiticamente :
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 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 k l {\displaystyle n_{kl}} de encontrar uma ligação entre os nós de graus k e l no modelo BA, quando m = 1 {\displaystyle m=1} é dada por Isso certamente não é o resultado esperado se as distribuições forem correlacionados, n k ℓ = k − 3 ℓ − 3 {\displaystyle 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. 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, 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.
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.
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.
