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

摘要：

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

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

所属期刊栏目：14

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金项目61562091;云南省应用基础研究计划面上项目2016FB110

在线出版日期：2019-07-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：761-768