Dynamic sparse graphs with overlapping communities

Título: Gráficos Esparsos Dinâmicos com Comunidades Sobrepostas

Autores: Xenia Miscouridou, Francesca Panero e Antreas Laos.

1. O Problema

A detecção de comunidades em redes é uma tarefa central na modelagem estatística de redes, visando identificar grupos de nós com padrões de conectividade semelhantes. Embora modelos estáticos (como o Modelo de Blocos Estocásticos - SBM) sejam bem estabelecidos, a maioria das redes do mundo real é dinâmica: as conexões e a estrutura das comunidades evoluem ao longo tempo (emergência, fusão, dissolução e mudança de membros).

Existem três desafios principais não resolvidos simultaneamente pela literatura existente:

1. Esparsidade e Distribuição de Lei de Potência: Muitas redes reais são esparsas (o número de arestas cresce subquadraticamente em relação aos nós) e exibem distribuições de grau de lei de potência (poucos nós altamente conectados e muitos com poucas conexões). Modelos clássicos baseados em matrizes de adjacência e troca de permutação (exchangeability) tendem a gerar redes densas ou vazias, falhando em capturar a esparsidade observada.
2. Membros Múltiplos (Sobreposição): Em cenários reais, entidades (nós) pertencem frequentemente a múltiplas comunidades simultaneamente (membros mistos), e essa afiliação muda ao longo do tempo.
3. Dependência Temporal: É necessário modelar a evolução temporal das afiliações e das conexões de forma coerente, permitindo que nós entrem e saiam da rede, em vez de assumir um conjunto fixo de nós.

2. Metodologia: O Modelo dynSNetOC

Os autores propõem um novo modelo Bayesiano não paramétrico chamado dynSNetOC (Dynamic Sparse Network with Overlapping Communities). O modelo é construído sobre a representação de grafos como processos pontuais, utilizando Medidas Completamente Aleatórias (CRMs).

Componentes Principais:

• Representação como Processo Pontual: O grafo é modelado como uma medida aleatória em um plano, onde cada nó $i$ é mapeado para uma localização $\theta_i$. As arestas são geradas por um processo de Poisson condicionado a pesos latentes.
• Medidas Completamente Aleatórias (CRMs): Para lidar com a esparsidade e a lei de potência, o modelo utiliza CRMs. Especificamente, emprega um Processo Generalizado de Gamma (GGP) composto. A escolha da medida de Lévy (controlada pelo parâmetro $\sigma$) determina se o grafo resultante é denso ($\sigma < 0$) ou esparso com lei de potência ($\sigma \in (0, 1)$).
• Afiliações Dinâmicas e Sobrepostas:
  • Cada nó possui um vetor de pontuações de afiliação ($\beta_{ki}^{(t)}$) para $p$ comunidades no tempo $t$.
  • A conectividade é definida por uma fatoração de Poisson não negativa, onde a probabilidade de uma aresta entre $i$ e $j$ depende da soma dos produtos das pontuações de afiliação em todas as comunidades.
  • Isso permite membros mistos: um nó pode ter afiliação significativa para múltiplas comunidades simultaneamente.
• Processo de Markov Latente: A evolução temporal das afiliações é governada por um processo de Markov. As pontuações $\beta_{ki}^{(t)}$ evoluem estocasticamente com base em variáveis de augmentação ($\gamma$), garantindo que a distribuição marginal das pontuações seja preservada ao longo do tempo, mas permitindo correlações temporais controladas pelo parâmetro $\psi$.
• Flexibilidade Estrutural: O modelo permite que nós entrem e saiam da rede (nós ativos vs. inativos em diferentes passos de tempo), ao contrário de modelos que exigem um número fixo de nós.

Inferência Aproximada:

