Autoregressive networks with dependent edges

Resumo Técnico: Redes Autoregressivas com Arestas Dependentes

1. Problema e Motivação

A modelagem de redes dinâmicas é fundamental para entender a evolução de sistemas sociais, biológicos e econômicos. No entanto, a maioria dos modelos existentes enfrenta desafios técnicos significativos ao lidar com dependência entre arestas (edges).

• Limitações dos Modelos Atuais:
  • Modelos como ERGMs (Exponential Random Graph Models) e seus equivalentes temporais (TERGMs) são flexíveis, mas a inferência estatística (especialmente a estimação de máxima verossimilhança) é computacionalmente complexa e carece de teoria assintótica robusta para redes de alta dimensão.
  • Modelos autoregressivos (AR) anteriores frequentemente assumem que as arestas são independentes condicionalmente ao passado ou dependem apenas de suas próprias histórias (dependência aresta-a-aresta), ignorando fenômenos sociais cruciais como transitividade ("o amigo do meu amigo é meu amigo") e heterogeneidade de grau (popularidade).
  • Modelos baseados em variáveis latentes (como SBM dinâmico) induzem dependência de forma implícita, dificultando a configuração direta de características estilísticas observadas em dados reais.
• O Desafio: Desenvolver um framework que permita dependência explícita entre arestas (dentro de um instante de tempo e ao longo do tempo), seja computacionalmente tratável e possua fundamentação teórica assintótica rigorosa, mesmo quando o número de nós ($p$) cresce junto com o tamanho da amostra ($n$).

2. Metodologia Proposta

Os autores propõem uma nova classe de Modelos Autoregressivos de Arestas Dependentes (dep. edge AR).

• Estrutura do Modelo:

  • O processo é definido em tempo discreto com $p$ nós.
  • A probabilidade de uma aresta $X_{i,j}^t$ existir no tempo $t$ depende condicionalmente das arestas no tempo $t-1$ (e possivelmente $t-m$), mas, crucialmente, a formação/dissolução de uma aresta específica depende do estado de outras arestas na rede (não apenas da sua própria história).
  • Assumem-se arestas condicionalmente independentes dado o histórico da rede inteira. Isso permite a construção de uma estrutura de diferença de martingale, facilitando a análise teórica.
  • As probabilidades de transição ($\alpha$ para formação, $\beta$ para dissolução) são modeladas como funções de parâmetros globais (comuns a toda a rede) e parâmetros locais (específicos por nó), capturando heterogeneidade.

• Exemplos de Modelos Específicos:

  1. Heterogeneidade de Grau: Captura o efeito "o rico fica mais rico", onde nós com alto grau têm maior probabilidade de formar novas conexões.
  2. Persistência: Modela a estabilidade das conexões ao longo de múltiplos períodos.
  3. Transitividade: Modela explicitamente a probabilidade de formação de arestas baseada no número de vizinhos comuns (triângulos) e dissolução baseada em vizinhos disjuntos.

• Procedimento de Estimação:

  • Devido ao grande número de parâmetros (especialmente os locais, que crescem com $p$), a estimação direta de máxima verossimilhança (MLE) sofre de taxas de convergência lentas.
  • Solução Proposta: Um estimador de dois estágios baseado em projeção:
    1. Estimador Inicial: Maximização de funções de verossimilhança parciais para obter estimadores iniciais para parâmetros globais e locais.
    2. Estimador Melhorado: Utiliza a projeção da função de pontuação (score function) na direção do parâmetro de interesse. Isso mitiga o impacto dos parâmetros de "incômodo" (nuisance parameters) de alta dimensão.
  • A distribuição assintótica do estimador melhorado é derivada sem assumir estacionariedade estrita, embora reduza-se à normalidade sob condições de mistura (mixing conditions).

3. Contribuições Principais

1. Novo Framework de Modelagem: Estende os modelos AR de redes para permitir dependência explícita entre arestas, acomodando características estilísticas complexas (transitividade, heterogeneidade) que modelos AR anteriores não conseguiam capturar facilmente.
2. Teoria Assintótica de Alta Dimensão: Fornece uma análise assintótica rigorosa para estimadores de máxima verossimilhança em redes dinâmicas onde o número de nós $p$ pode divergir com o tamanho da amostra $n$ (cenário $p \ll n^\delta$). Isso é um avanço significativo, pois a ergodicidade e o Teorema do Limite Central padrão não se aplicam diretamente quando $p$ cresce.
3. Método de Estimação Eficiente: Desenvolve um algoritmo de estimador melhorado via projeção que supera as limitações de convergência dos estimadores iniciais, permitindo inferência estatística válida (intervalos de confiança) em redes grandes.
4. Conexão com TERGMs: Demonstra teoricamente como os modelos propostos se relacionam com os TERGMs (Temporal Exponential Random Graph Models), mostrando que uma classe específica de TERGMs com independência condicional de arestas pode ser reescrita como um modelo AR.
5. Software e Aplicação: Implementação em um pacote R de código aberto (arnetworks) e aplicação em dados reais de interações por e-mail e redes de conferências.

4. Resultados

• Simulações:
  • Os experimentos mostram que o estimador melhorado (projetado) supera significativamente o estimador inicial em termos de erro médio absoluto (rMAE), especialmente em cenários de alta dimensão.
  • As probabilidades de cobertura dos intervalos de confiança de 95% permanecem próximas do nível nominal, validando a aproximação assintótica normal proposta.
  • O método é robusto para redes com $p$ até 500 nós e $n=100$.
• Análise de Dados Reais (Interações por E-mail):
  • Aplicado a dados de uma empresa polonesa (106 nós, 39 semanas).
  • O modelo de transitividade capturou efeitos significativos: a probabilidade de formação de arestas aumenta com o número de amigos em comum, e a dissolução aumenta com vizinhos disjuntos.
  • Identificou heterogeneidade nos nós: gerentes tendem a formar mais arestas do que não-gerentes.
  • Comparação de Modelos: O modelo AR com transitividade obteve o menor critério de informação bayesiano (BIC) e desempenho competitivo no critério de Akaike (AIC) em comparação com modelos concorrentes (como STERGMs e modelos de média aresta-a-aresta), demonstrando eficiência na parametrização de redes esparsas.
  • Previsão: O modelo superou ou foi competitivo com modelos globais e de média em tarefas de previsão de links (ROC curves), embora modelos altamente parametrizados (edge-wise) tenham tido desempenho ligeiramente superior em AUC, sugerindo estrutura de ordem superior não capturada apenas por dois parâmetros por nó.

5. Significado e Impacto

Este trabalho preenche uma lacuna crítica na estatística de redes dinâmicas. Ao combinar a flexibilidade de modelar dependências complexas entre arestas (como transitividade) com a tratabilidade computacional e teórica de modelos autoregressivos, os autores oferecem uma ferramenta poderosa para analisar dados de redes em evolução.

A capacidade de realizar inferência estatística rigorosa em cenários de alta dimensão (onde o número de nós é grande) torna este método aplicável a problemas do mundo real, como análise de redes sociais corporativas, interações biológicas e fluxos de comércio internacional, onde a dependência estrutural é a regra, não a exceção. A disponibilização do software e a validação empírica sólida reforçam a utilidade prática da proposta.