Link prediction algorithm based on network representation learning and random walk

doi:10.11772/j.issn.1001-9081.2017.08.2234

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (8): 2234-2239.DOI: 10.11772/j.issn.1001-9081.2017.08.2234

Previous Articles Next Articles

Link prediction algorithm based on network representation learning and random walk

LIU Si¹, LIU Hai^1,2, CHEN Qimai¹, HE Chaobo³

1. School of Computer, South China Normal University, Guangzhou Guangdong 510631, China;
2. Guangdong Provincial Key Laboratory of High Performance Computing, Guangzhou Guangdong 510033, China;
3. School of Information Science and Technology, Zhongkai University of Agriculture and Engineering, Guangzhou Guangdong 510225, China

Received:2016-12-29 Revised:2017-02-09 Online:2017-08-10 Published:2017-08-12
Supported by:
This work is partially supported by the Natural Science Foundation of Guangdong Province (2016A030313441),the Science and Technology Planning Project of Guangdong Province (2015B010129009,2016A030303058,2016A090922008,2015A020209178),the Open Project Program of Guangdong Provincial Key Laboratory of High Performance Computing (T191527),the Science and Technology Program of Guangzhou (201604016035).

基于网络表示学习与随机游走的链路预测算法

刘思¹, 刘海^1,2, 陈启买¹, 贺超波³

1. 华南师范大学计算机学院, 广州 510631;
2. 广东省高性能计算重点实验室, 广州 510033;
3. 仲恺农业工程学院信息科学与技术学院, 广州 510225

通讯作者: 刘海
作者简介:刘思(1992-),男,江西丰城人,硕士研究生,CCF会员,主要研究方向:数据挖掘、大数据处理;刘海(1974-),男,湖南张家界人,副教授,博士,CCF会员,主要研究方向:文本挖掘、深度学习;陈启买(1965-),男,湖南衡阳人,教授,硕士,主要研究方向:数据挖掘、机器学习;贺超波(1981-),男,广东河源人,副教授,博士,CCF高级会员,主要研究方向:数据挖掘、社会计算。
基金资助:
广东省自然科学基金自由申请项目（2016A030313441）；广东省科技计划项目（2015B010129009，2016A030303058，2016A090922008，2015A020209178）；广东省高性能计算重点实验室开放课题项目（T191527）；广州市科技计划项目（201604016035）。

Abstract

Abstract: The transition process of existing link prediction indexes based on random walk exists strong randomness in the unweighted network and does not consider the effect of the similarity of the network structure between different neighbor nodes on transition probability. In order to solve the problems, a new link prediction algorithm based on network representation learning and random walk was proposed. Firstly, the latent structure features of network node were learnt by DeepWalk which is a network representation learning algorithm based on deep learning, and the network nodes were encoded into low-dimensional vector space. Secondly, the similarity between neighbor nodes in vector space was incorporated into the transition process of Random Walk with Restart (RWR) and Local Random Walk (LRW) respectively and the transition probability of each random walk was redefined. Finally, a large number of experiments on five real datasets were carried out. The experimental results show that the AUC (Area Under the receiver operating characteristic Curve) values of the proposed algorithms are improved up to 3.34% compared with eight representative link prediction benchmarks based on network structure.

Key words: link prediction, similarity, Random Walk with Restart (RWR), Local Random Walk (LRW), network representation learning

摘要： 现有的基于随机游走链路预测指标在无权网络上的转移过程存在较强随机性，没有考虑在网络结构上不同邻居节点间的相似性对转移概率的作用。针对此问题，提出一种基于网络表示学习与随机游走的链路预测算法。首先，通过基于深度学习的网络表示学习算法——DeepWalk学习网络节点的潜在结构特征，将网络中的各节点表征到低维向量空间；然后，在重启随机游走（RWR）和局部随机游走（LRW）算法的随机游走过程中融合各邻居节点在向量空间上的相似性，重新定义出邻居节点间的转移概率；最后，在5个真实数据集上进行大量实验验证。实验结果表明：相比8种具有代表性的基于网络结构的链路预测基准算法，所提算法链路预测结果的AUC值均有提升，最高达3.34%。

关键词: 链路预测, 相似性, 重启随机游走, 局部随机游走, 网络表示学习

CLC Number:

TP391
TP18

LIU Si, LIU Hai, CHEN Qimai, HE Chaobo. Link prediction algorithm based on network representation learning and random walk[J]. Journal of Computer Applications, 2017, 37(8): 2234-2239.

刘思, 刘海, 陈启买, 贺超波. 基于网络表示学习与随机游走的链路预测算法[J]. 计算机应用, 2017, 37(8): 2234-2239.

References

