TY - GEN

T1 - Network robustness via global k-cores

AU - Dey, Palash

AU - Maity, Suman Kalyan

AU - Medya, Sourav

AU - Silva, Arlei

N1 - Publisher Copyright:
© 2021 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - K-core

KW - Network optimization

KW - Network robustness

UR - http://www.scopus.com/inward/record.url?scp=85112228641&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85112228641&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85112228641

T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

SP - 438

EP - 446

BT - 20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2021

PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

T2 - 20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2021

Y2 - 3 May 2021 through 7 May 2021

ER -