Network Higher-Order Structure Dismantling
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-03-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/26/3/248 |
| _version_ | 1797241159186120704 |
|---|---|
| author | Peng Peng Tianlong Fan Linyuan Lü |
| author_facet | Peng Peng Tianlong Fan Linyuan Lü |
| author_sort | Peng Peng |
| collection | DOAJ |
| description | 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 <i>k</i>-cores arises from their internal high connectivity. Thus, we transform higher-order structure measurement into measurements on <i>k</i>-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. |
| first_indexed | 2024-04-24T18:18:53Z |
| format | Article |
| id | doaj.art-28a61d2723144e79ad0893d8c11f900f |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-24T18:18:53Z |
| publishDate | 2024-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-28a61d2723144e79ad0893d8c11f900f2024-03-27T13:36:57ZengMDPI AGEntropy1099-43002024-03-0126324810.3390/e26030248Network Higher-Order Structure DismantlingPeng Peng0Tianlong Fan1Linyuan Lü2Institute of Fundamental and Frontier Studies, University of Electronic Science and Technology of China, Chengdu 611731, ChinaSchool of Cyber Science and Technology, University of Science and Technology of China, Hefei 230026, ChinaInstitute of Fundamental and Frontier Studies, University of Electronic Science and Technology of China, Chengdu 611731, ChinaDiverse 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 <i>k</i>-cores arises from their internal high connectivity. Thus, we transform higher-order structure measurement into measurements on <i>k</i>-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.https://www.mdpi.com/1099-4300/26/3/248complex networkshigher-order structureshigher-order structure dismantling |
| spellingShingle | Peng Peng Tianlong Fan Linyuan Lü Network Higher-Order Structure Dismantling Entropy complex networks higher-order structures higher-order structure dismantling |
| title | Network Higher-Order Structure Dismantling |
| title_full | Network Higher-Order Structure Dismantling |
| title_fullStr | Network Higher-Order Structure Dismantling |
| title_full_unstemmed | Network Higher-Order Structure Dismantling |
| title_short | Network Higher-Order Structure Dismantling |
| title_sort | network higher order structure dismantling |
| topic | complex networks higher-order structures higher-order structure dismantling |
| url | https://www.mdpi.com/1099-4300/26/3/248 |
| work_keys_str_mv | AT pengpeng networkhigherorderstructuredismantling AT tianlongfan networkhigherorderstructuredismantling AT linyuanlu networkhigherorderstructuredismantling |