Identification Methods of Vital Nodes Based on K-shell in Hypernetworks
ZHOU Lina, LI Faxu, GONG Yunchao, HU Feng
a. Computer College, Xining 810008, China; b. Tibetan Information Processing and Machine Translation Key Laboratory of Qinghai Province, Xining 810008, China; c. The State Key Laboratory of Tibetan Intelligent Information Processing and Application, Qinghai Normal University, Xining 810008, China
Abstract：In this paper, the K-shell index is extended to the hypernetwork to avoid the influence of the nodes with larger hyperdegree but located at the edge of the hypernetwork on the mining of vital nodes. Due to the limitation of K-shell method, the result of node sorting is too rough. In order to solve this problem, this paper proposes a kds (complex K-shell and degree) index to identify the vital nodes of the hypernetwork by combining the hyperdegree and K-shell (ks) value and using the Euclidean distance formula, and verifies it by using the protein complex hypernetwork. Experiments show that kds index can accurately and effectively identify the vital nodes in the hypernetwork.
周丽娜, 李发旭, 巩云超, 胡枫. 基于K-shell的超网络关键节点识别方法[J]. 复杂系统与复杂性科学, 2021, 18(3): 15-22.
ZHOU Lina, LI Faxu, GONG Yunchao, HU Feng. Identification Methods of Vital Nodes Based on K-shell in Hypernetworks. Complex Systems and Complexity Science, 2021, 18(3): 15-22.
[1] Lü L, Chen D, Ren X, et al. Vital nodes identification in complex networks[J]. Physics Reports, 2016, 650: 1-63. [2] 任晓龙,吕琳媛.网络重要节点排序方法综述[J].科学通报, 2014, 59(13): 1175-1197. Ren Xiaolong, Lü Linyuan. Review of ranking nodes in complex networks[J]. Chinese Science Bulletin, 2014, 59(13): 1175-1197. [3] 刘建国,任卓明,郭强,等.复杂网络中节点重要性排序的研究进展[J].物理学报, 2013, 62(17): 9-18. Liu Jianguo, Ren Zhuoming, Guo Qiang, et al. Comprehensive survey for the frontier disciplines node importance ranking of complex networks[J]. Acta Physica Sinica, 2013, 62(17): 9-18. [4] 陈诗,任卓明,刘闯,等.时序网络中关键节点的识别方法研究进展[J].电子科技大学学报,2020,49(2):291-314. Chen Shi, Ren Zhuoming, Liu Chuang, et al. Identification methods of vital nodes on temporal networks[J].Journal of University of Electronic Science and Technology of China, 2020,49(2):291-314. [5] Keeling M J, Rohani P, Pourbohloul B. Modeling infectious diseases in humans and animals[J]. Clinical Infectious Diseases, 2008, 47(6):864-865. [6] Moreno Y, NeKovee M, Pacheco A F. Dynamics of rumor spreading in complex networks[J]. Physical Review E, 2004, 69(6): 066130. [7] Albert R, Nakarado G L. Structural vulnerability of the north American power grid[J]. Physical Review E,2004,69(2), 025103. [8] Newman M E J. The structure and function of complex network[DB/OL]. (2003-03-25)[2020-03-20].https:∥arXiv.org/abs/cond-mat/0303516. [9] Dorogovtsev S N, Mendes J F F. Evolution of networks[J]. Advances in Physics, 2002, 51(4):1079-1187. [10] Strogatz S H. Exploring complex networks[J]. Nature, 2001,410(6825): 268-276. [11] 吕琳媛,陆君安,张子柯,等.复杂网络观察[J].复杂系统与复杂性科学,2010, 7(1): 173-186. Lü Linyuan, Lu Junan, Zhang Zike, et al. Looking into complex networks[J].Complex Systems and Complexity Science, 2010, 7(1): 173-186. [12] Lü L, Zhou T, Zhang Q M, et al. The H-index of a network node and its relation to degree and coreness[J]. Nature Communications, 2016, 7: 10168. [13] Li Z, Ren T, Ma X Q, et al. Identifying influential spreaders by gravity model[J]. Scientific Reports, 2019, 9: 8387. [14] 卢鹏丽,郭旭东,董璊,等.基于介度熵的复杂网络节点重要度识别方法[J].兰州理工大学学报,2020,46(2):111-115. Lu Pengli, Guo Xudong, Dong Men, et al. Importance identification method of complex network nodes based on betweenness and degree entropy[J]. Journal of Lanzhou University of Technology, 2020,46(2):111-115. [15] 李亚飞,梁琛,戴福青.航路网关键节点识别及抗毁性分析[J].中国安全科学学报,2020, 30(5) : 115-121. Li Yafei, Liang Chen, Dai Fuqing. Key node identification and invulnerability analysis of China’s air route network[J]. China Safety Science Journal, 2020, 30(5) : 115-121. [16] Kistak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893. [17] Zeng A, Zhang C J. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013, 377(14): 1031-1035. [18] 王凯莉,邬春学,艾均,等.基于多阶邻居壳数的向量中心性度量方法[J].物理学报,2019,68(19):235-245. Wang Kaili, Wu Chunxue, Ai Jun, et al. Complex network centrality method based on multi-order K-shell vector[J]. Acta Physica Sinica, 2019, 68(19):235-245. [19] Yu Y, Jing M, Zhao N, et al. Lowest degree decomposition of complex networks[DB/OL].[2020-01-15].http:∥arXiv:2002.05358. [20] 黄丽亚,汤平川,霍宥良,等.基于加权K-阶传播数的节点重要性[J].物理学报, 2019, 68(12): 128901. Huang Liya, Tang Pingchuan, Huo Youliang, et al. Node importance based on the weighted K-order propagation number algorithm[J]. Acta Physica Sinica, 2019, 68(12): 128901. [21] Neubauer N, Obermayer K. Hyperincident connected components of tagging networks[C].Proceedings of the 20th ACM Conference on Hypertext and Hypermedia. New York: ACM Press, 2009: 229-238. [22] Estrada E, Rodríguez-Velázquez J A. Subgraph centrality and clustering in complex hyper-networks[J]. Physica A, 2006, 364: 581-594. [23] 王志平,王众托.超网络理论及其应用[M]. 北京: 科学出版社,2008: 206-222. [24] Liu J G, Yang G Y, Hu Z L. A knowledge generation model via the hypernetwork[J]. PLoS One, 2014, 9(3): e89746. [25] 胡枫,赵海兴,马秀娟.一种超网络模型构建及特性分析[J].中国科学:物理学 力学 天文学,2013, 43(1): 16-22. Hu Feng, Zhao Haixing, Ma Xiujuan. An evolving hypernetwork model and its properties[J]. Chinese Science: Physica,Mechanica＆Astronomica, 2013, 43(1): 16-22. [26] 郭进利,祝昕昀.超网络中标度律的涌现[J].物理学报,2014, 63(9):55-61. Guo Jinli, Zhu Xinyun. Emergence of scaling in hypernetworks[J]. Acta Physica Sinica, 2014, 63(9):55-61. [27] 胡枫,刘猛,赵静,等.蛋白复合物超网络特性分析及应用[J].复杂系统与复杂性科学,2018,15(4):31-38. Hu Feng, Liu Meng, Zhao Jing, et al. Analysis and application of the topological properties of protein complex hypernetworks[J].Complex Systems and Complexity Science,2018,15(4):31-38. [28] 王雨,郭进利. 超网络视角下的科研合作网络节点重要性评估[J].图书馆杂志, 2018,37(10):91-102. Wang Yu, Guo Jinli. The evaluation of node importance within the scientific collaboration network from hypernetwork perspective[J]. Library Journal, 2018, 37(10):91-102. [29] 单而芳,蔡蕾,曾晗,等.超网络中心性度量的υ-Position值方法[J].运筹与管理,2020,29(5):135-142. Shan Erfang, Cai Lei, Zeng Han, et al. The υ-position value measure on centrality of hypernetworks[J].Operations Research and Management Science, 2020, 29(5):135-142. [30] 孙琳,郭进利.基于超网络视角对上海轨道交通网络的研究[J].物流科技,2015,38(4):15-19. Sun Lin, Guo Jinli. Study of Shanghai rail transit network based on the hypernetwork[J]. Logistics Management, 2015, 38(4): 15-19. [31] Nagurney A, Dong J. Supernetworks: decision-making for the information age[M]. Cheltenham: Edward Elgar Publishing, 2002. [32] Berge C. Graphs and Hypergraphs [M]. New York: Elsevier,1973. [33] Ruepp A, Waegele B, Lechneet M, et al. CORUM: the comprehensive resource of mammalian protein complexes-2009[J]. Nucleic Acids Research, 2009, 38: D497-D501. [34] Hahn M W,Kern A D.Comparative genomics of centrality and essentiality in three eukaryotic protein-interaction networks[J]. Molecular Biology & Evolution, 2005(4): 803-806. [35] Jeong H, Mason S P, Barabasi A L, et al. Lethality and centrality in protein networks[J]. Nature, 2001, 411(6833): 41-42. [36] Kim P M , Korbel J O , Gerstein M B . Positive selection at the protein network periphery: evaluation in terms of structural constraints and cellular context[J]. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(51):20274-20279. [37] Chen W H, Minguez P, Lerecher M J, et al. OGEE: an online gene essentially database[J]. Nucleic Acids Research, 2011, 40: 901-906.
