Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs

Anne-Sophie Himmel, Hendrik Molter, Rolf Niedermeier, Manuel SorgeSoc. Netw. Anal. Min 2017 · OpenReview

TL;DR

This paper adapts the classic Bron-Kerbosch algorithm for finding maximal cliques in static graphs to the temporal domain, introducing a new algorithm for enumerating "Δ-cliques" in temporal graphs. Their approach significantly outperforms existing methods, achieving speedups of up to two orders of magnitude on real-world datasets, and introduces a novel parameter, "Δ-slice degeneracy," for theoretical analysis.

What Problem Does This Paper Address?

Analyzing complex networks often involves understanding how interactions evolve over time. Traditional graph analysis focuses on static snapshots, which can oversimplify dynamic systems. Temporal graphs, where interactions (edges) have timestamps, offer a more realistic model. A key challenge in temporal graphs is identifying dense substructures analogous to cliques in static graphs. The paper addresses this by focusing on "Δ-cliques," a temporal generalization where a group of vertices must interact with each other at least every Δ time steps within a given interval. Existing methods for enumerating these Δ-cliques are based on a greedy approach, and this paper aims to provide a more efficient, algorithmically grounded solution by adapting the well-established Bron-Kerbosch algorithm.

Methods

The core contribution is the adaptation of the Bron-Kerbosch algorithm, a recursive backtracking algorithm, to the temporal setting for enumerating maximal Δ-cliques. This involves several conceptual shifts:

  • Temporalizing Concepts: The algorithm's core components (sets of vertices) are transformed into sets of "vertex-interval pairs" to account for the temporal nature of interactions.
  • Δ-Neighborhood: A new concept, the Δ-neighborhood, is introduced to define temporal adjacency, considering interactions within a Δ-time window.
  • Δ-Cut: A temporal analogue of set intersection is defined to combine temporal neighborhoods.
  • Pivoting: The paper adapts the pivoting technique from static Bron-Kerbosch to reduce recursive calls. This involves selecting a "pivot" vertex-interval pair and pruning the search space based on its temporal neighborhood.
  • Δ-Slice Degeneracy: A new parameter, Δ-slice degeneracy, is introduced. This measures the degeneracy of "Δ-slices" of the temporal graph (subgraphs considering interactions within Δ-time windows), providing a theoretical basis for complexity analysis.

Datasets

The authors evaluated their algorithm on several real-world temporal graph datasets, chosen to represent diverse contexts of communication and interaction:

  • internet-router communication (as733)
  • email communication (karlsruhe)
  • social-network communication (facebook-like)
  • physical proximity (highschool-2011, highschool-2012, highschool-2013, hospital-ward, hypertext, infectious, primaryschool)

The dataset "highschool-2012" was previously used by Viard et al. [29] for their Δ-clique enumeration work.

Key Insights and Ideas

  • Bron-Kerbosch's Temporal Adaptability: The classic Bron-Kerbosch algorithm, known for its efficiency in static graphs, can be successfully adapted to the temporal domain, offering a significant performance improvement over existing greedy methods.
  • The Power of Pivoting in Temporal Graphs: While pivoting is a known optimization for static graphs, its application in temporal graphs is more complex but still yields substantial speedups, especially for larger Δ values.
  • Δ-Slice Degeneracy as a Key Parameter: This new parameter effectively captures the sparsity of temporal graphs in a way relevant to Δ-clique enumeration, enabling fixed-parameter tractable complexity analysis. This suggests that temporal graph problems might be efficiently solvable if this parameter is small, even if the overall problem is NP-hard.
  • Real-World Data Exhibits Small Δ-Slice Degeneracy: The experimental results show that for many real-world temporal graphs and relevant Δ values, the Δ-slice degeneracy is indeed small, validating its practical utility.

Key Results

  • Significant Speedup: The adapted Bron-Kerbosch algorithm (BRONKERBOSCHDELTAPIVOT*) achieved speedups of up to two orders of magnitude compared to the algorithm by Viard et al. [29] for most interesting Δ values.
  • Pivoting Effectiveness: For larger Δ values, pivoting strategies (particularly 1G and MG) reduced recursive calls by up to 60% and significantly improved running times.
  • Theoretical Bounds: The paper provides theoretical running time analyses based on Δ-slice degeneracy, showing that the problem is fixed-parameter tractable with respect to this parameter.
  • Small Δ-Slice Degeneracy in Practice: Experiments confirmed that Δ-slice degeneracy is small for many real-world datasets, especially for relevant Δ values, suggesting the practical efficiency of the proposed algorithm.

Limitations and Future Work

  • Computational Cost of Δ-Slice Degeneracy: The current method for computing Δ-slice degeneracy is described as "rather inefficient," taking significant time for some instances. Future work could focus on finding more efficient ways to compute this parameter, potentially through different characterizations.
  • Theoretical Running Time Upper Bound: While the theoretical analysis provides an upper bound, the paper suggests that the impact of pivoting on this bound could be further explored to potentially improve it.
  • Further Branching Rules: The authors mention that implementing further improved branching rules on top of pivoting, similar to successes in static graph algorithms, could be a direction for future research.
  • Temporal Degeneracy Ordering: Investigating whether an analogue to degeneracy ordering can be defined in the temporal setting and used to further improve the algorithm is also suggested.

Summary updated

Abstract

Dynamics of interactions play an increasingly important role in the analysis of complex networks. A modeling framework to capture this is 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 Δ-cliques, an extension of the concept of cliques to temporal graphs: for a given time period Δ, a Δ-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 Δ time steps within the time interval. Viard, Latapy, and Magnien (ASONAM 2015, TCS 2016) proposed a greedy algorithm for enumerating all maximal Δ-cliques in temporal graphs. In contrast to this approach, we adapt the Bron–Kerbosch algorithm—an efficient, recursive backtracking algorithm which enumerates all maximal cliques in static graphs—to the temporal setting. We obtain encouraging results both in theory (concerning worst-case running time analysis based on the parameter “Δ-slice degeneracy” of the underlying graph) as well as in practice with experiments on real-world data. The latter culminates in an improvement for most interesting Δ-values concerning running time in comparison with the algorithm of Viard, Latapy, and Magnien.
BibTeX
@inproceedings{himmel2017adapting,
  author = {Anne-Sophie Himmel and Hendrik Molter and Rolf Niedermeier and Manuel Sorge},
  title = {{Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs}},
  booktitle = {Soc. Netw. Anal. Min},
  year = {2017},
  url = {https://openreview.net/forum?id=m7yjehcdeG},
}
Figure