Modelling sparsity, heterogeneity, reciprocity and community structure in temporal interaction data.

Xenia Miscouridou, Francois Caron, Yee Whye TehNeurIPS 2018 · OpenReview

Abstract

We propose a novel class of network models for temporal dyadic interaction data. Our objective is to capture important features often observed in social interactions: sparsity, degree heterogeneity, community structure and reciprocity. We use mutually-exciting Hawkes processes to model the interactions between each (directed) pair of individuals. The intensity of each process allows interactions to arise as responses to opposite interactions (reciprocity), or due to shared interests between individuals (community structure). For sparsity and degree heterogeneity, we build the non time dependent part of the intensity function on compound random measures following Todeschini et al., 2016. We conduct experiments on real-world temporal interaction data and show that the proposed model outperforms competing approaches for link prediction, and leads to interpretable parameters.

Introduction

Most social interactions—such as emails, forum posts, or phone calls—are "temporal dyadic interactions," occurring between two individuals at specific points in time. Accurately modeling these networks requires balancing four critical, intertwined properties:

  1. Reciprocity: The "back-and-forth" nature of communication (e.g., Bob replying to Alice).
  2. Community Structure: The tendency for interactions to cluster within specific social circles.
  3. Sparsity: The reality that in large populations, most pairs never interact.
  4. Degree Heterogeneity: The presence of "hubs" or highly active individuals alongside a majority with few interactions.

Historically, models have struggled to integrate all four features. For instance, failing to account for degree heterogeneity can lead to "hubs" being incorrectly grouped into the same community simply due to their high volume of links. Previous models usually tackled one or two of these features, but combining all four into a mathematically principled and scalable model remained an open problem.

The Hawkes-CCRM Framework

To address these challenges, we introduce the Hawkes-CCRM model. This framework combines two distinct mathematical engines:

  • Mutually-Exciting Hawkes Processes: These capture the temporal "burstiness" of interactions. The rate of interaction from $i$ to $j$ spikes whenever $j$ interacts with $i$, effectively modeling reciprocity.
  • Compound Completely Random Measures (CCRM): This handles the static network structure. It assigns each node a sociability score ($w_{i0}$) to model degree heterogeneity and community affiliations ($eta_{ik}$) to allow for overlapping groups.
The Hawkes process captures the bursty nature of interactions, where events trigger temporary spikes in the intensity function λ(t), leading to clusters in the counting process N(t).

The "glue" of the model is the base rate of interaction, determined by shared community interests. This base rate feeds into the Hawkes process, adding the temporal dimension of excitement and response. To maintain scalability, we utilize a two-step approximate inference procedure, first estimating static community structure and sociability before fitting the temporal Hawkes parameters.

Decoupling Popularity from Interest

A key innovation of Hawkes-CCRM is its ability to distinguish between general sociability and specific community-driven interactions. By using a degree correction parameter, the model identifies whether a node is active because it is a "social hub" or because it is deeply embedded in a particular community.

Intensity functions for different pairs demonstrate how the model handles varying interaction patterns, from low-activity pairs to highly reciprocal, bursty interactions.

Furthermore, the model includes a parameter $\sigma$ that allows it to transition smoothly between dense and sparse regimes, making it adaptable to the massive, sparse networks typical of real-world data.

Empirical Evaluation and Results

We evaluated the model on four diverse datasets from the Stanford Large Network Dataset Collection: EMAIL (European research institution), COLLEGE (student social network), MATH Overflow, and UBUNTU (Ask Ubuntu stack exchange).

Key findings include:

  • Superior Link Prediction: Hawkes-CCRM consistently achieved the lowest Root Mean Square Error (RMSE) when predicting future interactions, outperforming standard Poisson and Hawkes-IRM models.
  • Interpretable Latent Structure: The model successfully recovered known social structures, such as the four distinct departments in the EMAIL dataset.
  • Realistic Degree Distributions: The posterior predictive distribution closely matched the heavy-tailed empirical distributions of the real-world data, effectively capturing the behavior of network hubs.

Conclusion and Future Directions

The Hawkes-CCRM model provides a principled way to model the rich dynamics of temporal networks by simultaneously accounting for sparsity, heterogeneity, community structure, and reciprocity. While the current two-step inference procedure ensures scalability, future work could explore fully integrated one-step inference for better uncertainty estimation. Additionally, extending the model to automatically estimate the number of communities and allowing for asymmetric base rates to model social hierarchies are promising avenues for further research.

Summary updated

Abstract

We propose a novel class of network models for temporal dyadic interaction data. Our objective is to capture important features often observed in social interactions: sparsity, degree heterogeneity, community structure and reciprocity. We use mutually-exciting Hawkes processes to model the interactions between each (directed) pair of individuals. The intensity of each process allows interactions to arise as responses to opposite interactions (reciprocity), or due to shared interests between individuals (community structure). For sparsity and degree heterogeneity, we build the non time dependent part of the intensity function on compound random measures following Todeschini et al., 2016. We conduct experiments on real-world temporal interaction data and show that the proposed model outperforms competing approaches for link prediction, and leads to interpretable parameters.
BibTeX
@inproceedings{miscouridou2018modelling,
  author = {Xenia Miscouridou and Francois Caron and Yee Whye Teh},
  title = {{Modelling sparsity, heterogeneity, reciprocity and community structure in temporal interaction data.}},
  booktitle = {NeurIPS},
  year = {2018},
  url = {https://openreview.net/forum?id=bScSVe8m4rH},
}
Figure