Trust your data or not—stqp remains stqp: Community detection via robust standard quadratic optimization

Immanuel M. Bomze, Michael Kahr, Markus Leitner

Research output: Contribution to JournalArticleAcademicpeer-review

11 Downloads (Pure)

Abstract

We consider the robust standard quadratic optimization problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is optimized over the standard simplex. Following most approaches, we model the uncertainty sets by balls, polyhedra, or spectrahedra, more generally, by ellipsoids or order intervals intersected with subcones of the copositive matrix cone. We show that the copositive relaxation gap of the RStQP equals the minimax gap under some mild assumptions on the curvature of the aforementioned uncertainty sets and present conditions under which the RStQP reduces to the standard quadratic optimization problem. These conditions also ensure that the copositive relaxation of an RStQP is exact. The theoretical findings are accompanied by the results of computational experiments for a specific application from the domain of graph clustering, more precisely, community detection in (social) networks. The results indicate that the cardinality of communities tend to increase for ellipsoidal uncertainty sets and to decrease for spectrahedral uncertainty sets.

Original languageEnglish
Pages (from-to)301-316
Number of pages16
JournalMathematics of Operations Research
Volume46
Issue number1
Early online date15 Sep 2020
DOIs
Publication statusPublished - Feb 2021

Bibliographical note

Funding Information:
Funding: This work was supported by the Austrian Science Fund [Grant P 26755-N26] and the Vienna Science and Technology Fund [Grant ICT15-014]. These supports are greatly acknowledged.

Publisher Copyright:
Copyright: © 2020 INFORMS.

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

Keywords

  • Community detection
  • Quadratic optimization
  • Robust optimization
  • Social networks

Fingerprint

Dive into the research topics of 'Trust your data or not—stqp remains stqp: Community detection via robust standard quadratic optimization'. Together they form a unique fingerprint.

Cite this