Enumerating Maximal Cliques in Temporal Graphs

Anne-Sophie Himmel (TU Berlin)

In many complex systems, interactive dynamics play a very important role in the analysis of such systems. A modeling framework to capture these dynamics are temporal graphs. Our main focus lies on the extension of the concept of cliques to temporal graphs: for a given time period $\Delta$, a Delta-clique in temporal graphs is a set of vertices and a time interval, such that all vertices interact with each other at least after every Delta time steps within the time interval.
A greedy algorithm which enumerates all maximal Delta-cliques in a temporal graph was already introduced. In contrast to this approach, we apply the Bron-Kerbosch algorithm---an efficient, recursive backtracking algorithm which enumerates all maximal cliques in simple graphs---to this problem. Experiments on real-world datasets show that there is a significant improvement in the running time in comparison to the greedy algorithm approach.

Back to the research colloquium site.