A new centrality measure based on neighbor loop structure for network dismantling

Abstract

Nearly all real-world networks are complex networks and usually are in danger of collapse. Therefore, it is crucial to exploit and understand the mechanisms of network attacks and provide better protection for network functionalities. Network dismantling aims to find the smallest set of nodes such that after their removal the network is broken into connected components of sub-extensive size. To overcome the limitations and drawbacks of existing network dismantling methods, this paper focuses on network dismantling problem and proposes a neighbor-loop structure based centrality metric, NL, which achieves a balance between computational efficiency and evaluation accuracy. In addition, we design a novel method combining NL-based nodes-removing, greedy tree-breaking and reinsertion. Moreover, we compare five baseline methods with our algorithm on ten widely used real-world networks and three types of model networks including Erdös-Rényi random networks, Watts-Strogatz small-world networks and Barabási-Albert scale-free networks with different network generation parameters. Experimental results demonstrate that our proposed method outperforms most peer methods by obtaining a minimal set of targeted attack nodes. Furthermore, the insights gained from this study may be of assistance to future practical research into real-world networks.

Keywords

Complex networks / Network dismantling / Centrality measure

References

[1] R. Albert, A.L. Barabasi, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (1) (2001) 47-97.

[2] Y. Li, H. Ma, L. Wang, S. Mao, G. Wang, Optimized content caching and user association for edge computing in densely deployed heterogeneous networks, IEEE Trans. Mobile Comput. 21 (6) (2022) 2130-2142.

[3] X. Zhou, X. Xu, W. Liang, Z. Zeng, Z. Yan, Deep-learning-enhanced multitarget detection for end-edge-cloud surveillance in smart iot, IEEE Internet Things J. 8 (16) (2021) 12588-12596.

[4] Z. Cai, Z. Xiong, H. Xu, P. Wang, W. Li, Y. Pan, Generative adversarial networks: a survey toward private and secure applications, ACM Comput, Far E. Surv. 54 (6)(2021) 38.

[5] A. Barrat, M. Barthélemy, A. Vespignani, Dynamical Processes on Complex Networks: Preliminaries:Networks and Graphs, Cambridge University Press, 2008.

[6] V. Colizza, A. Barrat, M. Barthelemy, A. Vespignani,The role of the airline transportation network in the prediction and predictability of global epidemics, Proc. Natl. Acad. Sci. U.S.A. 103 (7) (2006) 2015-2020.

[7] Y. Soon-Hyung, J. Hawoong, A. Barabasi, Modeling the internet's large-scale topology,Proc. Natl. Acad. Sci. U.S.A. 99 (21) (2002) 13382-13386.

[8] R. Albert, I. Albert, G.L. Nakarado, Structural vulnerability of the north american power grid, Phys. Rev. E 69 (2 Pt 2) (2004) 025103.

[9] R. Cohen, K. Erez, D. Ben-Avraham, S. Havlin, Breakdown of the internet under intentional attack, Phys. Rev. Lett. 86 (16) (2001) 3682-3685.

[10] L. Valdez, S. Louis, C.E. La Rocca, X. Zhang, S.V. Buldyrev, P.A. Trunfio, L. A. Braunstein, S. Havlin, Cascading failures in complex networks, J Complex Netw 8 (2) (2020) 2.

[11] Z. Cai, Z. He, X. Guan, Y. Li, Collective data-sanitization for preventing sensitive information inference attacks in social networks, IEEE Trans. Dependable Secure Comput. 15 (4) (2018) 577-590.

[12] N. Almeira, O.V. Billoni, J.I. Perotti, Scaling of percolation transitions on erds-rényi networks under centrality-based attacks, Phys. Rev. E 101 (1) (2020) 012306.

[13] A. Braunstein, L. Dall'Asta, G. Semerjian, L. Zdeborová, Network dismantling,Proc. Natl. Acad. Sci. U.S.A. 113 (44) (2016) 12368-12373.

[14] M. Lalou, M.A. Tahraoui, H. Kheddouci,The critical node detection problem in networks: a survey, Comput. Sci. Rev. 28 (MAY) (2018) 92-117.

[15] R.C. Beineke, W. Lowell, And vandell, decycling graphs, J. Graph Theor. 25 (1)(2015) 59-77.

[16] R. Albert, H. Jeong, A.L. Barabasi, Error and attack tolerance of complex networks, Nature 406 (6794) (2000) 378-382.

[17] L.C. Freeman, Centrality in social networks conceptual clarification, Soc. Network. 1 (3) (1978) 215-239.

[18] U. Brandes, On variants of shortest-path betweenness centrality and their generic computation, Soc. Network. 30 (2) (2008) 136-145.

[19] H. Cherifi, G. Palla, B.K. Szymanski, X. Lu, On community structure in complex networks: challenges and opportunities, Appl. Netw. Sci. 4 (2019) 117.

[20] S. Mugisha, H. Zhou, Identifying optimal targets of network attack by belief propagation, Phys. Rev. E 94 (1) (2016) 012305.

