Targeted k-node collapse problem: Towards understanding the robustness of local k-core structure

Yuqian Lv, Bo Zhou, Jinhuan Wang and Qi Xuan

Physica A: Statistical Mechanics and its Applications, 2024, vol. 641, issue C

Abstract: The concept of k-core, which indicates the largest induced subgraph where each node has k or more neighbors, plays a significant role in measuring the cohesiveness and engagement of a network, and it is exploited in diverse applications, e.g., network analysis, anomaly detection, community detection, etc. However, recent studies have demonstrated the vulnerability of k-core under malicious perturbations which focus on removing the minimal number of edges to make k-core structures collapse. Despite this, to the best of our knowledge, no existing research has yet concentrated on the minimal number of edges that must be removed to collapse a specific node in the k-core. To address this issue, in this paper, we make the first attempt to study the robustness of individual nodes in k-core and propose the Targeted k-node Collapse Problem (TNCP) with three novel contributions. Firstly, we offer a general definition of TNCP problem with a proof of its NP-hardness. Secondly, in order to cover the TNCP problem, we propose a heuristic algorithm named TNC and its improved version named ATNC for implementations on large-scale networks. Finally, experiments on 20 real-world networks across various domains verify the superiority of our proposed algorithms over 6 baseline methods with detailed comparisons and analyses. Resource related to our study is publicly available at https://github.com/Yocenly/TNCP.

Keywords: k-core decomposition; k-core robustness; Adversarial attack; Network science; Graph data mining (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437124002413
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:641:y:2024:i:c:s0378437124002413

DOI: 10.1016/j.physa.2024.129732

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().