Continuous Cubic Optimization Formulations for Cluster Detection Problems in Networks

The celebrated Motzkin-Straus formulation of 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 Turan'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 talk presents continuous cubic formulations for the maximum s-defective clique and the maximum s-plex problems by generalizing the Motzkin-Straus formulation to the corresponding clique relaxations. The formulations are used to extend the Turan's theorem and other known lower bounds on the clique number to the considered clique relaxations. Results of preliminary numerical experiments demonstrate that the proposed formulations can be used to quickly compute large clusters of interest. The talk is based on a joint work with Vladimir Stozhkov, Austin Buchanan, and Vladimir Boginski.