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