Quantum mechanics

Algorithm

Gaussian

Theoretical computer science

Sparse matrix

Computation

Computer science

Physics

Graph

Mathematics

Dense graph

Artificial intelligence

Clique

Combinatorics

1-planar graph

Clique problem

Bounding overwatch

Chordal graph

This paper studies the problem of MCC-Sparse, Maximum Clique Computation over large real-world graphs that are usually Sparse. In the literature, MCC-Sparse has been studied separately and less extensively than its dense counterpart MCC-Dense, and advanced algorithmic techniques that are developed for MCC-Dense have not been utilized in the existing MCC-Sparse solvers. In this paper, we design an algorithm MC-BRB which transforms an instance of MCC-Sparse to instances of k-clique finding over dense subgraphs (KCF-Dense) that can be computed by the existing MCC-Dense solvers. To further improve the efficiency, we then develop a new branch-reduce-&-bound framework for KCF-Dense by proposing light-weight reducing techniques and leveraging the existing advanced branching and bounding techniques of MCC-Dense solvers. In addition, we also design an ego-centric algorithm MC-EGO for heuristically computing a near-maximum clique in near-linear time. We conduct extensive empirical studies on large real graphs and demonstrate the efficiency and effectiveness of our techniques.

Efficient Maximum Clique Computation over Large Sparse Graphs