Important edge identification in complex networks based on local and global features

doi:10.1088/1674-1056/aca6d8

Abstract Identifying important nodes and edges in complex networks has always been a popular research topic in network science and also has important implications for the protection of real-world complex systems. Finding the critical structures in a system allows us to protect the system from attacks or failures with minimal cost. To date, the problem of identifying critical nodes in networks has been widely studied by many scholars, and the theory is becoming increasingly mature. However, there is relatively little research related to edges. In fact, critical edges play an important role in maintaining the basic functions of the network and keeping the integrity of the structure. Sometimes protecting critical edges is less costly and more flexible in operation than just focusing on nodes. Considering the integrity of the network topology and the propagation dynamics on it, this paper proposes a centrality measure based on the number of high-order structural overlaps in the first and second-order neighborhoods of edges. The effectiveness of the metric is verified by the infection-susceptibility (SI) model, the robustness index R, and the number of connected branches θ. A comparison is made with three currently popular edge importance metrics from two synthetic and four real networks. The simulation results show that the method outperforms existing methods in identifying critical edges that have a significant impact on both network connectivity and propagation dynamics. At the same time, the near-linear time complexity can be applied to large-scale networks.

Keywords: complex networks high-order structure edge importance connectivity propagation dynamics

Received: 01 October 2022
Revised: 16 November 2022
Accepted manuscript online: 29 November 2022

PACS:

89.75.Fb

(Structures and organization in complex systems)

Corresponding Authors: Jia-Hui Song
E-mail: songjiahuizz123456@163.com

Cite this article:

Jia-Hui Song(宋家辉) Important edge identification in complex networks based on local and global features 2023 Chin. Phys. B 32 098901

[1] Bonacich P 1972 J. Math. Sociol. 2 113
[2] Lü L Y, Zhou T and Zhang Q M 2016 Nat. Comm. 7 10168
[3] Kitsak M, Gallos L K and Havlin S 2010 Nat. Phys. 6 888
[4] Crescenzi P, D'angelo G and Severini L 2016 ACM. T. Know. Discov. D 11 1
[5] Freeman L C 1977 Sociometry 40 35
[6] Ma Y, Cao Z and Qi X 2019 Physica A 527 121130
[7] Li Z, Ren T and Ma X 2019 Sci. Rep. 9 8387
[8] Li Z, Ren T and Xu Y 2020 IEEE Access 8 66068
[9] Holme P, Kim B and Yoon C 2002 Stat. Non. 65 056109
[10] Xia Y and Hill D J 2008 IEEE Trans. Biomed. Circ. S 55 65
[11] Cuadra L, Salcedo-Sanz S and Del Ser J 2015 Energies 8 9211
[12] Goltsev A V, Dorogovtsev S N and Oliveira J G 2012 Phys. Rev. Lett. 109 128702
[13] Ball M O, Golden B L and Vohra R V 1989 Oper. Res. Lett. 8 73
[14] Girvan M, Newman M, Girvan M and Newman M E J 2002 P. Natl. A. Sci. 99 7821
[15] Yu E Y, Chen D B and Zhao J Y 2018 Sci. Rep. 8 14469
[16] Kanwar K, Kumar H and Kaushal S 2019 Soc. Netw. Anal. Min. 12 49
[17] Holme P, Kim B and Yoon C 2002 Phys. Rev. E 65 056109
[18] Onnela J P, Saramäki J and Hyvönen J 2007 Nat. Aca. Sci. 104 7332
[19] Cheng X Q, Ren F X and Shen H W 2010 J. Stat. Mech-theory. E 2010 P10011
[20] Liu Y, Tang M and Zhou T 2015 Sci. Rep. 5 131725
[21] Matamalas J T, Arenas A and Gómez S 2018 Sci. Adv. 4 eaau4212
[22] Ouyang B, Xia Y and Wang C 2018 IEEE Trans. Biomed. Circ. S 65 1244
[23] Xu Y, Ren T and Sun S 2021 Math. 9 2531
[24] Yu E Y, Chen D B and Zhao J Y 2018 Sci. Rep. 8 14469
[25] Zhao N, Li J and Wang J 2018 Physica A 548 123877
[26] Bröhl T and Lehnertz K 2019 Chaos 29 1098
[27] Kossinets G and Watts D J 2006 Science 311 88
[28] Battiston F 2021 Nat. Phys. 17 1093
[29] Rubinov M and Sporns O 2010 Neuroimage 52 1059
[30] Reijneveld J C, Ponten S C and Berendse H W 2007 Clin. Neurophysiol. 118 2317
[31] Wu T, Zhang X and Liu Z 2022 Front. Phys. 17 31504
[32] Wu J, Tse C K and Lau F C M 2013 IEEE Trans. Biomed. Circ.S 60 3303
[33] Chen Z, Wu J and Xia Y 2018 IEEE Trans. Circ. I 65 115
[34] De la Cruz Cabrera O, Jin J and Noschese S 2022 Appl. Numer. Math. 172 186
[35] Cai S M, Hong L and Zhong Q 2011 Complex Syst. Complexity Sci. 10 1099
[36] Milanović J V and Zhu W 2017 IEEE T. Smart. Grid 9 4637
[37] Yang F, Zhu J and Sun J 2019 J. Netw. Comput. Appl. 39 72
[38] Muldoon, Sarah and Feldt 2018 Phys. Life. Rev. 24 143
[39] Rubinov M and Sporns O 2010 Neuroimage 52 1059
[40] Papo D, Buld'u J M and Boccaletti S 2014 Biol. Sci. 369 20130520

