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 language | English |
|---|---|
| Pages (from-to) | 145-161 |
| Number of pages | 17 |
| Journal | Annals of Operations Research |
| Volume | 216 |
| Issue number | 1 |
| DOIs | |
| State | Published - 1 Jan 2014 |
| Externally published | Yes |
Fingerprint
Keywords
- Clique
- Cluster detection
- Graph-based data mining
- Quasi-clique
Cite this
}
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 journal › Article
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 -