Gere redes sem escala com distribuições de diplomas de direito de energia usando Barabasi-Albert

11

Estou tentando reproduzir as redes sintéticas (gráficos) descritas em alguns papéis.

Afirma-se que o modelo Barabasi-Albert foi usado para criar "redes sem escala com distribuições de graduação em direito do poder, ".PA(k)kλ

PA é uma distribuição de probabilidade que retorna a probabilidade de um nó com grau k . Por exemplo, PA(2) indica a probabilidade de escolher aleatoriamente um nó da rede e obter um nó com grau 2.

O grau médio de golpe k parece ser 4 em um artigo, com um mínimo de k de 2. Nenhuma palavra sobre o máximo de k . No outro artigo, não está especificado. Não parece tão importante definir a rede.

Os valores Lambda λ são fornecidos, assim como o número de nós n . Combinações são

  1. n = 50000, λ = 3, 2,7, 2,3, com em um papel
  2. n = 4000 e λ = 2,5, ou n = 6000 e λ = 3 no outro artigo

Procurei bibliotecas implementando o algoritmo Barabasi-Albert e elas parecem exigir parâmetros diferentes do lambda e do grau médio. Um é o NetworkX , o outro é o GraphStream (implementação aqui ). Eles trabalham de maneira semelhante e pedem:

  • n : int - número de nós
  • m : int - número de arestas a serem anexadas de um novo nó aos nós existentes; o número de arestas a serem adicionadas em cada etapa

Como posso calcular as configurações m para gerar um gráfico comparável?

Aqui estão algumas referências:

  • Cascata catastrófica de falhas em redes interdependentes, Buldyrev et al. 2010, com informações suplementares fornecidas separadamente
  • Cluster pequeno em sistemas físicos cibernéticos, Huang et al. 2014
  • Cascata catastrófica de falhas em redes interdependentes, Havlin et al. 2010, este é o Arxiv e esclarece um pouco a primeira

Observe que esses trabalhos usaram "funções geradoras" para estudar analiticamente algumas propriedades desses gráficos. No entanto, eles também executam simulações nesses modelos, portanto devem ter gerado essas redes de alguma forma.

Obrigado.

Agostino
fonte
A propósito, o Mathematica também faz isso .
Juho

Respostas:

7

A resposta curta é que você não pode usar esse software para obter o que deseja. Para um fixo , o modelo Barabasi-Albert sempre tem a distribuição de graus , independentemente de . A fórmula exata para o grau de probabilidade do que essas partes do software implementam (que é o modelo BA) éP kk - 3 mmPkk3m

Pk=2m(m+1)k(k+1)(k+2)

Os trabalhos (com ) provavelmente estão falando sobre algum tipo de modelo generalizado de BA, presumo. Ajudaria a dar mais detalhes (citações completas) sobre eles.λ3

EDIT: OK, vou dar uma olhada nessas referências. Enquanto isso, descobri que há um pacote R chamado igraph que pode fazer o que você deseja. O trabalho teórico relevante / citado utilizado é:

Possui cerca de 400 citações no Google Scholar, portanto é provavelmente um método amplamente usado. O artigo de 2009 mais tarde citado nessa página do pacote R diz claramente "As redes SF contêm graus heterogêneos e sua distribuição segue uma lei de potência, . Para construir redes SF artificiais, um método estocástico modelo chamado Chung e Lu (CL) é usado ".Pd(k)kλ

EDIT2: Eu acho que você leu Huang et al. "Construímos redes sintéticas aleatórias, sem escala e de mundo pequeno usando o modelo Erdos-Renyi, o modelo Barabasi-Albert e o modelo Watts e Strogatz [9], respectivamente." Não diz em nenhum lugar que eles conseguiram que a BA fizesse outra potência além de 3. Existe uma legenda na figura que diz "Usamos o modelo de interdependência 'k-n' para acoplar duas redes sintéticas sem escala e com os expoentes da lei de energia 2.5 e 3 respectivamente." Mas isso não significa que eles usaram o BA para esses gráficos de 2,5 graus. Há uma figura posterior que diz apenas "O modelo Barabasi-Albert é usado para gerar rede sem escala com o expoente da lei de energia 3."G cGpGc

EDIT3: O artigo de Buldyrev et al. não diz em nenhum lugar que eles usaram gráficos BA. "Resultados de simulação para P8 em função de p para redes SF com = 3, 2.7, 2.3". Eles não dizem como conseguiram esses gráficos. Eles citam os artigos da BA, mas apenas em uma longa lista de 10 artigos sobre vários modelos de rede aleatórios. O segundo artigo deste grupo de Havlin et al. de fato ceder p. 5 o modelo BA como tendo indeterminado / não especificado , citando o artigo de 1999 sobre BA. Eu realmente não quero chamar este artigo de errado, mas a única leitura correta é . Novamente, não diz como eles geraram seusλ λ = 3 λ = 2,7λλλ=3λ=2.7gráficos da Fig. 8. Posso ver como, ao ler este artigo, você pode concluir que o BA pode gerar esses gráficos ... mas não pode.

EDIT4: Sim, encontrei-o agora na versão real publicada na Nature "Para duas redes interdependentes sem escala 2 com distribuição de diplomas de direito, , descobrimos que os critérios de existência para o componente gigante são bem diferentes daqueles em uma única rede ". A citação é realmente enganosa da mesma maneira que em Halvin et al., Mas eles não dizem que usaram o processo BA para gerar os gráficos. A passagem pode ser interpretada como apenas uma referência citada pela BA 1999 para o que significa rede sem escala e / ou quem originou o conceito. De qualquer forma, confie na matemática ... você pode encontrar a derivação para a fórmula do grau BA em vários lugares, incluindo o próprio papel da BA ou em mais detalhes λ λ = 3 λPA(k)PB(k)/kλem um livro posterior [let] . BA obviamente entendeu a generalidade do que eles observaram, então eles declararam uma lei que é mais geral (arbitrária ) do que a sua construção fornece, isto é, . Como eu disse antes, existem outros métodos (publicados posteriormente por outros, por exemplo, Chung e Lu) para obter um diferente , mas eles não estão usando a construção BA, embora seus gráficos também sejam chamados corretamente sem escala.λλ=3λ

Efervescer
fonte
Obrigado pela captura. Eles poderiam ter sido muito mais claros do que isso, no entanto. De fato, ainda estou faltando o parâmetro m aqui, existe apenas um grau médio na Fig. 2. #
245 Agostino
O primeiro artigo cita também a BA, exatamente quando eles falam sobre como eles criaram o gráfico sem escala "Para duas redes interdependentes sem escala com distribuições de diplomas de lei de potência". 2 é uma referência ao documento de 1999 da BA. 2
Agostino
Estão falando sobre o mesmo artigo? Não consigo encontrar a string em arxiv.org/pdf/0907.1182v1.pdf
Fizz
Não, o primeiro artigo a que me refiro, de Buldyrev et al., Tem o mesmo título, mas foi publicado em 2010 e, infelizmente, não está no Arxiv. É o único com muitas citações, se você pesquisar no Google.
Agostino
@Agostino: Sim, encontrei e li agora; veja EDIT4.
Fizz