A game theoretic approach for k-core minimization

Sourav Medya, Tianyi Ma, Arlei Silva, Ambuj Singh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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 inter-dependencies 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020
EditorsBo An, Amal El Fallah Seghrouchni, Gita Sukthankar
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1922-1924
Number of pages3
ISBN (Electronic)9781450375184
StatePublished - 2020
Event19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020 - Virtual, Auckland, New Zealand
Duration: May 19 2020 → …

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume2020-May
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020
Country/TerritoryNew Zealand
CityVirtual, Auckland
Period5/19/20 → …

Keywords

  • K-core
  • Network design
  • Network resilience
  • Shapley value

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'A game theoretic approach for k-core minimization'. Together they form a unique fingerprint.

Cite this