journal article·2022-11-25Open access

Directed Network Disassembly Method Based on Non-Backtracking Matrix

Jinlong Ma, Peng Wang, Huijia Li

Applied Sciences· Volume 12· Issue 23

Abstract

Network disassembly refers to the removal of the minimum set of nodes to split the network into disconnected sub-part to achieve effective control of the network. However, most of the existing work only focuses on the disassembly of undirected networks, and there are few studies on directed networks, because when the edges in the network are directed, the application of the existing methods will lead to a higher cost of disassembly. Aiming at fixing the problem, an effective edge module disassembly method based on a non-backtracking matrix is proposed. This method combines the edge module spectrum partition and directed network disassembly problem to find the minimum set of key points connecting different edge modules for removal. This method is applied to large-scale artificial and real networks to verify its effectiveness. Multiple experimental results show that the proposed method has great advantages in disassembly accuracy and computational efficiency.
Source: crossref · Quality: baseline

Research context

OpenAlex topics: Manufacturing Process and Optimization · Industrial Vision Systems and Defect Detection · Machine Learning in Materials Science

SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.

Affiliations

School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang 050018, China

Hebei Technology Innovation Center of Intelligent Internet of Things, Shijiazhuang 050018, China

School of Science, Beijing University of Posts and Telecommunication, Beijing 100876, China

Funding

National Natural Science Foundation of China · Science and Technology Project of Hebei Education Department · Research on the Development of Social Science of Hebei Province · Fundamental Research Funds for the Hebei Universities

References (28)

Show source-provided references
1. Barrat, A., Barthelemy, M., and Vespignani, A. (2008). Dynamical Processes on Complex Networks, Cambridge University Press.10.1017/CBO9780511791383 ↗
2. Traffic dynamics on multilayer networks with different speeds
3. The hidden geometry of complex, network-driven contagion phenomena10.1126/science.1245200 ↗
4. Globally networked risks and how to respond10.1038/nature12047 ↗
5. The spreading of misinformation online10.1073/pnas.1517441113 ↗
6. Assessing the risks of ‘infodemics’ in response to COVID-19 epidemics10.1038/s41562-020-00994-6 ↗
7. Epidemic spreading in scale-free networks10.1103/PhysRevLett.86.3200 ↗
8. Kempe, D., Kleinberg, J., and Tardos, É. (2003, January 24–27). Maximizing the spread of influence through a social network. Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.10.1145/956750.956769 ↗
9. Breakdown of the internet under intentional attack10.1103/PhysRevLett.86.3682 ↗
10. Simulation of strategies for large-scale spread containment of infectious diseases
11. Network dismantling10.1073/pnas.1605083113 ↗
12. Postscript about NP-hard problems10.1145/1008304.1008305 ↗
13. Influence maximization in complex networks through optimal percolation10.1038/nature14604 ↗
14. Generalized network dismantling10.1073/pnas.1806108116 ↗
15. Fast and simple decycling and dismantling of networks10.1038/srep37954 ↗
16. A comparative analysis of approaches to network-dismantling10.1038/s41598-018-31902-8 ↗
17. Dismantling and vertex cover of network through message passing
18. A neighborhood link sensitive dismantling method for social networks10.1016/j.jocs.2020.101129 ↗
19. Evolution of networks10.1080/00018730110112519 ↗
20. Normalized cuts and image segmentation10.1109/34.868688 ↗
21. Spectral embedding of directed networks10.1007/s13278-016-0387-0 ↗
22. Spectral redemption in clustering sparse networks10.1073/pnas.1312486110 ↗
23. The phase transition in inhomogeneous random graphs10.1002/rsa.20168 ↗
24. The monotonicity theorem, Cauchy’s interlace theorem, and the Courant-Fischer theorem
25. Partitioning sparse matrices with eigenvectors of graphs10.1137/0611030 ↗
26. Collective dynamics of ‘small-world’networks10.1038/30918 ↗
27. Assortativity in complex networks10.1093/comnet/cnv005 ↗
28. Modularity and community structure in networks10.1073/pnas.0601602103 ↗