A branch-and-bound approach for maximum quasi-cliques

Foad Mahdavi Pajouh, Zhuqi Miao, Balabhaskar Balasundaram

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

Detecting quasi-cliques in graphs is a useful tool for detecting dense clusters in graph-based data mining. Particularly in large-scale data sets that are error-prone, cliques are overly restrictive and impractical. Quasi-clique detection has been accomplished using heuristic approaches in various applications of graph-based data mining in protein interaction networks, gene co-expression networks, and telecommunication networks. Quasi-cliques are not hereditary, in the sense that every subset of a quasi-clique need not be a quasi-clique. This lack of heredity introduces interesting challenges in the development of exact algorithms to detect maximum cardinality quasi-cliques. The only exact approaches for this problem are limited to two mixed integer programming formulations that were recently proposed in the literature. The main contribution of this article is a new combinatorial branch-and-bound algorithm for the maximum quasi-clique problem.

Original languageEnglish
Pages (from-to)145-161
Number of pages17
JournalAnnals of Operations Research
Volume216
Issue number1
DOIs
StatePublished - May 2014

Keywords

  • Clique
  • Cluster detection
  • Graph-based data mining
  • Quasi-clique

Fingerprint

Dive into the research topics of 'A branch-and-bound approach for maximum quasi-cliques'. Together they form a unique fingerprint.

Cite this