Coherent closed quasi-clique discovery from large dense graph databases

Zhiping Zeng, Jianyong Wang, Lizhu Zhou, George Karypis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

87 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationKDD 2006
Subtitle of host publicationProceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
PublisherAssociation for Computing Machinery (ACM)
Pages797-802
Number of pages6
ISBN (Print)1595933395, 9781595933393
DOIs
StatePublished - 2006
EventKDD 2006: 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - Philadelphia, PA, United States
Duration: Aug 20 2006Aug 23 2006

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Volume2006

Other

OtherKDD 2006: 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
CountryUnited States
CityPhiladelphia, PA
Period8/20/068/23/06

Keywords

  • Coherent subgraph
  • Graph mining
  • Quasi-clique

Fingerprint Dive into the research topics of 'Coherent closed quasi-clique discovery from large dense graph databases'. Together they form a unique fingerprint.

Cite this