Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Effective Monotone Knowledge Integration in Kernel Support Vector Machines Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Knowledge-Guided Maximal Clique Enumeration

Authors : Steve Harenberg, Ramona G. Seay, Gonzalo A. Bello, Rada Y. Chirkova, P. Murali Doraiswamy, Nagiza F. Samatova

Published in: Advanced Data Mining and Applications

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Event Evolution Model Based on Random Walk Model with Hot Topic Extraction
next chapter Got a Complaint?- Keep Calm and Tweet It!
Literature
1.
2.
3.
Angles, R.: A comparison of current graph database models. In: Workshops Proceedings of the IEEE 28th International Conference on Data Engineering, ICDE, pp. 171–177 (2012)
4.
Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant time shortest-path queries in road networks. In: Proceedings of the Nine Workshop on Algorithm Engineering and Experiments, ALENEX (2007)
5.
Bron, C., Kerbosch, J.: Finding all cliques of an undirected graph (algorithm 457). Commun. ACM 16(9), 575–576 (1973)CrossRefMATH
6.
Creamer, G., Rowe, R., Hershkop, S., Stolfo, S.J.: Segmentation and automated social hierarchy detection through email network analysis. In: Advances in Web Mining and Web Usage Analysis, 9th International Workshop on Knowledge Discovery on the Web, WebKDD 2007, pp. 40–58 (2007)
7.
Cui, W., Xiao, Y., Wang, H., Lu, Y., Wang, W.: Online search of overlapping communities. In: Proceedings of the International Conference on Management of Data, SIGMOD 2013, pp. 277–288 (2013)
8.
Cui, W., Xiao, Y., Wang, H., Wang, W.: Local search of communities in large graphs. In: International Conference on Management of Data, SIGMOD, pp. 991–1002 (2014)
9.
Davis, A.P., Murphy, C.G., Johnson, R., Lay, J.M., Lennon-Hopkins, K., Saraceni-Richards, C.A., Sciaky, D., King, B.L., Rosenstein, M.C., Wiegers, T.C., Mattingly, C.J.: The comparative toxicogenomics database: update 2013. Nucleic Acids Res. 41(D1), D1104–D1114 (2013)CrossRef
10.
Franceschini, A., Szklarczyk, D., Frankild, S., Kuhn, M., Simonovic, M., Roth, A., Lin, J., Minguez, P., Bork, P., von Mering, C., Jensen, L.J.: STRING v9.1: protein-protein interaction networks, with increased coverage and integration. Nucleic Acids Res. 41(D1), D808–D815 (2013)CrossRef
11.
Goldenberg, S.B., Shapiro, L.J.: Physical mechanisms for the association of El Niño and West African rainfall with Atlantic major hurricane activity. J. Clim. 9(6), 1169–1187 (1996)CrossRef
12.
Iordanov, B.: HyperGraphDB: a generalized graph database. In: Web-Age Information Management, pp. 25–36 (2010)
13.
Jia, L., Ye, J., Haiyan, L.V., Wang, W., Zhou, C., Zhang, X., Xu, J., Wang, L., Jia, J.: Genetic association between polymorphisms of pen2 gene and late onset Alzheimer’s disease in the north chinese population. Brain Res. 1141, 10–14 (2007)CrossRef
14.
Klotzbach, P.J.: On the Madden-Julian oscillation-Atlantic hurricane relationship. J. Clim. 23(2), 282–293 (2010)CrossRef
15.
Modani, N., Dey, K.: Large maximal cliques enumeration in large sparse graphs. In: Proceedings of the 15th International Conference on Management of Data (2009)
16.
17.
Sozio, M., Gionis, A.: The community-search problem and how to plan a successful cocktail party. In: Proceedings of the 16th International Conference on Knowledge Discovery and Data Mining, KDD. pp. 939–948 (2010)
18.
Steinhaeuser, K., Chawla, N.V., Ganguly, A.R.: Complex networks as a unified framework for descriptive analysis and predictive modeling in climate science. Stat. Anal. Data Min. 4(5), 497–511 (2011)MathSciNetCrossRef
19.
Tsourakakis, C.E., Bonchi, F., Gionis, A., Gullo, F., Tsiarli, M.A.: Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In: The 19th International Conference on Knowledge Discovery and Data Mining, KDD, pp. 104–112 (2013)
20.
Vicknair, C., Macias, M., Zhao, Z., Nan, X., Chen, Y., Wilkins, D.: A comparison of a graph database and a relational database: a data provenance perspective. In: Proceedings of the 48th Annual Southeast Regional Conference, p. 42 (2010)
21.
Vimont, D.J., Kossin, J.P.: The Atlantic meridional mode and hurricane activity. Geophysical Research Letters 34(7) (2007)
22.
Wei, F.: TEDI: efficient shortest path query answering on graphs. In: Graph Data Management: Techniques and Applications., pp. 214–238 (2011)
23.
Wilkinson, K., Sayers, C., Kuno, H.A., Reynolds, D.: Efficient RDF storage and retrieval in Jena2. In: Proceedings of The First International Workshop on Semantic Web and Databases, SWDB, pp. 131–150 (2003)
24.
Xiao, Y., Wu, W., Pei, J., Wang, W., He, Z.: Efficiently indexing shortest paths by exploiting symmetry in graphs. In: 12th International Conference on Extending Database Technology, EDBT, pp. 493–504 (2009)
25.
Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. In: 12th International Conference on Data Mining, ICDM, pp. 745–754 (2012)
26.
Zhang, B., Park, B.H., Karpinets, T., Samatova, N.F.: From pull-down data to protein interaction networks and complexes with biological relevance. Bioinformatics 24(7), 979–986 (2008)CrossRef
27.
Zhu, F., Yan, X., Han, J., Yu, P.S.: gPrune: a constraint pushing framework for graph pattern mining. In: Zhou, Z.-H., Li, H., Yang, Q. (eds.) PAKDD 2007. LNCS (LNAI), vol. 4426, pp. 388–400. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-71701-0_​38 CrossRef
Metadata
Title
Knowledge-Guided Maximal Clique Enumeration
Authors
Steve Harenberg
Ramona G. Seay
Gonzalo A. Bello
Rada Y. Chirkova
P. Murali Doraiswamy
Nagiza F. Samatova
Copyright Year
2016
Book
Advanced Data Mining and Applications

Print ISBN: 978-3-319-49585-9

Electronic ISBN: 978-3-319-49586-6

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-49586-6_43

Premium Partner

    Image Credits