Adapting the Bron-Kerbosch Algorithm for Enumerating Maximal Cliques in Temporal Graphs

Understand

Dynamics of interactions play an increasingly important role in the analysis of complex networks.

• A modeling framework to capture this are temporal graphs which consist of a set of vertices (entities in the network) and a set of time-stamped binary interactions between the vertices.
• We focus on enumerating delta-cliques, an extension of the concept of cliques to temporal graphs: for a given time period delta, a delta-clique in a temporal graph 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.
• Viard, Latapy, and Magnien [ASONAM 2015, TCS 2016] proposed a greedy algorithm for enumerating all maximal delta-cliques in temporal graphs.