基于图勾勒的图链路预测方法

PDF下载HTML

Title:

Graph sketches-based link prediction over graph data

作者:

尤洁¹, 李劲^1,2, 张赛¹, 李婷¹

1. 云南大学 软件学院, 云南 昆明 650091;
2. 云南省软件工程重点实验室, 云南 昆明 650091

Author(s):

YOU Jie¹, LI Jin^1,2, ZHANG Sai¹, LI Ting¹

1. School of Software, Yunnan University, Kunming 650091, China;
2. Key Laboratory in Software Engineering of Yunnan Province, Kunming 650091, China

关键词:

图数据; 算法复杂度; 链路预测; 图勾勒; 节点相似性; 并行计算; Apache Spark

Keywords:

graph data; algorithm complexity; link-prediction; graph sketches; nodes similarity; parallel computing; Apache Spark

分类号:

TP311

DOI:

10.11992/tis.201806007

摘要:

针对已有链路预测算法复杂度高，不适于在大规模图上进行链接预测的问题，本文基于图勾勒近似技术对已有链路预测方法进行优化，提出了基于图勾勒的链路预测方法。该方法将链路预测算法的计算复杂度由O（n³）降低至O（n²k²log²n）。为进一步提高链接预测效率，给出了基于Spark的并行化链路预测实现方法。在真实图数据集上进行测试，实验结果表明本文方法在保证链接预测精度的前提下，可有效提升算法效率。

Abstract:

The high computational complexity of existing link prediction algorithms makes them unsuitable for link prediction on large-scale graphs. To solve this problem, we propose a novel link prediction approach that involves combining the existing link prediction approaches with graph sketch approximation. Our proposed approach reduces the computation complexity of link prediction from O(n³) to O(n²k²log²n) Furthermore, to enhance the efficiency of our approach; we also provide a parallel link prediction algorithm, which is implemented on the parallel computing framework Apache Spark. Finally, we conducted extensive experiments on a real network dataset to test the validation and efficiency of our approach. The experimental results indicate that our methods can effectively improve the efficiency of link prediction while guaranteeing prediction accuracy as well.