Robust clustering in social networks

(joint with M. Kahr and M. Leitner)

During the last decades the importance of considering data uncertainty in optimization problems has become increasingly apparent, since small
fluctuations of input data may lead to comparably bad decisions in many
practical problems when uncertainty is ignored. If the probability
distribution of the uncertain data is not known (or cannot be sufficiently estimated), a common technique is to estimate bounds on the uncertain data (i.e., define uncertainty sets) and to identify optimal solutions that are robust against data fluctuations within these bounds. This approach leads to the robust optimization paradigm that allows to consider uncertain objectives and constraints [1].

Optimization problems where only the objective is uncertain arise, for instance, prominently in the analysis of social networks.
This stems from the fact that the strength of social ties (i.e., the amount of influence individuals exert on each
other) or the willingness of individuals to adopt and share information can, for example, only be roughly estimated based on observations.
A fundamental problem arising in social network analysis regards the identification of communities (e.g., work groups, interest groups), which can be modeled as a Dominant Set Clustering Problem [5,6,7] which in turn leads to a Standard Quadratic Optimization Problem (StQP); see [2]. Here the link strengths enter the objective while the constraints are familiar probability constraints, so that they can be considered certain.

Hence we investigate data uncertainty in the objective function of StQPs, considering different uncertainty sets, and derive implications for the complexity of robust variants of the corresponding deterministic counterparts. We can show that considering data uncertainty in a StQP results in another StQP of the same complexity if ellipsoidal, spherical or boxed uncertainty sets are assumed [4]. Moreover we discuss implications when considering polyhedral uncertainty sets, and derive rigorous bounds for this case, based upon copositive optimization [3].

References

[1] Ben-Tal A, El Ghaoui L, Nemirovski AS (2009) Robust optimization. Princeton Series in Applied Mathematics (Princeton NJ: Princeton University Press).

[2] Bomze IM (1998) On standard quadratic optimization problems. Journal of Global Optimization 13(4):369–387.

[3] Bomze IM (2012) Copositive optimization – Recent developments and applications. European Journal of Operational Research 216(3):509–520.

[4] Bomze IM, Kahr M, Leitner M. (2020) Trust your data or not - StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization. To appear in Mathematics of OR.

[5] Pavan M, Pelillo M (2007) Dominant sets and pairwise clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence 29(1):167–172.

[6] Rota Bulò S, Pelillo M (2017) Dominant-set clustering: A review. European Journal of Operational Research 262(1):1–13.

[7] Rota Bul\`{o} S, Pelillo M, Bomze IM (2011) Graph-based quadratic optimization: A fast evolutionary approach. Computer Vision and Image Understanding 115(7):984–995.