Network robustness via global k-cores

Palash Dey, Suman Kalyan Maity, Sourav Medya, Arlei Silva

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

Abstract

Network robustness is a measure a network's ability to survive adversarial attacks. But not all parts of a network are equal. K-cores, which are dense subgraphs, are known to capture some of the key properties of many real-life networks. Therefore, previous work has attempted to model network robustness via the stability of its k-core. However, these approaches account for a single core value and thus fail to encode a global network resilience measure. In this paper, we address this limitation by proposing a novel notion of network resilience that is defined over all cores. In particular, we evaluate the stability of the network under node removals with respect to each node's initial core. Our goal is to compute robustness via a combinatorial problem: find b most critical nodes to delete such that the number of nodes that fall from their initial cores is maximized. One of our contributions is showing that it is NP-hard to achieve any polynomial factor approximation of the given objective. We also present a fine-grained complexity analysis of this problem under the lens of parameterized complexity theory for several natural parameters. Moreover, we show two applications of our notion of robustness: measuring the evolution of species and characterizing networks arising from different domains.

Original languageEnglish (US)
Title of host publication20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2021
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages438-446
Number of pages9
ISBN (Electronic)9781713832621
StatePublished - 2021
Event20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2021 - Virtual, Online
Duration: May 3 2021May 7 2021

Publication series

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

Conference

Conference20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2021
CityVirtual, Online
Period5/3/215/7/21

Keywords

  • K-core
  • Network optimization
  • Network robustness

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'Network robustness via global k-cores'. Together they form a unique fingerprint.

Cite this