Abstract
Algorithms for identifying the infection states of nodes in a network are crucial for understanding and containing epidemics and cascades. Often, however, only the infection states of a small set of nodes are known. Moreover, the length of time that each node has been infected is also unknown. This missing data – infection states of most nodes and the infection times of the observed infected nodes – poses a challenge to the study of real-world epidemics/cascades. In this work, we develop techniques to identify the latent infected nodes in the presence of missing infection time-and-state data. Based on likely epidemic paths predicted by a simple susceptible-infected epidemic model, we propose a measure (infection betweenness centrality) for uncovering unknown infection states. We evaluate infection state classifiers based on Naive Bayes, Naive Bayes with kernel density estimation, and decision trees, in combination with features including infection betweenness centrality and different centrality measures. Our experimental results show that among the set of features that include degree and different centrality measures, infection betweenness centrality is the most effective feature for identifying latent infected nodes.
The Challenge of Hidden Infections
When a virus, rumor, or piece of malware spreads through a complex network, researchers rarely have a complete view of the system. Typically, only a small, random sample of infected nodes is discovered—such as patients visiting a clinic or specific servers triggering security alerts. Crucially, the exact time of infection and the specific transmission paths are often unknown.
The primary objective is to "fill in the blanks": given a partial snapshot of infected nodes and the underlying network structure, can we accurately classify the remaining unobserved nodes as either "susceptible" or "infected"?
Standard network metrics, such as degree centrality, often fail in this context because they do not account for the specific paths an infection is likely to have taken between known cases.
Methodology: Infection Betweenness Centrality (IBC)
The researchers propose a novel approach based on the Susceptible-Infected (SI) epidemic model. The process involves three key stages:
- Deterministic Reduction: Using graph theory, the algorithm first identifies nodes that must be susceptible. For instance, if removing all observed healthy nodes disconnects a portion of the graph that contains no known infections, that entire component can be ruled out as healthy.
- Infection Betweenness Centrality (IBC): This is the core innovation. Unlike standard betweenness centrality, which considers all shortest paths, IBC calculates the probability that a node lies on a transmission path specifically between known infected pairs. It utilizes a weighted sum of all possible paths via matrix inversion: $N = (I - \alpha A)^{-1}$.
- Machine Learning Classification: IBC is integrated with other features—including normalized degree, observed infected neighbor ratio, and standard centrality measures (betweenness, closeness, and eigenvector)—into classifiers like Naive Bayes (NB), Naive Bayes with Kernel Density Estimation (NBK), and C4.5 Decision Trees.
Experimental Evaluation
The methodology was tested across five diverse real-world networks: YEAST (protein interactions), GRQC & HEPTH (ArXiv collaborations), POWER (power grid topology), and OREGON (Internet Autonomous Systems). These networks represent a wide range of topologies, from nearly planar to highly skewed scale-free structures.
Key Insights and Results
The experimental results consistently highlighted Infection Betweenness Centrality (IBC) as the most effective feature for identifying latent infected nodes.
- Performance Gains: In the YEAST and POWER networks, adding IBC to a C4.5 Decision Tree improved the F-measure by approximately 0.15 to 0.3.
- Classifier Strengths: C4.5 Decision Trees generally achieved the highest precision, while NBK was superior for recall (identifying a higher total percentage of infected nodes).
- Topological Impact: The study found a strong negative correlation between a network's degree skewness and classifier performance. In "scale-free" networks like OREGON, where a few hubs connect the entire graph, isolating infection paths becomes significantly more difficult.
Conclusion and Future Directions
While IBC significantly advances our ability to track hidden cascades, limitations remain. The current model assumes a single infection source and follows the SI model, where nodes do not recover. Future research will focus on adapting these techniques to the SIR (Recovered) model and scenarios involving multiple initial sources or partially hidden network structures.
Summary updated