Link Prediction Algorithm Based on Improved TADW

doi:10.12068/j.issn.1005-3026.2021.11.003

Abstract

Abstract: Aiming at the problem that the classic node similarity link prediction algorithm only considers the network topology or node attribute information， the word embedding model Word2vec to learn the representation of node text attribute information is employed， and then TADW(text-associated deep walk)algorithm for its insufficient ability to express semantic information is improved. Based on the improved TADW graph embedding method， a similarity index which incorporate the topological structure and node attribute information is proposed. Furthermore， the link prediction algorithm is proposed based on this similarity index. Experimental results on three real datasets demonstrate the superiority of the proposed algorithm with better robustness on predicting precision as well as network sparsity solvability.

Key words: TADW(text-associated deep walk)algorithm; attribute information; link prediction; word embedding; Word2vec

CLC Number:

TP391

CHEN Dong-ming， SUN Zheng-ping， YU Kai-shuai， WANG Dong-qi. Link Prediction Algorithm Based on Improved TADW[J]. Journal of Northeastern University(Natural Science), 2021, 42(11): 1533-1539.

References

[1]Lyu L，Zhou T.Link prediction in complex networks:a survey ［J］.Physica A: Statistical Mechanics & Its Applications，2011，390(6):1150-1170.
[2]胡文斌，彭超，梁欢乐，等.基于链路预测的社会网络事件检测方法［J］.软件学报，2015，26(9):2339-2355.(Hu Wen-bin，Peng Chao，Liang Huan-le，et al.Event detection method based on link prediction for social network evolution［J］.Journal of Software，2015，26(9):2339-2355.)
[3]Daminelli S，Thomas J M，Durán C，et al.Common neighbours and the local-community-paradigm for topological link prediction in bipartite networks［J］.New Journal of Physics，2015，17(11):113037.
[4]Lin D.An information-theoretic definition of similarity［J］.Icml，1998，98(1998):296-304.
[5]傅颖斌，陈羽中.基于链路预测的微博用户关系分析［J］.计算机科学，2013，41(2):201-205.(Fu Ying-bin，Chen Yu-zhong.Relationship analysis of microblogging user with link prediction［J］.Computer Science，2013，41(2):201-205.)
[6]许烁娜，曾碧卿.基于Skyline查询的社会网络链接预测［J］.计算机科学，2014，42(1):264-267.(Xu Shuo-na，Zeng Bi-qing.Skyline based link prediction on social networks［J］.Computer Science，2014，42(1):264-267.)
[7]刘冶，朱蔚恒，潘炎，等.基于低秩和稀疏矩阵分解的多源融合链接预测算法［J］.计算机研究与发展，2015，52(2):423-436.(Liu Ye，Zhu Wei-heng，Pan Yan，et al.Multiple sources fusion for link prediction via low-rank and sparse matrix decomposition［J］.Journal of Computer Research and Development，2015，52(2):423-436.)
[8]Yuan G，Murukannaiah P K，Zhang Z，et al.Exploiting sentiment homophily for link prediction［C］// 8th ACM Conference on Recommender Systems.Foster City:ACM，2014:17-24.
[9]Igor R，Maxim Z.The distribution of the maximum number of common neighbors in the random graph［J］.arXiv Preprint arXiv，2018，1804:04430.
[10]Yin D，Hong L，Davison B D.Structural link analysis and prediction in microblogs［C］//Proceedings of the 20th ACM International Conference on Information and Knowledge Management.Glasgow，2011:1163-1168.
[11]黄立威，李德毅，马于涛，等.一种基于元路径的异质信息网络链路预测模型［J］.计算机学报，2014，37(4):848-858.(Huang Li，Li De-yi，Ma Yu-tao，et al.A meta path-based link prediction model for heterogeneous information［J］.Chinese Journal of Computers， 2014，37(4):848-858.)
[12]Popescul A，Ungar L H.Structural logistic regression for link analysis［J］.Departmental Papers(CIS)，2003，133:1-19.
[13]Backstrom L，Leskovec J.Supervised random walks:predicting and recommending links in social networks［C］//Proceedings of the Fourth ACM International Conference on Web Search and Data Mining.Boston，2011:635-644.
[14]Ahmed C，El Korany A.Enhancing link prediction in Twitter using semantic user attributes［C］//2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining(ASONAM).Paris:IEEE，2015:1155-1161.
[15]Getoor L.Link mining:a new data mining challenge［J］.ACM SIGKDD Explorations Newsletter，2003，5(1):84-89.
[16]孙志远，鲁成祥，史忠植，等.深度学习研究与进展［J］.计算机科学，2016，43(2):1-8.(Sun Zhi-yuan，Lu Cheng-xiang，Shi Zhong-zhi，et al.Research and advances on deep learning［J］.Computer Science，2016，43(2):1-8.)
[17]Mikolov T，Sutskever I，Chen K，et al.Distributed representations of words and phrases and their compositionality［J］.Advances in Neural Information Processing Systems，2013，26:3111-3119.
[18]Perozzi B，Al-Rfou R，Skiena S.Deepwalk:online learning of social representations［C］//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM，2014:701-710.
[19]Yang C，Liu Z，Zhao D，et al.Network representation learning with rich text information［C］//Twenty-Fourth International Joint Conference on Artificial Intelligence.Buenos，2015:2111-2117.
[20]DBLP.Dblp dataset［DB/OL］.(2020-03-26)［2019-11-22］.https://dblp.uni-trier.de/xml/.
[21]Cora.Cora datasets［DB/OL］.(2020-03-26)［2015-01-01］.https://linqs.soe.ucsc.edu/data/.
[22]CiteSeer.CiteSeer dataset(2020-03-26)［2015-01-01］.https://linqs.soe.ucsc.edu/data/.
[23]吕琳媛.复杂网络链路预测［J］.电子科技大学学报，2010，39(5):651-661.(Lyu Lin-yuan.Link prediction on complex networks ［J］.Journal of University of Electronic Science and Technology of China，2010，39(5):651-661.)