Knowledge-guided maximal clique enumeration


Conference Paper

© Springer International Publishing AG 2016. Maximal clique enumeration is a long-standing problem in graph mining and knowledge discovery. Numerous classic algorithms exist for solving this problem. However, these algorithms focus on enumerating all maximal cliques, which may be computationally impractical and much of the output may be irrelevant to the user. To address this issue, we introduce the problem of knowledge-biased clique enumeration, a query-driven formulation that reduces output space, computation time, and memory usage. Moreover, we introduce a dynamic state space indexing strategy for efficiently processing multiple queries over the same graph. This strategy reduces redundant computations by dynamically indexing the constituent state space generated with each query. Experimental results over real-world networks demonstrate this strategy’s effectiveness at reducing the cumulative query-response time. Although developed in the context of maximal cliques, our techniques could possibly be generalized to other constraint-based graph enumeration tasks.

Full Text

Duke Authors

Cited Authors

  • Harenberg, S; Seay, RG; Bello, GA; Chirkova, RY; Doraiswamy, PM; Samatova, NF

Published Date

  • January 1, 2016

Published In

Volume / Issue

  • 10086 LNAI /

Start / End Page

  • 604 - 618

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783319495859

Digital Object Identifier (DOI)

  • 10.1007/978-3-319-49586-6_43

Citation Source

  • Scopus