Identifying Critical Nodes of Collaboration Networks Based on Improved K-shell Decomposition
Zhang Dayong1(),Men Hao2,Su Zhan1
1Key Laboratory of Interactive Media Design and Equipment Service Innovation, Harbin Institute of Technology, Harbin 150001, China 2Faculty of Computing, Harbin Institute of Technology, Harbin 150001, China
[Objective] This paper proposes an improved K-shell decomposition algorithm based on semi-local centrality, aiming to address the degradation issue of critical nodes identification. [Methods] First, we constructed a semi-local centrality index based on the nodes’ first-order neighbor information. Then, we determined the final key node set by recursive removal, with the semi-local information of the remaining and removed nodes. [Results] We examined our algorithm with six groups of cooperative networks. It could effectively eliminate the degradation issue of the original algorithm with high computational accuracy and low computational complexity. [Limitations] Due to the influence of network structures, the calculation accuracy of some sample networks was lower than that of the betweenness centrality algorithm. [Conclusions] The new algorithm can improve the stability of the collaboration network and identify key node sets in large-scale practical networks.
张大勇, 门浩, 苏展. 一种基于改进K核分解的合作网络关键节点集识别方法*[J]. 数据分析与知识发现, 2024, 8(5): 80-90.
Zhang Dayong, Men Hao, Su Zhan. Identifying Critical Nodes of Collaboration Networks Based on Improved K-shell Decomposition. Data Analysis and Knowledge Discovery, 2024, 8(5): 80-90.
Zhai L, Yan X B. A Directed Collaboration Network for Exploring the Order of Scientific Collaboration[J]. Journal of Informetrics, 2022, 16(4): Article No.101345.
[2]
Nakata C, Im S. Spurring Cross-Functional Integration for Higher New Product Performance: A Group Effectiveness Perspective[J]. Journal of Product Innovation Management, 2010, 27(4): 554-571.
[3]
Quintane E, Pattison P E, Robins G L, et al. Short- and Long-Term Stability in Organizational Networks: Temporal Structures of Project Teams[J]. Social Networks, 2013, 35(4): 528-540.
(He Chaocheng, Wu Jiang, Liu Fuzhen, et al. Identifying Key Nodes via a Geographical Research Dominance Network: A Case Study of the Pharmaceutical Field[J]. Journal of the China Society for Scientific and Technical Information, 2021, 40(12): 1312-1324.)
(Cui Fang, Sun Xiaoming, Xiong Wang, et al. The Research on the Impact of the Ego-Network’s Changes from the Key Inventors to the Innovation Performance: The Whole Network as an Intermediary Variable[J]. Science & Technology Progress and Policy, 2017, 34(17): 80-90.)
[6]
Lü L Y, Chen D B, Ren X L, et al. Vital Nodes Identification in Complex Networks[J]. Physics Reports, 2016, 650: 1-63.
(Ren Xiaolong, Lü Linyuan. Review of Ranking Nodes in Complex Networks[J]. Chinese Science Bulletin, 2014, 59(13): 1175-1197.)
[8]
Moody J. The Structure of a Social Science Collaboration Network: Disciplinary Cohesion from 1963 to 1999[J]. American Sociological Review, 2004, 69(2): 213-238.
[9]
Pinto P E, Vallone A, Honores G. The Structure of Collaboration Networks: Findings from Three Decades of Co-Invention Patents in Chile[J]. Journal of Informetrics, 2019, 13(4): Article No.100984.
[10]
Kitsak M, Gallos L K, Havlin S, et al. Identification of Influential Spreaders in Complex Networks[J]. Nature Physics, 2010, 6: 888-893.
[11]
Freeman L C. Centrality in Social Networks Conceptual Clarification[J]. Social Networks, 1978, 1(3): 215-239.
[12]
Newman M E J. The Structure and Function of Complex Networks[J]. SIAM Review, 2003, 45(2): 167-256.
[13]
Wang S B, Zhao J L. Multi-Attribute Integrated Measurement of Node Importance in Complex Networks[J]. Chaos, 2015, 25(11): Article No.113105.
[14]
Zhao J, Wang Y C, Deng Y. Identifying Influential Nodes in Complex Networks from Global Perspective[J]. Chaos, Solitons & Fractals, 2020, 133: Article No.109637.
[15]
Buldyrev S V, Parshani R, Paul G, et al. Catastrophic Cascade of Failures in Interdependent Networks[J]. Nature, 2010, 464: 1025-1028.
[16]
Rossa F D, Pecora L, Blaha K, et al. Symmetries and Cluster Synchronization in Multilayer Networks[J]. Nature Communications, 2020, 11: Article No.3179.
[17]
Peng K Y, Lu Z, Lin V, et al. A Multilayer Network Model of the Coevolution of the Spread of a Disease and Competing Opinions[J]. Mathematical Models and Methods in Applied Sciences, 2021, 31(12): 2455-2494.
(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.)
[19]
Chen D B, Lü L Y, Shang M S, et al. Identifying Influential Nodes in Complex Networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012, 391(4): 1777-1787.
[20]
Liu F C, Zhang N, Cao C. An Evolutionary Process of Global Nanotechnology Collaboration: A Social Network Analysis of Patents at USPTO[J]. Scientometrics, 2017, 111(3): 1449-1465.
[21]
Brin S, Page L. The Anatomy of a Large-Scale Hypertextual Web Search Engine[J]. Computer Networks and ISDN Systems, 1998, 30(1-7): 107-117.
[22]
Kleinberg J M. Authoritative Sources in a Hyperlinked Environment[J]. Journal of the ACM, 1999, 46(5): 604-632.
[23]
Xu S, Wang P. Identifying Important Nodes by Adaptive LeaderRank[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 469: 654-664.
(Xiong Huixiang, Du Jin, Dai Qinquan, et al. Scholars Academic Influence Evaluation Research Based on Topics and Multi-Dimensional Metrics[J]. Information Studies: Theory & Application, 2021, 44(8): 22-27.)
doi: 10.16353/j.cnki.1000-7490.2021.08.004
[25]
Chen B L, Jiang W X, Chen Y X, et al. Influence Blocking Maximization on Networks: Models, Methods and Applications[J]. Physics Reports, 2022, 976: 1-54.
[26]
Kempe D, Kleinberg J, Tardos É. Maximizing the Spread of Influence Through a Social Network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003: 137-146.
[27]
Mugisha S, Zhou H J. Identifying Optimal Targets of Network Attack by Belief Propagation[J]. Physical Review E, 2016, 94(1): 12305.
[28]
Yu S B, Zeng Y F, Pan Y H, et al. Discovering a Cohesive Football Team Through Players’ Attributed Collaboration Networks[J]. Applied Intelligence, 2023, 53(11): 13506-13526.
[29]
Liu X Y, Ye S, Fiumara G, et al. Influential Spreaders Identification in Complex Networks with TOPSIS and K-Shell Decomposition[J]. IEEE Transactions on Computational Social Systems, 2023, 10(1): 347-361.
[30]
Maji G, Namtirtha A, Dutta A, et al. Influential Spreaders Identification in Complex Networks with Improved K-Shell Hybrid Method[J]. Expert Systems with Applications, 2020, 144: Article No.113092.
[31]
Zeng A, Zhang C J. Ranking Spreaders by Decomposing Complex Networks[J]. Physics Letters A, 2013, 377(14): 1031-1035.
(Yang Qing, Zheng Lu, Zou Xingqi. Risk Analysis of Complex R&D Projects Based on Risk Propagation Network and K-Shell Method[J]. Management Review, 2021, 33(9): 119-127.)
[33]
Zachary W W. An Information Flow Model for Conflict and Fission in Small Groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[34]
Hage P, Harary F. Structural Models in Anthropology[M]. Cambridge: Cambridge University Press, 1983: 56-60.
[35]
Albert R, Jeong H, Barabási A L. Error and Attack Tolerance of Complex Networks[J]. Nature, 2000, 406: 378-382.
[36]
Crucitti P, Latora V, Marchiori M, et al. Error and Attack Tolerance of Complex Networks[J]. Physica A: Statistical Mechanics and Its Applications, 2004, 340(1-3): 388-394.
[37]
Schneider C M, Moreira A A, Andrade J S, et al. Mitigation of Malicious Attacks on Networks[J]. PNAS, 2011, 108(10): 3838-3841.
doi: 10.1073/pnas.1009440108
pmid: 21368159
(Han Zhongming, Chen Yan, Li Mengqi, et al. An Efficient Node Influence Metric Based on Triangle in Complex Networks[J]. Acta Physica Sinica, 2016, 65(16): 289-300.)
[39]
Bae J, Kim S. Identifying and Ranking Influential Spreaders in Complex Networks by Neighborhood Coreness[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 395: 549-559.
[40]
Gleiser P M, Danon L. Community Structure in Jazz[J]. Advances in Complex Systems, 2003, 6(4): 565-573.
