Please wait a minute...
浙江大学学报(工学版)  2018, Vol. 52 Issue (3): 552-559    DOI: 10.3785/j.issn.1008-973X.2018.03.018
计算机与通信技术     
基于卷积神经网络的链接表示及预测方法
张林, 程华, 房一泉
华东理工大学 信息科学与工程学院, 上海 200237
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
 全文: PDF(1440 KB)   HTML
摘要:

针对节点全局表示和链接局部拓扑关系,提出链接序列化表示及卷积神经网络(CNN)提取序列特征的链接预测方法.研究节点间的局部拓扑及共邻关系,基于共邻紧密度构建链接局部拓扑的有序节点序列,并用node2vec节点向量表达生成潜在链接的矩阵表示;基于CNN建立链接预测的分类模型,采用CNN可变滤波器窗口卷积运算提取序列中共邻与节点对的多层隐含关系,分类训练实现链接的有效预测.在4种大规模网络数据集上的实验结果表明,相比已有方法,该方法的AUC值有显著提高,最高达12.4%,稳定性及普适性较强,解决了传统方法对大规模稀疏网络的预测准确率下降问题.

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.

收稿日期: 2017-04-14 出版日期: 2018-09-11
CLC:  TP391  
基金资助:

国家自然科学基金资助项目(61501187).

通讯作者: 程华,男,副研究员.orcid.org/0000-0003-1109-7832.     E-mail: hcheng@ecust.edu.cn
作者简介: 张林(1993-),女,硕士生,从事数据挖掘和社会网络分析研究.orcid.org/0000-0002-3234-2051.E-mail:linzhang_best@163.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  

引用本文:

张林, 程华, 房一泉. 基于卷积神经网络的链接表示及预测方法[J]. 浙江大学学报(工学版), 2018, 52(3): 552-559.

ZHANG Lin, CHENG Hua, FANG Yi-quan. CNN-based link representation and prediction method. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(3): 552-559.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2018.03.018        http://www.zjujournals.com/eng/CN/Y2018/V52/I3/552

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

[1] 韩勇, 宁连举, 郑小林, 林炜华, 孙中原. 基于社交信息和物品曝光度的矩阵分解推荐[J]. 浙江大学学报(工学版), 2019, 53(1): 89-98.
[2] 郑洲, 张学昌, 郑四鸣, 施岳定. 基于区域增长与统一化水平集的CT肝脏图像分割[J]. 浙江大学学报(工学版), 2018, 52(12): 2382-2396.
[3] 赵丽科, 郑顺义, 王晓南, 黄霞. 单目序列的刚体目标位姿测量[J]. 浙江大学学报(工学版), 2018, 52(12): 2372-2381.
[4] 何杰光, 彭志平, 崔得龙, 李启锐. 局部维度改进的教与学优化算法[J]. 浙江大学学报(工学版), 2018, 52(11): 2159-2170.
[5] 李志, 单洪, 马涛, 黄郡. 基于反向标签传播的移动终端用户群体发现[J]. 浙江大学学报(工学版), 2018, 52(11): 2171-2179.
[6] 王硕朋, 杨鹏, 孙昊. 听觉定位数据库构建过程优化[J]. 浙江大学学报(工学版), 2018, 52(10): 1973-1979.
[7] 魏小峰, 程承旗, 陈波, 王海岩. 基于独立边数的链码方法[J]. 浙江大学学报(工学版), 2018, 52(9): 1686-1693.
[8] 陈荣华, 王鹰汉, 卜佳俊, 于智, 高斐. 基于KNN算法与局部回归的网站无障碍采样评估[J]. 浙江大学学报(工学版), 2018, 52(9): 1702-1708.
[9] 张承志, 冯华君, 徐之海, 李奇, 陈跃庭. 图像噪声方差分段估计法[J]. 浙江大学学报(工学版), 2018, 52(9): 1804-1810.
[10] 刘洲洲, 李士宁, 李彬, 王皓, 张倩昀, 郑然. 基于弹性碰撞优化算法的传感云资源调度[J]. 浙江大学学报(工学版), 2018, 52(8): 1431-1443.
[11] 王勇超, 祝凯林, 吴奇轩, 鲁东明. 基于局部渲染的高精度模型自适应展示技术[J]. 浙江大学学报(工学版), 2018, 52(8): 1461-1466.
[12] 孙念, 李玉强, 刘爱华, 刘春, 黎威威. 基于松散条件下协同学习的中文微博情感分析[J]. 浙江大学学报(工学版), 2018, 52(8): 1452-1460.
[13] 郑守国, 崔雁民, 王青, 杨飞, 程亮. 飞机装配现场数据采集平台设计[J]. 浙江大学学报(工学版), 2018, 52(8): 1526-1534.
[14] 毕晓君, 王朝. 基于超平面投影的高维多目标进化算法[J]. 浙江大学学报(工学版), 2018, 52(7): 1284-1293.
[15] 张廷蓉, 滕奇志, 李征骥, 卿粼波, 何小海. 岩心三维CT图像超分辨率重建[J]. 浙江大学学报(工学版), 2018, 52(7): 1294-1301.