More Web Proxy on the site http://driver.im/

research-article

Redundancy-aware maximal cliques

Authors:

Ada Wai-Chee FuAuthors Info & Claims

KDD '13: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 122 - 130

https://doi.org/10.1145/2487575.2487689

Published: 11 August 2013 Publication History

Abstract

Recent research efforts have made notable progress in improving the performance of (exhaustive) maximal clique enumeration (MCE). However, existing algorithms still suffer from exploring the huge search space of MCE. Furthermore, their results are often undesirable as many of the returned maximal cliques have large overlapping parts. This redundancy leads to problems in both computational efficiency and usefulness of MCE.

In this paper, we aim at providing a concise and complete summary of the set of maximal cliques, which is useful to many applications. We propose the notion of τ-visible MCE to achieve this goal and design algorithms to realize the notion. Based on the refined output space, we further consider applications including an efficient computation of the top-k results with diversity and an interactive clique exploration process. Our experimental results demonstrate that our approach is capable of producing output of high usability and our algorithms achieve superior efficiency over classic MCE algorithms.

References

[1]

J. Abello, M. G. C. Resende, and S. Sudarsky. Massive quasi-clique detection. In LATIN, pages 598--612, 2002.

Digital Library

[2]

F. Afrati, A. Gionis, and H. Mannila. Approximating a collection of frequent sets. In SIGKDD, 2004.

Digital Library

[3]

R. Agrawal, S. Gollapudi, A. Halverson, and S. Leong. Diversifying search results. In Second ACM Int. Conf. on Web Search and Data Mining (WSDM), 2009.

Digital Library

[4]

N. M. Berry, T. H. Ko, T. Moy, J. Smrcka, J. Turnley, and B. Wu. Emergent clique formation in terrorist recruitment. In The AAAI-04 Workshop on Agent Organizations: Theory and Practice, 2004.

[5]

C. Bron and J. Kerbosch. Algorithm 457: finding all cliques of an undirected graph. Commun. ACM, 16(9):575--577, 1973.

Digital Library

[6]

F. Cazals and C. Karande. A note on the problem of reporting maximal cliques. Theor. Comput. Sci., 407(1-3):564--568, 2008.

Digital Library

[7]

J. Cheng, Y. Ke, S. Chu, and M. T. Özsu. Efficient core decomposition in massive networks. In ICDE, pages 51--62, 2011.

Digital Library

[8]

J. Cheng, Y. Ke, A. W.-C. Fu, J. X. Yu, and L. Zhu. Finding maximal cliques in massive networks by h*-graph. In SIGMOD Conference, pages 447--458, 2010.

Digital Library

[9]

J. Cheng, Y. Ke, A. W.-C. Fu, J. X. Yu, and L. Zhu. Finding maximal cliques in massive networks. ACM Trans. Database Syst., 36(4):21, 2011.

Digital Library

[10]

J. Cheng, L. Zhu, Y. Ke, and S. Chu. Fast algorithms for maximal clique enumeration with limited memory. In KDD, pages 1240--1248, 2012.

Digital Library

[11]

S. Chu and J. Cheng. Triangle listing in massive networks and its applications. In KDD, pages 672--680, 2011.

Digital Library

[12]

S. Chu and J. Cheng. Triangle listing in massive networks. TKDD, 6(4):17, 2012.

Digital Library

[13]

D. Eppstein, M. Löffler, and D. Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In ISAAC (1), pages 403--414, 2010.

[14]

M. Hua, J. Pei, A. Fu, and X. Lin. Top-k typicality queries and efficient query answering methods on large databases. The VLDB Journal, 18:809--835, 2009.

Digital Library

[15]

F. Kose, W. Weckwerth, T. Linke, and O. Fiehn. Visualizing plant metabolomic correlation networks using clique-metabolite matrices. Bioinformatics, 17(12):1198--1208, 2001.

[16]

G. Liu and L. Wong. Effective pruning techniques for mining quasi-cliques. In ECML/PKDD (2), pages 33--49, 2008.

Digital Library

[17]

H. Matsuda, T. Ishihara, and A. Hashimoto. Classifying molecular sequences using a linkage graph with their pairwise similarities. Theor. Comput. Sci., 210(2):305--325, 1999.

Digital Library

[18]

J. Moon and L. Moser. On cliques in graphs. Israel J. Math, 3:23--28, 1965.

[19]

G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Math. Programming, 14:265--294, 1978.

Digital Library

[20]

J. Pei, D. Jiang, and A. Zhang. On mining cross-graph quasi-cliques. In SIGKDD, 2005.

Digital Library

[21]

E. Tomita, A. Tanaka, and H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci., 363(1):28--42, 2006.

Digital Library

[22]

E. Vee, U. Srivastava, J. Shanmugasundaram, P. Bhat, and S. Yahia. Efficient computation of diverse query results. In ICDE, 2008.

Digital Library

[23]

J. Wang and J. Cheng. Truss decomposition in massive networks. PVLDB, 5(9):812--823, 2012.

