图流中针对节点的链路预测算法研究

论文摘要

图流是一种大规模的、高度动态的、无止境的图结构,其节点和边以流的形式快速到达,图流的这些性质使得它很难被存储在内存里面,甚至磁盘上。很多应用可以用图流来描述,例如社交网络、电商网络等。在这些应用中,链路预测是一个很重要的问题,其目的是预测网络中尚未产生连边的两个节点之间产生链接的可能性。然而,在图流中,针对节点的链路预测相比于常规意义上的链路预测有着更广泛的应用。考虑好友推荐的例子,好友推荐系统一般需要给指定的用户推荐一些好友,而不是随机挑选两个用户,判断他们是否会成为好友。如何在图流这种高度动态并且超大规模的图结构中准确、快速的进行链路预测,成为了一个很大的挑战。一种双阶段选择链路预测系统（TPLP,Two-Phase Selection Link Prediction System）旨在预测图流中最有可能与目标节点发生链接的top-k个节点。为了在图流中高效、准确地解决该问题,TPLP使用了一种双阶段选择算法获取目标节点的候选集。并且,TPLP提出了一种新的近似算法去估算图流中的共同邻居指标,这个指标在图计算领域是很重要的。进一步地,TPLP实现了一种在图流中估计节点聚集系数的方法,并将其运用到图流的链路预测当中。为了测试算法的效率和准确性,实验中使用了四种真实的图流数据集进行测试,分别是亚马逊数据集、DBLP数据集、维基百科数据集、Super-User数据集。实验结果证明TPLP相比于现有方法更高效、更准确,可以运用在真实的图流场景当中。

论文目录

• 摘要
• Abstract
• 1 绪论
•   1.1 研究背景
•   1.2 国内外研究现状
•   1.3 研究内容与目标
•   1.4 主要贡献
•   1.5 论文组织结构
• 2 双阶段选择算法
•   2.1 重要定义
•   2.2 TPLP系统
•   2.3 双阶段选择算法介绍
•   2.4 第一阶段选择算法
•   2.5 第二阶段选择算法
•   2.6 本章小结
• 3 图流中相似度指标的估计
•   3.1 共同邻居指标估计
•   3.2 图流中基于NCC的相似度指标
•   3.3 图流中NCC的估算
•   3.4 本章小结
• 4 系统测试与分析
•   4.1 测试数据集
•   4.2 双阶段选择算法测试
•   4.3 共同邻居估计算法准确率测试
•   4.4 链路预测准确率测试
•   4.5 阈值N对 APP-NCC准确率的影响
•   4.6 采样带来的准确率误差
•   4.7 本章小结
• 5 总结与展望
•   5.1 总结
•   5.2 展望
• 致谢
• 参考文献
• 附录1 攻读硕士学位期间发表论文
• 附录2 攻读硕士学位期间申请的国家发明专利
• 附录3 攻读硕士学位期间参与的主要科研项目

文章来源

类型: 硕士论文

作者: 肖洋

导师: 陈汉华

关键词: 图流,链路预测,相似度指标,动态图

来源: 华中科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 华中科技大学

分类号: O157.5

DOI: 10.27157/d.cnki.ghzku.2019.001520

总页数: 54

文件大小: 2025K

下载量: 11