Temporal Triadic Closure: Finding Dense Substructures in Social Networks That Evolve over Time

Tom Davot, Jessica A. Enright, Jayakrishnan Madathil, Kitty MeeksAAAI 2025 · DOI

TL;DR

This paper introduces "temporal c-closed graphs" as a new way to model social networks that evolve over time, capturing the idea that friends of friends are likely to become friends. They show this parameter is useful for analyzing real-world temporal networks and provides a theoretical basis for efficient algorithms to find dense substructures like cliques.

What Problem Does This Paper Address?

Many real-world networks, like social media interactions or collaborations, are dynamic. Connections are formed and broken over time, and even continuous relationships involve discrete interactions. Traditional graph theory often models these as static snapshots, which can lose crucial temporal information. While temporal graph models exist, many standard algorithmic problems (like finding cliques) become NP-hard. This paper aims to bridge this gap by defining a new structural parameter for temporal graphs, "temporal c-closedness," inspired by the "triadic closure" property (friends of friends are friends) observed in static social networks. The goal is to find a parameter that is both theoretically useful for algorithm design and practically relevant for real-world temporal networks.

Methods

The core contribution is the definition of temporal c-closed graphs. This extends the static c-closed graph concept: if two individuals have at least c common "friends" (neighbors) within a specific short time window, they are likely to be connected themselves around that time. The authors formalize this with parameters $\Delta_0, \Delta_1, \Delta_2$ that define the "look-back" and "look-ahead" periods for common neighbors and the time interval for adjacency.

They also introduce weakly (Δ₀, Δ₁, Δ₂, γ)-closed graphs as a more relaxed condition, inspired by weakly c-closed graphs in the static setting.

To address algorithmic challenges, they define Δ-cliques in temporal graphs – sets of vertices and time intervals where edges are sufficiently frequent. They then establish theoretical bounds on the number of maximal Δ-cliques in temporal c-closed graphs, particularly when the graph exhibits local η-instability (meaning neighborhoods of vertices don't change drastically between consecutive time steps) or pairwise η-instability (a weaker condition on how common neighborhoods change). These bounds are crucial for developing efficient algorithms.

Datasets

The authors evaluated their proposed parameters on several real-world temporal networks from the Sociopatterns dataset. They selected modestly-sized instances (up to 250 vertices) for computational feasibility. The specific datasets used include:

  • baboons: Interactions between guinea baboons.
  • hospital: Co-presence in a hospital workplace.
  • kenya_across and kenya_within: Contact networks of rural Kenyan households.
  • malawi: Contact patterns in a rural Malawian village.
  • workplace13 and workplace15: Co-presence in workplace settings over different years.

They note that they did not test all possible parameter combinations for $(\Delta_0, \Delta_1, \Delta_2)$, but rather focused on a few configurations to observe trends.

Key Insights and Ideas

  • Temporal Triadic Closure is Quantifiable: The paper demonstrates that the intuitive notion of "friends of friends are friends" can be mathematically formalized for evolving networks, providing a concrete parameter ($\Delta_0, \Delta_1, \Delta_2, c$-closedness) to capture this.
  • Real-World Networks Exhibit Temporal Closure: Empirical results suggest that real-world temporal networks, even with their dynamic nature, often exhibit small values for their temporal closure numbers, indicating the parameter's relevance.
  • Instability Matters for Algorithms: The "stability" of a temporal graph (how much its structure changes over time) is critical for deriving theoretical bounds on dense substructures. Local or pairwise instability allows for more tractable analysis.
  • Bridging Static and Temporal Graph Algorithms: The work provides a theoretical foundation for adapting efficient algorithms designed for static c-closed graphs to temporal networks, by bounding the number of temporal cliques.

Key Results

  • Empirical Evidence: The temporal c-closure and weak temporal c-closure numbers are often small for the real-world temporal networks analyzed, and notably smaller than their static counterparts.
  • Theoretical Bounds: The paper establishes bounds on the number of maximal Δ-cliques in (Δ₀, Δ₁, Δ₂, c)-closed temporal graphs that are locally or pairwise η-unstable. Specifically, Theorem 4.1 states that such graphs with n vertices and lifetime Λ have at most $3 \cdot 2^{c-1+2\eta(\Delta+1-\Delta_1)} \cdot n^2 \cdot \Lambda$ maximal Δ-cliques.
  • Algorithmic Implications: These bounds lead to efficient algorithms for enumerating maximal Δ-cliques in temporal graphs, with Theorem 4.3 showing a runtime of $O(2^{\gamma-1+2\eta(\Delta+1-\Delta_1)} \cdot n^2 \cdot m \cdot \Lambda)$ for weakly (Δ₀, Δ₁, Δ₂, γ)-closed graphs.
  • Generalization to Dense Subgraphs: The techniques are extended to bound the number of maximal (Δ, k+1)-plexes and (Δ, k)-defective cliques, showing similar theoretical tractability.

Limitations and Future Work

  • Parameter Choice: The paper acknowledges that choosing the right values for $\Delta_0, \Delta_1, \Delta_2$ and $c$ (or $\gamma$) is crucial and can be challenging. The empirical evaluation used a limited set of parameter configurations.
  • Dataset Size: The empirical analysis was limited to smaller temporal networks due to computational constraints. Further evaluation on larger and more diverse real-world datasets is needed.
  • Instability Conditions: While local or pairwise instability provides sufficient conditions for theoretical bounds, the authors suggest exploring other, potentially more realistic, conditions that can still yield useful bounds.
  • Practical Applicability: The authors emphasize that while these parameters offer theoretical guarantees, practical applications might require further refinement and tuning. They hope their work will spur further research into these parameters and their applications.

Summary updated

BibTeX
@inproceedings{davot2025temporal,
  author = {Tom Davot and Jessica A. Enright and Jayakrishnan Madathil and Kitty Meeks},
  title = {{Temporal Triadic Closure: Finding Dense Substructures in Social Networks That Evolve over Time}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i25.34899},
}
Figure