Classifying latent infection states in complex networks

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

TL;DR

This paper tackles the challenge of identifying infected nodes in a network when only a small subset of nodes have known infection states and no infection timestamps are available. They introduce "Infection Betweenness," a novel metric that leverages epidemic propagation models to pinpoint likely infected nodes, achieving up to 90% accuracy in simulations.

What Problem Does This Paper Address?

In many real-world scenarios, like tracking computer malware or the spread of rumors, we only observe a fraction of infected entities. This makes it difficult to understand the full scope of an epidemic and take effective action. The problem is compounded when we don't even know when an infection started for the observed nodes. This paper aims to solve the problem of accurately identifying the infection state of unobserved nodes in a network, given a limited set of observed infected/susceptible nodes and the network's topology.

Methods

The core of the paper's contribution lies in the introduction of Infection Betweenness (IB). This metric is derived from the Susceptible-Infected (SI) epidemic model and quantifies how likely a node is to be infected based on its position within potential epidemic paths connecting known infected nodes.

Here's a breakdown of the method:

  • Propagation Properties: They first establish two key properties based on the SI model:
  • If removing susceptible nodes disconnects the network, infected nodes must reside in the remaining connected component.
  • If a set of nodes divides known infected nodes into separate components, at least one node in that set must be infected.
  • Infection Betweenness (IB): This metric is calculated for each unobserved node. It essentially measures the proportion of weighted paths between known infected nodes that pass through the unobserved node. A higher IB suggests a greater likelihood of that node being infected.
  • Machine Learning Integration: IB is then used as a feature in machine learning classifiers (Naive Bayes, NBK, and C4.5 decision trees) to predict the infection state of unobserved nodes. They also incorporate other standard network features like degree, betweenness centrality, and closeness centrality.

Datasets

The authors evaluated their approach on five real-world network datasets, categorized as:

  • Biological: YEAST
  • Collaboration: GRQC, HEPTH
  • Device: POWER, OREGON

These datasets vary in size and characteristics, allowing for a comprehensive evaluation of the proposed method across different network structures.

Key Insights and Ideas

  • IB as a Powerful Feature: The most significant finding is that Infection Betweenness (feature P) is a highly effective predictor of a node's infection state, often outperforming other standard network centrality measures.
  • Simplicity vs. Complexity: While combining multiple features generally improves performance, the paper notes that for some classifiers (like C4.5), IB alone is so powerful that adding more features doesn't significantly boost accuracy and can sometimes even lead to slight degradation. This suggests that IB captures a fundamental aspect of epidemic spread.
  • Network Structure Matters: The performance of the classifiers is influenced by network characteristics. Specifically, lower degree skewness and standard deviation lead to more accurate predictions, indicating that more homogeneous networks are easier to analyze.
  • Trade-off between Precision and Recall: Different classifiers exhibit different strengths. NBK tends to achieve higher recall (finding more infected nodes) but with lower precision (more false positives), while C4.5 offers better precision.

Key Results

  • The proposed method using Infection Betweenness as a feature achieved classification accuracies of up to 90%.
  • The IB metric was found to be the most effective feature for identifying latent infected nodes across various machine learning algorithms and network topologies.
  • Machine learning classifiers using IB outperformed random-guessing significantly in both precision and recall.
  • Increasing the fraction of observed nodes generally leads to improved prediction accuracy for all classifiers.
  • For the OREGON network, while precision was relatively high, recall was low, indicating that many infected nodes were misclassified as healthy.

Limitations and Future Work

  • Limited Infection Timestamps: The current work assumes no knowledge of infection timestamps. The authors suggest that incorporating this information could further improve accuracy.
  • Network Characteristics Impact: While they identified correlations between network characteristics (like degree skewness) and performance, a deeper theoretical analysis is suggested for future work.
  • Extensive Experiments: The authors plan to conduct more extensive experiments with larger networks and explore other classifiers, such as those based on random forests.
  • Improving Recall: For classifiers that struggle with recall (like NBK in some cases), future work will focus on methods to improve their ability to identify infected nodes.

Summary updated

Abstract

In this work, we develop techniques to identify the latent infected nodes in the presence of missing infection time-and-state data. Based on the likely epidemic paths predicted by the simple susceptible-infected epidemic model, we propose a measure (Infection Betweenness Centrality) for uncovering unknown infection states. Our experimental results using machine learning algorithms show that Infection Betweenness Centrality is the most effective feature for identifying latent infected nodes.
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