基于最简子图的链接表示及预测

计算机工程与科学

• 计算机网络与信息安全 • 上一篇下一篇

基于最简子图的链接表示及预测

尚振浩，程华，房一泉

（华东理工大学信息科学与工程学院，上海 200237）

收稿日期:2018-04-23 修回日期:2018-07-12 出版日期:2019-02-25 发布日期:2019-02-25
基金资助:
国家自然科学基金(61501187)

Link representation and prediction

based on the simplest subgraph

SHANG Zhenhao,CHENG Hua,FANG Yiquan

(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

Received:2018-04-23 Revised:2018-07-12 Online:2019-02-25 Published:2019-02-25

摘要/Abstract

摘要：

稀疏网络的传统链接预测准确率低，为了捕捉稀疏网络节点间建立链接的可能性，提出基于节点间最短路径的最简子图概念。最简子图反映了节点间的拓扑紧密关系，在采用node2vec节点向量化方法的基础之上，实现了基于最短路径的链接表示，并采取长短期记忆循环神经网络(LSTM)学习长链接节点序列的特征，最终实现链接的分类。实验结果表明，该方法与已有方法相比，在4种不同数据集上的预测AUC值平均提高了11.6%，AP值平均提高了13.3%。

关键词: 最短路径, 最简子图, 链接表示, 长短期记忆网络(LSTM), 链接预测

Abstract:

Traditional link prediction methods of sparse networks have low accuracy. In order to capture the possibility of link establishment among sparse network nodes, we propose the concept of simplest subgraph based on the shortest path between a pair of nodes, which reflects the tight topology relationship between nodes. Based on the node2vec node vectorization method, the link representation based on the shortest path is implemented. To complete the link classification task, we use the long short-term memory (LSTM) recurrent neural network to learn the characteristics of long-link node sequences. Compared with existing methods, the proposed method can increase the AUC value on 4 different datasets by 11.6% averagely, and the AP value by an average of 13.3%.

Key words: shortest path, simplest subgraph, link representation, LSTM, link prediction

尚振浩，程华，房一泉. 基于最简子图的链接表示及预测[J]. 计算机工程与科学.

SHANG Zhenhao,CHENG Hua,FANG Yiquan.

Link representation and prediction

based on the simplest subgraph

[J]. Computer Engineering & Science.

[1]	程佳乐，李伟东. 具有树和路约束的平行机排序问题[J]. 计算机工程与科学, 2018, 40(12): 2273-2279.
[2]	杨晓花1,2，武继刚1,2，史雯隽1,2，赵国栋1,2. 稳定的最短路径树及其构造算法[J]. J4, 2016, 38(03): 418-424.
[3]	汪晓洁，郭文强，王思秀，蔡咏梅. 一种高效的最短路径完全动态更新算法[J]. J4, 2016, 38(03): 449-453.
[4]	伍杰华1，2，朱岸青1，3 ，蔡雪莲1，张小兰1. 差分化节点特征对复杂网络链接预测的分类性能分析[J]. J4, 2015, 37(01): 173-178.
[5]	魏文红1，李清霞2，蔡昭权3. 一种基于桶结构的单源最短路径算法[J]. J4, 2012, 34(4): 77-81.
[6]	邹北骥,贺加贝,阮鹏. 一种改进的地图匹配算法及其在移动通信巡检系统中的应用[J]. J4, 2010, 32(10): 49-53.
[7]	徐飞孙劲光. 中文分词切分技术研究[J]. J4, 2008, 30(5): 126-128.
[8]	唐晋韬王挺. 复杂社会网络的介数性质近似计算方法研究[J]. J4, 2008, 30(12): 9-14.
[9]	陈立潮刘佳吕亚男. 带杂交算子的蚁群算法求解动态网络中的最短路径问题[J]. J4, 2007, 29(5): 81-82.
[10]	刘建伟卢建朱张彦军. 一个改进的调配算法[J]. J4, 2007, 29(1): 73-75.
[11]	徐凤生. 求最短路径的新算法[J]. J4, 2006, 28(2): 83-85.
[12]	徐凤生李天志. 所有最短路径的求解算法[J]. J4, 2006, 28(12): 83-84.
[13]	陈欣[1,2] 熊岳山[1] 谭珂[3] 郭光友[3]. 基于A^＊搜索方法的主动轮廓提取算法[J]. J4, 2006, 28(1): 86-88.
[14]	周培德. 交通道路网中任意两点之最短路径的快速算法[J]. J4, 2002, 24(4): 35-37.

基于最简子图的链接表示及预测

Link representation and prediction

based on the simplest subgraph

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 14

编辑推荐

Metrics

本文评价