2012 FastAlgorithmsforMaximalCliqueE

• (Cheng et al., 2012) ⇒ James Cheng, Linhong Zhu, Yiping Ke, and Shumo Chu. (2012). “Fast Algorithms for Maximal Clique Enumeration with Limited Memory.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339724

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222012%22+Fast+Algorithms+for+Maximal+Clique+Enumeration+with+Limited+Memory
• http://dl.acm.org/citation.cfm?id=2339530.2339724&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; graph algorithms; i/o efficient; massive networks; maximal clique enumeration; parallel algorithm; sparse graphs

Abstract

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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 FastAlgorithmsforMaximalCliqueE	Shumo Chu James Cheng Linhong Zhu Yiping Ke			Fast Algorithms for Maximal Clique Enumeration with Limited Memory				10.1145/2339530.2339724		2012