An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph

Zhuqi Miao () and Balabhaskar Balasundaram ()
Additional contact information
Zhuqi Miao: Center for Health Systems Innovation, Oklahoma State University, Stillwater, Oklahoma 74078
Balabhaskar Balasundaram: School of Industrial Engineering and Management, Oklahoma State University, Stillwater, Oklahoma 74078

INFORMS Journal on Computing, 2020, vol. 32, issue 3, 763-778

Abstract: A γ -quasi-clique in a simple undirected graph refers to a subset of vertices that induces a subgraph with edge density at least γ. When γ equals one, this definition corresponds to a classical clique. When γ is less than one, it relaxes the requirement of all possible edges by the clique definition. Quasi-clique detection has been used in graph-based data mining to find dense clusters, especially in large-scale error-prone data sets in which the clique model can be overly restrictive. The maximum γ -quasi-clique problem , seeking a γ-quasi-clique of maximum cardinality in the given graph, can be formulated as an optimization problem with a linear objective function and a single quadratic constraint in binary variables. This article investigates the Lagrangian dual of this formulation and develops an upper-bounding technique using the geometry of ellipsoids to bound the Lagrangian dual. The tightness of the upper bound is compared with those obtained from multiple mixed-integer programming formulations of the problem via experiments on benchmark instances.

Keywords: quasi-clique; clique relaxations; graph-based data mining; Lagrangian duality (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0922 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:3:i:2020:p:763-778

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().