Journal
KDD'19: PROCEEDINGS OF THE 25TH ACM SIGKDD INTERNATIONAL CONFERENCCE ON KNOWLEDGE DISCOVERY AND DATA MINING
Volume -, Issue -, Pages 529-538Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3292500.3330986
Keywords
Maximum Clique; Large Sparse Graph; Branch-bound-and-reduce
Funding
- ARC [DP160101513, FT180100256]
- Australian Research Council [FT180100256] Funding Source: Australian Research Council
Ask authors/readers for more resources
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 (KC F-Den se) 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 KC F-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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available