@inproceedings{86da89a742ca4b6c899d217984782e9d,
title = "Coherent closed quasi-clique discovery from large dense graph databases",
abstract = "Frequent coherent subgraphs can provide valuable knowledge about the underlying internal structure of a graph database, and mining frequently occurring coherent subgraphs from large dense graph databases has been witnessed several applications and received considerable attention in the graph mining community recently. In this paper, we study how to efficiently mine the complete set of coherent closed quasi-cliques from large dense graph databases, which is an especially challenging task due to the downward-closure property no longer holds. By fully exploring some properties of quasi-cliques, we propose several novel optimization techniques, which can prune the unpromising and redundant sub-search spaces effectively. Meanwhile, we devise an efficient closure checking scheme to facilitate the discovery of only closed quasi-cliques. We also develop a coherent closed quasi-clique mining algorithm, Cocain 1. Thorough performance study shows that Cocain is very efficient and scalable for large dense graph databases.",
keywords = "Coherent subgraph, Graph mining, Quasi-clique",
author = "Zhiping Zeng and Jianyong Wang and Lizhu Zhou and George Karypis",
year = "2006",
doi = "10.1145/1150402.1150506",
language = "English (US)",
isbn = "1595933395",
series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",
publisher = "Association for Computing Machinery (ACM)",
pages = "797--802",
booktitle = "KDD 2006",
address = "United States",
note = "KDD 2006: 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ; Conference date: 20-08-2006 Through 23-08-2006",
}