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 the engagement of a network, and it is exploited in diverse applications, e.g., network analysis, anomaly detection, community detection, etc. Recent works have demonstrated the vulnerability of k-core under malicious perturbations which focuses on removing the minimal number of edges to make a whole k-core structure collapse. However, to the best of our knowledge, there is no existing research concentrating on how many edges should be removed at least to make an arbitrary node in k-core collapse. Therefore, in this paper, we make the first attempt to study the Targeted k-node Collapse Problem (TNCP) with four novel contributions. Firstly, we offer the general definition of TNCP problem with the proof of its NP-hardness. Secondly, in order to address the TNCP problem, we propose a heuristic algorithm named TNC and its improved version named ATNC for implementations on large-scale networks. After that, the experiments on 16 real-world networks across various domains verify the superiority of our proposed algorithms over 4 baseline methods along with detailed comparisons and analyses. Finally, the significance of TNCP problem for precisely evaluating the resilience of k-core structures in networks is validated.


翻译:k-core 概念,它表明每个节点都有或有更多的邻接点的最大引导子集,在衡量网络的凝聚力和参与程度方面起着重要作用,并且被各种应用,例如网络分析、异常检测、社区探测等所利用。 最近的工作表明,k-core在恶意干扰下的脆弱性,这些恶意干扰的重点是消除最小的边缘,使整个 k-core 结构崩溃。然而,根据我们的知识,目前没有集中研究至少应消除多少边缘以使K-core 崩溃成为任意的节点的现有研究。因此,在本文中,我们第一次尝试研究目标 k-node 崩溃问题(TNCP),并作出四项新的贡献。首先,我们用其NP- 硬性证据来说明TRCP 问题的一般定义。第二,为了解决TNCP 问题,我们建议了一种叫跨国公司的超自然算法,其改进版名为ATNC,用于大规模网络的实施。随后,对16个真实世界网络的实验,在各个领域进行详细的K-nordfredistructional 分析,最后核实了我们提议的Kral 4 结构的超标度。

0
下载
关闭预览

相关内容

Networking:IFIP International Conferences on Networking。 Explanation:国际网络会议。 Publisher:IFIP。 SIT: http://dblp.uni-trier.de/db/conf/networking/index.html
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年2月27日
Arxiv
14+阅读 · 2020年12月17日
VIP会员
相关资讯
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员