The Minimum Spanning K-Core Problem With Bounded Cvar Under Probabilistic Edge Failures

Keywords

Conditional value-at-risk history; Hop constraints; Minimum spanning k-core; Survivable network design

Abstract

This article introduces the minimum spanning k-core problem that seeks to find a spanning subgraph with a minimum degree of at least k (also known as a k-core) that minimizes the total cost of the edges in the subgraph. The concept of k-cores was introduced in social network analysis to identify denser portions of a social network. We exploit the graph-theoretic properties of this model to introduce a new approach to survivable interhub network design via spanning k-cores; the model preserves connectivity and diameter under limited edge failures. The deterministic version of the problem is polynomial-time solvable due to its equivalence to generalized graph matching. We propose two conditional value-at-risk (CVaR) constrained optimization models t obtain risk-averse solutions for the minimum spanning k-core problem under probabilistic edge failures. We present polyhedral reformulations of the convex piecewise linear loss functions used in these models that enable Benders-like decomposition approaches. A decomposition and branch-and-cut approach is then developed to solve the scenario-based approximation of the CVaR-constrained minimum spanning k-core problem for the aforementioned loss functions. The computational performance of the algorithm is investigated via numerical experiments.

Publication Date

3-1-2016

Publication Title

INFORMS Journal on Computing

Volume

28

Issue

2

Number of Pages

295-307

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1287/ijoc.2015.0679

Socpus ID

84969922985 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84969922985

This document is currently not available here.

Share

COinS