Mining Persistent Activity in Continually Evolving Networks

Caleb Belth, Xinyi Zheng, Danai Koutra

Introduction

In the analysis of dynamic networks, researchers often equate high frequency with high importance. We count "motifs"—recurring subgraphs—and assume that those appearing most often are the most significant. However, frequency alone can be a misleading metric. A viral event may generate a massive burst of activity that vanishes quickly, whereas a subtle, coordinated behavior might occur with clockwork regularity over years. In "Mining Persistent Activity in Continually Evolving Networks," Belth et al. argue that understanding evolving networks requires a formal measure of persistence.

The Persistence Framework

The authors address the gap in current research: the lack of a scalable method to quantify "regularity" and "duration" in edge streams. They propose the PENminer framework, which rests on three conceptual pillars:

  1. Activity Snippets: These are small sequences of edge updates. Unlike standard motifs, snippets can track specific node identities or general structural patterns.
  2. A Principled Persistence Measure: Persistence ($P$) is defined mathematically through components of Width (temporal coverage), Frequency (log-scale count), and Spread (regularity). Spread is calculated using the Shannon Entropy of the time intervals between occurrences, where higher entropy signifies more regular, and thus more persistent, behavior.
  3. Algorithmic Implementation: The framework includes oPENminer for offline analysis and sPENminer for real-time streaming. The latter utilizes an incremental entropy update to maintain efficiency on massive data streams.
Illustration of activity snippets and their corresponding occurrence timelines, showing the difference between regular and bursty patterns.

Key Insights: Persistence vs. Frequency

A primary tool introduced is the Persistence vs. Frequency (PvF) plot. By plotting these two metrics against each other, different classes of network behavior emerge. "Bursty" events, which are frequent but short-lived, cluster in the high-frequency/low-persistence region. Conversely, "subtly persistent" events—often the most interesting for anomaly detection—occupy the low-frequency/high-persistence region.

Persistence vs. Frequency (PvF) plots for Boston and Columbus bike-sharing data, highlighting how persistence distinguishes long-term patterns from transient bursts.

The utility of this distinction was demonstrated across several domains:

  • Resilience: In NYC taxi data during Hurricane Sandy, persistent routes highlighted critical infrastructure like hospital access.
  • Social Dynamics: On StackOverflow, comments on answers were found to be more persistent than those on questions, indicating the long-term utility of solutions.
  • Security: The framework identified "stealthy" network intruders who intentionally limit their frequency to avoid detection but maintain a persistent presence.

Experimental Results

The authors evaluated PENminer on diverse datasets ranging from transportation to security. Key findings include:

  • Superior Detection: sPENminer outperformed baselines like Midas-R and SedanSpot in anomaly detection by 9.8% to 48% in AUC.
  • Extreme Efficiency: The streaming algorithm processed edge updates up to 360,000 times faster than the data's arrival rate.
  • Linear Scalability: The offline algorithm scales linearly with dataset size, ensuring viability for massive historical logs.

Conclusion

PENminer shifts the focus of network mining from "what is trending" to "what is enduring." By providing a principled and scalable way to measure persistence, it enables the detection of subtle but vital patterns that frequency-based methods overlook. Future research will focus on automating the tuning of persistence parameters to enhance usability for non-experts.

Summary updated

Abstract

Frequent pattern mining is a key area of study that gives insights into the structure and dynamics of evolving networks, such as social or road networks. However, not only does a network evolve, but often the way that it evolves, itself evolves. Thus, knowing, in addition to patterns' frequencies, for how long and how regularly they have occurred---i.e., their persistence---can add to our understanding of evolving networks. In this work, we propose the problem of mining activity that persists through time in continually evolving networks---i.e., activity that repeatedly and consistently occurs. We extend the notion of temporal motifs to capture activity among specific nodes, in what we call activity snippets, which are small sequences of edge-updates that reoccur. We propose axioms and properties that a measure of persistence should satisfy, and develop such a persistence measure. We also propose PENminer, an efficient framework for mining activity snippets' Persistence in Evolving Networks, and design both offline and streaming algorithms. We apply PENminer to numerous real, large-scale evolving networks and edge streams, and find activity that is surprisingly regular over a long period of time, but too infrequent to be discovered by aggregate count alone, and bursts of activity exposed by their lack of persistence. Our findings with PENminer include neighborhoods in NYC where taxi traffic persisted through Hurricane Sandy, the opening of new bike-stations, characteristics of social network users, and more. Moreover, we use PENminer towards identifying anomalies in multiple networks, outperforming baselines at identifying subtle anomalies by 9.8-48% in AUC.
BibTeX
@inproceedings{belth2020mining,
  author = {Caleb Belth and Xinyi Zheng and Danai Koutra},
  title = {{Mining Persistent Activity in Continually Evolving Networks}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2020},
  url = {https://openreview.net/forum?id=IDrCVXsa5My},
}

Loading related content...

Figure