Fast algorithms for maximal clique enumeration with limited memory

• Main Authors: Cheng, James, Zhu, Linhong, Ke, Yiping, Chu, Shumo
• Other Authors: School of Computer Engineering
• Format: Conference or Workshop Item
• Language: English
• Published: 2013
• Online Access: https://hdl.handle.net/10356/98958; http://hdl.handle.net/10220/12578
• Institution: Nanyang Technological University

Maximal clique enumeration (MCE) is a long-standing problem in graph theory and has numerous important applications. Though extensively studied, most existing algorithms become impractical when the input graph is too large and is disk-resident. We first propose an efficient partition-based algorithm for MCE that addresses the problem of processing large graphs with limited memory. We then further reduce the high cost of CPU computation of MCE by a careful nested partition based on a cost model. Finally, we parallelize our algorithm to further reduce the overall running time. We verified the efficiency of our algorithms by experiments in large real-world graphs.