2012 FastAlgorithmsforMaximalCliqueE: Difference between revisions
Jump to navigation
Jump to search
(Importing text file) |
m (Text replacement - " </i> " to "</i> ") |
||
Line 15: | Line 15: | ||
===Abstract=== | ===Abstract=== | ||
<i> [[Maximal clique enumeration (MCE)]] </i> is a [[long-standing problem]] in [[graph theory]] and has numerous important [[application]]s. </s> | <i> [[Maximal clique enumeration (MCE)]]</i> is a [[long-standing problem]] in [[graph theory]] and has numerous important [[application]]s. </s> | ||
Though extensively [[studied]], most existing [[algorithm]]s become impractical when the [[input]] [[graph]] is too [[large]] and is [[disk-resident]]. </s> | Though extensively [[studied]], most existing [[algorithm]]s become impractical when the [[input]] [[graph]] is too [[large]] and is [[disk-resident]]. </s> | ||
[[We]] first propose an efficient [[partition-based algorithm for MCE]] that addresses the [[problem of processing large graphs with limited memory]]. </s> | [[We]] first propose an efficient [[partition-based algorithm for MCE]] that addresses the [[problem of processing large graphs with limited memory]]. </s> |
Revision as of 03:18, 2 October 2015
- (Cheng & 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:
Notes
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 |