Knowledge-Guided Maximal Clique Enumeration
| Autor: | P. Murali Doraiswamy, Steve Harenberg, Rada Chirkova, Ramona G. Seay, Nagiza F. Samatova, Gonzalo A. Bello |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
0301 basic medicine
Clique Theoretical computer science Computer science Search engine indexing Context (language use) 02 engineering and technology Graph enumeration 03 medical and health sciences 030104 developmental biology Knowledge extraction 020204 information systems 0202 electrical engineering electronic engineering information engineering Enumeration State space Graph (abstract data type) |
| Zdroj: | Advanced Data Mining and Applications ISBN: 9783319495859 ADMA |
| DOI: | 10.1007/978-3-319-49586-6_43 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|