Unsupervised Link Prediction Algorithm Fusing Node Importance

doi:10.3778/j.issn.1002-8331.2105-0425

Abstract

Abstract: Improving the accuracy of weighted network link prediction algorithm is one of the basic problems in the study of complex networks. The common unsupervised prediction methods based on local network structure do not take into account that the nodes are more important, the they are more likely to generate new connections, and nodes with lower centrality are also highly important in real networks. To solve these problems, an unsupervised link prediction algorithm fusing node importance is proposed. In this algorithm, the possibility of new connections is calculated from the perspectives of structural similarity and node importance, and the influence degree is adjusted by using the custom coefficient. Experimental results on five real weighted network datasets show that, in solving the problem of fast prediction of small-scale weighted networks, the algorithm is more accurate than the same type of methods, and the supervised link prediction method is not applicable.

Key words: link prediction, node importance, unsupervised, weighted network

摘要： 提高加权网络链路预测算法精确度是研究复杂网络的基础问题之一。常用的基于局部网络结构的无监督预测方法没有考虑到重要性越高的节点越容易产生新连接，且在真实网络上中心性小的节点同样具有高度重要性。针对上述问题，提出一种融合节点重要性的无监督链路预测算法，从结构相似性和节点重要性两个角度计算新连接产生的可能性，并利用自定义系数调节影响程度。在5个真实加权网络数据集上进行实验，结果表明在解决小规模加权网络的快速预测问题上，该算法相比同类方法的预测精确度更高，有监督式链路预测方法并不适用。

关键词: 链路预测, 节点重要性, 无监督, 加权网络

FU Xinyu, GU Yijun. Unsupervised Link Prediction Algorithm Fusing Node Importance[J]. Computer Engineering and Applications, 2022, 58(16): 94-101.

傅馨玉, 顾益军. 融合节点重要性的无监督链路预测算法[J]. 计算机工程与应用, 2022, 58(16): 94-101.

References

[1] AN C，O’MALLEY A J，ROCKMORE D N.Towards intelligent complex networks：the space and prediction of information walks[J].Applied Network Science，2019，4（1）：1-21.
[2] RAHIMI F，REZAEI H.An event-triggered recursive state estimation approach for time-varying nonlinear complex networks with quantization effects[J].Neurocomputing，2021，426：104-113.
[3] KUMAR R，NOVAK J，TOMKINS A.Structure and evolution of online social networks[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM，2006：611-617.
[4] 李博，陈志刚，黄瑞，等.用于在线社交网络的链路预测好友推荐算法JAFLink[J].小型微型计算机系统，2017，38（8）：1741-1745.
LI B，CHEN Z G，HUANG R，et al.Link prediction friends recommendation algorithm for online social networks named JAFLink[J].Journal of Chinese Computer Systems，2017，38（8）：1741-1745.
[5] IMTIAZ Z B，MANZOOR A，ISLAM S，et al.Discovering communities from disjoint complex networks using multi-layer ant colony optimization[J].Future Generation Computer Systems，2021，115：659-670.
[6] 吕琳媛，周涛.链接预测[M].北京：高等教育出版社，2013.
LV L Y，ZHOU T.Link prediction[M].Beijing：Higher Education Press，2013.
[7] WANG M H，QIU L L，WANG X L.A survey on knowledge graph embeddings for link prediction[J].Symmetry，2021，13（3）：485.
[8] WATTS D J，STROGATZ S H.Collective dynamics of “small-world” networks[J].Nature，1998，393（6684）：440-442.
[9] AARON CLAUSET，CRISTOPHER MOORE，M.E.J.NEWMAN.Hierarchical structure and the prediction of missing links in networks[J].Nature，2008，453（7191）：98-101.
[10] AHMAD Z，RIZOS S.Similarity-based link prediction in social networks using latent relationships between the users[J].Scientific Reports，2020，10：20137.
[11] WANG M X，LOU X Y，CUI B T.A degree-related and link clustering coefficient approach for link prediction in complex networks[J].The European Physical Journal B，2021，94（1）：1-12.
[12] GAO T R，ZHU X Z.Link prediction based on the powerful combination of endpoints and neighbors[J].International Journal of Modern Physics B，2020，34（28）：2050269.
[13] 袁榕，宋玉蓉，孟繁荣.一种基于加权网络拓扑权重的链路预测方法[J].计算机科学，2020，47（5）：265-270.
YUAN R，SONG Y R，MENG F R.A link prediction method based on weighted network topology weight[J].Computer Science，2020，47（5）：265-270.
[14] MA G S，YAN H R，QIAN Y H，et al.Path-based estimation for link prediction[J].International Journal of Machine Learning and Cybernetics，2021，12（9）：2443-2458.
[15] SAMAD A，AZAM M，QADIR M.Structural importance-based link prediction techniques in social network[J].EAI Endorsed Transactions on Industrial Networks and Intelligent Systems，2021，7（25）：167840.
[16] AHMAD I，AKHTAR M U，NOOR S，et al.Missing link prediction using common neighbor and centrality based parameterized algorithm[J].Scientific Reports，2020，10：364.
[17] OU M，CUI P，PEI J，et al.Asymmetric transitivity preserving graph embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM，2016：672-681.
[18] GROVER A，LESKOVEC J.Node2vec：scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM，2016：855-864.
[19] WANG D X，CUI P，ZHU W W.Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM，2016：1225-1234.
[20] LV L Y，ZHOU T.Link prediction in weighted networks：the role of weak ties[J].Europhysics Letters，2010，89（1）：18001.
[21] ZHAO J，MIAO L L，YANG J，et al.Prediction of links and weights in networks by reliable routes[J].Scientific Reports，2015，5：12261.
[22] BAI M，HU K，TANG Y.Link prediction based on a semi-local similarity index[J].Chinese Physics B，2011，20（12）：502-508.
[23] 刘苗苗，郭景峰，罗旭.加权网络中基于多路径节点相似性的链接预测[J].浙江大学学报，2016，50（6）：1140.
LIU M M，GUO J F，LUO X.Link prediction in weighted networks based on multi-path node similarity[J].Journal of Zhejiang University，2016，50（6）：1140.
[24] 白杨，邓贵仕.结合用户互动加权图的社交网络链接预测[J].小型微型计算机系统，2018，39（9）：1988-1992.
BAI Y，DENG G S.Social network link prediction based on weighted graph of user interaction[J].Journal of Chinese Computer Systems，2018，39（9）：1988-1992.
[25] CAO R M，LIU S Y，XU X K.Network embedding for link prediction：the pitfall and improvement[J].Chaos，2019，29（10）：103102.