Mathematical programming formulations for the Collapsed k-Core Problem

Martina Cerulli, Domenico Serra, Carmine Sorgente, Claudia Archetti and Ivana Ljubić

European Journal of Operational Research, 2023, vol. 311, issue 1, 56-72

Abstract: In social network analysis, the size of the k-core, i.e., the maximal induced subgraph of the network with minimum degree at least k, is frequently adopted as a typical metric to evaluate the cohesiveness of a community. We address the Collapsed k-Core Problem, which seeks to find a subset of b users, namely the most critical users of the network, the removal of which results in the smallest possible k-core. For the first time, both the problem of finding the k-core of a network and the Collapsed k-Core Problem are formulated using mathematical programming. On the one hand, we model the Collapsed k-Core Problem as a natural deletion-round-indexed Integer Linear formulation. On the other hand, we provide two bilevel programs for the problem, which differ in the way in which the k-core identification problem is formulated at the lower level. The first bilevel formulation is reformulated as a single-level sparse model, exploiting a Benders-like decomposition approach. To derive the second bilevel model, we provide a linear formulation for finding the k-core and use it to state the lower-level problem. We then dualize the lower level and obtain a compact Mixed-Integer Nonlinear single-level problem reformulation. We additionally derive a combinatorial lower bound on the value of the optimal solution and describe some pre-processing procedures, and valid inequalities for the three formulations. The performance of the proposed formulations is compared on a set of benchmarking instances with the existing state-of-the-art solver for mixed-integer bilevel problems proposed in (Fischetti, Ljubić, Monaci, and Sinnl, 2017).

Keywords: (O) combinatorial optimization; Bilevel optimization; Social networks; k-Core (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172300320X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:311:y:2023:i:1:p:56-72

DOI: 10.1016/j.ejor.2023.04.038

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().