Abstract
Traditional network analysis often relies on static graph representations that aggregate contacts over time, leading to the creation of "ghost paths" and the loss of temporal dynamics. This paper introduces Joint Diagonalisation (JD) as a robust framework for analyzing dynamic contact networks. By identifying a shared eigenspace across multiple network snapshots—represented as spanning trees—the method uncovers distinct "modes" of behavior. Evaluation on real-world datasets, including the Haggle project and MIT Reality Mining, demonstrates that JD can effectively distinguish between structural states such as day/night cycles and conference schedules, offering a middle ground between static amalgamation and high-frequency temporal snapshots.
Introduction
Real-world contact networks, such as human interactions in a workplace or conference, are inherently dynamic. However, the standard approach to analyzing these systems involves "amalgamating" all contacts into a single static graph. This simplification is problematic: it ignores the chronological order of interactions, potentially suggesting paths for information or disease spread that never actually existed.
The challenge lies in representing the "average" structure of a network while respecting its temporal evolution. This paper addresses the problem by seeking a way to identify if a network possesses different "modes of operation"—distinct, recurring structural states. By moving beyond static averages, we can better understand the underlying generators of network behavior.
Methodology
The proposed pipeline utilizes Joint Diagonalisation (JD) to find a common structural basis for a set of temporal snapshots. The process involves four key steps:
- Sampling via Spanning Trees: To ensure causality, the authors use Breadth-First Search (BFS) to generate spanning trees from specific nodes at specific times. These trees represent the actual paths a message might take through the network.
- Joint Diagonalisation: While standard diagonalisation reveals the eigenvectors (axes of importance) of a single matrix, JD seeks a single, shared set of eigenvectors ($U$) that approximately diagonalizes a set of matrices simultaneously. This $U$ represents the "average" eigenspace of the dynamic system.
- Mode Detection: The deviation ($\delta_i$) of each snapshot from this shared eigenspace is measured. A Gaussian Mixture Model (GMM) is then applied to these deviations to statistically identify clusters, which correspond to different behavioral modes.
- Reconstruction: For each identified mode, an "average" static graph can be reconstructed, providing a clear mathematical representation of the network's state during that period.
Experimental Setup and Datasets
The study evaluates the JD method using three real-world traces and a suite of synthetic data:
- Cambridge (Haggle Project): Bluetooth contacts among 36 students/staff over 11 days.
- Infocom06 (Haggle Project): Contacts between 78 conference participants over 3 days.
- MIT Reality Mining: Long-term data from 100 smartphones over 9 months.
- Synthetic Networks: Networks generated using Random, Waxman, and GLP models to verify the algorithm's ability to recover known underlying topologies.
Key Results and Insights
The Multi-Modal Nature of Networks
A primary finding is that real-world networks are not monolithic; they are mixtures of distinct states. The distribution of deviations from the shared eigenspace was consistently multi-modal, proving that "average" behavior is often an artifact of several specific, alternating behaviors.
Mode-Specific Connectivity
In the Cambridge dataset, the analysis identified five distinct modes. While Mode 1 reflected structured "class year" groupings (undergraduates vs. graduates), Mode 5 revealed a specific "bridge" between two groups that only appeared at night. Similarly, in the Infocom06 trace, the four identified modes mapped directly to the conference schedule, distinguishing between high-mixing periods (coffee breaks) and sparse connectivity (presentation sessions).
Predictive and Epidemiological Utility
The MIT dataset revealed highly repetitive, recurring patterns, suggesting that JD could be used to forecast future network states—a critical capability for routing in delay-tolerant networks. Furthermore, nodes identified as "central" within specific JD modes were found to be the most effective at spreading simulated infections during those specific time windows, highlighting the method's relevance to epidemic modeling.
Conclusion and Future Work
Joint Diagonalisation provides a powerful lens for viewing dynamic networks as a sequence of structural modes. While the method effectively captures temporal shifts, transitions between modes can sometimes be "fuzzy" due to the nature of spanning tree sampling. Future work will focus on improving the scalability of JD for networks with millions of nodes and developing "time-specific algorithms" that allow network protocols to adapt their behavior based on the currently detected mode.
Summary updated