Research map / Graph learning / Graph algorithms and clustering
Temporal Triadic Closure: Finding Dense Substructures in Social Networks That Evolve over Time
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces temporal c-closed graphs (a (Δ0,Δ1,Δ2,c) triadic-closure definition for temporal graphs) and proves that slowly evolving (η-unstable) ones have polynomially bounded numbers of maximal Δ-cliques and other dense temporal subgraphs, giving FPT enumeration algorithms.
Problem
Enumerating maximal cliques and similar dense substructures in temporal social networks is intractable in general (exponentially many maximal Δ-cliques), and existing temporal graph parameters are either too restrictive or fail on dense graphs.
Approach
Adapt the static c-closed graph (triadic closure) notion to temporal graphs with time windows (Δ0,Δ1,Δ2), and combine it with a slow-evolution condition (local or pairwise η-instability) to bound the number of maximal Δ-cliques by a function of c, η, Δ and polynomial in n and lifetime.
Key results
- On seven SocioPatterns temporal networks, the (Δ0,Δ1,Δ2)-closure numbers and especially weak closure numbers are often small (e.g., kenya_across weak closure 3, malawi 4) and much smaller than static closure numbers on the footprint.
- Theorem: an η-unstable (Δ0,Δ1,Δ2,c)-closed temporal graph with n vertices and lifetime Λ has at most 3·2^(c-1+2η(Δ+1-Δ1))·n²·Λ maximal Δ-cliques, when Δ ≥ Δ0+Δ1+Δ2.
- An algorithm enumerates all maximal Δ-cliques in time O(2^(c-1+2η(Δ+1-Δ1))·n²·m·Λ), making the problem FPT in c+η+Δ.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use temporal closure parameters instead of the static footprint closure numbers | Temporal c-closure and weak closure · baboons | closure number, weak closure number: 15, 4 -> 8, 5 | Helped |
| Use temporal closure parameters instead of the static footprint closure numbers | Temporal c-closure and weak closure · hospital | closure number, weak closure number: 45, 25 -> 20, 15 | Helped |
| Use temporal closure parameters instead of the static footprint closure numbers | Temporal c-closure and weak closure · kenya_across | closure number, weak closure number: 10, 4 -> 8, 3 | Helped |
| Use temporal closure parameters instead of the static footprint closure numbers | Temporal c-closure and weak closure · kenya_within | closure number, weak closure number: 27, 11 -> 11, 7 | Helped |
| Use temporal closure parameters instead of the static footprint closure numbers | Temporal c-closure and weak closure · malawi | closure number, weak closure number: 10, 5 -> 5, 4 | Helped |
| Use temporal closure parameters instead of the static footprint closure numbers | Temporal c-closure and weak closure · workplace13 | closure number, weak closure number: 70, 45 -> 36, 15 | Helped |
| Use temporal closure parameters instead of the static footprint closure numbers | Temporal c-closure and weak closure · workplace15 | closure number, weak closure number: 41, 20 -> 19, 12 | Helped |
| Set Δ0=Δ2=10 rather than Δ0=Δ2=0 (Δ1=0) (ablation) | Temporal closure · baboons | closure number, weak closure number: 8, 5 -> 5, 3 | Helped |
| Set Δ0=Δ2=10 rather than Δ0=Δ2=0 (Δ1=0) (ablation) | Temporal closure · hospital | closure number, weak closure number: 20, 15 -> 20, 9 | Mixed |
| Set Δ0=Δ2=10 rather than Δ0=Δ2=0 (Δ1=0) (ablation) | Temporal closure · kenya_within | closure number, weak closure number: 11, 7 -> 10, 6 | Helped |
| Set Δ0=Δ2=10 rather than Δ0=Δ2=0 (Δ1=0) (ablation) | Temporal closure · malawi | closure number, weak closure number: 5, 4 -> 4, 2 | Helped |
| Set Δ0=Δ2=10 rather than Δ0=Δ2=0 (Δ1=0) (ablation) | Temporal closure · workplace13 | closure number, weak closure number: 36, 15 -> 14, 7 | Helped |
Surprising findings
- Without slow evolution, maximal Δ-cliques can be exponential (2^Ω(n)) even for temporal c-closed graphs with c=1, shown by a construction.
Limitations
- Local/pairwise η-instability may be too restrictive; empirical η values are sometimes large (e.g., workplace13 at 77).
- Evaluation only on modest-sized SocioPatterns instances (at most 250 vertices) and a few parameter settings.
- Parameters are crude abstractions of real social networks; practical tractability not established.
Experimental setup
Datasets: SocioPatterns baboons SocioPatterns hospital SocioPatterns kenya_across SocioPatterns kenya_within SocioPatterns malawi SocioPatterns workplace13 SocioPatterns workplace15
Benchmarks: SocioPatterns temporal contact networks
Metrics: temporal closure number c weak closure number gamma pairwise instability eta
Builds on: c-closed graphs (Fox et al.) Δ-cliques (Himmel et al.) weakly γ-closed graphs
Closest papers by meaning
- Approximating Optimal Labelings for Temporal Connectivity (AAAI 2025 · similarity 0.87)
- S3Former: Sequential, Structural, and Statistical Fusion for Continuous-Time Dynamic Graphs (NeurIPS 2026 · similarity 0.87)
- Using Time-Aware Graph Neural Networks to Predict Temporal Centralities in Dynamic Graphs (NeurIPS 2024 · similarity 0.86)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.86)
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better (ICML 2024 · similarity 0.85)
- Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.