Essec\Faculty\Model\Contribution {#2216
#_index: "academ_contributions"
#_id: "13981"
#_source: array:26 [
"id" => "13981"
"slug" => "mathematical-programming-formulations-for-the-collapsed-k-core-problem"
"yearMonth" => "2023-11"
"year" => "2023"
"title" => "Mathematical programming formulations for the collapsed k-core problem"
"description" => "CERULLI, M., SERRA, D., SORGENTE, C., ARCHETTI, C. et LJUBIC, I. (2023). Mathematical programming formulations for the collapsed k-core problem. <i>European Journal of Operational Research</i>, 311(1), pp. 56-72."
"authors" => array:5 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "CERULLI Martina"
]
2 => array:1 [
"name" => "SERRA Domenico"
]
3 => array:1 [
"name" => "SORGENTE Carmine"
]
4 => array:1 [
"name" => "ARCHETTI Claudia"
]
]
"ouvrage" => ""
"keywords" => array:4 [
0 => "(O) combinatorial optimization"
1 => "Bilevel optimization"
2 => "Social networks"
3 => "k-Core"
]
"updatedAt" => "2024-10-31 13:51:19"
"publicationUrl" => "https://doi.org/10.1016/j.ejor.2023.04.038"
"publicationInfo" => array:3 [
"pages" => "56-72"
"volume" => "311"
"number" => "1"
]
"type" => array:2 [
"fr" => "Articles"
"en" => "Journal articles"
]
"support_type" => array:2 [
"fr" => "Revue scientifique"
"en" => "Scientific journal"
]
"countries" => array:2 [
"fr" => null
"en" => null
]
"abstract" => array:2 [
"fr" => "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 k 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)."
"en" => "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 k 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)."
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2024-12-03T17:21:44.000Z"
"docTitle" => "Mathematical programming formulations for the collapsed k-core problem"
"docSurtitle" => "Journal articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, CERULLI Martina, SERRA Domenico, SORGENTE Carmine, ARCHETTI Claudia"
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, CERULLI Martina, SERRA Domenico, SORGENTE Carmine, ARCHETTI Claudia</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">2023</span>"
"keywordList" => "<a href="#">(O) combinatorial optimization</a>, <a href="#">Bilevel optimization</a>, <a href="#">Social networks</a>, <a href="#">k-Core</a>"
"docPreview" => "<b>Mathematical programming formulations for the collapsed k-core problem</b><br><span>2023-11 | Journal articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://doi.org/10.1016/j.ejor.2023.04.038" target="_blank">Mathematical programming formulations for the collapsed k-core problem</a>"
]
+lang: "en"
+"_type": "_doc"
+"_score": 7.7418003
+"parent": null
}