A inferência Bayesiana exata sob um prior de GGP de atividade infinita é computacionalmente proibitiva. Os autores propõem uma aproximação utilizando a distribuição etBFRY (exponentially tilted BFRY), que converge para o GGP à medida que o nível de truncamento aumenta. A inferência é realizada utilizando Hamiltonian Monte Carlo (HMC) via algoritmo NUTS (No-U-Turn Sampler), implementado na linguagem probabilística NumPyro.

3. Contribuições Chave

1. Generalização para Regimes Esparsos: O modelo generaliza os modelos de blocos mistos (Mixed Membership SBM) existentes para o regime de grafos esparsos e de lei de potência, resolvendo a limitação de troca de permutação que força a densidade em modelos clássicos.
2. Dinâmica Realista: Introduz dependência temporal diretamente nas medidas aleatórias, criando um processo gerativo dinâmico genuíno (não apenas uma sequência de grafos estáticos independentes).
3. Propriedades Assintóticas: Estabelecem resultados teóricos rigorosos provando que o modelo gera grafos esparsos com distribuição de grau de lei de potência (expoente $1+\sigma$) quando $\sigma \in (0, 1)$.
4. Interpretabilidade e Quantificação de Incerteza: Fornece estimativas de parâmetros com intervalos de credibilidade, permitindo a análise da evolução das comunidades e a incerteza nas afiliações.

4. Resultados e Validação

Os autores validaram o modelo através de dados sintéticos e um conjunto de dados do mundo real.

• Experimentos Sintéticos:

  • O modelo recuperou com sucesso as afiliações das comunidades e os pesos de sociabilidade dos nós.
  • A distribuição de grau empírica dos dados gerados foi bem coberta pelos intervalos de credibilidade preditiva posterior (95% PPCI), confirmando a capacidade do modelo de capturar a lei de potência e a esparsidade.
  • A aproximação de inferência demonstrou alta cobertura (96% para pesos e 95% para pontuações).

• Aplicação Real: Reuters Terrorist Dataset:

  • Dados: Rede de co-ocorrência de palavras em notícias sobre os ataques de 11 de setembro de 2001 e eventos subsequentes (ataques de antraz, guerra no Afeganistão) ao longo de 6 semanas.
  • Descobertas: O modelo identificou comunidades temáticas que evoluíram semanticamente ao longo do tempo:
    • "Ataque": Começou focado no 11/09 (WTC, avião) e migrou para incluir o ataque ao Afeganistão.
    • "Afeganistão": Inicialmente focado no Talibã, expandiu-se para incluir termos de guerra.
    • "Segurança": Evoluiu de segurança aeroportuária para segurança nacional e, posteriormente, para segurança de saúde (devido ao antraz).
    • "Antraz": Emergiu como uma nova comunidade na semana 4, absorvendo termos relacionados a saúde e política.
  • Comparação: O modelo superou significativamente os concorrentes:
    • SNetOC (Estático): Falhou em capturar a evolução temporal e a mudança de significado das comunidades.
    • dynSBM (Blocos Estocásticos Dinâmicos): Falhou em capturar a esparsidade e a distribuição de lei de potência, gerando um ajuste ruim.
    • dMMSB (Membros Mistos Dinâmicos): Falhou em detectar estrutura de comunidade significativa, agrupando apenas os nós de maior grau em uma única comunidade.

5. Significância

O trabalho dynSNetOC representa um avanço significativo na modelagem de redes complexas. Ele preenche uma lacuna crítica ao oferecer um framework unificado que lida simultaneamente com:

• Esparsidade e Lei de Potência: Essenciais para modelar redes sociais, biológicas e de citações reais.
• Sobreposição Dinâmica: Captura a natureza fluida e multifacetada das afiliações em redes temporais.
• Evolução Temporal: Permite rastrear o surgimento, fusão e dissolução de comunidades de forma interpretável.

A capacidade de modelar a evolução semântica de comunidades (como demonstrado no caso do 11/09) e a robustez em dados esparsos tornam esta ferramenta valiosa para análise de redes em ciências sociais, biologia e economia, onde a estrutura da rede é inerentemente dinâmica e heterogênea.