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

Foad Mahdavi Pajouh, Zhuqi Miao, Balabhaskar Balasundaram

Research output: Contribution to journalArticle

17 Citations (Scopus)

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 - 1 Jan 2014
Externally publishedYes

Fingerprint

Branch-and-bound
Clique
Graph
Data mining
Telecommunication network
Protein
Gene
Mixed integer programming
Branch and bound algorithm
Interaction
Heuristics

Keywords

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

Cite this

Mahdavi Pajouh, Foad ; Miao, Zhuqi ; Balasundaram, Balabhaskar. / A branch-and-bound approach for maximum quasi-cliques. In: Annals of Operations Research. 2014 ; Vol. 216, No. 1. pp. 145-161.
@article{f712bc3857a040c09e029a1ae0df70f3,
title = "A branch-and-bound approach for maximum quasi-cliques",
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.",
keywords = "Clique, Cluster detection, Graph-based data mining, Quasi-clique",
author = "{Mahdavi Pajouh}, Foad and Zhuqi Miao and Balabhaskar Balasundaram",
year = "2014",
month = "1",
day = "1",
doi = "10.1007/s10479-012-1242-y",
language = "English",
volume = "216",
pages = "145--161",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer Netherlands",
number = "1",

}

A branch-and-bound approach for maximum quasi-cliques. / Mahdavi Pajouh, Foad; Miao, Zhuqi; Balasundaram, Balabhaskar.

In: Annals of Operations Research, Vol. 216, No. 1, 01.01.2014, p. 145-161.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Mahdavi Pajouh, Foad

AU - Miao, Zhuqi

AU - Balasundaram, Balabhaskar

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

KW - Clique

KW - Cluster detection

KW - Graph-based data mining

KW - Quasi-clique

UR - http://www.scopus.com/inward/record.url?scp=84897426188&partnerID=8YFLogxK

U2 - 10.1007/s10479-012-1242-y

DO - 10.1007/s10479-012-1242-y

M3 - Article

AN - SCOPUS:84897426188

VL - 216

SP - 145

EP - 161

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - 1

ER -