Analytical Models for Motifs in Temporal Networks

Alexandra M. Porter, Baharan Mirzasoleiman, Jure LeskovecWWW 2022 · DOI

TL;DR

This paper introduces the Temporal Activity State Block Model (TASBM), a novel analytical framework for understanding temporal networks. TASBM allows for efficient computation of expected temporal motif frequencies and their variances, enabling the discovery of statistically significant motifs and anomalies in dynamic network data.

What Problem Does This Paper Address?

Temporal networks, where interactions (edges) occur at specific times, are ubiquitous in real-world systems like social networks, communication systems, and financial markets. Identifying recurring patterns, known as temporal motifs, within these networks is crucial for understanding their evolution and function. However, existing methods for analyzing temporal motifs are computationally expensive, often requiring the generation of many synthetic networks and then counting motifs. Furthermore, there's a lack of analytical models that can directly model and predict temporal motif frequencies over time, making it difficult to detect anomalies or understand network dynamics. This paper addresses this gap by proposing an efficient analytical model for temporal graphs that can directly compute expected motif frequencies and their variances.

Methods

The core of this work is the Temporal Activity State Block Model (TASBM). TASBM models temporal networks by:

  • Partitioning Nodes into Activity Groups: Nodes are grouped based on their activity levels (rates of incoming and outgoing edges). This allows the model to capture different behavioral patterns within the network.
  • Modeling Edge Arrivals with Poisson Processes: Temporal edges between nodes in different activity groups are modeled as independent Poisson processes. The rates of these processes are learned from the data.
  • Deriving Closed-Form Expressions for Motif Frequencies: The key innovation is the development of analytical formulas to directly calculate the expected number and variance of temporal motif instances. This bypasses the need for computationally intensive simulations and motif counting on synthetic graphs.
  • Efficient Parameter Inference: The model includes efficient methods for fitting its parameters to temporal network data, scaling linearly with the number of edges.

Datasets

The authors evaluated their framework on several real-world temporal networks:

  • Financial Transaction Network: A subset of a European country's transaction log (118.7 thousand nodes, 2.9 million temporal edges).
  • Phone Call Network: A network of phone calls (1.2 million nodes, 21.9 million temporal edges).
  • Email Network: A network of emails exchanged within a European research institution (997 nodes, 307,869 temporal edges).

They also used synthetic networks generated according to the TASBM model for evaluating model accuracy and robustness.

Key Insights and Ideas

  • Analytical Tractability for Temporal Motifs: The most significant insight is that it's possible to derive closed-form analytical solutions for expected temporal motif frequencies, making analysis computationally feasible for large networks.
  • Activity-Based Grouping Captures Dynamics: Grouping nodes by their temporal activity (in/out-degree rates) effectively captures the intermittent and bursty nature of interactions in real-world networks.
  • Anomaly Detection via Deviation from Expected Frequencies: Deviations between observed motif counts and the model's predicted expected counts serve as powerful indicators of anomalies in the network.
  • Scalability is Key: The analytical approach offers a significant speedup over traditional simulation-based methods, enabling analysis of massive temporal networks.

Key Results

  • Accurate Motif Frequency Tracking: The TASBM model accurately tracks temporal motif frequencies over time in financial, email, and phone call networks.
  • Successful Anomaly Localization: The framework successfully identified anomalies in financial transaction networks, correlating with a financial crisis, and in synthetic networks with planted anomalies.
  • Efficiency Gains: The analytical method is significantly faster than random graph counting methods, with run times scaling much better for large networks. For example, analytical model run times were orders of magnitude faster than randomized ensemble methods.
  • Robustness to Hyperparameters: The model shows robustness to choices of hyperparameters like the number of groups, with relatively small numbers of groups (e.g., 2-5) providing good accuracy.

Limitations and Future Work

  • Approximation for Large T: For scenarios where the time window T is much larger than the motif window δ, the calculation of expected motif frequencies involves approximations.
  • Model Complexity for Highly Localized Networks: For highly localized networks like phone call data, the model's ability to fit actual motif counts was limited, suggesting that more sophisticated modeling of community structure and temporal activity might be needed. The authors note that TASBM is extendable to such settings.
  • Future Work: The authors suggest extending the model to incorporate more complex temporal dependencies and community structures. They also highlight the potential for using the framework for anomaly detection and understanding network dynamics in various domains.

Summary updated

BibTeX
@inproceedings{porter2022analytical,
  author = {Alexandra M. Porter and Baharan Mirzasoleiman and Jure Leskovec},
  title = {{Analytical Models for Motifs in Temporal Networks}},
  booktitle = {The Web Conference},
  year = {2022},
  doi = {10.1145/3487553.3524669},
}

Loading related content...

Figure