An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph
Zhuqi Miao, Balabhaskar Balasundaram
INFORMS Journal on Computing · 2020 · Volume 32 · Issue 3
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
Enable JavaScript for citation tools and additional paper interactions.