Continuous cubic formulations for cluster detection problems in networks
- PDF / 509,304 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 82 Downloads / 181 Views
Series B
Continuous cubic formulations for cluster detection problems in networks Vladimir Stozhkov1 · Austin Buchanan2 Vladimir Boginski4
· Sergiy Butenko3 ·
Received: 19 March 2020 / Accepted: 23 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract The celebrated Motzkin–Straus formulation for the maximum clique problem provides a nontrivial characterization of the clique number of a graph in terms of the maximum value of a nonconvex quadratic function over a standard simplex. It was originally developed as a way of proving Turán’s theorem in graph theory, but was later used to develop competitive algorithms for the maximum clique problem based on continuous optimization. Clique relaxations, such as s-defective clique and s-plex, emerged as attractive, more practical alternatives to cliques in network-based cluster detection models arising in numerous applications. This paper establishes continuous cubic formulations for the maximum s-defective clique problem and the maximum s-plex problem by generalizing the Motzkin–Straus formulation to the corresponding clique relaxations. The formulations are used to extend Turán’s theorem and other known lower bounds on the clique number to the considered clique relaxations. Results of preliminary numerical experiments with the CONOPT solver demonstrate that the proposed formulations can be used to quickly compute high-quality solutions for the maximum s-defective clique problem and the maximum s-plex problem. The proposed formulations can also be used to generate interesting test instances for global optimization solvers. Keywords Clique relaxations · Maximum s-defective clique problem · Maximum s-plex problem · Motzkin–Straus formulation · Turán’s theorem · Cubic optimization · Fractional b-matching Mathematics Subject Classification 90C26 · 90C27 · 90C35 · 05C35 · 05C50 · 05C69
Electronic supplementary material The online version of this article (https://doi.org/10.1007/s10107020-01572-4) contains supplementary material, which is available to authorized users. Extended author information available on the last page of the article
123
V. Stozhkov et al.
1 Introduction Let G = (V , E) be a simple (undirected) graph with vertex set V = {1, 2, . . . , n} and edge set E ⊆ V2 consisting of m unordered pairs of adjacent vertices. A subset of vertices C ⊆ V is called a clique if {i, j} ∈ E for every pair of distinct vertices i, j ∈ C. The maximum clique problem is to find a clique of largest cardinality in a graph, and the clique number ω(G) of G is the cardinality of a maximum clique in G. Turán [44] established the following inequality between the number of edges m, the number of vertices n, and the clique number ω(G) of a simple graph G: m ≤ 1−
1 ω(G)
n2 . 2
(1)
This inequality, known as Turán’s theorem, is one of the most prominent results in extremal graph theory [2]. Motzkin and Straus [33] discovered a nontrivial connection between the clique number of a simple graph G and the global
Data Loading...
