Resumo Técnico: Bootstrap Paramétrico para Modelos de Rede com Probabilidade de Aresta Fixa

Declaração do Problema

O artigo aborda o desafio de quantificar a incerteza de estatísticas de rede (por exemplo, contagens de subgrafos, coeficientes de agrupamento, medidas de centralidade) em dados de rede aleatória. Embora métodos existentes de reamostragem de rede, como subamostragem e procedimentos jackknife, tenham sido desenvolvidos principalmente para estatísticas de contagem sob modelos de grafon com troca de nós, eles frequentemente falham em abordar dois problemas críticos:

1. Não troca de nós: Muitas aplicações práticas envolvem redes com propriedades heterogêneas de nós, onde a suposição de troca de nós (invariância a permutações de rótulos) é indesejável ou incorreta. Nesses casos, preservar informações específicas de cada nó é crucial.
2. Viés do Bootstrap: O "natural" bootstrap paramétrico padrão, que estima os parâmetros do modelo gerador da rede e depois reamostra a partir do modelo estimado, sofre de um viés não desprezível. Esse viés surge porque o estimador de plug-in da estatística da rede, $\hat{\mu} = \mu(\hat{P})$, não aproxima com precisão a verdadeira esperança $\mu(P)$ quando o número de parâmetros cresce com o tamanho da rede $n$. Especificamente, a razão entre viés e desvio padrão pode ser da ordem $\Theta(p^{-1/2})$ ou $\Theta((np)^{-1/2})$, tornando os intervalos de confiança padrão inválidos, particularmente em redes esparsas.

Os autores focam no modelo Chung–Lu (um modelo de probabilidade de aresta fixa onde $P_{ij} = p\theta_i\theta_j$) como um quadro de trabalho. Diferentemente dos modelos de grafon, onde posições latentes são aleatórias, este cenário assume posições latentes fixas (ou uma matriz de probabilidade de aresta $P$ fixa), o que significa que a única aleatoriedade provém da realização independente de Bernoulli das arestas.

Metodologia

O artigo propõe um procedimento de bootstrap de dois níveis (duplo) para corrigir o viés inerente ao bootstrap paramétrico padrão.

1. Bootstrap Paramétrico Natural (Um Nível):

   • Estimar a matriz de probabilidade de aresta $\hat{P}$ a partir da rede observada $A$ (por exemplo, usando Estimativa de Máxima Verossimilhança ou SVD).
   • Gerar $B$ redes bootstrap $\hat{A}^{(b)}$ a partir de $\hat{P}$.
   • Calcular a estatística $T(\hat{A}^{(b)})$ para cada amostra.
   • A distribuição dessas estatísticas aproxima a distribuição de $T(A)$, mas a média dessa distribuição bootstrap, $\mu(\hat{P})$, é viesada em relação à média verdadeira $\mu(P)$.

2. Bootstrap de Dois Níveis (Correção de Viés):

   • Nível 1: Gerar $B_1$ redes bootstrap $\hat{A}^{(b)}$ a partir do modelo estimado $\hat{P}$.
   • Nível 2: Para cada $\hat{A}^{(b)}$, reestimar os parâmetros do modelo para obter $\hat{\hat{P}}^{(b)}$. Em seguida, gerar $B_2$ redes de segundo nível $\hat{\hat{A}}^{(b,c)}$ a partir de $\hat{\hat{P}}^{(b)}$.
   • Estimação do Viés: O viés do estimador de um nível é estimado como:
     $$\widehat{\text{Viés}}_{\hat{P}} = \mathbb{E}_{\hat{P}}[\mu(\hat{\hat{P}})] - \mu(\hat{P}) \approx \frac{1}{B_1} \sum_{b=1}^{B_1} \mu(\hat{\hat{P}}^{(b)}) - \mu(\hat{P})$$
   • Correção: A estimativa pontual corrigida para o viés é construída como $2\mu(\hat{P}) - \mathbb{E}_{\hat{P}}[\mu(\hat{\hat{P}})]$.

Esta abordagem estende o princípio clássico do bootstrap iterativo para o cenário de rede, onde a dimensão do parâmetro escala com $n$. O método é aplicável tanto a estatísticas globais (por exemplo, contagem total de triângulos) quanto a estatísticas locais (por exemplo, contagens de subgrafos enraizados, coeficientes de agrupamento locais).

Principais Contribuições e Resultados Teóricos

1. Caracterização do Viés do Bootstrap

Os autores derivam a ordem assintótica do viés do bootstrap para contagens de subgrafos sob o modelo Chung–Lu.

• Para uma contagem de subgrafo enraizado de um grafo $R$ com $v$ vértices e $e$ arestas, o viés é da ordem $\Theta(n^{v-2}p^{e-1})$.
• Para uma contagem global de subgrafos, o viés é da ordem $\Theta(n^{v-1}p^{e-1})$.
• Crucialmente, a razão entre viés e desvio padrão é mostrada como não desprezível:
  • Contagens globais: $\Theta(p^{-1/2})$.
  • Contagens enraizadas: $\Theta((np)^{-1/2})$.
    Isso confirma que, mesmo com estimação consistente de parâmetros, o estimador de plug-in $\mu(\hat{P})$ é viesado em relação à variabilidade de amostragem, levando a inferências inválidas se não for corrigido.

