Visual Mining of Epidemic Networks

Stéphan Clémençon, Héctor de Arazoza, Fabrice Rossi, Viet-Chi Tran

Abstract

We show how an interactive graph visualization method based on maximal modularity clustering can be used to explore a large epidemic network. The visual representation is used to display statistical tests results that expose the relations between the propagation of HIV in a sexual contact network and the sexual orientation of the patients.

Introduction

Analyzing large-scale epidemic networks is a significant challenge for public health officials. When thousands of patients and their sexual contacts are mapped, the resulting graph typically resembles an unreadable "hairball." Standard macroscopic metrics, such as average shortest path, often obscure critical details, while manual inspection is unfeasible at scale. This research addresses the challenge of visual mining: simplifying massive networks without losing the statistical nuances that explain disease transmission dynamics.

Methodology

The study introduces a hierarchical visualization strategy based on three main pillars:

  1. Maximal Modularity Clustering: Instead of individual nodes, the algorithm groups patients into clusters where internal connections are significantly denser than external ones. A multi-level algorithm maximizes "modularity," ensuring clusters represent meaningful communities.
  2. Clustered Graph Visualization: The network is redrawn with each node representing an entire cluster. Node size reflects the number of patients, and edge thickness indicates the volume of sexual contact between groups.
  3. Statistical Overlay: Chi-squared tests are performed on each cluster to determine if its sexual orientation distribution differs significantly from the general population. Nodes are color-coded based on $p$-values, allowing researchers to identify "atypical" pockets of the epidemic.
Statistical overlay on the clustered network showing chi-square p-values and Pearson's residuals for the MSM population.

Data and Insights

The study utilizes the Cuban HIV/AIDS Database, an anonymized national dataset of 5,389 residents detected between 1986 and 2004. A "giant component" of approximately 2,400 patients is linked in a single connected structure.

The most striking discovery was that the epidemic is not homogeneous. It consists of two sparsely connected structures with distinct demographic profiles:

  • The "Mixed" Component: Containing more women and heterosexual men, this component dominated the early phase of the epidemic but is now stagnating.
  • The "MSM" Component: This newer, more densely connected sub-population is currently driving the epidemic's growth.
Temporal shift in the Cuban HIV epidemic showing the rise of MSM cases relative to other groups from 1986 to 2003.

The research found that "geodesic distances" were much shorter within these sub-groups than between them, confirming that the virus remains trapped within these sub-populations for extended periods before jumping to others.

Key Results

The giant component was partitioned into 39 clusters with a high modularity score of 0.85, significantly higher than random graphs (0.74). This proves a very strong community structure. The analysis demonstrated that MSM-dominant clusters are more isolated from the rest of the network than mixed clusters. Furthermore, temporal data illustrates that while "Mixed" clusters are decaying, "MSM" clusters have seen explosive growth since the late 1990s.

Conclusion

Visual mining using modularity-based clustering provides a powerful tool for identifying structural shifts in epidemic networks. Future work will focus on integrating these techniques into open-source platforms like Gephi and validating the methodology on other epidemic types, such as airborne pathogens.

Summary updated

Abstract

We show how an interactive graph visualization method based on maximal modularity clustering can be used to explore a large epidemic network. The visual representation is used to display statistical tests results that expose the relations between the propagation of HIV in a sexual contact network and the sexual orientation of the patients.
BibTeX
@inproceedings{clemencon2011visual,
  author = {Stéphan Clémençon and Héctor de Arazoza and Fabrice Rossi and Viet-Chi Tran},
  title = {{Visual Mining of Epidemic Networks}},
  booktitle = {IWANN},
  year = {2011},
  url = {https://openreview.net/forum?id=MrwVgjfGEEC},
}
Figure