[1]	Self-similarity of complex networks under centrality-based node removal strategy Dan Chen(陈单), Defu Cai(蔡德福), and Housheng Su(苏厚胜). Chin. Phys. B, 2023, 32(9): 098903.
[2]	Stability and multistability of synchronization in networks of coupled phase oscillators Yun Zhai(翟云), Xuan Wang(王璇), Jinghua Xiao(肖井华), and Zhigang Zheng(郑志刚). Chin. Phys. B, 2023, 32(6): 060503.
[3]	Identification of key recovering node for spatial networks Zijian Yan(严子健), Yongxiang Xia(夏永祥), Lijun Guo(郭丽君), Lingzhe Zhu(祝令哲), Yuanyuan Liang(梁圆圆), and Haicheng Tu(涂海程). Chin. Phys. B, 2023, 32(6): 068901.
[4]	AG-GATCN: A novel method for predicting essential proteins Peishi Yang(杨培实), Pengli Lu(卢鹏丽), and Teng Zhang(张腾). Chin. Phys. B, 2023, 32(5): 058902.
[5]	Analysis of cut vertex in the control of complex networks Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Chin. Phys. B, 2023, 32(2): 028902.
[6]	SLGC: Identifying influential nodes in complex networks from the perspectives of self-centrality, local centrality, and global centrality Da Ai(艾达), Xin-Long Liu(刘鑫龙), Wen-Zhe Kang(康文哲), Lin-Na Li(李琳娜), Shao-Qing Lü(吕少卿), and Ying Liu(刘颖). Chin. Phys. B, 2023, 32(11): 118902.
[7]	Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Chin. Phys. B, 2023, 32(1): 018903.
[8]	Characteristics of vapor based on complex networks in China Ai-Xia Feng(冯爱霞), Qi-Guang Wang(王启光), Shi-Xuan Zhang(张世轩), Takeshi Enomoto(榎本刚), Zhi-Qiang Gong(龚志强), Ying-Ying Hu(胡莹莹), and Guo-Lin Feng(封国林). Chin. Phys. B, 2022, 31(4): 049201.
[9]	Robust H_∞ state estimation for a class of complex networks with dynamic event-triggered scheme against hybrid attacks Yahan Deng(邓雅瀚), Zhongkai Mo(莫中凯), and Hongqian Lu(陆宏谦). Chin. Phys. B, 2022, 31(2): 020503.
[10]	Fault-tolerant finite-time dynamical consensus of double-integrator multi-agent systems with partial agents subject to synchronous self-sensing function failure Zhi-Hai Wu(吴治海) and Lin-Bo Xie(谢林柏). Chin. Phys. B, 2022, 31(12): 128902.
[11]	Finite-time synchronization of uncertain fractional-order multi-weighted complex networks with external disturbances via adaptive quantized control Hongwei Zhang(张红伟), Ran Cheng(程然), and Dawei Ding(丁大为). Chin. Phys. B, 2022, 31(10): 100504.
[12]	LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks Gui-Qiong Xu(徐桂琼), Lei Meng(孟蕾), Deng-Qin Tu(涂登琴), and Ping-Le Yang(杨平乐). Chin. Phys. B, 2021, 30(8): 088901.
[13]	Detection of influential nodes with multi-scale information Jing-En Wang(王静恩), San-Yang Liu(刘三阳), Ahmed Aljmiai, and Yi-Guang Bai(白艺光). Chin. Phys. B, 2021, 30(8): 088902.
[14]	Complex network perspective on modelling chaotic systems via machine learning Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Chin. Phys. B, 2021, 30(6): 060506.
[15]	Exploring individuals' effective preventive measures against epidemics through reinforcement learning Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni (倪顺江), and Shi-Fei Shen(申世飞). Chin. Phys. B, 2021, 30(4): 048901.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Important edge identification in complex networks based on local and global features

Cite this article:

Online attention