Skeletal Cores and Graph Resilience

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

doi:10.1007/978-3-031-43418-1_18

Skeletal Cores and Graph Resilience

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

Department of Electrical Engineering & Computer Science

Research output: Chapter in Book/Entry/Poem › Conference contribution

Abstract

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 language	English (US)
Title of host publication	Machine Learning and Knowledge Discovery in Databases
Subtitle of host publication	Research Track - European Conference, ECML PKDD 2023, Proceedings
Editors	Danai Koutra, Claudia Plant, Manuel Gomez Rodriguez, Elena Baralis, Francesco Bonchi
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	293-308
Number of pages	16
ISBN (Print)	9783031434174
DOIs	https://doi.org/10.1007/978-3-031-43418-1_18
State	Published - 2023
Event	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2023 - Turin, Italy Duration: Sep 18 2023 → Sep 22 2023

Publication series

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

Conference

Conference	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2023
Country/Territory	Italy
City	Turin
Period	9/18/23 → 9/22/23

Keywords

k-cores
networks
robustness

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-43418-1_18

Cite this

Honcharov, D., Sarıyüce, A. E., Laishram, R., & Soundarajan, S. (2023). Skeletal Cores and Graph Resilience. In D. Koutra, C. Plant, M. Gomez Rodriguez, E. Baralis, & F. Bonchi (Eds.), Machine Learning and Knowledge Discovery in Databases: Research Track - European Conference, ECML PKDD 2023, Proceedings (pp. 293-308). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14171 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-43418-1_18

Skeletal Cores and Graph Resilience. / Honcharov, Danylo; Sarıyüce, Ahmet Erdem; Laishram, Ricky et al.
Machine Learning and Knowledge Discovery in Databases: Research Track - European Conference, ECML PKDD 2023, Proceedings. ed. / Danai Koutra; Claudia Plant; Manuel Gomez Rodriguez; Elena Baralis; Francesco Bonchi. Springer Science and Business Media Deutschland GmbH, 2023. p. 293-308 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14171 LNAI).

Research output: Chapter in Book/Entry/Poem › Conference contribution

Honcharov, D, Sarıyüce, AE, Laishram, R & Soundarajan, S 2023, Skeletal Cores and Graph Resilience. in D Koutra, C Plant, M Gomez Rodriguez, E Baralis & F Bonchi (eds), Machine Learning and Knowledge Discovery in Databases: Research Track - European Conference, ECML PKDD 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14171 LNAI, Springer Science and Business Media Deutschland GmbH, pp. 293-308, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2023, Turin, Italy, 9/18/23. https://doi.org/10.1007/978-3-031-43418-1_18

Honcharov D, Sarıyüce AE, Laishram R, Soundarajan S. Skeletal Cores and Graph Resilience. In Koutra D, Plant C, Gomez Rodriguez M, Baralis E, Bonchi F, editors, Machine Learning and Knowledge Discovery in Databases: Research Track - European Conference, ECML PKDD 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 293-308. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-43418-1_18

Honcharov, Danylo ; Sarıyüce, Ahmet Erdem ; Laishram, Ricky et al. / Skeletal Cores and Graph Resilience. Machine Learning and Knowledge Discovery in Databases: Research Track - European Conference, ECML PKDD 2023, Proceedings. editor / Danai Koutra ; Claudia Plant ; Manuel Gomez Rodriguez ; Elena Baralis ; Francesco Bonchi. Springer Science and Business Media Deutschland GmbH, 2023. pp. 293-308 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a0b9ef4a4a364dddb03788ca97c28ebf,

title = "Skeletal Cores and Graph Resilience",

abstract = "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.",

keywords = "k-cores, networks, robustness",

author = "Danylo Honcharov and Sarıy{\"u}ce, {Ahmet Erdem} and Ricky Laishram and Sucheta Soundarajan",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2023 ; Conference date: 18-09-2023 Through 22-09-2023",

year = "2023",

doi = "10.1007/978-3-031-43418-1_18",

language = "English (US)",

isbn = "9783031434174",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "293--308",

editor = "Danai Koutra and Claudia Plant and {Gomez Rodriguez}, Manuel and Elena Baralis and Francesco Bonchi",

booktitle = "Machine Learning and Knowledge Discovery in Databases",

address = "Germany",

}

TY - GEN

T1 - Skeletal Cores and Graph Resilience

AU - Honcharov, Danylo

AU - Sarıyüce, Ahmet Erdem

AU - Laishram, Ricky

AU - Soundarajan, Sucheta

PY - 2023

Y1 - 2023

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

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

KW - k-cores

KW - networks

KW - robustness

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

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

U2 - 10.1007/978-3-031-43418-1_18

DO - 10.1007/978-3-031-43418-1_18

M3 - Conference contribution

AN - SCOPUS:85174442379

SN - 9783031434174

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 293

EP - 308

BT - Machine Learning and Knowledge Discovery in Databases

A2 - Koutra, Danai

A2 - Plant, Claudia

A2 - Gomez Rodriguez, Manuel

A2 - Baralis, Elena

A2 - Bonchi, Francesco

PB - Springer Science and Business Media Deutschland GmbH

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

Y2 - 18 September 2023 through 22 September 2023

ER -