Barabási–Albert model

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde fevereiro de 2014).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.


O modelo denominado Barabási–Albert (BA) é um algoritmo para gerar redes sem escala de forma aleatória, este metodo faz uso de um acessório como mecanismo. As redes sem escala são amplamente observadas e aplicadas em sistemas naturais e artificiais, incluindo a internet, redes de citação e em algumas redes sociais.

Conceitos[editar | editar código-fonte]

Segundo Barabási e Albert o essencial para construir uma rede livre de escala consiste na existência de ligações preferenciais que proporcionaram o seu crescimento da rede ao longo do tempo.

Muitas das redes observadas enquadram-se na classe denominada de "redes de escala livre", esta declaração quer dizer que as suas distribuições de graus seguem leis exponenciais (ou de escala-livre), enquanto outros, modelos de gráficos aleatórios como o modelo Erdös-Rényi (ER) e Watts-Strogatz de (WS) não apresentam essa característica de exponencialidade. O modelo Barabási-Albert é um dos que foram propostos para a produção de redes de escala livre. Ele incorpora dois conceitos gerais: crescimento e fixação preferencial. Estes dois conceitos podem ser encontrados amplamente em redes reais em torno de nós. Na teoria de redes a propriedade de crescimento significa que as redes possuem uma quantidade crescente de nós cada vez maior ao longo do tempo.

Fixação preferencial significa que quanto mais conectado é um nó, o mais provável é receber novas ligações. Os nós com maior grau têm maior capacidade para agarrar links adicionados à rede. Intuitivamente, o anexo preferencial pode ser entendido se pensarmos em termos de redes sociais conectam pessoas. Aqui um link de A para B significa que a pessoa A "sabe" ou "está familiarizado com" nós pessoa B. fortemente ligado representar pessoas conhecidas com muitas relações. Quando um novato entra na comunidade, ele / ela é mais provável de se familiarizar com uma dessas pessoas mais visíveis do que com um parente desconhecido. Da mesma forma, na web, novas páginas vincular preferencialmente aos hubs, ou seja, locais muito conhecidos como o Google ou a Wikipédia, ao invés de páginas que quase ninguém conhece. Se alguém escolhe uma nova página a vincular que foi escolhida aleatoriamente um link existente, a probabilidade de selecionar uma página específica seria proporcional ao seu grau. Isso explica a regra de probabilidade preferencial anexo.

Ligação preferencial é um exemplo de um ciclo de feedback positivo 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çado, ampliando assim as diferenças. Isso às vezes também é chamado de efeito Mateus, "os ricos ficam mais ricos", e em autocatálise química.

Algoritmo[editar | editar código-fonte]

A rede inicia-se com uma rede inicial de 'm0 nós. Quando m0 ≥ 2 e o grau de cada nó da rede inicial deve ser de pelo menos 1, senão será sempre desligado do resto da rede.

De tempos em temos novos nós são adicionados à rede. Cada novo nós é ligado aos m nós já existentes, com uma proporcionalidade igual ao número de ligações que os nós existentes já possuem. Formalmente a probabilidade pi de que o novo nó esta ligado está ligado ao nó i é dada pela seguinte expressão:

p_i = \frac{k_i}{\sum_j k_j},

Em que ki é o grau de nó i e a soma é realizada sobre todos os nós j já existentes inicialmente.

Os nós fortemente ligados tendem a acumular rapidamente ainda mais ligações, enquanto nós com apenas algumas ligações não são suscetíveis de ser escolhido como o destino para um novo link. Os novos nós tem uma "preferência" para unir-se aos nós já fortemente ligadas.


Propriedades[editar | editar código-fonte]

Grau de distribuição[editar | editar código-fonte]

O grau de distribuição do Modelo BA, que segue uma lei de potência

O grau de distribuição resultante do modelo BA é orientada a uma rede livre de escala que pode ser calculada tendo em consideração a seguinte formula:

P\left(k\right)\sim k^{-3} \,

Duração média do caminho[editar | editar código-fonte]

O comprimento médio da via do 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 nó[editar | editar código-fonte]

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}[1]

Coeficiente Clustering[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Modelo A[editar | editar código-fonte]

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ó pré-existente é 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[editar | editar código-fonte]

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[editar | editar código-fonte]

O primeiro uso de um mecanismo de fixaçã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 "fixação preferencial" e a atual popularidade dos modelos de rede scale-free é 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.

Veja Também[editar | editar código-fonte]

Referências

  1. Erro de citação: Tag <ref> inválida; não foi fornecido texto para as refs chamadas RMP