Computing maximal cliques in link streams


Tiphaine Viard, Matthieu Latapy and Clémence Magnien

Theoretical Computer Science (TCS), Volume 609, Part 1, 4 January 2016, Pages 245–252. DOI: 10.1016/j.tcs.2015.09.030


A link stream is a collection of triplets (t, u, v) indicating that an interaction
occurred between u and v at time t. We generalize the classical notion of cliques
in graphs to such link streams: for a given ∆, a ∆-clique is a set of nodes and
a time interval such that all pairs of nodes in this set interact at least once
during each sub-interval of duration ∆. We propose an algorithm to enumerate
all maximal (in terms of nodes or time interval) cliques of a link stream, and
illustrate its practical relevance on a real-world contact trace.

This entry was posted in Papers