FROMANNUAL REVIEWS

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

Content not yet available

This lecture has no active video or poster.

AAAI 2025

•

February 28, 2025

•

Philadelphia, United States

keywords:

other foundations of search optimization

so

A graph $G$ is $c$-closed if any two vertices with at least $c$ common neighbors are adjacent to each other. Introduced by Fox, Roughgarden, Seshadhri, Wei and Wein ICALP 2018, SICOMP 2020, this definition is an abstraction of the triadic closure property exhibited by many real-world social networks, namely, friends of friends tend to be friends themselves. Social networks, however, are temporal rather than static---the connections change over a period of time. And hence temporal graphs, rather than static graphs, are often better suited to model social networks. Motivated by this, we introduce a definition of temporal $c$-closed graphs, in which if two vertices $u$ and $v$ have at least $c$ common neighbors during a short interval of time, then $u$ and $v$ are adjacent to each other around that time. Our pilot experiments show that several real-world temporal networks are indeed $c$-closed for rather small values of $c$. We also study the computational problems of enumerating maximal cliques and similar dense subgraphs in temporal $c$-closed graphs; a clique in a temporal graph is a subgraph that lasts for a certain period of time, during which every possible edge in the subgraph becomes active often enough, and other dense subgraphs are defined similarly. We bound the number of such maximal dense subgraphs, and thus show that the corresponding enumeration problems admit efficient algorithms, provided the graph evolves slowly over time; by slow evolution, we mean that between consecutive time-steps, the local change in adjacencies remains small. Our work also adds to a growing body of literature on defining suitable structural parameters for temporal graphs that can be leveraged to design efficient algorithms.

Downloads

SlidesPaper

Next from AAAI 2025

Identifying Query-Relevant Neurons in Large Language Models for Long-Form Texts
technical paper

Identifying Query-Relevant Neurons in Large Language Models for Long-Form Texts

AAAI 2025

Lihu Chen
Lihu Chen and 2 other authors

28 February 2025

Similar lecture

Fusing Temporal Graphs into Transformers for Time-Sensitive Question Answering
poster

Fusing Temporal Graphs into Transformers for Time-Sensitive Question Answering

EMNLP 2023

Xin Su
Steven Bethard
+1
Xin Su and 3 other authors

08 December 2023

Stay up to date with the latest Underline news!

Select topic of interest (you can select more than one)

PRESENTATIONS

  • All Presentations
  • For Librarians
  • Resource Center
  • Free Trial
Underline Science, Inc.
1216 Broadway, 2nd Floor, New York, NY 10001, USA

© 2026 Underline - All rights reserved

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.