[21] L. Zdeborová, P. Zhang, H. Zhou, Fast and simple decycling and dismantling of networks, Sci. Rep. 6 (2016) 37954.

[22] S. Jiachen, L. Rong, F. Zhengping, X. Jiarong, M. Xiao, H. Yanqing, Lower bound of network dismantling problem, Chaos 28 (6) (2018) 063128.

[23] S.M. Qin, X.L. Ren, L.Y. Lü, Efficient network dismantling via node explosive percolation, Commun. Theor. Phys. 71 (6) (2019) 764-772.

[24] G.M. Wittenbaum, A.P. Hubbell, C. Zuckerman, Mutual enhancement : toward an understanding of the collective preference for shared information, J. Pers. Soc. Psychol. 77 (5) (1999) 967-978.

[25] F. Morone, H.A. Makse, Influence maximization in complex networks through optimal percolation, Nature 524 (7563) (2015) 65-68.

[26] F. Morone, B. Min, L. Bo, R. Mari, H.A. Makse, Collective influence algorithm to find influencers via optimal percolation in massively large social media, Sci. Rep. 6 (1)(2016) 30062.

[27] P.F. Bonacich, Factoring and weighting approaches to status scores and clique identification, J. Math. Sociol. 2 (1) (1972) 113-120.

[28] B. Sergey,The anatomy of a large-scale hypertextual web search engine, in:Proceedings of the Seventh International World Wide Web Conference, 1998.

[29] H. Hotelling, Simplified calculation of principal components, Psychometrika 1 (1)(1936) 27-35.

[30] P. Clusella, P. Grassberger, F.J. Perez-Reche, A. Politi, Immunization and targeted destruction of networks using explosive percolation, Phys. Rev. Lett. 117 (20) (2016) 208301.

[31] C. Guo, L. Yang, X. Chen, D. Chen, J. Ma, Influential nodes identification in complex networks via information entropy, Entropy 22 (2) (2020) 242.

[32] L.C. Freeman, A set of measures of centrality based on betweenness, Sociometry 40 (1) (1977) 35-41.

[33] G. Sabidussi, The centrality index of a graph, Psychometrika 31 (4) (1966) 581-603.

[34] H. Zhou, Spin glass approach to the feedback vertex set problem, Eur. Phys. J. B 86 (11) (2013) 1-9.

[35] X. Ren, N. Gleinig, D. Helbing, N. Antulov-Fantulin, Generalized network dismantling,Proc. Natl. Acad. Sci. U.S.A. 116 (14) (2018) 6554-6559.

[36] Y. Li, C. Liao, Y. Wang, C. Wang, Energy-efficient optimal relay selection in cooperative cellular networks based on double auction, IEEE Trans. Wireless Commun. 14 (8) (2015) 4093-4104.

[37] S. Rajeh, M. Savonnet, E. Leclercq, H. Cherifi, Interplay between hierarchy and centrality in complex networks, IEEE Access 8 (2020) 129717-129742.

[38] J. Kunegis, Konect: the koblenz network collection,in: Proceedings of the 22nd International Conference on World Wide Web, 2013.

[39] B. Vladimir, M. Andrej, Pajek datasets. http://vlado.fmf.uni-lj.si/pub/networks/data/. (Accessed 12 December 2020).

[40] M.S. Aslan, X. Chen, H. Cheng, Analyzing and learning sparse and scale-free networks using Gaussian graphical models, Int. J. Data Sci. Anal. 1 (2016) 99-109.

[41] R.A. Rossi, N.K. Ahmed,The network data repository with interactive graph analytics and visualization, in:Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.

[42] D. Gleich, L. Zhukov, P. Berkhin, Fast parallel pagerank: a linear system approach, Tech. Rep. 13 (2004) 22.

[43] D.J. Watts, S.H. Strogatz, Collective dynamics of ’small-world’ networks, Nature 393 (6684) (1998) 440.

[44] J. Leskovec, J. Kleinberg, C. Faloutsos, Graph evolution: densification and shrinking diameters, ACM Trans. Knowl. Discov. Data 1 (1) (2007) 2.

[45] G. Song, Y. Li, X. Chen, X. He, J. Tang, Influential node tracking on dynamic social network: an interchange greedy approach, IEEE Trans. Knowl. Data Eng. 29 (2)(2017) 359-372.

[46] S. Xia, Z. Yao, Y. Li, S. Mao, Online distributed offloading and computing resource management with energy harvesting for heterogeneous mec-enabled iot, IEEE Trans. Wireless Commun. 20 (10) (2021) 6743-6757.

[47] X. Zhou, W. Liang, K.I.-K. Wang, R. Huang, Q. Jin, Academic influence aware and multidimensional network analysis for research collaboration navigation based on scholarly big data, IEEE Trans. Emerg. Topics Comput. 9 (1) (2021) 246-257.

[48] N. Yodo, P. Wang, Engineering resilience quantification and system design implications: a literature survey, J. Mech. Des. 138 (11) (2016) 111408.