Community-Based Event Detection in Temporal Networks

Pablo Moriano, Jorge Finke, Yong‐Yeol AhnScientific 2019 · DOI

TL;DR

This paper introduces a novel method for detecting large-scale events by analyzing the communication patterns within and across communities in temporal networks. By focusing on the ratio of inter-community to intra-community communication, the authors demonstrate a more robust approach to event detection than traditional volume-based methods, even when event-driven communication spikes are not significant.

What Problem Does This Paper Address?

Detecting significant events in complex systems, such as cyberattacks, financial fraud, or societal disruptions, is crucial. Traditional methods often rely on monitoring the overall volume of activity, which can be misleading as natural fluctuations in communication can mimic event signals. Furthermore, distinguishing true events from background noise is challenging. This paper addresses the need for a more sophisticated event detection mechanism that leverages the structural properties of communication networks, specifically how information flows between different groups (communities) within the network. The core challenge is to identify events that cause a shift in communication behavior, leading to increased interaction between communities, rather than just an overall increase in communication within communities.

Methods

The proposed method, "Community-Based Event Detection," hinges on the hypothesis that global events, due to their broad relevance, tend to trigger viral information cascades that easily cross community boundaries. The method works by:

  1. Establishing a "normal" community structure: This is done by aggregating network snapshots over a defined period (denoted by $m_0$) and applying a community detection algorithm (Infomap is used here) to identify distinct groups of nodes that communicate frequently with each other.
  2. Monitoring inter- and intra-community communication: For subsequent time intervals, the method calculates two ratios:
  3. Inter-community link ratio ($c_{inter}(k)$): The proportion of communication links that connect nodes in different communities.
  4. Intra-community link ratio ($c_{intra}(k)$): The proportion of communication links that connect nodes within the same community.
  5. Detecting events: An event is flagged when the difference between the inter- and intra-community link ratios ($c_{inter}(k) - c_{intra}(k)$) exceeds a statistically defined threshold (e.g., a certain number of standard deviations from the moving average of this difference). This deviation signifies a shift towards more cross-community communication, indicative of a global event.

The key innovation lies in focusing on the relative change in communication patterns between and within communities, rather than just the absolute volume of communication. This approach is designed to be more robust to natural variations in network activity.

Datasets

The authors evaluate their method using two real-world datasets:

  • Enron email communication network: This dataset comprises emails exchanged by Enron employees during the company's collapse period (1999-2002). It's a directed weighted network where nodes are employees and links represent the number of emails exchanged. Seven major events related to Enron's bankruptcy were identified for evaluation.
  • Twitter communication network: This dataset includes English tweets (mentions and retweets) during April 2013, specifically around the Boston Marathon bombing. This is used to analyze how events propagate on social media.

Key Insights and Ideas

  • Global events disrupt community boundaries: The central idea is that events of broad interest force communication to spill over community lines, making inter-community links more prominent.
  • Beyond volume: The method offers a more nuanced approach than simply looking at communication volume, which can be noisy and prone to false positives.
  • Temporal dynamics are key: The method explicitly leverages the temporal nature of networks, tracking changes in communication patterns over time.
  • Community structure as a baseline: Establishing a stable "normal" community structure is crucial for identifying deviations that signal events.

Key Results

  • Enron Email Network: The proposed method successfully detected most of the identified Enron events, often showing a significant deviation in the inter- vs. intra-community communication ratio even when email volume did not spike dramatically. Performance comparisons using ROC and Precision-Recall curves showed the proposed method generally outperformed volume-based detection, especially at lower resolutions (shorter time windows for analysis). For a resolution of $m=7$ weeks, the proposed method achieved "perfect performance."
  • Boston Marathon Bombing (Twitter): The method detected significant deviations in inter- vs. intra-community communication ratios coinciding with the bombing event and the subsequent manhunt. Analysis of hashtags revealed that event-related hashtags emerged with high inter-community communication shortly after the bombing, demonstrating the method's ability to capture event-driven information diffusion.

Limitations and Future Work

  • Dependence on initial community partition: The method's performance is sensitive to how the initial "normal" community structure is defined and updated. The authors acknowledge that there is "a lot of freedom" in choosing this strategy.
  • Temporality of detection intervals: The current evaluation assumes detection intervals are proportional to network formation intervals, meaning the exact timing of an event within an interval isn't precisely captured.
  • Threshold selection: Defining the detection threshold (number of standard deviations) is a parameter that needs careful consideration and might vary across different types of networks or events.

Future work could explore more dynamic ways to update the community structure and refine the detection thresholding mechanisms for greater adaptability and accuracy.

Summary updated

Abstract

We propose a method for detecting large events based on the structure of temporal communication networks. Our method is motivated by findings that viral information spreading has distinct diffusion patterns with respect to community structure. Namely, we hypothesize that global events trigger viral information cascades that easily cross community boundaries and can thus be detected by monitoring intra- and inter-community communications. By comparing the amount of communication within and across communities, we show that it is possible to detect events, even when they do not trigger a significantly larger communication volume. We demonstrate the effectiveness of our method using two examples-the email communication network of Enron and the Twitter communication network during the Boston Marathon bombing.
BibTeX
@inproceedings{moriano2019community,
  author = {Pablo Moriano and Jorge Finke and Yong‐Yeol Ahn},
  title = {{Community-Based Event Detection in Temporal Networks}},
  booktitle = {Scientific},
  year = {2019},
  doi = {10.1038/s41598-019-40137-0},
}
Figure