Reconstructing Network Outbreaks under Group Surveillance

Titolo: Ricostruzione di Focolai Epidemici sotto Sorveglianza di Gruppo

1. Il Problema

Il lavoro affronta la sfida cruciale di ricostruire la cascata di diffusione di una malattia (l'insieme dei nodi infetti e le vie di trasmissione) partendo da un insieme parziale di osservazioni, in un contesto di sorveglianza di gruppo (o group surveillance).

• Contesto: Tradizionalmente, la ricostruzione di focolai si basa su test individuali (pool di dimensione 1). Tuttavia, metodi moderni come il monitoraggio delle acque reflue o degli aerosol biologici utilizzano il pool testing: campioni di più individui vengono mescolati e testati insieme.
• La Sfida:
  • Un test negativo su un pool chiarisce che nessuno degli individui nel pool è infetto.
  • Un test positivo indica che almeno uno degli individui nel pool è infetto, ma non specifica chi.
• Obiettivo: Definire e risolvere il problema PoolCascadeMLE. L'obiettivo è trovare la cascata di diffusione con la massima verosimiglianza (Maximum Likelihood Estimation - MLE) che sia coerente con i risultati dei test di gruppo. A differenza dei casi precedenti, una cascata coerente deve includere almeno un nodo da ogni pool positivo, aggiungendo un livello combinatorio complesso.

2. Metodologia e Modelli

Gli autori utilizzano il modello Independent Cascade (IC) per la diffusione delle malattie su una rete non diretta $G=(V, E)$.

Formulazione del Problema

• PoolCascadeMLE: Dato un grafo, un nodo seme (o un insieme di semi) e un insieme di pool di test (positivi $\Gamma_1$ e negativi $\Gamma_0$), si cerca un sottografo (cascata) radicato che minimizzi il costo logaritmico derivante dalle probabilità di trasmissione e non-transmissione, rispettando i vincoli di coerenza (nessun nodo dai pool negativi, almeno un nodo da ogni pool positivo).
• One-HopCascadeMLE: Una variante semplificata in cui la malattia si diffonde per un solo passo temporale dopo la semina. Questo è rilevante per scenari come il monitoraggio delle acque reflue o negli allevamenti animali.

Risultati di Complessità (Hardness)

• PoolCascadeMLE: È dimostrato essere NP-hard da approssimare entro un fattore $O(\log^{2-\epsilon} k)$, dove $k$ è il numero di pool positivi. Questo è significativamente più difficile rispetto al caso con pool di dimensione 1 (che ammette un'approssimazione $O(\log k)$).
• One-HopCascadeMLE: Anche questa versione ristretta è NP-hard da approssimare entro un fattore $O(\log k)$, ridotta dal problema della Copertura degli Insiemi (Set Cover).

Algoritmi Proposti

1. ApproxCascade (per PoolCascadeMLE):

   • Si basa su una riduzione al problema del Group Steiner Tree (GST) su un grafo con pesi su nodi e archi.
   • Costruisce un grafo ausiliario rimuovendo i nodi dei pool negativi e assegnando pesi specifici agli archi e ai nodi basati sulle probabilità di trasmissione ($p_e$) e non-transmissione ($1-p_e$).
   • Utilizza un algoritmo di approssimazione per il Directed Steiner Tree (Charikar et al.) per ottenere un fattore di approssimazione di $O(k^\epsilon)$.
   • Assunzione: Probabilità di trasmissione $p_e \le 1/2$.

2. RoundCascade (per One-HopCascadeMLE):

   • Formula il problema come un Programma Lineare Intero (ILP).
   • Rilassa le variabili intere per ottenere un LP.
   • Utilizza una tecnica di arrotondamento randomizzato (randomized rounding) per convertire la soluzione frazionaria in una soluzione intera fattibile.
   • Garantisce un fattore di approssimazione randomizzato di $(2 + 2 \ln k)$.

3. Risultati Sperimentali

Gli algoritmi sono stati valutati su reti sintetiche (Barabási-Albert, Erdős-Rényi) e reti reali (rete di contatti dell'ICU di un ospedale UVA e una rete di una piccola città basata su dati demografici).

• Metriche:
  1. Recupero delle infezioni mancanti: Misurato tramite F1-score (confronto tra nodi ricostruiti e verità fondamentale).
  2. Stima della prevalenza: Misurata tramite errore relativo sulla dimensione della cascata.
• Confronto con Baseline:
  • ApproxCascade vs. Baseline: Le baseline riducevano i pool a dimensione 1 scegliendo nodi casualmente o assumendo che tutti i nodi del pool positivo fossero infetti.
  • Risultati: ApproxCascade supera significativamente le baseline, specialmente in condizioni di bassa probabilità di diffusione. In questi scenari, la selezione sistematica dei nodi infetti all'interno di un pool è cruciale. Quando la diffusione è alta e quasi tutti i nodi di un pool sono infetti, le performance si avvicinano, ma ApproxCascade rimane competitivo.
  • RoundCascade: Supera la baseline randomizzata in tutti i regimi di malattia e tipi di rete.
• Impatto della dimensione del pool: All'aumentare della dimensione del pool, le performance degradano (come atteso, data la crescita esponenziale delle combinazioni possibili), ma il metodo proposto rimane superiore alle baseline.

4. Contributi Chiave

1. Introduzione del problema PoolCascadeMLE: Formalizzazione matematica della ricostruzione di focolai sotto vincoli di test di gruppo, un problema precedentemente non studiato in letteratura.
2. Analisi di Complessità: Dimostrazione che il problema è intrattabile anche per l'approssimazione, con limiti di approssimazione più severi rispetto ai test individuali.
3. Algoritmi di Approssimazione: Sviluppo di ApproxCascade (basato su Group Steiner Tree) e RoundCascade (basato su LP e arrotondamento randomizzato) con garanzie teoriche.
4. Valutazione Empirica: Dimostrazione che l'approccio sistematico supera i metodi che trattano i pool come singoli individui, specialmente in scenari realistici di bassa trasmissione.
5. Analisi dei Limiti: Mostrare come il rumore nei test (falsi positivi/negativi) possa alterare drasticamente la soluzione MLE, portando a ricostruzioni molto diverse dalla verità fondamentale, e come la sovrapposizione dei pool possa mitigare questo problema.

5. Significato e Implicazioni

Questo lavoro è fondamentale per la epidemiologia computazionale e la sorveglianza sanitaria pubblica.

• Applicazioni Pratiche: Fornisce un framework teorico e pratico per interpretare dati provenienti da monitoraggio delle acque reflue, aerosol e test di gruppo su larga scala, strumenti sempre più usati per il tracciamento di patogeni (es. COVID-19, influenza aviaria).
• Ottimizzazione delle Risorse: Dimostra che non è sufficiente trattare i pool come singoli individui; è necessario un approccio combinatorio ottimizzato per recuperare accuratamente la struttura dell'epidemia.
• Robustezza: Evidenzia la sensibilità delle soluzioni MLE al rumore, suggerendo la necessità di strategie di test sovrapposti (overlapping pools) per migliorare la resilienza delle ricostruzioni.

In sintesi, il paper colma un divario significativo tra le tecniche di test di gruppo esistenti (focalizzate sull'allocazione dei test) e la necessità di ricostruire la dinamica di diffusione, offrendo algoritmi efficienti e teoricamente fondati per la gestione delle epidemie.