K-Core Minimization: A Game Theoretic Approach
arXiv:1901.02166
Abstract
K-cores are maximal induced subgraphs where all vertices have degree at least k. These dense patterns have applications in community detection, network visualization and protein function prediction. However, k-cores can be quite unstable to network modifications, which motivates the question: How resilient is the k-core structure of a network, such as the Web or Facebook, to edge deletions? We investigate this question from an algorithmic perspective. More specifically, we study the problem of computing a small set of edges for which the removal minimizes the -core structure of a network. This paper provides a comprehensive characterization of the hardness of the k-core minimization problem (KCM), including innaproximability and fixed-parameter intractability. Motivated by such a challenge in terms of algorithm design, we propose a novel algorithm inspired by Shapley value -- a cooperative game-theoretic concept -- that is able to leverage the strong interdependencies in the effects of edge removals in the search space. As computing Shapley values is also NP-hard, we efficiently approximate them using a randomized algorithm with probabilistic guarantees. Our experiments, using several real datasets, show that the proposed algorithm outperforms competing solutions in terms of k-core minimization while being able to handle large graphs. Moreover, we illustrate how KCM can be applied in the analysis of the k-core resilience of networks.
arXiv commentTo appear as an extended abstract in AAMAS 2020 and as a full paper in IJCAI 2020
References in corpus (10)
- Identification of influential spreaders in complex networks
- Network robustness and fragility: Percolation on random graphs
- Resilience of the Internet to random breakdowns
- Structural Vulnerability of the North American Power Grid
- New Model of Internet Topology Using k-shell Decomposition
- MEDUSA - New Model of Internet Topology Using k-shell Decomposition
- The k-core as a predictor of structural collapse in mutualistic ecosystems
- Graph measures and network robustness
- Bounding the Estimation Error of Sampling-based Shapley Value Approximation
- Accelerating Community Detection by Using K-core Subgraphs