Link prediction algorithm based on clustering coefficient and node centrality
YU Yong1,3, WANG Yinggang1, LUO Zhengguo1, YANG Yan1, WANG Xinkai1, GAO Tao2, YU Qian1,3
1. School of Software, Yunnan University, Kunming 650091, China; 2. School of Education, Yunnan University of Business Management, Kunming 650033, China; 3. Key Laboratory in Software Engineering of Yunnan Province, Kunming 650091, China
Abstract：Currently, more people are becoming interested in the field of complex networks. Link prediction is a popular subdiscipline in complex networks and is used to predict missing links and identify false links. The traditional similarity-based complex network link prediction focuses on a particular similarity index of each node. This paper proposes the link prediction algorithm based on clustering coefficient and node centrality (CCNC), which combines the degree index, clustering coefficient index, and proximity centrality index into the link prediction of a complex network. This algorithm considers local information using clustering coefficient and degree by introducing proximity centrality to consider the importance of nodes in the network. Finally, using six real networks as examples, the feasibility and effectiveness of the CCNC algorithm are verified by comparing the AUC and the precision values.
郁湧, 王莹港, 罗正国, 杨燕, 王鑫锴, 高涛, 于倩. 基于聚类系数和节点中心性的链路预测算法[J]. 清华大学学报（自然科学版）, 2022, 62(1): 98-104.
YU Yong, WANG Yinggang, LUO Zhengguo, YANG Yan, WANG Xinkai, GAO Tao, YU Qian. Link prediction algorithm based on clustering coefficient and node centrality. Journal of Tsinghua University(Science and Technology), 2022, 62(1): 98-104.
[1] GARCÍA-PÉREZ G, ALIAKBARISANI R, GHASEMI A, et al. Predictability of missing links in complex networks[Z/OL]. (2019-01-31)[2021-04-30]. https://arxiv.org/abs/1902.00035. [2] FARASHAH M V, ETEBARIAN A, AZMI R, et al. A hybrid recommender system based-on link predictionfor movie baskets analysis[J]. Journal of Big Data, 2021, 8(1):32. [3] SAXENA A, FLETCHER G, PECHENIZKIY M. Nodesim:Node similarity based network embedding for diverse link prediction[Z/OL]. (2021-02-01)[2021-04-30]. https://arxiv.org/abs/2102.00785. [4] ZHOU Y Z, WU C C, TAN L L. Biased random walk with restart for link prediction with graph embedding method[J]. Physica A:Statistical Mechanics and its Applications, 2021, 570:125783. [5] YANG X H, YANG X H, LING F, et al. Link prediction based on local major path degree[J]. Modern Physics Letters B, 2018, 32(29):1850348. [6] XU Z Q, PU C L, YANG J. Link prediction based on pathentropy[J]. Physica A:Statistical Mechanics and its Applications, 2016, 456:294-301. [7] CHEN X, JIAO P F, YU Y D, et al. Toward link predictability of bipartite networks based on structural enhancement and structural perturbation[J]. Physica A:Statistical Mechanics and its Applications, 2019, 527:121072. [8] LÜ L Y, PAN L M, ZHOU T, et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences, 2015, 112(8):2325-2330. [9] 陈嘉颖, 于炯, 杨兴耀, 等. 基于复杂网络节点重要性的链路预测算法[J]. 计算机应用, 2016, 36(12):3251-3255, 3268. CHEN J Y, YU J, YANG X Y, et al. Link prediction algorithm based on node importance in complex networks[J]. Journal of Computer Applications, 2016, 36(12):3251-3255, 3268. (in Chinese) [10] 贾承丰, 韩华, 吕亚楠, 等. 基于Word2vec和粒子群的链路预测算法[J]. 自动化学报, 2020, 46(8):1703-1713. JIA C F, HAN H, LÜ Y N, et al. Link prediction algorithm based on word2vec and particle swarm[J]. Acta Automatica Sinica, 2020, 46(8):1703-1713. (in Chinese) [11] 杨旭华, 俞佳, 张端. 基于局部社团和节点相关性的链路预测算法[J]. 计算机科学, 2019, 46(1):155-161. YANG X H, YU J, ZHANG D. Link predictionmethod based on local community and nodes' relativity[J]. Computer Science, 2019, 46(1):155-161. (in Chinese) [12] SUN Q, HU R, YANG Z, et al. An improved link prediction algorithm based on degrees and similarities ofnodes[C]//2017 IEEE/ACIS 16th International Conference on Computer and Information Science (ICIS). Wuhan, China:IEEE, 2017:13-18. [13] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684):440-442. [14] RAPOPORT A. Spread of information through a population with socio-structural bias:I. Assumption of transitivity[J]. The Bulletin of Bathematical Biophysics, 1953, 15(4):523-533. [15] ADAMIC L A, ADAR E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3):211-230. [16] ZHOU T, LÜ L Y, ZHANG Y C. Predicting missing links via local information[J]. The European Physical Journal B, 2009, 71(4):623-630. [17] LIBEN-NOWELL D, KLEINBERG J. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology, 2007, 58(7):1019-1031. [18] JACCARD P. Étude comparative de la distribution florale dans une portion des alpes et des jura[J]. Bulletinde la Societe Vaudoise des Sciences Naturelles, 1901, 37(142):547-579. [19] 高杨, 张燕平, 钱付兰, 等. 结合节点度和节点聚类系数的链路预测算法[J]. 小型微型计算机系统, 2017, 38(7):1436-1441. GAO Y, ZHANG Y P, QIAN F L, et al. Combined with node degree and node clustering coefficient of link prediction algorithm[J]. Journal of Chinese Computer Systems, 2017, 38(7):1436-1441. (in Chinese) [20] 陈紫扬, 张月霞. 结合二层节点度和聚类系数的链路预测算法[J]. 计算机工程与应用, 2019, 55(23):40-44. CHEN Z Y, ZHANG Y X. Link prediction algorithm combining two-layer node degree and clustering coefficient[J]. Computer Engineering and Applications, 2019,55(23):40-44. (in Chinese) [21] KOVÁCS I A, LUCK K, SPIROHN K, et al. Network-based prediction of protein interactions[J]. Nature Communications, 2019, 10(1):1240. [22] MUMIN D, SHI L L, LIU L. An efficient algorithm for link prediction based on local information:Considering the effect of node degree[C]//2019 15th International Conference on Semantics, Knowledge and Grids (SKG). Guangzhou, China:IEEE, 2019:131-138. [23] 白桦, 马云龙, 毕玉, 等. 一种基于节点局部相似性的复杂网络链路预测算法[J]. 计算机应用与软件, 2020, 37(5):298-301, 308. BAI H, MA Y L, BI Y, et al. A complicated network link prediction algorithm based on local similarity of nodes[J]. Computer Applications and Software, 2020, 37(5):298-301, 308. (in Chinese) [24] HANLEY J A, MCNEIL B J. The meaning and use of the area under a receiver operating characteristic (ROC) curve[J]. Radiology, 1982, 143(1):29-36. [25] HERLOCKER J L, KONSTAN J A, TERVEEN L G, et al. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems (TOIS), 2004, 22(1):5-53.
2022, Vol. 62 
