Please wait a minute...
Data Analysis and Knowledge Discovery  2024, Vol. 8 Issue (5): 80-90    DOI: 10.11925/infotech.2096-3467.2023.0485
Current Issue | Archive | Adv Search |
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
Download: PDF (2295 KB)   HTML ( 10 ) 
Export: BibTeX | EndNote (RIS)      
Abstract  

[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.
Key words： Collaboration Network      Decomposition Algorithm      Critical Nodes      Computational Complexity     
Received: 22 May 2023      Published: 15 March 2024
ZTFLH:  TP393  
  G203  
Fund:National Social Science Fund of China(21BDJ062);Emerging Interdisciplinary Innovation Program of Harbin Institute of Technology(SYL-JC-202203)
Corresponding Authors: Zhang Dayong， ORCID：0000-0001-9122-2220， E-mail： yongzhhit@163.com。   
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Dayong Zhang
Hao Men
Zhan Su

Cite this article:

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.

URL:

https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.2096-3467.2023.0485     OR     https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/Y2024/V8/I5/80

The Computational Procedure of K-shell and IKs
Network n m <k> L LCC C β t h
AstroPh 18 772 198 110 21.107 4.194 17 903 0.677 0.015
CondMat 23 133 93 497 8.083 5.352 21 363 0.706 0.045
CA-GrQc 5 242 14 496 5.531 6.049 4 158 0.687 0.059
HepTh 9 877 25 998 5.264 5.945 8 638 0.600 0.079
NetScience 1 589 2 742 3.451 5.823 379 0.878 0.144
Jazz 198 2 742 27.697 2.235 198 0.633 0.026
The Basic Structure of Six Collaboration Networks
Propagation Results Between IKs Algorithm and Three Representative Algorithms on the Real Networks
The Network Vulnerability Index and the Largest Connected Component Under Different Attack Strategies
[1] 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.
[4] 贺超城, 吴江, 刘福珍, 等. 基于地理科研主导网络的关键节点识别研究——以药学领域为例[J]. 情报学报, 2021, 40(12): 1312-1324.
[4] (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.)
[5] 崔芳, 孙笑明, 熊旺, 等. 关键研发者自我中心网络变化对企业创新绩效的影响: 以整体网络为中介变量[J]. 科技进步与对策, 2017, 34(17): 80-90.
[5] (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.
[7] 任晓龙, 吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 2014, 59(13): 1175-1197.
[7] (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.
[18] 陈诗, 任卓明, 刘闯, 等. 时序网络中关键节点的识别方法研究进展[J]. 电子科技大学学报, 2020, 49(2): 291-314.
[18] (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.
[24] 熊回香, 杜瑾, 代沁泉, 等. 基于主题与多维计量指标的学者学术影响力评价研究[J]. 情报理论与实践, 2021, 44(8): 22-27.
doi: 10.16353/j.cnki.1000-7490.2021.08.004
[24] (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.
[32] 杨青, 郑璐, 邹星琪. 基于风险传播网络和K-Shell方法的复杂研发项目风险评价[J]. 管理评论, 2021, 33(9): 119-127.
[32] (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
[38] 韩忠明, 陈炎, 李梦琪, 等. 一种有效的基于三角结构的复杂网络节点影响力度量模型[J]. 物理学报, 2016, 65(16): 289-300.
[38] (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.
[1] Lu Yunmeng,Liu Tiezhong. Diffusion Model for Tacit Knowledge of Scientific Cooperation Network Based on Relevance: Case Study of Major Sci-Tech Projects[J]. 数据分析与知识发现, 2021, 5(9): 10-20.
[2] Yanshuang Mei,Hengmin Zhu,Jing Wei. A Study on the Mechanism of Media Collaboration on the Spread of Internet Public Opinion[J]. 数据分析与知识发现, 2019, 3(2): 65-71.
[3] Chen Yunwei,Zhang Ruihong. Comparing on Community Detection Algorithms for Information Mining[J]. 数据分析与知识发现, 2018, 2(10): 84-94.
[4] Yu Chuanming,Gong Yutian,Zhao Xiaoli,An Lu. Collaboration Recommendation of Finance Research Based on Multi-feature Fusion[J]. 数据分析与知识发现, 2017, 1(8): 39-47.
[5] Lv Weimin,Wang Xiaomei,Han Tao. Recommending Scientific Research Collaborators with Link Prediction and Extremely Randomized Trees Algorithm[J]. 数据分析与知识发现, 2017, 1(4): 38-45.
[6] Zhang Yongyun, Zhang Shengtai. Star Effect and Broker Effect in Social Media Knowledge Collaboration Network: Discovery from Wikipedia Social Media[J]. 现代图书情报技术, 2015, 31(4): 72-78.
[7] Li Shengqing, Cai Guoyong. Study on Network Evolution and Knowledge Dissemination of Scientific Collaboration Network in the Field of Complex Networks[J]. 现代图书情报技术, 2013, (5): 64-72.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626，82624938   E-mail:jishu@mail.las.ac.cn