EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3136. Assessing Network Cohesion Using the Collapsed k-Core

Invited abstract in session TD-52: Integer Programming and Combinatorial Optimization: Complexity Questions and Algorithms, stream Combinatorial Optimization.

Tuesday, 14:30-16:00
Room: 8003 (building: 202)

Authors (first author is the speaker)

1. Domenico Serra
Department of Mathematics, University of Salerno
2. Martina Cerulli
Computer Science Department, University of Salerno
3. Carmine Sorgente
Department of Mathematics, University of Salerno
4. Claudia Archetti
Università degli Studi di Brescia
5. Ivana Ljubic
IDS, ESSEC Business School of Paris

Abstract

In social network analysis, the size of the k-core, representing the largest subgraph with minimum degree k, is often used to measure community cohesion. The Collapsed k-Core Problem aims to identify a subset of crucial users, whose removal results in the smallest k-core. We formulate this problem using mathematical programming for the first time. One approach employs an Integer Linear formulation, modeling deletion rounds. Another approach presents two bilevel programs, differing in their formulation of the k-core identification. We reformulate the first bilevel model as a single-level sparse model using a decomposition method. For the second model, we provide a linear formulation for k-core identification and dualize it, resulting in a compact single-level Mixed-Integer Nonlinear problem. We also outline preprocessing steps and valid inequalities for all formulations. Performance comparison is conducted against a state-of-the-art solver on benchmark instances.

Keywords

Status: accepted

Back to the list of papers