2. Redução de Viés via Bootstrap de Dois Níveis

O artigo prova que o bootstrap de dois níveis reduz a ordem do viés remanescente:

• Para contagens enraizadas, o viés remanescente em relação ao viés original é $O_P((np)^{-1/2})$.
• Para contagens globais, a redução é $O_P((np)^{-1})$.
  Consequentemente, o viés remanescente torna-se desprezível em relação ao desvio padrão, permitindo a construção de intervalos de confiança válidos.

3. Estimação de Variância e Intervalos de Confiança

Os autores estabelecem que o bootstrap de segundo nível fornece um estimador consistente para a variância do estimador de plug-in $\mu(\hat{P})$.

• Comparação de Variância: Para muitas estatísticas, $\text{Var}_P(\mu(\hat{P})) \ll \text{Var}_P(T(A))$. Isso implica que os intervalos de confiança baseados na distribuição do estimador de plug-in $\mu(\hat{P})$ (que utiliza a estrutura completa da rede) são significativamente mais estreitos do que aqueles baseados apenas na estatística bruta $T(A)$.
• Construção de Intervalos: O artigo propõe tanto intervalos de aproximação normal quanto intervalos não normais (bootstrap empírico), ambos centrados no estimador corrigido para o viés.

4. Teorema do Limite Central (TLC)

Como um subproduto, o artigo estabelece um TLC para contagens de subgrafos sob o modelo Erdős–Rényi inhomogêneo (uma generalização do modelo Chung–Lu). Este resultado aplica-se tanto a contagens globais quanto a enraizadas de subgrafos sob condições de esparsidade que são mais fracas do que aquelas exigidas pela literatura existente baseada em grafons.

Resultados Empíricos

Experimentos numéricos foram conduzidos utilizando:

• Dados Sintéticos: Redes geradas a partir de Modelos de Bloco Estocástico (SBM) e SBMs Corrigidos por Grau (DCSBM) com níveis de esparsidade variados.
• Dados Reais: A rede do Clube de Karate de Zachary e a rede de Blogs Políticos.

Descobertas:

• Correção de Viés: Os intervalos de bootstrap ingênuos (sem correção de viés) cobrem severamente abaixo do parâmetro verdadeiro, especialmente em redes esparsas. Os intervalos corrigidos para o viés alcançam uma cobertura próxima ao nível nominal (por exemplo, 95%).
• Largura do Intervalo: Intervalos baseados na distribuição de $\mu(\hat{P})$ são consistentemente mais estreitos do que aqueles baseados em $T(A)$, particularmente para estatísticas locais e em regimes esparsos.
• Robustez do Estimador: A correção de viés funciona efetivamente mesmo quando $\hat{P}$ é estimado via SVD ou quando o modelo é ligeiramente mal especificado (por exemplo, número errado de comunidades), embora o estimador DCSBM geralmente produza melhor desempenho do que o SVD.
• Custo Computacional: Embora o bootstrap de dois níveis seja computacionalmente intensivo ($O(B_1 B_2 n^2)$), ele é paralelizável. Os autores observam que, para estatísticas onde a aproximação normal se mantém, o custo computacional pode ser reduzido usando o bootstrap apenas para estimação de variância.

Significado e Alegações

O artigo alega fornecer um remédio geral para o problema do viés do bootstrap em estatísticas de rede sob modelos de probabilidade de aresta fixa. Seu significado reside em:

1. Extensão da Teoria do Bootstrap: Adapta o conceito de bootstrap iterativo para cenários onde o número de parâmetros cresce com o tamanho da amostra, um cenário onde a consistência padrão do bootstrap frequentemente falha.
2. Tratamento da Não Troca de Nós: Ao condicionar em posições latentes fixas (ou uma $P$ fixa), o método preserva propriedades específicas de cada nó, tornando-o adequado para analisar estatísticas locais e redes heterogêneas onde as suposições de troca de nós são inadequadas.
3. Inferência Prática: O método proposto permite a construção de intervalos de confiança precisos e estreitos para uma ampla classe de estatísticas de rede, incluindo aquelas que não são estatísticas U, preenchendo uma lacuna deixada por métodos de reamostragem existentes que focam principalmente em estatísticas de contagem sob modelos de grafon.
4. Fundação Teórica: A derivação da ordem do viés e a prova do TLC para contagens de subgrafos sob modelos Erdős–Rényi inhomogêneos fornecem uma base teórica rigorosa para inferência de rede em regimes esparsos.

Os autores enfatizam que, embora a análise seja conduzida sob o modelo Chung–Lu, espera-se que o fenômeno do viés surja em modelos mais complexos (como DCSBMs multi-comunidade), e o bootstrap de dois níveis serve como um mecanismo de correção robusto e baseado em simulação aplicável a esses cenários.