Source-linked AI summary
Tight bounds and output sensitive algorithms for maximal clique enumeration in link streams
George Manoussakis
TL;DR
Link-stream clique enumeration has lacked known algorithms with polynomial time delay per output, and prior bounds could be exponential in clique size. This paper uses maximum degree and degeneracy of instantaneous graphs to derive tighter bounds and two output-sensitive algorithms. It proves improved clique-count bounds and gives algorithms with polynomial delay in the respective parameters.
Problem
Known algorithms may spend time exponential in clique size per maximal-clique output, and the best known count bound has a 2^k factor.
Source: §1 · p. 4Method
The paper sweeps static graphs associated with start times and develops output-sensitive algorithms parameterized by maximum degree and degeneracy.
Source: §1 · p. 5Results
The bounds are O(mΔ^2 3^{Δ/3}) and O(n|T|k^2 3^{k/3}); both are tight up to polynomial factors, and the algorithms have polynomial delay.
Source: §1 · p. 5Takeaways & Limitations
The algorithms provide polynomial-delay enumeration for cliques maximal in both vertex set and interval, and the results also apply to Δ-cliques of temporal graphs.
Source: §1 · p. 5The second algorithm stores proper suffixes in memory, and the online version has a total-time bound rather than a per-event bound.
Source: §7 · p. 19
Abstract
from arXiv · showhide
A link stream is a set of interactions between pairs of vertices, each one lasting during some time interval, and a clique of a link stream is a set of vertices together with a time interval during which all of them interact. A clique is maximal if neither its vertex set nor its interval can be enlarged. All known algorithms listing the maximal cliques of a link stream may spend time exponential in the size of a clique for each clique they output. Here, we approach the question under the light of two parameters of the instantaneous graphs of the stream, their maximum degree $\Delta$ and their degeneracy $k$. We prove that a link stream with $m$ links has $O(m\Delta^2 3^{\Delta/3})$ maximal cliques, and that a link stream with $n$ vertices and $|\mathcal{T}|$ distinct end times has $O(n|\mathcal{T}|k^2 3^{k/3})$ maximal cliques. Both bounds are tight up to a factor polynomial in $\Delta$ and $k$ respectively, and the second one improves the factor $2^k$ of previous bounds to $3^{k/3}$. Then we present two algorithms. The first one has setup time $O(m\log m)$ and polynomial time delay $\mathrm{poly}(\Delta)\log m$. The second one has setup time $O(m\log m+mk^2\log^3 n)$ and polynomial time delay $\mathrm{poly}(k)\log m$. To the best of our knowledge, these are the first algorithms with polynomial time delay for this problem. We also give an online version of the second algorithm, and we show that our results apply to the $\Delta$-cliques and $(\Delta,\gamma)$-cliques of temporal graphs.
1 Introduction
The paper studies maximal cliques whose vertex sets and time intervals are both maximal, addressing output-sensitive enumeration in link streams. It uses maximum degree and degeneracy to bound the number of such cliques and obtain algorithms with polynomial delay.
1 Introduction
- Previous algorithms may spend time exponential in clique size per output, while the best known count bound carried a 2^k factor rather than the static-graph 3^{k/3} factor.The paper targets cliques maximal in both vertex set and interval, a notion distinct from maximal vertex sets across all times.Source: §1 · p. 4
- The paper distinguishes its interval-and-vertex-maximal cliques from temporal cliques defined only as vertex sets maximal across all times.The two solution families do not imply one another, and the number of link-stream maximal cliques can be exponentially larger.Source: §1 · p. 4
- A maximal clique ending at time e is determined by its start time and a maximal clique in a static graph, enabling a sweep over start times.As the start time increases, these static graphs only gain edges.Source: §1 · p. 5
- O(mΔ^2 3^{Δ/3}) maximal cliques suffice for a link stream with m links, and the bound is tight up to a factor O(Δ^2).The first output-sensitive algorithm has setup time O(m log m) and polynomial delay in Δ and log m.Source: §1 · p. 5
- O(n|T|k^2 3^{k/3}) maximal cliques suffice for a stream with n vertices and |T| distinct end times, tight up to a factor polynomial in k.This improves the previous 2^k factor to 3^{k/3}.Source: §1 · p. 5
- The second algorithm anchors each clique at its end time and first vertex in a low-later-neighbor ordering, using suffix checks to reject nonmaximal candidates.It has setup time O(m log m + mk^2 log^3 n) and polynomial delay in k and log m; it also has an online version and applies to Δ-cliques.Source: §1 · p. 5
2 Definitions
This section fixes the graph and link-stream notation, defines maximality and the parameters used in the paper, and formalizes enumeration delay.
2 Definitions
- A graph clique is a pairwise-adjacent vertex set, maximal when it is not strictly contained in another clique.The paper also recalls that an h-vertex graph has at most 3^{h/3} maximal cliques.Source: §2 · p. 6
- A link stream consists of a time interval, a finite vertex set, and links (b,e,u,v) representing interactions over intervals.The stream is simple when links of the same pair have disjoint intervals; isolated vertices are excluded, so n ≤ 2m.Source: §2 · p. 6
- The instantaneous graph contains pairs interacting at time t, while G[t0,t1] contains pairs interacting throughout [t0,t1].Simplicity makes the link containing a given pair's time unique.Source: §2 · p. 6
- A link-stream clique is a vertex set of size at least two that forms a clique throughout an interval; maximality forbids enlarging either the set or interval.The paper counts these maximal cliques by α and defines Δ, k, and q from instantaneous-graph degree, degeneracy, and clique size.Source: §2 · p. 6
- Time delay bounds the work between consecutive outputs, while amortized delay bounds cumulative work; a charging map can convert candidate-processing bounds into amortized delay.Buffering solutions can turn amortized delay into time delay, potentially using space proportional to total solution size.Source: §2 · pp. 6–7
3 Basic results
The section characterizes temporal maximal cliques through static maximal cliques in interval-induced graphs: their start and end times determine the interval, while maximality requires a static maximal clique at the start threshold.
3 Basic results
- A clique C at time t remains a clique exactly for intervals contained in [st(C), ft(C)].Here st(C) is the latest start time among C's pair-links, and ft(C) is their earliest end time.Source: §3 · p. 7
- A clique (C, [τ, e]) is maximal exactly when C is maximal in G[τ,e], se(C)=τ, and some pair of C ends at e.Source: §3 · p. 7
- If C is maximal in G[τ,e], then se(C)≤τ and C remains maximal in G[se(C),e].Source: §3 · p. 8
4 Algorithms parameterized by the maximum degree
The section bounds the number of maximal cliques in terms of maximum degree and gives a link-anchored enumeration algorithm. The algorithm has polynomial time delay and can also run online.
4 Algorithms parameterized by the maximum degree
- The algorithm anchors each clique at its canonical ending link, tests thresholds in Θℓ, and forms candidates from maximal cliques in Hτℓ.It outputs a candidate only when se(C)=τ and the anchor pair is canonical.Source: §4 · p. 8
- Algorithm 1 outputs exactly all maximal cliques without duplication.Source: §4 · p. 9
- A link stream with m links and maximum instantaneous degree Δ has O(mΔ^2 3^(Δ/3)) maximal cliques, with a lower construction giving Ω(m3^(Δ/3)) when R≥Mp.The upper and lower bounds differ by at most a factor O(Δ^2).Source: §4 · pp. 9–10
- Setup takes O(m log m), and polynomial time delay is O(Δ^4(Δ log m + Δ^2 + λ(Δ))).Amortized time delay is O(q^2Δ^2(Δ log m + Δ^2 + λ(Δ))).Source: §4 · p. 10
- The algorithm can run online, outputting each maximal clique at its end time with total time O(m log m) + αO(q^2Δ^2(Δ^2 + λ(Δ))).Source: §4 · p. 11
5 Algorithms parameterized by the degeneracy
This section develops a maximal-clique count bound using the number of vertices and end times, alongside algorithms parameterized by degeneracy. It presents Algorithm 2’s polynomial-delay approach and total-running-time bound, relates it to static-graph algorithms, and describes a space-saving alternative that reintroduces maximum degree.
5.1 Orders, anchors and suffixes
- Degeneracy orders define bounded forward neighborhoods and anchors; suffixes of cliques identify candidates that were already output at an earlier anchor.For a degeneracy ordering, the largest forward neighborhood has size c ≤ k; Lemma 9 establishes that a non-maximal candidate extends to a maximal clique whose first vertex has lower rank.Source: §5.1 · p. 11
5.2 The algorithm for given orders
- Algorithm 2 outputs every maximal clique exactly once, with amortized delay O(q^3c^2(c^2A + λ(c) + q log n)) under the stated operation-time assumptions.It examines end times, ending pairs, anchors, and thresholds; a dictionary of proper suffixes rejects candidates already represented by earlier outputs.Source: §5.2 · pp. 12–14
5.3 The number of maximal cliques
- The number of maximal cliques is O(n|T|k^2 3^(k/3)), with a matching lower bound up to polynomial factors when h ≥ k.More precisely, the upper bound is O(k^2 3^(k/3) sum_{e∈T} n_e), where n_e counts non-isolated vertices; the construction gives Ω(n|T|3^(k/3)) when h ≥ k.Source: §5.3 · pp. 14–15
5.4 Maintaining the orders over time
- The online algorithm outputs each maximal clique at its end time in total time O(m log m + mk log^3 n) + αO(k^5(k^2 log n + λ(k))).A time sweep maintains an acyclic orientation with out-degree O(k), using levels and vertex indices to define the orders used by the given-orders algorithm.Source: §5.4 · p. 15
- O(k^5(k^2 log m + λ(k))) delay follows a setup phase of O(m log m + mk^2 log^3 n) time for Algorithm 2.The algorithm uses O(mk^2 log^3 n) space, besides the space used by dictionary D and Lemma 1.Source: §5.4 · p. 16
- Persistent balanced search trees store historical pair-anchor and out-neighborhood orders, with O(mk^2 log^3 n) setup time and space.The method records versions at each event; during enumeration it retrieves the versions for an end time and uses binary search to recover levels and link values. The persistent-tree construction uses path copying.Source: §5.4 · pp. 16–17
- O(m log m + mk^2 log^3 n) + O(n|T|3^(k/3)) poly(k) log m total time matches Theorem 6’s lower bound up to poly(k) log m when output dominates setup.The factor α in the analysis does not depend on the algorithm’s orders.Source: §5.4 · p. 17
- For a static graph, Algorithm 2 with a degeneracy ordering reduces to the algorithm of [47], and Theorem 5 yields delay polynomial in degeneracy, as in.The static graph is represented by links over [0, 1]; the generalized suffix tree is replaced by dictionary D, and the sets Π(xy) are computed in O(m + nk^2) time.Source: §5.4 · p. 17
- Avoiding dictionary D and Lemma 1 can give polynomial input-space delay poly(k)Δ log m log α, but reintroduces maximum degree.Direct maximality testing scans lower-ranked neighbors of the anchor in G_e; geometric amortization instead of Lemma 1 yields the stated delay bound, with log α = O(log n + log |T| + k) by Theorem 6.Source: §5.4 · p. 17
6 Application to ∆-cliques
The section reduces discrete temporal-graph Δ-cliques to ordinary cliques in a constructed link stream, transferring maximality and instantaneous-graph parameters. This yields bounds and polynomial-delay enumeration guarantees, with a tight degeneracy-based bound and extensions to frequency-constrained cliques.
6 Application to Δ-cliques
- Replacing each pair’s consecutive window-start ranges with links creates Lθ, whose maximal cliques correspond bijectively to maximal Δ-cliques via (X, [a, b]) ↦ (X, [a, b − θ]).The instantaneous graph of Lθ at integer τ is Gθ.Source: §6 · pp. 17–18
- O(n min(|E|, tmax−tmin+1)k^2 3^(k/3)) bounds the number of maximal Δ-cliques, with setup time O(|E| log |E| + |E|k^2 log^3 n) and polynomial delay.Here k is the Δ-slice degeneracy; for every fixed θ, the count bound is tight up to a factor polynomial in k.Source: §6 · p. 18
- The Corollary 1 bound is tight up to O((θ + 2)k^2), and its 3^(k/3) factor cannot be improved.The construction has at least Rh^3p maximal cliques, Δ-slice degeneracy 3p + 2, and O(R(θ + 2)) time steps.Source: §6 · p. 18
- The reduction also yields O(n min(|E|, tmax−tmin+1)k^2 3^(k/3)) maximal (Δ, γ)-cliques, with polynomial-delay enumeration, and accommodates positive weights.For the frequency constraint, each pair’s valid window starts are represented by at most r consecutive-integer ranges; the weighted reduction is also stated to apply.Source: §6 · p. 18
- The reduction does not directly apply to Boekhout and Takes’ maximal cliques, whose intervals must start and end with an interaction.Their definition therefore yields different maximal cliques.Source: §6 · p. 19
7 Concluding remarks
The paper concludes that it gives the first polynomial-delay algorithms for maximal-clique enumeration in link streams and establishes a tight degeneracy-based count bound. It also identifies memory, delay, and online-update questions, alongside further extensions to investigate.
7 Concluding remarks
- The paper gives the first polynomial-delay algorithms for maximal-clique enumeration in link streams, parameterized respectively by maximum degree and instantaneous-graph degeneracy.It also proves a maximum count of Θ(n|T|3^(k/3)) up to a factor polynomial in k.Source: §7 · p. 19
- The degeneracy-parameterized algorithm stores proper suffixes of maximal cliques ending at the current time, leaving polynomial input-space enumeration as an open question.The paper notes a similar open question for static graphs.Source: §7 · p. 19
- Both algorithms’ delays include log m from setup-phase predecessor searches; whether delay can depend only on k may depend on the computation model.Source: §7 · p. 19
- The online algorithm has only a total-running-time bound; a per-event guarantee would require maintaining an acyclic small-out-degree orientation with worst-case update time.The paper leaves open whether such an orientation can be maintained and used for per-event delay polynomial in k and polylogarithmic in n.Source: §7 · p. 19
- For an h-order graph, O(h^2 3^(h/3)) bounds the number of cliques maximal when their last edge appears; removing h^2 remains open.A heuristic search found no insertion sequence exceeding about 3.5 · 3^(h/3) such cliques for h ≤ 12.Source: §7 · p. 19
- The paper identifies extensions to Δ-k-plexes, interaction-bounded weighted cliques, and isolated temporal cliques as open directions.For listing the cited Brunelli et al. cliques in streams with repeated pair interactions, the stated difficulty is testing containment in cliques from other times.Source: §7 · p. 19
- Outputs matched exhaustive search on more than 10,000 random streams with up to ten vertices, and the temporal-graph reductions were also checked on random instances.The exhaustive checks covered streams with many links sharing end times and Δ-cliques, (Δ, γ)-cliques, and weighted cases.Source: §7 · pp. 19–20