Source-linked AI summary
Computing maximal cliques in link streams
Tiphaine Viard, Matthieu Latapy, Clémence Magnien
TL;DR
The paper addresses how to identify maximal groups interacting over time in link streams, proposing an algorithm to enumerate them. Applied to high-school contact data, it found a temporal clique invisible in the corresponding graph-clique analysis.
Problem
Link-stream interactions can represent meetings, discussions, or distributed applications, motivating a way to identify such patterns over time.
Source: §1 · p. 1Method
The algorithm grows candidate ∆-cliques by adding nodes or extending their time intervals, and outputs all maximal ∆-cliques.
Source: §2 · pp. 3, 7Results
A 60-clique involving four students from different classrooms lasted roughly five minutes and was invisible when considering graph cliques.
Source: §3 · p. 11Takeaways & Limitations
In the contact trace, ∆-cliques exposed time-dependent patterns that graph cliques did not show.
Source: §3 · p. 11Adapting Bron-Kerbosch-style clique algorithms is not straightforward because their candidate-node approach does not directly translate to link streams with time.
Source: §4 · p. 11
Abstract
from arXiv · showhide
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 $\Delta$, a $\Delta$-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 $\Delta$. 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.
1. Introduction
The paper extends cliques to link streams, defining groups whose pairs interact at least once in every interval of duration ∆. It proposes the first algorithm for listing maximal ∆-cliques and illustrates it on real-world contact data.
1. Introduction
- Link streams model temporal interactions such as contacts, email exchanges, and network traffic [2] [12] [14].The paper presents ∆-cliques as a natural generalization of graph cliques and relates them to substreams of ∆-density 1 [12].Source: §1 · pp. 1–2
- A ∆-clique is a node set of at least two nodes and a time interval in which every pair interacts at least once in each ∆-duration sub-interval.A ∆-clique is maximal when no other ∆-clique contains both its node set and time interval.Source: §1 · p. 1
- The first proposed algorithm lists all maximal ∆-cliques in a link stream, and the paper illustrates its relevance on a real-world contact dataset.In real-world settings, ∆-cliques can be signatures of meetings, discussions, or distributed applications.Source: §1 · pp. 1–2
- The paper assumes undirected links, no self-loops, and no isolated nodes.It treats (t, u, v) and (t, v, u) as the same link.Source: §1 · p. 2
2. Algorithm
The algorithm explores candidate Δ-cliques by adding nodes or extending interval boundaries, and outputs those that cannot be enlarged. It computes the set of all maximal Δ-cliques.
Algorithm
- Each candidate is expanded by adding eligible nodes or extending its interval left or right; candidates are processed once using a memorization set.The algorithm initializes candidates from individual links and outputs a candidate only when none of these enlargements succeeds.Source: §2 · p. 3
- The algorithm extends a clique's start to f − Δ and its end to l + Δ, using the latest first occurrence and earliest last occurrence of its links.These boundary choices identify larger intervals that remain Δ-cliques; the end-extension argument is given in p37.Source: §2 · pp. 4–5
Correctness
- Algorithm 1 computes the set of all maximal Δ-cliques of a link stream for a given duration Δ.The proof establishes that returned cliques are valid and maximal, and that every maximal Δ-clique is returned.Source: §2 · pp. 5, 7
Complexity
- For a link stream with n nodes, m links, and duration Δ, Algorithm 1 computes all maximal Δ-cliques using O(2^n n m^2) space and O(2^n n^2 m^3 + 2^n n^3 m^2) time.Configuration-space endpoints may be link times or link times shifted by Δ (and, for e, by −Δ), giving O(m^2) possible subintervals. The O(2^n) subset bound is attained when every node pair has a link at the same time.Source: §2 · pp. 7–8
Optimizations
- Restricting boundary searches and propagating candidate nodes can reduce work without changing the algorithm's worst-case complexity.Nodes eligible for an expanded clique are included among those eligible for its parent, allowing fewer node checks.Source: §2 · pp. 8–9
3. Experiments
The experiments apply the algorithm to an eight-day high-school contact trace and examine how Δ and search order affect the cliques found. Temporal cliques reveal contact patterns that the graph formed from any contact does not preserve, while the DFS advantage is dataset-dependent.
3. Experiments
- The Thiers-Highschool trace has 181 nodes and 45,047 links across 2,220 distinct pairs over 729,500 seconds; the implementation took an hour to compute results for four Δ values.The tested values were 60, 900, 3,600, and 10,800 seconds, chosen to reflect school-day rhythms.Source: §3 · p. 9
- Larger Δ values trivially yield larger and longer Δ-cliques, while the number of maximal Δ-cliques generally decreases but does not always do so.In the example stream, the counts are four for Δ = 1, six for Δ = 2, and four for Δ = 3.Source: §3 · p. 10
- Figure 4 plots complementary cumulative distributions of maximal Δ-clique size and duration for each Δ; its sharp drop at 2·Δ is attributed to single-link cliques.The distributions cover clique size |X| and duration e − b.Source: Figure 4 · p. 10, §3 · p. 10
- At Δ = 3,600 seconds, DFS rapidly finds many cliques, including non-trivial ones, but which search order is preferable depends on the dataset.Execution time is essentially the same for DFS and BFS; the data structure changes the order of discovery.Source: §3 · p. 10, Figure 5 · p. 11
- The contact graph contains 1,742 cliques, its largest has 14 nodes, and approximately 70% involve students in the same class.The graph connects a pair if they had at least one contact in the stream.Source: §3 · pp. 10–11
- A 60-clique involving four students from different classrooms lasted roughly five minutes, a contact pattern invisible in graph cliques.The paper suggests it is likely the signature of a coffee break.Source: §3 · p. 11
4. Conclusion
The paper introduces Δ-cliques and the first algorithm to compute maximal ones, which it implements to detect interesting cliques in real-world data. It also identifies algorithmic improvement and duration-based links as future directions.
4. Conclusion
- The authors introduce Δ-cliques and the first algorithm to compute maximal ones, then implement it to detect interesting cliques in real-world data.The conclusion presents both the concept and algorithm as contributions.Source: §4 · p. 11
- Adapting Bron–Kerbosch-style methods is promising, but their candidate-node tracking does not directly translate because link-stream cliques also vary over time.Those methods use tree-shaped configuration spaces to avoid redundant computations.Source: §4 · p. 11
- For links with duration, the authors propose dropping Δ, defining clique density as link probability at a randomly chosen time, and extending the algorithm to maximal cliques.The paper presents this case as a promising perspective.Source: §4 · pp. 11–12