2019/01/08 by Sourav Medya, Medya, Sourav, Tiyani Ma +6 · 8 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Neural Networks #Advanced Graph Theory Research #Algorithm #Artificial intelligence #Complex Network Analysis Techniques #Computer science #Cooperative game theory #Core (optical fiber) #Data Structures and Algorithms (cs.DS) #Enhanced Data Rates for GSM Evolution #FOS: Computer and information sciences #Game theory #Leverage (statistics) #Mathematical optimization #Mathematics #Probabilistic logic #Randomized algorithm #Social and Information Networks (cs.SI) #Theoretical computer science #cs.DS #cs.SI
paper · pdf · doi:10.48550/arxiv.1901.02166
published in arXiv (Cornell University) (Cornell University) · To appear as an extended abstract in AAMAS 2020 and as a full paper in IJCAI 2020
openalex publication_date 2019/01/08 · arxiv created 2020/04/20 · arxiv updated 2020/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 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.