Mathematical programming formulations for the collapsed k-core problem
From MaRDI portal
(Redirected from Publication:6168587)
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 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 et al., A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs, Operations Research 65(6), 2017).
Recommendations
- Mathematical Programming Formulations for the Bottleneck Hyperplane Clustering Problem
- Optimization problems for the maximum k-plex
- A unified framework for a class of mathematical programming problems
- Multi-constrained matroidal knapsack problems
- The constrained compartmentalized knapsack problem: mathematical models and solution methods
- Combinatorial \(n\)-fold integer programming and applications
- Combinatorial \(n\)-fold integer programming and applications
- Theory and Applications of n-Fold Integer Programming
- Integer Programming Formulations for the k-Cardinality Tree Problem
- scientific article; zbMATH DE number 1973871
Cites work
- A branch-and-cut algorithm for the edge interdiction clique problem
- A new general-purpose algorithm for mixed-integer bilevel linear programs
- A parameterized complexity view on collapsing \(k\)-cores
- A survey of network interdiction models and algorithms
- A survey on mixed-integer programming techniques in bilevel optimization
- An overview of bilevel optimization
- Bilevel and multilevel programming: A bibliography review
- Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
- Collective dynamics of `small-world' networks
- Community structure in social and biological networks
- Fortification Against Cascade Propagation Under Uncertainty
- Foundations of bilevel programming
- scientific article; zbMATH DE number 437527 (Why is no real title available?)
- Interdiction Games and Monotonicity, with Application to Knapsack Problems
- On integer and bilevel formulations for the \(k\)-vertex cut problem
- Preventing unraveling in social networks: the anchored \(k\)-core problem
- Smallest-last ordering and clustering and graph coloring algorithms
- The integer \(L\)-shaped method for stochastic integer programs with complete recourse
- The maximum clique interdiction problem
- The structure of scientific collaboration networks
Cited in
(2)
This page was built for publication: Mathematical programming formulations for the collapsed k-core problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168587)