Digital Library

[24]

D. Xin, H. Cheng, X. Yan, and J. Han. Extracting redundancy-aware top-k patterns. In SIGKDD, 2006.

Digital Library

[25]

X. Yan, H. Cheng, J. Han, and D. Xin. Summarizing itemset patterns: A profile-based approach. In SIGKDD, 2005.

Digital Library

Cited By

Xu XLiu HLv XWang YLi D(2024)An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph DiscoveryProceedings of the ACM on Management of Data10.1145/36988002:6(1-26)Online publication date: 20-Dec-2024
https://dl.acm.org/doi/10.1145/3698800
Huang KCui YYe QZhao YZhao XTian YZheng KHu HZhou X(2024)TED$^+$: Towards Discovering Top-k Edge-Diversified Patterns in a Graph DatabaseIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3312566(1-14)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3312566
Do AGuo MNeumann ANeumann F(2024)Evolutionary Multi-objective Diversity OptimizationParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70085-9_8(117-134)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70085-9_8
Show More Cited By

Index Terms

Redundancy-aware maximal cliques
1. Information systems
  1. Information systems applications
    1. Data mining
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Mining maximal cliques from a large graph using MapReduce

We consider Maximal Clique Enumeration (MCE) from a large graph. A maximal clique is perhaps the most fundamental dense substructure in a graph, and MCE is an important tool to discover densely connected subgraphs, with numerous applications to data ...
Finding maximal cliques in massive networks

Maximal clique enumeration is a fundamental problem in graph theory and has important applications in many areas such as social network analysis and bioinformatics. The problem is extensively studied; however, the best existing algorithms require memory ...
Coloring the Maximal Cliques of Graphs

In this paper we are concerned with the so-called clique-colorations of a graph, that is, colorations of the vertices so that no maximal clique is monochromatic. On one hand, it is known to be NP-complete to decide whether a perfect graph is 2-clique-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '13: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2013

1534 pages

ISBN:9781450321747

DOI:10.1145/2487575

Editors:
Rayid Ghani
University of Chicago
,
Ted E. Senator
SAIC
,
Paul Bradley
MethodCare, Inc.
,
Rajesh Parekh
Groupon
,
Jingrui He
Stevens Institute of Technology
,
General Chairs:
Robert L. Grossman
University of Chicago and Open Data Group
,
Ramasamy Uthurusamy
General Motors Corporation (retired)
,
Program Chairs:
Inderjit S. Dhillon
University of Texas
,
Yehuda Koren
Google

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 August 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD' 13

Sponsor:

KDD' 13: The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 11 - 14, 2013

Illinois, Chicago, USA

Acceptance Rates

KDD '13 Paper Acceptance Rate 125 of 726 submissions, 17%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
792
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)2

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xu XLiu HLv XWang YLi D(2024)An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph DiscoveryProceedings of the ACM on Management of Data10.1145/36988002:6(1-26)Online publication date: 20-Dec-2024
https://dl.acm.org/doi/10.1145/3698800
Huang KCui YYe QZhao YZhao XTian YZheng KHu HZhou X(2024)TED$^+$: Towards Discovering Top-k Edge-Diversified Patterns in a Graph DatabaseIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3312566(1-14)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3312566
Do AGuo MNeumann ANeumann F(2024)Evolutionary Multi-objective Diversity OptimizationParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70085-9_8(117-134)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70085-9_8
Do AGuo MNeumann ANeumann FElkind E(2023)Diverse approximations for monotone submodular maximization problems with a matroid constraintProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/617(5558-5566)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/617
Huang KHu HYe QTian KZheng BZhou X(2023)TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph DatabaseProceedings of the ACM on Management of Data10.1145/35887361:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588736
Do AGuo MNeumann ANeumann F(2022)Analysis of Evolutionary Diversity Optimization for Permutation ProblemsACM Transactions on Evolutionary Learning and Optimization10.1145/35619742:3(1-27)Online publication date: 19-Oct-2022
https://dl.acm.org/doi/10.1145/3561974
Li XZhou RChen LLiu CHe QYang YIves ZBonifati AEl Abbadi A(2022)One Set to Cover All Maximal Cliques ApproximatelyProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517881(2006-2019)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517881
Sun SLi WWang YLiao WYu P(2022)Continuous Monitoring of Maximum Clique Over Dynamic GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.300370134:4(1667-1683)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TKDE.2020.3003701
Abidi AChen LLiu CZhou R(2022)On Maximising the Vertex Coverage for ${\text{Top}}-k$ t-Bicliques in Bipartite Graphs2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00221(2346-2358)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00221
Jabbour SKmimech MRaddaoui B(2022)Discovering Overlapping Communities Based on Cohesive Subgraph Models over Graph DataBig Data Analytics and Knowledge Discovery10.1007/978-3-031-12670-3_16(189-201)Online publication date: 26-Jul-2022
https://doi.org/10.1007/978-3-031-12670-3_16
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents