| Computer and Communication Technology |
|
|
|
|
| CNN-based link representation and prediction method |
| ZHANG Lin, CHENG Hua, FANG Yi-quan |
| College of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China |
|
|
|
Abstract A novel link prediction method of link serialized representation and convolution neural network (CNN) extracting sequence features was proposed in view of the global node representation and the link's local topology. The local topological and common neighbors' relationship between node pairs were studied. Based on common neighbors' density, the ordered node sequences of links' local topology were constructed, and the matrix representation of potential links were generated by node2vec to express the nodes in the sequences vectorically. The classification model of link prediction was established based on CNN. The variable-size filter windows in CNN were used for convolution operation to extract the multilayer implicit relation features among common neighbors and node pairs in the sequences. After the training and classification process, potential links were effectively predicted. The experimental results on four large scale network datasets show that this method has significantly improved AUC value of up to 12.4% compared with the existing methods, and has strong stability and universality, which also solves the problem that traditional methods' accuracy for link prediction decreases with the large-scale sparse network.
|
|
Received: 14 April 2017
Published: 11 September 2018
|
|
|
基于卷积神经网络的链接表示及预测方法
针对节点全局表示和链接局部拓扑关系，提出链接序列化表示及卷积神经网络（CNN）提取序列特征的链接预测方法.研究节点间的局部拓扑及共邻关系，基于共邻紧密度构建链接局部拓扑的有序节点序列，并用node2vec节点向量表达生成潜在链接的矩阵表示；基于CNN建立链接预测的分类模型，采用CNN可变滤波器窗口卷积运算提取序列中共邻与节点对的多层隐含关系，分类训练实现链接的有效预测.在4种大规模网络数据集上的实验结果表明，相比已有方法，该方法的AUC值有显著提高，最高达12.4%，稳定性及普适性较强，解决了传统方法对大规模稀疏网络的预测准确率下降问题.
|
|
| [1] BUCCAFURRI F, LAX G, NOCERA A, et al. Discovering missing me edges across social networks[J].Information Sciences, 2015, 319(C):18-37.
[2] LIU H. Uncovering the network evolution mechanism by link prediction[J]. Scientia Sinica, 2011,41(7):816-823.
[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] PAPADIMITRIOU A, SYMEONIDIS P, MANOLOPO ULOS Y. Fast and accurate link prediction in social networking systems[J]. Journal of Systems and Software, 2012, 85(9):2119-2132.
[5] DONG Y, TANG J, WU S, et al. Link prediction and recommendation across heterogeneous social networks[C]//IEEE International Conference on Data Mining. Brussels:IEEE, 2013:181-190.
[6] 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. Hong Kong:ACM, 2011:635-644.
[7] KAYA B, POYRAZ M. Age-series based link prediction in evolving disease networks[J]. Computers in Biology and Medicine, 2015, 63(C):1-10.
[8] 刘智慧,张泉灵. 大数据技术研究综述[J]. 浙江大学学报:工学版, 2014,48(6):957-972. LIU Zhi-hui, ZHANG Quan-ling. Research overview of big data technology[J]. Journal of Zhejiang University:Engineering Science, 2014,48(6):957-972.
[9] LIBEN-NOWELL D, KLEINBERG J. The link prediction problem for social networks[J]. Journal of the Association for Information Science and Technology, 2007, 58(7):1019-1031.
[10] HASAN, MOHAMMAD A. Link prediction using supervised learning[J]//Workshop on Link Analysis Counter-terrorism and Security, 2006, 30(9):798-805.
[11] LESKOVEC J, HUTTENLOCHER D, KLEINBERG J. Predicting positive and negative links in online social networks[C]//Proceedings of the 19th International Conference on World Wide Web. Raleigh:ACM,2010:641-650.
[12] ZHOU T, LV L, ZHANG Y C. Predicting missing links via local information[J].The European Physical Journal B, 2009, 71(4):623-630.
[13] SCHLICHTKRULL M, KIPF T N, BLOEM P, et al. Modeling relational data with graph convolutional networks[EB/OL].[2017-04-14]. https://arxiv.org/pdf/1703.06103.pdf.
[14] 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. San Francisco:ACM,2016:855-864.
[15] KIM Y. Convolutional neural networks for sentence classification[EB/OL].[2017-04-14]. https://arxiv.org/pdf/1408.5882.pdf.
[16] KALCHBRENNER N, GREFENSTETTE E, BLUNSOM P. A convolutional neural network for modelling sentences[EB/OL].[2017-04-14]. https://arxiv.org/pdf/1404.2188.pdf.
[17] ZHANG Y, WALLACE B. A sensitivity analysis of (and practitioners' guide to) convolutional neural networks for sentence classification[EB/OL].[2017-04-14].https://arxiv.org/pdf/1510.03820.pdf.
[18] PEROZZI B, ALRFOU 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] NEWMAN M E. Clustering and preferential attachment in growing networks[J]. Physical Review E Statistical Nonlinear and Soft Matter Physics, 2001, 64(2):025102.
[20] LV L, ZHOU T. Link prediction in complex networks:a survey[J]. Physical A:Statistical Mechanics and its Applications, 2011, 390(6):1150-1170.
[21] 李彦冬, 郝宗波, 雷航. 卷积神经网络研究综述[J]. 计算机应用, 2016, 36(9):2508-2515. LI Yan-dong, HAO Zong-bo, LEI Hang. Research overview of convolutional neural network[J]. Application of Computers, 2016,36(9):2508-2515.
[22] HINTON G E, SRIVASTAVA N, KRIZHEVSKY A, et al. Improving neural networks by preventing co-adaptation of feature detectors[J]. Computer Science, 2012, 3(4):212-223.
[23] LESKOVEC J. Stanford large network dataset collection[EB/OL].[2017-04-14]. http://snap.stanford.edu/data/index.html.
[24] ADAMIC L A, ADAR E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3):211-230.
[25] LICHTENWALTER R N, LUSSIER J T, CHAWLA N V. New perspectives and methods in link prediction[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington:ACM,2010:243-252.
[26] 庄福振, 罗平, 何清,等. 迁移学习研究进展[J].软件学报, 2015, 26(1):26-39. ZHUANG Fu-zhen, LUO Ping, HE Qing, et al. Survey on transfer learning research[J]. Journal of Software, 2015,26(1):26-39. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
