Link prediction algorithm based on clustering coefficient and node centrality

doi:10.16511/j.cnki.qhdxxb.2021.21.039

Abstract
Figures/Tables
References
Related Articles
Metrics

Download: PDF(1747 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords complex network link prediction clustering coefficient node centrality

Issue Date: 14 January 2022

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

	YU Yong
	WANG Yinggang
	LUO Zhengguo
	YANG Yan
	WANG Xinkai
	GAO Tao
	YU Qian

Cite this article:

YU Yong,WANG Yinggang,LUO Zhengguo, et al. Link prediction algorithm based on clustering coefficient and node centrality[J]. Journal of Tsinghua University(Science and Technology), 2022, 62(1): 98-104.

URL:

http://jst.tsinghuajournals.com/EN/10.16511/j.cnki.qhdxxb.2021.21.039 OR http://jst.tsinghuajournals.com/EN/Y2022/V62/I1/98

[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.

[1]	LI Ziyuan, SUN Hao, LI Linbo. Analysis of intercity travel in the Yangtze River Delta based on mobile signaling data[J]. Journal of Tsinghua University(Science and Technology), 2022, 62(7): 1203-1211.
[2]	XIE Lixia, SUN Honghong, YANG Hongyu, ZHANG Liang. Key node recognition in complex networks based on the K-shell method[J]. Journal of Tsinghua University(Science and Technology), 2022, 62(5): 849-861.
[3]	DING Ying, ZHANG Jianqin, YANG Mu, GONG Peng, JIA Lipeng, DENG Shaocun. Communicable disease transmission model for the prevention and control of COVID-19 in Wuhan City, China[J]. Journal of Tsinghua University(Science and Technology), 2021, 61(12): 1452-1461.
[4]	WANG Zhiru, SU Guofeng, LIANG Zuolun. Information transfer efficiency based small-world assessment methodology for metro networks[J]. Journal of Tsinghua University(Science and Technology), 2016, 56(4): 411-416.
[5]	NI Shunjiang, WENG Wenguo, ZHANG Hui. Simulation of strategies for large-scale spread containment of infectious diseases[J]. Journal of Tsinghua University(Science and Technology), 2016, 56(1): 97-101.

Viewed

Full text

Abstract

Cited

Shared

Discussed