q-Voter em networks
Junho-julho/2026, Mestrado, TF.
Implementação do modelo em redes com distribuição de graus \(p(k)\) (Poisson, lei de potência, \(\dots\)).
Mean-field e q-Voter
O ponto de partida aqui, então, é o artigo:
📄 Mean-Field Analysis of the q-Voter Model on Networks
Paolo Moretti, Suyu Liu, Claudio Castellano, and Romualdo Pastor-Satorras
Journal of Statistical Physics 151, 113–130 (2013).
Neste artigo, os autores implementam a teoria de campo médio num grafo completo e com a teoria heterogênea, HMF. Nos dois casos, a teoria prevê duas fases, para (fase de fragmentação da opinião média) e ferromagnética (consenso da opinião média), bem como um região de biestabilidade, que, dependendo da condição inicial, leva ao consenso ou à fragmentação.
A curva que define a fronteira crítica entre a fase paramagnética e ferromagnética é dada por \[ \overline{\varepsilon_c}(\phi) = \frac{\phi^2+3}{2\phi^2+14}\,, \tag{1}\] onde \(\phi\) é a magnetização (opinião) média da rede. Para a teoria HMF, sendo \(\langle k\rangle\) o grau médio da rede, a fronteira é dada por \[ \overline{\varepsilon_c}(\phi) = \frac{1}{2} - \frac{2\langle k\rangle(\langle k\rangle-2)}{\phi^2(\langle k\rangle-2) \tag{2}\]
Algumas conclusões centrais deste artigo: - As teorias de campo médio prevem biestabilidade para o q-voter para \(q\geq4\), cuja fronteira é dada pelas equações {ref}fronteira_critica e {ref}fronteira_critica; - A taxa do modelo em redes heterogêneas fica definida para um nó de grau \(k\) com \(n\) vizinhos em um estado diferente por: \[f_k(n;q,\varepsilon) = \left(\frac{n}{k}\right)^q + \varepsilon\left[1 - \left(\frac{n}{k}\right)^q - \left(\frac{k-n}{k}\right)^q\right]\,;\] - Em RRNs com \(K=4\), a biestabilidade não é observada, como previsto pelas teorias de campo médio, por conta da esparsidade da rede; - Questões se RRNs muito densas e redes heterogêneas, como as em lei de potência, recuperam a biestabilidade permanecem abertas no artigo.
Nos interessa, aqui, o caso \(q=4\), o menor valor de \(q\) em que a biestabilidade é observada na teoria de campo médio. Procuramos fazer um diagrama de fases semelhante ao da Figura {ref}biestabilidade, onde, para um dado valor \(\varepsilon\), examinamos a dinâmica varrendo as condições iniciais da magnetização, \(\phi_0\in[0,1]\).
Implementação computacional: benchmarks e resultados
Nas subseções que seguem, explico detalhadamente de que forma as redes complexas e a dinâmica (em tempo contínuo) foram implementadas. Também apresento benchmarks sobre a coerência e exatidão dos algoritmos, bem como as otimizações (lista dinâmica e paralelismo).
### Dinâmica em tempo contínuo
Para utilizar o algoritmo de Gillespie, o método de aceitação-rejeição (eventos reais e nulos) com lista dinâmica é a forma otimizada. A referência principal para implementação do algoritmo foi: > 📄 Dynamic sampling from a discrete probability distribution with a known distribution of rates
> Federico D’Ambrosio, Hans L. Bodlaender, and Gerard T. Barkema
> Computational Statistics 37, 1203–1228 (2022).
A ideia é considerar apenas os nós que podem flipar. Basta definir uma lista que contém todos os \(N_{\text{ativos}}\) nós ativos da rede (isto é, aqueles com \(f_k>0\)) e atualizá-la dinamicamente durante a evolução. Em suma: - A um dado tempo \(t\), sorteia-se aleatoriamente um nó \(i\) exclusivamente dentre os \(N_\text{ativos}\) sítios com taxa não-nula; - Aceitação-rejeição padrão: dado um número aleatório uniforme \(r^\text{r}\in[0,1)\), o spin flipa caso \(f_{k_i}(n_i) \geq r^\text{r} \cdot \max_f\); - Caso o estado seja alterado, a vizinhança local é atualizada. Sítios vizinhos que passam a ter \(0\) vizinhos discordantes são removidos da lista dinâmica (tornam-se inativos), enquanto sítios que adquirem discordância são adicionados à lista; - O tempo físico do sistema avança independentemente do flip ter sido aceito ou rejeitado (evento nulo), considerando \(u^\text{r}\in[0,1)\), por: \[t \leftarrow t - \frac{\ln(1-u^\text{r})}{N_\text{ativos} \cdot \max_f}\,.\]
No pior dos casos, a lista dinâmica tem complexidade temporal igual ao método ingênuo de aceitação-rejeição (onde o sorteio do nó \(i\) é feito sobre toda a rede). Mas em dinâmicas próximas ao estado de consenso, o tamanho da lista decresce rapidamente, de forma que o uso da lista dinâmica reduz a complexidade temporal. Outros métodos de otimização, a princípio, não geram melhorias no tempo computacional.
:name: benchmark_equiv
:width: 80%
:align: center
Equivalência entre o algoritmo de Gillespie otimizado com a lista dinâmica e o algoritmo em passos discretos de Markov.A Figura {ref}benchmark_equiv mostra a equivalência (estatística) das implementações em tempo discreto e tempo contínuo com lista dinâmica. As Figuras abaixo mostram o ganho computacional com o método em tempo contínuo.
 |
 |
### Amostragem dos resultados
Para obtenção dos resultados, a condição de parada da simulação é dada por um tempo máximo numericamente igual ao tamanho da rede Gillespie_time = t_max=real(N) ou à obtenção do consenso, N_ativos = 0. Isto é feito para diferenciar claramente as fases de fragmentação e consenso. Na fase paramagnética o consenso é obtido em tempos muito grandes (\(\tau\sim\exp(N)\)), de modo que este “tempo máximo” serve para relevar o efeito de tamanho finito. De qualquer forma, a análise de tamanho finito ainda não foi realizada.
Para reproduzir a {ref}refbiestabilidade, foram 50 amostras (feitas com uma única rede) de cada ponto no espaço \((\phi_0,\varepsilon)\). Aqui, \(\phi_0\) entra como condição inicial: \((\phi_0+1)/2\) é a proporção (probabilidade) de agentes no estado \(+1\). Os diagramas abrangem 123 pontos distribuídos linearmente para \(\varepsilon\in[0,0,0.3]\) e 101 para \(\phi_0\in[-0.95,0.95]\) (totalizando 12423 pontos * 50 amostras = 621150 runs para cada rede).
Para adiantar a obtenção de amostras, a ferramenta OpenMP foi utilizada, utilizando somente núcleos de desempenho das máquinas do GISC. Para realizar o teste de benchmarking, 100 amostras (50 na fase paramagnética e 50 na fase ferromagnética) foram rodadas sequencialmente (em único núcleo) e com/sem hyper-threading na máquina Weiss. Como os processadores das máquinas Ising, Parisi, Fisher e Weiss seguem a mesma topologia (verificado com lstopo), o resultado percentual da tabela abaixo se mantém. O atraso do hyper-threading se explica porque a memória que a dinâmica ocupa é maior que a metade da memória disponível no cache L2: matriz de estados: 80 KB, matriz de taxas: 80 KB, lista de adjacência: 781 KB e lista dinâmica: 160KB, memória total de aproximadamente 1,1 MB, o que inviabiliza alocar duas threads simultâneas disputando o mesmo cache L2 de 2 MB sem causar cache misses.
| Execução | Nº de Threads | Speedup (Ganho) | Eficiência Paralela | Tempo de Execução (s) |
|---|---|---|---|---|
| Sequencial Puro | 1 | 1,00x | 100 % | 351.013 |
| Sem Hyper-Threading | 8 | 6,05x | 75,7 % | 57.954 |
| Com Hyper-Threading | 16 | 5,74x | 35,9 % | 61.087 |
Resultados preliminares
:name: label
:width: 100%
:align: center
legenda:name: label
:width: 100%
:align: center
legenda:name: label
:width: 50%
:align: center
legenda:name: label
:width: 100%
:align: center
legenda:name: label
:width: 100%
:align: center
legenda:name: label
:width: 100%
:align: center
legenda