A Game Theoretic Approach For k-Core Minimization

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 inspires the question: How resilient is the k-core structure of a network, such as the Web or Facebook, to edge deletions? More specifically, we study the problem of computing a small set of edges for which the removal minimizes the k-core structure of a network. This paper provides a comprehensive characterization of the hardness of the k-core minimization problem (KCM), including innaproximability and parameterized complexity. Motivated by these challenges, 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. Our experiments, show that the proposed algorithm outperforms competing solutions in terms of k-core minimization.