学位论文 > 优秀研究生学位论文题录展示

基于标签传播的链路预测算法研究与应用

作　者: 辛霆麟
导　师: 徐保民
学　校: 北京交通大学
专　业: 计算机科学与技术
关键词: 复杂网络链路预测标签传播社区发现
分类号: O157.5
类　型: 硕士论文
年　份: 2014年
下　载: 15次
引　用: 0次
阅　读: 论文下载

内容摘要

近十年,复杂网络研究在许多科学领域内掀起了高潮。包括生物、物理、计算机等领域的科学家在内,相当一部分人都立足于揭示复杂网络进化的内在驱动因素。作为复杂网络研究中的一个重要分支,链路预测问题既可以在理论意义上帮助我们认识复杂网络的进化机制,又可以在实际应用上帮助我们揭示各学科内的许多重要问题。链路预测旨在推断复杂网络中节点之间存在连边的可能性,其中包括预测已经存在但尚未被发现的连边和将来出现的连边。近几年,基于结构相似性的链路预测算法受到了广泛地关注,研究者们陆续提出了各种基于局部网络结构和基于全局网络结构的方法。本文主要研究的是复杂网络中基于标签传播的链路预测算法,并将研究重点放在了如何提高链路预测精度的问题上。首先,本文系统地概述了复杂网络链路预测相关背景知识和基本内容,根据所依赖的网络结构差异,分类总结了基于结构相似性的链路预测指标。其次,提出了基于标签传播的链路预测算法和基于最大值的计算分数值方法,模拟了社交网络中人与人之间信息的动态交互过程。再次,通过实验,详细比较了基于标签传播的链路预测算法与几种经典的基于结构相似性指标的预测性能差异,证明了在现实网络数据上,基于标签传播的链路预测算法表现的更为优越。最后,提出了将链路预测算法应用于社区发现中的思想,使用基于标签传播的链路预测算法来优化Louvain社区发现算法。结果表明,经过改进后的Louvain算法能够产生比原始基本算法更好的效果,从而发现复杂网络中更加精确的社区结构。

全文目录

致谢  5-6
中文摘要  6-7
ABSTRACT  7-10
1 引言  10-14
  1.1 研究背景和意义  10-11
  1.2 本文研究的主要内容  11-12
  1.3 论文的组织安排  12-14
2 相关背景知识简介  14-28
  2.1 网络属性  14-17
    2.1.1 网络大小和密度  14-15
    2.1.2 聚类系数  15
    2.1.3 路径长度  15-16
    2.1.4 度分布  16-17
  2.2 链路预测的基本概念  17-20
    2.2.1 问题描述  17-18
    2.2.2 数据集划分  18-20
  2.3 复杂网络上链路预测指标简介  20-27
    2.3.1 局部相似性指标  21-23
    2.3.2 全局相似性指标  23-25
    2.3.3 准局部相似性指标  25-27
  2.4 本章小结  27-28
3 基于标签传播的链路预测算法  28-42
  3.1 算法描述  28-33
    3.1.1 社区发现中的标签传播算法  28-30
    3.1.2 基于标签传播的链路预测算法  30-33
  3.2 实验环境和数据  33-34
  3.3 算法评估指标  34-36
    3.3.1 AUC值  35
    3.3.2 Precision值  35-36
  3.4 实验及结果分析  36-40
  3.5 本章小结  40-42
4 链路预测算法在社区发现中的应用  42-51
  4.1 Louvain社区发现算法  42-44
  4.2 ILP算法对Louvain算法的优化  44-45
  4.3 算法评估指标  45
  4.4 实验及结果分析  45-50
  4.5 本章小结  50-51
5 总结与展望  51-53
参考文献  53-56
作者简历  56-58
学位论文数据集  58

基于标签传播的链路预测算法研究与应用

内容摘要

全文目录

相似论文