Hypergraph Ego-networks and Their Temporal Evolution

Cazamere Comrie, Jon Kleinberg

Abstract: Interactions involving multiple objects simultaneously are ubiquitous across many domains. The systems these interactions inhabit can be modelled using hypergraphs, a generalization of traditional graphs in which each edge can connect any number of nodes. Analyzing the global and static properties of these hypergraphs has led to a plethora of novel findings regarding how these modelled systems are structured. However, less is known about the localized structure of these systems and how they evolve over time. In this paper, we propose the study of hypergraph ego-networks, a structure that can be used to model higher-order interactions involving a single node. We also propose the temporal reconstruction of hypergraph ego-networks as a benchmark problem for models that aim to predict the local temporal structure of hypergraphs. By combining a deep learning binary classifier with a hill-climbing algorithm, we will present a model for reconstructing hypergraph ego-networks by incorporating structural patterns found across multiple domains.

Introduction

Most network research focuses on dyadic graphs, which represent simple point-to-point connections. However, real-world interactions—such as a group of researchers co-authoring a paper or a CC’d email thread—involve multiple participants simultaneously. These are best modeled as hypergraphs, where a single "hyperedge" can connect an arbitrary number of nodes. While global and static properties of hypergraphs are well-studied, their local temporal evolution remains largely unexplored. This paper addresses this gap by introducing hypergraph ego-networks and proposing a benchmark problem: temporal reconstruction.

Defining Hypergraph Ego-networks

To capture different levels of local interaction surrounding a central node (the "ego"), the authors define three distinct types of hypergraph ego-networks:

  1. Star: Includes only hyperedges that explicitly contain the ego node.
  2. Radial: Includes any hyperedge where all members are either the ego or the ego’s direct neighbors.
  3. Contracted: Captures interactions between neighbors even if they involve individuals outside the ego's immediate circle, achieved by intersecting external hyperedges with the ego's neighborhood.
Figure 1: Visual definitions of Star, Radial, and Contracted hypergraph ego-networks based on a sample dataset.

Temporal Reconstruction Methodology

The core challenge posed is whether a shuffled sequence of a person's group interactions can be reordered correctly without timestamps. The authors employ a two-step approach:

  • Supervised Learning: A deep neural network is trained as a binary classifier to distinguish between "correctly ordered" and "randomly shuffled" sequences.
  • Reconstruction Algorithm: A hill-climbing algorithm iteratively swaps pairs of hyperedges in a shuffled sequence, guided by the neural network's predictions to find the most likely chronological order.

This methodology was tested across three diverse datasets: academic co-authorship (coauth-DBLP), corporate email (email-Avocado), and online forum interactions (threads-ask-ubuntu).

Key Insights and Results

Temporal Locality and "Burstiness"

A primary finding is the existence of temporal locality: adjacent hyperedges in a real temporal sequence share significantly more nodes than those in a random sequence. This suggests that people tend to interact within the same small groups in "bursts" before shifting to new circles.

Figure 5: Average intersection size in Radial networks (email-Avocado). The gap between the actual order (blue) and randomized order (green) illustrates temporal locality.

Predictive Features

  • Alter-Network Spread: This measure of how a specific neighbor's interactions are distributed across the ego's timeline was the most powerful predictor, yielding 75-89% accuracy in classification. In real networks, interactions with specific individuals are typically clustered in time.
  • The Anthropic Principle: In radial and contracted networks, the ego often arrives after their neighbors have already begun interacting. In the DBLP dataset, for instance, the ego typically enters their own radial network around the fifth interaction.
  • Performance: The neural network achieved up to 93% accuracy in classification for Star networks. In the harder task of full reconstruction, the hill-climbing algorithm correctly ordered pairs with 63-70% accuracy, significantly outperforming random baselines.

Conclusion

This study demonstrates that the temporal evolution of local hypergraph structures is highly predictable and follows a consistent "grammar" across domains. While the current model focuses on growing networks and is computationally intensive for large ego-networks, it establishes a robust framework for future research into the decay of ties and more efficient sorting heuristics.

Summary updated

Abstract

Interactions involving multiple objects simultaneously are ubiquitous across many domains. The systems these interactions inhabit can be modelled using hypergraphs, a generalization of traditional graphs in which each edge can connect any number of nodes. Analyzing the global and static properties of these hypergraphs has led to a plethora of novel findings regarding how these modelled system are structured. However, less is known about the localized structure of these systems and how they evolve over time. In this paper, we propose the study of hypergraph ego-networks, a structure that can be used to model higher-order interactions involving a single node. We also propose the temporal reconstruction of hypergraph ego-networks as a benchmark problem for models that aim to predict the local temporal structure of hypergraphs. By combining a deep learning binary classifier with a hill-climbing algorithm, we will present a model for reconstructing hypergraph ego-networks by incorporating structural patterns found across multiple domains.
BibTeX
@inproceedings{comrie2021hypergraph,
  author = {Cazamere Comrie and Jon Kleinberg},
  title = {{Hypergraph Ego-networks and Their Temporal Evolution}},
  booktitle = {2021},
  year = {2021},
  doi = {10.1109/icdm51629.2021.00019},
}
Figure