Classifying Latent Infection States in Complex Networks

Yeon-Sup Lim, Bruno F. Ribeiro, Don Towsley

Introduction

When a cascade—such as a biological epidemic, a computer virus, or a viral tweet—spreads through a network, researchers rarely possess a complete picture. Typically, only a small subset of infected nodes is observed, such as patients admitted to a hospital or computers reporting a specific bug. This leaves two major gaps: missing states (the status of most nodes is unknown) and missing timestamps (the exact time of infection for observed nodes is unavailable).

Visualizing the challenge: known infected nodes (red), known susceptible (white), and latent/unobserved nodes (dashed).

Identifying these latent infected nodes is critical for effective containment and mitigation strategies. However, most existing tools require complete data, which is rarely available in real-world scenarios.

Methods: Infection Betweenness

To address this, the authors propose a novel centrality measure: Infection Betweenness (IB). While standard betweenness centrality measures how often a node lies on the shortest path between any two nodes, IB is tailored for epidemics. It calculates the likelihood that an unobserved node lies on a transmission path between two known infected nodes.

The IB metric considers all possible paths, assigning higher weights to shorter ones via a parameter $\alpha$. By calculating the fraction of weighted paths passing through a specific unobserved node $u$ to connect known infected nodes, the model estimates the probability that $u$ is part of the cascade.

The workflow involves:

  1. Graph Pruning: Identifying "definitely healthy" nodes that, if removed, would disconnect the infection source from the rest of the graph.
  2. Feature Extraction: Calculating IB and other standard network features (degree, closeness, etc.) for unobserved nodes.
  3. Classification: Using machine learning models like Naive Bayes and C4.5 Decision Trees to predict infection states.

Key Insights: The "Silver Bullet" Feature

A primary finding of the study is that Infection Betweenness (denoted as $P$ in analysis) is the most predictive feature across diverse network topologies, including biological (Yeast), collaboration (GrQc, HepTh), infrastructure (Power), and internet (Oregon) networks.

Feature importance heatmap for the C4.5 classifier across different topologies. Feature 'P' (Infection Betweenness) consistently shows the highest predictive power.

While standard metrics like degree or closeness provide some utility, they are significantly less reliable than IB for identifying latent states. Furthermore, the "shape" of the network influences difficulty; networks with a few massive "hubs" are often harder to classify accurately than those with more uniform degree distributions.

Results and Performance

The proposed method achieved up to 90% accuracy in classifying unobserved nodes and successfully identified up to 80% of total infected nodes, even with limited initial observations. The integration of IB into standard feature sets provided a substantial boost to the F-measure, particularly in biological and collaboration networks. While performance naturally improves as the observation rate increases (from 5% to 25%), the IB-based classifiers consistently outperformed baseline models even at very low observation levels.

Conclusion and Future Work

This research demonstrates that latent infection states can be accurately predicted using structural network properties and machine learning. Future work may extend this model to accommodate multiple infection sources and more complex epidemic models like SIR (Recovered) or SIS (Susceptible-Infected-Susceptible), as well as addressing the computational scalability required for massive social networks.

Summary updated

BibTeX
@inproceedings{lim2014classifying,
  author = {Yeon-Sup Lim and Bruno F. Ribeiro and Don Towsley},
  title = {{Classifying Latent Infection States in Complex Networks}},
  booktitle = {The Web Conference},
  year = {2014},
  doi = {10.1145/2567948.2579361},
}
Figure