Seminario: “Trust your data or not - Standard remains Standard (QP); implications for robust clustering in social networks”

Venerdì 6 Aprile 2018, ore 14:30 - Aula 1BC45 - I. M. Bomze


Venerdì 6 Aprile 2018 alle ore 14:30 in Aula 1BC45, I. M. Bomze (VCOR/ISOR and DataScience@UniWien) terrà un seminario dal titolo “Trust your data or not - Standard remains Standard (QP); implications for robust clustering in social networks”.

In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite of its simplicity, this nonconvex continuous optimization model is quite versatile and can even serve to solve discrete problems like the Maximum-Clique-Problem. Here we will focus on Clustering in Social Networks applications in a Machine Learning context. A fundamental problem arising in social network analysis regards the identification of communities (e.g., work groups, interest groups), which can be modeled naturally with the framework of StQP. However the problem data are uncertain as the strength of social ties can only be roughly estimated based on observations. Therefore the robust counterpart for these problems refers to uncertainty only in the objective, not in the constraints. It turns out that for the StQP, most of the usual uncertainty sets do not add complexity to the robust counterpart. On the other hand, it is well known that most probably within this problem class, a generic StQP instance is not too hard to solve as the worst cases are hidden in relatively thin manifolds of the class. These hard instances allow for remarkably rich patterns of coexisting local solutions, which are closely related to practical difficulties in solving StQPs globally.
Based upon joint work with Michael Kahr, Markus Leitner, Werner Schachinger and Reinhard Ullrich (all Univ.Wien).