Skeletal Cores and Graph Resilience

Danylo Honcharov, Ahmet Erdem Sarıyüce, Ricky Laishram, Sucheta Soundarajan

Research output: Chapter in Book/Entry/PoemConference contribution


In network analysis, one of the most important structures is the k-core: the maximal set of nodes such that each node in the k-core has at least k neighbors within the core. Recently, the notion of the skeletal k-core– a minimal subgraph that preserves the core structure of the graph– has attracted attention. However, the literature to date has contained only a biased greedy heuristic for sampling skeletal cores, which resulted in a skewed analysis of the network. In this work, we introduce a novel MCMC algorithm for sampling skeletal cores uniformly at random, as well as a novel algorithm for estimating the size of the space of skeletal k-cores, which, as we show, is important for understanding the core resilience of the network. With these algorithms, we demonstrate the relationship between resilience of the network and the core structure of the graph and suggest fast heuristics for evaluating graph structure from a skeletal cores perspective. We show that the normalized number of skeletal cores in the graph correlates with the resilience of k-core towards edge deletion attacks.

Original languageEnglish (US)
Title of host publicationMachine Learning and Knowledge Discovery in Databases
Subtitle of host publicationResearch Track - European Conference, ECML PKDD 2023, Proceedings
EditorsDanai Koutra, Claudia Plant, Manuel Gomez Rodriguez, Elena Baralis, Francesco Bonchi
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages16
ISBN (Print)9783031434174
StatePublished - 2023
EventEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2023 - Turin, Italy
Duration: Sep 18 2023Sep 22 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14171 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2023


  • k-cores
  • networks
  • robustness

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Skeletal Cores and Graph Resilience'. Together they form a unique fingerprint.

Cite this