Measuring and improving the core resilience of networks

Ricky Laishram, Ahmet Erdem Sariyüce, Tina Eliassi-Rad, Ali Pinar, Sucheta Soundarajan

Research output: Chapter in Book/Entry/PoemConference contribution

24 Scopus citations

Abstract

The concept of k-cores is important for understanding the global structure of networks, as well as for identifying central or important nodes within a network. It is often valuable to understand the resilience of the k-cores of a network to attacks and dropped edges (i.e., damaged communications links). We provide a formal definition of a network»s core resilience, and examine the problem of characterizing core resilience in terms of the network»s structural features: in particular, which structural properties cause a network to have high or low core resilience? To measure this, we introduce two novel node properties,Core Strength andCore Influence, which measure the resilience of individual nodes» core numbers and their influence on other nodes» core numbers. Using these properties, we propose theMaximize Resilience of k-Core algorithm to add edges to improve the core resilience of a network. We consider two attack scenarios - randomly deleted edges and randomly deleted nodes. Through experiments on a variety of technological and infrastructure network datasets, we verify the efficacy of our node-based resilience measures at predicting the resilience of a network, and evaluate MRKC at the task of improving a network»s core resilience. We find that on average, for edge deletion attacks, MRKC improves the resilience of a network by 11.1% over the original network, as compared to the best baseline method, which improves the resilience of a network by only 2%. For node deletion attacks, MRKC improves the core resilience of the original network by 19.7% on average, while the best baseline improves it by only 3%.

Original languageEnglish (US)
Title of host publicationThe Web Conference 2018 - Proceedings of the World Wide Web Conference, WWW 2018
PublisherAssociation for Computing Machinery, Inc
Pages609-618
Number of pages10
ISBN (Electronic)9781450356398
DOIs
StatePublished - Apr 10 2018
Event27th International World Wide Web, WWW 2018 - Lyon, France
Duration: Apr 23 2018Apr 27 2018

Publication series

NameThe Web Conference 2018 - Proceedings of the World Wide Web Conference, WWW 2018

Conference

Conference27th International World Wide Web, WWW 2018
Country/TerritoryFrance
CityLyon
Period4/23/184/27/18

Keywords

  • Graphs
  • K-core
  • Resilience

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software

Fingerprint

Dive into the research topics of 'Measuring and improving the core resilience of networks'. Together they form a unique fingerprint.

Cite this