Modelo configuracional

Research Reports

O modelo configuracional consiste no algoritmo abaixo:

• Dada a sequência de graus gerada, cria-se um vetor de “pontas soltas” (stubs) de tamanho \(\sum k_i\) em que cada nó \(i\) aparece (sequencialmente) \(k_i\) vezes;
• Para evitar correlações na geração sequencial (seeds colision), o vetor de stubs é embaralhado com o Algoritmo P (shuffling) [1] (também conhecido como Fisher-Yates);
• O vetor é percorrido emparelhando stubs adjacentes (índices \(j\) e \(j+1\)) para formar uma possível nova aresta entre os nós:
  • Caso a possível conexão for um auto-laço ou já existir, ela é rejeitada e o algoritmo continua:
    • Em caso de rejeição, um stub é sorteado (uniforme) dentre aqueles ainda não processados;
    • Caso falhe novamente, uma busca linear procura pelo primeiro stub válido disponível. Se nenhuma reatribuição for possível, o par é descartado;
  • Se a conexão for válida, a lista de adjacência de ambos os nós é atualizada, contabilizando a aresta final, e o processo avança até o esgotamento do vetor de stubs.

Amostragem de diferentes distribuições de graus

No modelo configuracional, temos a grande vantagem de podermos escolher como iremos fazer a amostragem dos graus. Interessam, principalmente, três distribuições: a lei de potência (Scale Free Networks), Poisson (Erdős-Rényi) e regular (Regular Random Networks).

Distribuição em lei de potência

Para distribuir em lei de potência, recorremos ao método de Clauset [2] de inversão de CDF contínua com apromiximação discreta. Dado um número aleatório uniforme \(u^{\text{r}}\in[0,1)\), então o número inteiro aleatório \(x^{\text{r}}\), dado pela transformação: \[ x^{\text{r}} = \left\lfloor \big(x_{\min}-0.5\big)\big(1-u^{\text{r}}\big)^{\frac{1}{\gamma-1}}\right\rfloor\,, \tag{1}\] é um número distribuído em lei de potência \(p(x;\gamma)\) no intervalo \([x_{\min},\infty)\). Para controlar o surgimento de outliers e/ou o grau máximo da rede em lei de potência, pode-se atribuir um determinado cut-off: estrutural \(\max(k) = \sqrt{N}\), natural \(\max(k) = N^{\frac{1}{\gamma-1}}\) ou rígido \(\max(k) = N^{\frac{1}{\gamma}}\).

Distribuição em Poisson

Para a Poisson, o algoritmo de D. Knuth [1] é ideal. Ele parte da ideia que um número de Poisson conta o número de eventos que ocorrem numa janela temporal, em que o intervalo de tempo entre eventos sucessivos é dado por uma distribuição exponencial. Em outras palavras, consiste em:

• Gerar números exponencialmente distribuídos com média \(1/\lambda\), \(x_1^{\text{r}},\,x_2^{\text{r}},\,\cdots\);
• Parar quando a soma cumulativa dos \(m\) números gerados exceder 1, \(x_1^{\text{r}}+x_2^{\text{r}}+\cdots+x_m^{\text{r}}\geq 1\);
• O número \(N^{\text{r}}=m-1\) é um número de Poisson com média \(\lambda\).

Por razões de consistência, a distribuição gerada é truncada à esquerda, rejeitando graus inferiores a um dado \(k_{\min}\).

Distribuição regular

O último caso é o mais simples. Todos os nós da rede têm o mesmo número de grau, \(K\), então basta escolher um valor \(K>1\) inteiro.

Conexão dos stubs

O método de sorteio e busca linear (two-stage cascade) serve para tentar ao máximo (para uma dada seed) encontrar conexões válidas para aquela distribuição. A {ref}benchmark_dist_efetiva_redes mostra que a distribuição efetiva de graus (a distribuição de graus real da rede, após a aplicação do modelo configuracional) de fato segue as distribuições usadas para a amostragem dos graus, com boa convergência mesmo para redes com \(N=10^4\) nós.

:name: benchmark_dist_efetiva_redes
:width: 100%
:align: center
Distribuições *efetivas* (reais) das redes geradas para dois tamanhos, $N=5\cdot10^5$ e $N=10^4$, em todo caso com $k_{\min}=4$. As linhas sólidas representam as distribuições teóricas com estes parâmetros, mostrando a concordância da distribuição efetiva obtida com o modelo configuracional e a "distribuição de entrada".

Benchmarking da implementação

Finalmente, para verificar a autoconsistência das redes sintéticas e medir os desvios da lista de graus induzidos pelo método, a função de report faz uma grande checagem estrutural e estatística da topologia gerada. A verificação é dividida em duas etapas:

1. Autoconsistência Topológica:
   • Teorema do Grau: o número de arestas tem que ser igual à metade da soma dos graus efetivos dos nós;
   • Nós isolados: Contabiliza a existência de sítios com grau nulo (\(k=0\));
   • Fragmentação da rede: Utilizando o algoritmo BFS, o código determina o tamanho da componente gigante (CG), de modo que, caso ela não equivalha à totalidade da da rede (sinalizando fragmentação), um alerta é emitido para que a componente principal seja isolada/extraída antes de iniciar a dinâmica.
2. Consistência Estatística (Teoria vs. Efetiva):
   • Arestas rejeitadas: Compara o número de arestas originais sorteadas com o número de arestas efetivamente conectadas, indicando a taxa de descarte exigida para manter a rede puramente simples;
   • Momentos da distribuição: Calcula o grau máximo (\(k_{\max}\)), o grau médio (\(\langle k \rangle\)) e o segundo momento matemático (\(\langle k^2 \rangle\)) da lista original e compara com a rede conectada. Uma tolerância estatística de \(1/\sqrt{N}\) é adotada para classificar a confiabilidade da topologia gerada.

Estes relatórios on-the-fly servem para garantir robustez e validade ao algoritmo de redes, evitando que desvios induzidos pelo método enviesem os resultados.

Para várias redes geradas, nenhum desvio significativo foi encontrado. Assim, a robustez e validade deste algoritmo ficam comprovadas. A tabela abaixo reúne estes resultados comparativos para os casos de interesse.

Distribuição	Parâmetros	Desvios da rede gerada
Power-law (Scale-Free)	\(\gamma \in \{2.3, 2.7, 3.5\}\), \(k_{\min}=4\)	“Insignificantes” Frequentemente 0 (ou \(\sim 10^{-5}\%\)) de descarte; CG abrange todos os nós; \(\langle k \rangle\), \(\langle k^2 \rangle\) e \(k_{\max}\) efetivos são idênticos aos da lista amostrada.
Poisson (Erdős-Rényi)	\(\langle k \rangle_{\text{teor}} \in \{6.0, 8.5, 10.0\}\), \(k_{\min}=4\)	Nulos. 0 arestas descartadas; CG abrange todos os nós; momentos estatísticos perfeitamente conservados.
Regular (RRN)	\(K \in \{4, 6, 10\}\)	Nulos. Conservação exata da topologia regular; 0 arestas descartadas; CG engloba toda a rede.

Referências

[1]

D. E. Knuth, The Art of Computer Programming: Semi-Numerical Algorithms, 3rd ed., v. 2. Addison-Wesley, 1998.

[2]

A. Clauset, C. R. Shalizi, e M. E. J. Newman, “Power-law distributions in empirical data”, SIAM Rev., v. 51, n. 4, p. 661–703, nov. 2009, doi: 10.1137/070710111.