TY - GEN
T1 - Skeletal Cores and Graph Resilience
AU - Honcharov, Danylo
AU - Sarıyüce, Ahmet Erdem
AU - Laishram, Ricky
AU - Soundarajan, Sucheta
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
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 - https://www.scopus.com/pages/publications/85174442379
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
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 - 23rd Joint European Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2023
Y2 - 18 September 2023 through 22 September 2023
ER -