Peng Peng, Fan Tianlong, Lü Linyuan
Institute of Fundamental and Frontier Studies, University of Electronic Science and Technology of China, Chengdu 611731, China.
School of Cyber Science and Technology, University of Science and Technology of China, Hefei 230026, China.
Entropy (Basel). 2024 Mar 11;26(3):248. doi: 10.3390/e26030248.
Diverse higher-order structures, foundational for supporting a network's "meta-functions", play a vital role in structure, functionality, and the emergence of complex dynamics. Nevertheless, the problem of dismantling them has been consistently overlooked. In this paper, we introduce the concept of dismantling higher-order structures, with the objective of disrupting not only network connectivity but also eradicating all higher-order structures in each branch, thereby ensuring thorough functional paralysis. Given the diversity and unknown specifics of higher-order structures, identifying and targeting them individually is not practical or even feasible. Fortunately, their close association with -cores arises from their internal high connectivity. Thus, we transform higher-order structure measurement into measurements on -cores with corresponding orders. Furthermore, we propose the Belief Propagation-guided Higher-order Dismantling (BPHD) algorithm, minimizing dismantling costs while achieving maximal disruption to connectivity and higher-order structures, ultimately converting the network into a forest. BPHD exhibits the explosive vulnerability of network higher-order structures, counterintuitively showcasing decreasing dismantling costs with increasing structural complexity. Our findings offer a novel approach for dismantling malignant networks, emphasizing the substantial challenges inherent in safeguarding against such malicious attacks.
多样的高阶结构是支持网络“元功能”的基础，在结构、功能以及复杂动态的出现中起着至关重要的作用。然而，拆解这些高阶结构的问题一直被忽视。在本文中，我们引入了拆解高阶结构的概念，目的不仅是破坏网络连通性，还要消除每个分支中的所有高阶结构，从而确保彻底的功能瘫痪。鉴于高阶结构的多样性和未知细节，单独识别和针对它们是不实际甚至不可行的。幸运的是，它们与k核的紧密关联源于其内部的高连通性。因此，我们将高阶结构测量转化为对相应阶数的k核的测量。此外，我们提出了信念传播引导的高阶拆解（BPHD）算法，在最小化拆解成本的同时，实现对连通性和高阶结构的最大破坏，最终将网络转化为森林。BPHD展示了网络高阶结构的爆炸性脆弱性，与直觉相反的是，随着结构复杂性的增加，拆解成本反而降低。我们的研究结果为拆解恶意网络提供了一种新方法，强调了防范此类恶意攻击所固有的重大挑战。
