Learning the Latent State Space of Time-Varying Graphs
Abstract
Dynamic networks, such as university email systems, are non-stationary, with structural properties that drift in response to external real-world events. Traditional analysis often relies on static snapshots or discrete time-aggregation, which can lose temporal dynamics or become overwhelmed by diurnal noise. This paper presents a framework for uncovering the latent states of graph streams by mapping snapshots into a structural state space. We compare a standard discrete aggregation model with a probabilistic "aging" model where edge existence decays over time. Our results, based on seven months of university email logs, demonstrate that the probabilistic model more effectively filters noise and identifies significant global behavioral shifts corresponding to the academic calendar.
Introduction
Communication networks like email, SMS, and social media consist of rapid, short-lived interactions. Analyzing these as "graph streams" is challenging because their properties are non-stationary. Aggregating data over long periods obscures dynamics, while daily snapshots often fail to distinguish between routine local fluctuations and significant global events. We propose a methodology to learn the higher-level "states" of a network, enabling a clearer visualization of its temporal evolution.
Methods
The framework maps a sequence of graph snapshots into a latent state space using two primary components: representation modeling and structural attribute mapping.
- Representation Models: We compare a Discrete Model, where edges exist only within fixed 1-day windows, against a Probabilistic Model. In the latter, edges are treated as having a lifetime; the probability of an edge existing decays exponentially: $p_{ij} = \exp(-(t - t')/\tau)$. This allows older interactions to "age out" gracefully.
- State-Space Mapping: Each snapshot is characterized by its average degree and average clustering coefficient. These attributes form a 2D space where snapshots are clustered using K-Means into seven distinct states (A-G).
Datasets
The study utilizes email logs from Purdue University mail servers spanning seven months (August 2011 to February 2012). This period encompasses a full academic semester, including Labor Day, Fall Break, Thanksgiving, and Winter Break.
Results and Discussion
The probabilistic model (with $\tau = 12$ days) significantly outperformed the discrete model in tracking global academic events. While the discrete model's state transitions were erratic due to daily noise, the probabilistic model showed clear, sustained shifts into specific states during university breaks.
As illustrated in Figure 2, the network enters "State A" during the Winter Break, a state characterized by minimal activity. Notably, the framework distinguishes between different types of breaks based on connectivity intensity; for instance, the model labeled Thanksgiving Break and Fall Break as different states (C and A, respectively), reflecting the varying levels of campus activity and the superior filtering of the probabilistic approach.
Conclusion
By treating network interactions as decaying probabilities, we can effectively filter high-frequency noise and reveal the underlying latent states of dynamic graphs. This approach provides a robust tool for monitoring large-scale social systems and identifying significant structural transitions. Future work will investigate the use of these latent states for predictive modeling of future network characteristics.
Summary updated