[1] 吕琳媛.复杂网络链路预测[J].电子科技大学学报,2010,39(5):651-661.(LYU L Y. Link prediction on complex networks[J]. Journal of University of Electronic Science and Technology, 2010, 39(5):651-661.)
[2] 胡文斌,彭超,梁欢乐,等.基于链路预测的社会网络事件检测方法[J].软件学报,2015,26(9):2239-2355.(HU W B, PENG C, LIANG H L, et al. Event detection method based on link prediction for social network evolution[J]. Journal of Software, 2015, 26(9):2339-2355.)
[3] LU L Y, ZHOU T. Link prediction in complex networks:a survey[J]. Physica A:Statistical Mechanics and Its Applications, 2011, 390(6):1150-1170.
[4] JACCARD P. Étude comparative de la distribution florale dans uneportion des Alpes et des Jura[J]. Bulletin del la Société Vaudoise des Sciences Naturelles, 1901, 37:547-579.
[5] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social Networks, 2003, 25(3):211-230.
[6] BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439):509-512.
[7] ZHOU T, LU L Y, ZHANG Y C. Predicting missing links via local information[J]. The European Physical Journal Condensed Matter and Complex System, 2009, 71(4):623-630.
[8] LU L Y, JIN C H, ZHOU T, Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, 2009, 80(4):046122.
[9] KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1):39-43.
[10] LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks[J]. Physical Review E, 2006, 73(2):026120.
[11] KLEIN D J, RANDIC M. Resistance distance[J]. Journal of Mathematical Chemistry, 1993, 12(1):81-95.
[12] TONG H, FALOUTSOS C, PAN J Y. Fast random walk with restart and its applications[C]//Proceedings of the 6th International Conference on Data Mining. Piscataway, NJ:IEEE, 2006:613-622.
[13] LIU W P, LU L Y. Link prediction based on local random walk[J]. Europhysics Letters, 2010, 89(5):58007.
[14] CHERRY A, ABBER E. Enhancing link prediction in twitter using semantic user attribute[C]//Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. New York:ACM, 2015:1155-1161.
[15] 陈维政,张岩,李晓明.网络表示学习[J].大数据,2015,1(3):8-22.(CHEN W Z, ZHANG Y, LI X M. Network representation learning[J]. Big Data Research, 2015, 1(3):8-22.)
[16] 孙志远,鲁成祥,史忠植,等.深度学习研究与进展[J].计算机科学,2016,43(2):1-8.(SUN Z Y, LU C X, SHI Z Z, 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[C]//NIPS'13:Proceedings of the 26th International Conference on Neural Information Processing Systems. Red Hook, NY:Curran Associates Inc., 2013: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] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1):107-117.
[20] YOSHUA B, REJEAN D, PASCAL V, et al. A neural probabilistic language model[J]. Journal of Machine Learning Research, 2003, 3(6):1137-1155.
[21] MORIN F, BENGIO Y. Hierarchical probabilistic neural network language model[C]//Proceedings of the 10th International Workshop Conference on Artificial Intelligence and Statistics. Cambridge, CA:MIT Press, 2005:246-252.
[22] 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.

Link prediction algorithm based on network representation learning and random walk

基于网络表示学习与随机游走的链路预测算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	CAI Biao, LI Ruicen, WU Yuanyuan. Impact and enhancement of similarity features on link prediction [J]. Journal of Computer Applications, 2021, 41(9): 2569-2577.
[2]	ZHANG Cheng, WAN Yuan, QIANG Haopeng. Deep unsupervised discrete cross-modal hashing based on knowledge distillation [J]. Journal of Computer Applications, 2021, 41(9): 2523-2531.
[3]	CHEN Jun, HE Qing. Improved butterfly optimization algorithm based on cosine similarity [J]. Journal of Computer Applications, 2021, 41(9): 2668-2677.
[4]	WANG Yue, JIANG Yiming, LAN Julong. Intrusion detection based on improved triplet network and K-nearest neighbor algorithm [J]. Journal of Computer Applications, 2021, 41(7): 1996-2002.
[5]	ZHANG Yuanjun, ZHANG Xihuang. Dynamic network representation learning model based on graph convolutional network and long short-term memory network [J]. Journal of Computer Applications, 2021, 41(7): 1857-1864.
[6]	WU Yue, LUO Jiangtao, LIU Rui, HU Zhongyin. Video similarity detection method based on perceptual hashing and dicing [J]. Journal of Computer Applications, 2021, 41(7): 2070-2075.
[7]	ZHANG Hao, ZHU Rui, SONG Fuyao, FANG Peng, XIA Xiufeng. Bichromatic reverse k nearest neighbor query method based on distance-keyword similarity constraint [J]. Journal of Computer Applications, 2021, 41(6): 1686-1693.
[8]	YANG Mengmeng, ZHANG Aihua. Fractal image compression based on gray-level co-occurrence matrix and simultaneous orthogonal matching pursuit [J]. Journal of Computer Applications, 2021, 41(5): 1445-1449.
[9]	FAN Wei, WANG Huimin, XING Yan. Auto-encoder based multi-view attributed network representation learning model [J]. Journal of Computer Applications, 2021, 41(4): 1064-1070.
[10]	HU Lihua, ZUO Weijian, NIE Yaoyao. Feature matching method based on weighted similarity measurement [J]. Journal of Computer Applications, 2021, 41(2): 511-516.
[11]	Yubin ZHOU, Hong XIAO, Tao WANG, Wenchao JIANG, Meng XIONG, Zhongtang HE. Health index construction and remaining useful life prediction of mechanical axis based on action cycle degradation similarity measurement [J]. Journal of Computer Applications, 2021, 41(11): 3192-3199.
[12]	ZHU Yi, NING Zhenhu, ZHOU Yihua. Lightweight detection technology of typosquatting based on visual features [J]. Journal of Computer Applications, 2020, 40(8): 2279-2285.
[13]	ZHU Lin, YU Haitao, LEI Xinyu, LIU Jing, WANG Ruofan. Brain network feature identification algorithm for Alzheimer's patients based on MRI image [J]. Journal of Computer Applications, 2020, 40(8): 2455-2459.
[14]	LI Weizhong. Multi-exposure image fusion based on local features of scene [J]. Journal of Computer Applications, 2020, 40(8): 2365-2371.
[15]	ZHAO Xiaohu, ZHAO Chenglong. Knowledge base question answering system based on multi-feature semantic matching [J]. Journal of Computer Applications, 2020, 40(7): 1873-1878.