Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-540-87481-2_3
Title: Effective pruning techniques for mining quasi-cliques
Authors: Liu, G. 
Wong, L. 
Issue Date: 2008
Source: Liu, G.,Wong, L. (2008). Effective pruning techniques for mining quasi-cliques. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5212 LNAI (PART 2) : 33-49. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-540-87481-2_3
Abstract: Many real-world datasets, such as biological networks and social networks, can be modeled as graphs. It is interesting to discover densely connected subgraphs from these graphs, as such subgraphs represent groups of objects sharing some common properties. Several algorithms have been proposed to mine quasi-cliques from undirected graphs, but they have not fully utilized the minimum degree constraint for pruning. In this paper, we propose an efficient algorithm called Quick to find maximal quasi-cliques from undirected graphs. The Quick algorithm uses several effective pruning techniques based on the degree of the vertices to prune unqualified vertices as early as possible, and these pruning techniques can be integrated into existing algorithms to improve their performance as well. Our experiment results show that Quick is orders of magnitude faster than previous work on mining quasi-cliques. © 2008 Springer-Verlag Berlin Heidelberg.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/40630
ISBN: 3540874801
ISSN: 03029743
DOI: 10.1007/978-3-540-87481-2_3
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

46
checked on Dec 13, 2017

Page view(s)

51
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.