A General Marked Point Process Framework For Self-Exciting Network Evolution

1. Problema e Motivação

O artigo aborda a modelagem de redes dinâmicas que evoluem em tempo contínuo, onde tanto o momento das atualizações (tempo) quanto a natureza dessas atualizações (topologia: adição de nós e arestas) são interdependentes.

• Limitações dos Modelos Atuais:
  • Modelos tradicionais de redes dinâmicas (como SAOM, TERGM, STERGM) geralmente tratam o conjunto de nós como fixo e focam apenas na formação de arestas, não permitindo inferência sobre a chegada de novos nós.
  • Modelos de processos pontuais existentes (como processos de Hawkes multivariados ou modelos de eventos relacionais) frequentemente assumem que a intensidade é separável (o tempo e o tipo de evento são independentes após condicionar ao histórico) ou dependem de suposições de Markov de primeira ordem que ignoram dependências de longo prazo e a estrutura complexa da rede.
  • Em muitos cenários reais (ex.: redes sociais, interações biológicas), existe auto-excitação: a chegada de um nó ou aresta aumenta a probabilidade de futuras atualizações, e a topologia atual da rede determina quais atualizações são plausíveis.

O objetivo é criar um framework unificado que modele conjuntamente o tempo e a topologia da rede, capturando a dependência não separável entre o momento do evento e o conteúdo do evento (a atualização da rede).

2. Metodologia Proposta: HawkesNet

Os autores propõem um novo framework baseado em Processos Pontuais Marcados (MPP - Marked Point Processes), denominado HawkesNet.

Conceitos Fundamentais:

• Processo Pontual Markado: Cada atualização da rede (adição de nós e/ou arestas) é tratada como um evento em um tempo $t_i$, com um "marcador" ($m_i$) que descreve a mudança estrutural específica (quais nós e arestas foram adicionados).
• Espaço de Marcas Dinâmico: Diferente de processos pontuais clássicos com espaços de marcas fixos, o espaço de marcas admissíveis ($\mathcal{M}_t$) evolui com o estado atual da rede $\mathcal{G}_{t-}$. Uma marca é admissível apenas se respeitar as regras do grafo (ex.: não criar arestas duplicadas, nós devem existir ou ser criados simultaneamente).
• Intensidade Condicional Não-Separável: A intensidade condicional $\lambda(t, m | \mathcal{H}_t)$ é fatorada como:
  $$\lambda(t, m | \mathcal{H}_t) = \lambda_g(t | \mathcal{H}_t) \cdot q(m | t, \mathcal{H}_t)$$
  Onde:
  • $\lambda_g$: Taxa de base (ground rate) que determina quando ocorre uma atualização.
  • $q$: Função de massa de probabilidade (PMF) que determina qual atualização ocorre, baseada no histórico.
  • Não-separabilidade: Ambos os componentes podem depender do histórico completo da rede (topologia e tempo), permitindo feedback entre a estrutura da rede e a taxa de eventos.

Especificações do Modelo (HawkesNet):

Os autores propõem duas especificações induzidas para a PMF $q$:

1. Preferential Attachment HawkesNet (BA): Baseado no modelo Barabási-Albert. Novos nós tendem a se conectar a nós existentes com alta grau, com um decaimento temporal na "aptidão" (fitness) dos nós.
2. Change Statistic HawkesNet (CS): Baseado em Estatísticas de Mudança (similar a ERGMs). A probabilidade de uma aresta ser adicionada depende de estatísticas de rede (ex.: fechamento de triângulos, popularidade de nós) e covariáveis nodais, modelada via uma função logística com decaimento temporal.

Processos de Hawkes Dependentes do Caminho (Mark Path Dependent):

O framework introduz uma generalização dos processos de Hawkes onde o kernel de excitação não é fixo no nascimento do evento, mas depende do estado atual do grafo. Isso permite que uma aresta antiga, que inicialmente tinha pouco impacto, ganhe influência à medida que se torna parte de muitos triângulos ou estruturas densas.

3. Contribuições Chave

1. Framework Unificado: Uma caracterização teórica rigorosa de redes em crescimento contínuo como processos pontuais marcados, unificando a modelagem de tempo e topologia.
2. Inferência Baseada em Verossimilhança: Demonstração de que, apesar da complexidade do espaço de marcas dinâmico, a decomposição algébrica da intensidade permite uma avaliação de verossimilhança tratável e eficiente ($O(n)$ para kernels exponenciais).
3. Teoria de Estabilidade e Bem-Postura:
   • Prova de existência, unicidade e não-explosão do processo sob condições de contração (Lipschitz ponderado).
   • Estabelecimento de que o crescimento esperado da rede é no máximo linear, garantindo estabilidade.
4. Algoritmo de Simulação: Implementação de um algoritmo de "thinning" (riscamento) de Ogata adaptado para espaços de marcas dinâmicos, permitindo a simulação exata de redes complexas.
5. Software: Desenvolvimento do pacote R hawkesNet para implementação, simulação e inferência.

4. Resultados

Estudo de Simulação:

• Recuperação de Parâmetros: Em regimes estáveis, os estimadores de máxima verossimilhança (MLE) recuperam com precisão os parâmetros tanto da componente temporal (Hawkes) quanto da componente estrutural (PMF de marcas).
• Consistência: À medida que a janela de tempo de observação aumenta, a variância dos estimadores diminui e eles convergem para os valores verdadeiros.
• Regimes Críticos: O estudo ilustra a diferença entre regimes estáveis e supercríticos (explosivos), mostrando que a condição de não-explosão é crucial para a inferência confiável.

Aplicação Empírica (Conferência ACM Hypertext 2009):

• Dados: Rede de contatos face-a-face de 100 participantes durante 16 horas.
• Modelo Ajustado: Utilizou-se o modelo Change Statistic HawkesNet com termos de "Geometrically Weighted Edgewise Shared Partners" (GWESP) e "Geometrically Weighted Degree" (GWDEG) para capturar fechamento social e popularidade.
• Desempenho:
  • O modelo capturou com sucesso a distribuição de graus, a distribuição de parceiros compartilhados (ESP) e as distâncias geodésicas.
  • Os parâmetros indicaram forte evidência de fechamento social (triadic closure) e preferências por nós populares.
  • A taxa de decaimento temporal ($\beta$) foi alta, sugerindo que interações são altamente localizadas no tempo (eventos desencadeiam interações imediatas).
  • O ajuste foi superior a modelos que tentavam usar apenas termos simples de triângulos e estrelas, que falharam em reproduzir a estrutura observada.

5. Significância e Conclusão

O artigo fornece uma fundação estatística principista para a análise de redes em tempo contínuo. Ao tratar a evolução da rede como um processo pontual marcado com dependência não separável, o HawkesNet supera as limitações de modelos discretos e de processos pontuais lineares tradicionais.

• Interpretabilidade: Permite inferência direta sobre mecanismos sociais e estruturais (ex.: como a estrutura atual influencia a probabilidade de novas conexões).
• Flexibilidade: O framework é modular e pode acomodar diferentes mecanismos de crescimento (preferencial, baseado em covariáveis, etc.).
• Aplicabilidade: A demonstração em dados reais de contatos humanos valida a utilidade do método para entender dinâmicas sociais complexas, onde o tempo e a estrutura evoluem em conjunto.

Em resumo, o trabalho estabelece um novo padrão para modelagem de redes dinâmicas, permitindo a análise de dependências de longo prazo e a interação complexa entre a evolução temporal e a topológica da rede, com garantias teóricas de estabilidade e ferramentas computacionais práticas.