基于局部网络结构的链路预测算法研究

论文摘要

链路预测,作为复杂网络研究和分析的重要手段之一,具有巨大的科研和应用价值。具体来讲,链路预测就是通过对网络中不同因素间的相关性进行量化,充分运用这些量化指标对网络中缺失或者是真实存在但尚未发现的连接以及将来有可能出现的连接进行预测。近年来,该方向的研究成果迭出,以基于相似性的链路预测方法最为普遍。该类方法的关键在于利用网络中的诸如节点属性和网络结构等信息来定义节点之间的相似性。其中,由于网络结构信息较于节点属性的获取和筛选更为容易,所以在网络科学领域学者们的研究中备受青睐。然而,现阶段的链路预测算法对这类信息的挖掘和利用还不够充分,如何高效且准确地预测不完整复杂网络中的缺失链接仍具挑战。本文,为了有效平衡算法的精度和时间复杂度,以基于局部网络结构的链路预测算法为研究主线,分析现有的基于网络结构的链路预测算法及其目前存在的主要问题,根据网络规模的不同,提出相应的链路预测算法。内容概述如下:（1）针对中、小规模网络,本文从局部网络拓扑信息着手,在基于共同邻居节点是影响预测节点对相似性的重要因素之一这一事实之上,考虑到局部网络环境,即链路聚类信息在预测缺失链接中的功能,提出了基于集体影响和边聚类信息的链路预测算法CELP,实现对节点相似性这一网络结构特征的刻画,有效开发了公共节点本身及其连边形成的局部网络结构在预测网络链路形成方面的价值。此外,“物以类聚,人以群分”的规律,表明了网络的社区属性这一结构特征的普遍性。因此,本文利用社区发现算法ComST来获取网络的社区结构并计算社区相似性,然后将其与CELP结合,建模成贝叶斯网络。根据贝叶斯定理,设计出基于局部网络结构信息的链路预测算法LNSLP,进一步提高了算法预测精度,保证了网络结构信息的充分挖掘和利用。来自各个领域的多个数据集的对比实验结果表明了所提算法的有效性,也进一步肯定了节点、连边、社区等信息对于链路预测工作的重要意义。（2）针对大规模网络,传统的高维稀疏表示形式,即邻接矩阵,因消耗的计算空间与时间较多,同时面临较为严重的数据稀疏问题而具有很大的局限性。另一方面,传统的基于邻接矩阵表示方案而设计的链路预测算法,处理大型网络的效率太低。因此,本文转变研究思维,先是提出了基于局部网络结构信息的网络表示学习算法LNSNRL,通过语言模型Skip-Gram对所构造的随机游走节点序列进行学习,实现网络节点的低维向量表示。在此基础上,设计了基于网络表示学习的链路预测算法NRLLP,利用任意两个节点表示向量之间的欧式距离定义其相似性,距离越近的节点,其相似性越高。实验结果表明,NRLLP算法相较于基于原始网络表示形式设计的链路预测算法LNSLP,在处理大型网络问题时,效率和效果上都具有明显的优势。

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 链路预测问题研究现状
•   1.3 本文主要研究内容
•   1.4 论文组织结构
• 第二章 相关理论与技术概述
•   2.1 复杂网络的基本概念
•     2.1.1 复杂网络定义
•     2.1.2 图及其类型
•   2.2 网络的拓扑性质
•     2.2.1 度、平均度、网络密度与度分布
•     2.2.2 网络的连通性与路径
•     2.2.3 直径、平均路径长度与效率
•     2.2.4 聚类系数
•     2.2.5 社团结构
•   2.3 基本的复杂网络模型
•     2.3.1 小世界网络
•     2.3.2 无标度网络
•   2.4 链路预测理论综述
•     2.4.1 问题描述
•     2.4.2 经典算法介绍
•     2.4.3 网络数据集划分
•     2.4.4 性能评价指标
•   2.5 本章小结
• 第三章 基于局部网络结构信息的链路预测算法
•   3.1 引言
•   3.2 背景知识
•     3.2.1 集体影响
•     3.2.2 边聚类信息
•     3.2.3 社区发现算法
•     3.2.4 贝叶斯网络和期望最大化算法
•   3.3 基于集体影响和边聚类信息的链路预测算法
•     3.3.1 CELP算法
•     3.3.2 算法时间复杂度分析
•     3.3.3 CELP算法小结
•   3.4 基于局部网络结构信息的链路预测算法
•     3.4.1 社区相似性
• LP算法'>    3.4.2 LNS_LP算法
•     3.4.3 算法时间复杂度分析
• LP算法小结'>    3.4.4 LNS_LP算法小结
•   3.5 实验及结果分析
•     3.5.1 实验设置及实验环境说明
•     3.5.2 实验数据集
•     3.5.3 对比算法
•     3.5.4 结果与分析
•   3.6 本章小结
• 第四章 基于网络表示学习的链路预测算法
•   4.1 引言
•   4.2 背景知识
•     4.2.1 网络表示学习
•     4.2.2 语言模型
•   4.3 基于网络表示学习的链路预测算法
•     4.3.1 基于CELP的随机游走算法
•     4.3.2 基于社区感知的随机游走算法
•     4.3.3 基于网络表示学习的链路预测算法
•     4.3.4 算法时间复杂度分析
• LP算法小结'>    4.3.5 NRL_LP算法小结
•   4.4 实验结果与分析
•     4.4.1 实验设置及实验环境说明
•     4.4.2 实验数据集
•     4.4.3 对比算法
•     4.4.4 结果与分析
•   4.5 本章小结
• 第五章 总结与展望
•   5.1 总结
•   5.2 展望
• 致谢
• 参考文献
• 附录:作者在攻读硕士学位期间发表的论文

文章来源

类型: 硕士论文

作者: 杨晓翠

导师: 张曦煌

关键词: 链路预测,集体影响,边聚类信息,社区发现,贝叶斯网络,网络表示学习

来源: 江南大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 江南大学

分类号: O157.5

总页数: 77

文件大小: 3365K

下载量: 93