Cluster Events
NEXT SEMINAR 2024/2025
In this section, you will find the information (Speaker/Guest, abstract, date & time slot , location, online registration link..) about the upcoming seminar during the year. The seminar registrations will be on Eventbrite and everyone is welcome, from within ESSEC as well as from outside.
Immanuel Bomze - University of Vienna
Friday, December 6th 2024 from 12pm to 1pm
Room : A.034 - New signage
Zoom meeting : https://essec.zoom.us/j/91453966093
Title: Community Detection in (Social) Networks Under Uncertainty
(joint work with M.Kahr, M.Leitner, F.Rinaldi and D.Zeffiro)
Abstract: 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 estimated with sufficient precision), a common technique is to estimate bounds on the uncertain data
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 Problems (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].
If we switch to discrete models where decision on ties are binary (edge present or not), i.e., concentrate on the classic adjacency description of undirected graphs,
a different robustness seems more appropriate which is closer to the budgeted uncertainty robustness. The key notion here is that of an s-defective clique, a subgraph which
would be complete if at most s edges are added. We investigate a continuous cubic optimization model [8] of the combinatorial problem to find large s-defective cliques, where advanced first-order methods seem to be most efficient, and report on significant speed-up compared to earlier attempts [9] with the same quality.
Keywords. Graph clustering, community detection, dominant set, s-defective cliques, robust optimization, polynomial optimization.
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 (2021) Trust your data or not - StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization.
Mathematics of Operations Research} 46:301-316.
[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ò S, Pelillo M, Bomze IM (2011) Graph-based quadratic optimization: A fast evolutionary
approach. Computer Vision and Image Understanding 115(7):984–995.
[8] Bomze IM, Rinaldi F, Zeffiro D (2022) Fast cluster detection in networks by first order
optimization. SIAM J. Math. Data Sci. 4: 285-305.
[9] Stozhkov V, Buchanan A, Butenko S, Boginski V (2022). Continuous cubic formulations
for cluster detection problems in networks. Math.Progr. 196: 279-307.
Here is the registration link .
For any information about OMOR events, please send an e-mail to matta@essec.edu.