Seminar by Prof. Immanuel Bomze, University of Vienna
Event details
| Date | 04.02.2019 |
| Hour | 15:00 › 16:30 |
| Speaker | Prof. Immanuel Bomze, University of Vienna |
| Location | |
| Category | Conferences - Seminars |
"Robust clustering in social networks"
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 accuracy), 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. 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 which in turn leads to a Standard Quadratic Optimization Problems (StQP). 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. Moreover we discuss implications when considering polyhedral uncertainty sets, and derive rigorous bounds for this case.
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 accuracy), 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. 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 which in turn leads to a Standard Quadratic Optimization Problems (StQP). 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. Moreover we discuss implications when considering polyhedral uncertainty sets, and derive rigorous bounds for this case.
Practical information
- General public
- Free