Tight bounds and faster methods for finding cliques in time linked networks
Tight bounds and output sensitive algorithms for maximal clique enumeration in link streams
Data Structures and Algorithms
Summary
Finding groups of people or nodes that all interact together over the same time period can be very tricky and slow in networks where connections happen at specific times. The paper shows new mathematical limits on how many such groups (called maximal cliques) can exist in these time-stamped networks, improving previous estimates. The authors also design new algorithms that can list these groups more efficiently, without spending an exponential amount of time on each one. These are the first known methods with guaranteed polynomial-time steps between outputs, making such analysis more practical.
What this means in practice
- •For network analysts: Identify closely interacting groups over time more efficiently in dynamic communication or social networks using the new algorithms.
- •For cybersecurity teams: Detect coordinated activity periods in time-sensitive network traffic by enumerating maximal cliques with improved algorithmic delays.
Authors
George Manoussakis
Abstract
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 $Δ$ and their degeneracy $k$. We prove that a link stream with $m$ links has $O(mΔ^2 3^{Δ/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 $Δ$ 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}(Δ)\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 $Δ$-cliques and $(Δ,γ)$-cliques of temporal graphs.