Department of Computer Science Colloquium
2019 Series

Efficient Maximal Clique Computation over Large Sparse Graphs

Dr. Lijun Chang
Senior Lecturer and Future Fellow
School of Computer Science
University of Sydney

Date: May 15, 2019 (Wednesday)
Time: 5:00 - 6:00 pm
Venue: SCT909, Cha Chi Ming Science Tower, Ho Sin Hang Campus

Maximum clique computation, although being a classic NP-hard problem, has been extensively studied in the literature due to its importance in analyzing large real-world graphs. In this talk, I will give an overview of the existing maximum clique computation algorithms over large sparse graphs, and present our new MC-BRB algorithm that has been accepted to KDD 2019. In MC-BRB, we first transform an instance of maximum clique computation over sparse graphs to instances of k-clique finding over dense subgraphs, and then develop a branch-reduce-and-bound framework for k-clique finding over dense graphs. In addition, we also designed an ego-centric algorithm MC-EGO for heuristically computing a near-maximum clique in near-linear time.

Dr. Lijun Chang is a Senior Lecturer and Future Fellow in the School of Computer Science at the University of Sydney. He received Bachelor degree from Renmin University of China in 2007, and Ph.D. degree from The Chinese University of Hong Kong in 2011. He worked as a Postdoc and then DECRA research fellow at the University of New South Wales from 2012 to 2017. His research interests are in the fields of big graph (network) analytics, with a focus on designing practical algorithms and developing theoretical foundations for massive graph analysis. He has co-authored two monographs, and published over 50 papers in top venues such as SIGMOD, KDD, PVLDB, ICDE, VLDB Journal, TKDE, and Algorithmica.

********* ALL INTERESTED ARE WELCOME ***********
(For enquiry, please contact Computer Science Department at 3411 2385)

Photos  Slides