基于网络结构和随机游走理论的链路预测算法研究

论文摘要

复杂网络中链路预测问题作为网络科学领域的重要问题之一,近年来受到众多学者的关注.链路预测是根据观察到的网络结构和已有的节点信息等,利用给定的预测算法,计算出不相邻的节点之间存在连边的概率.然而,基于网络结构相似性的预测算法在挖掘网络结构信息时,不能准确地抓住当前节点之间的结构特征,导致网络结构利用率不高.针对此问题,本文从局部网络结构相似性和全局网络结构相似性两个角度进行链路预测.主要工作和结论如下:1.在无向无权网络中,传统的局部预测算法仅关注共同邻居节点的结构特征,忽略了节点对与共同邻居节点之间的网络结构对相似性的贡献.针对节点间存在局部结构差异性的问题,本文从节点的局部网络结构出发,分别考虑共同邻居节点的个数和节点对与共同邻居节点之间网络结构,提出了基于共同邻居和亲密度的链路预测算法.与其他5个典型预测算法对比,实验结果表明基于共同邻居和亲密度的链路预测算法具有良好的预测性能.此外,根据该算法的特点,将算法推广到加权网络中,改进了3个典型的加权预测算法,并且取得了不错的预测效果.2.在基于随机游走理论的链路预测中,一般游走粒子在节点之间是等概率转移的,但由网络的度相关性可知,粒子不一定等概率游走,可能会受到节点度值的影响.针对粒子在无向无权网络中存在偏向游走的问题,提出有偏向的重启随机游走链路预测算法.该算法从全局网络结构出发,考虑游走粒子基于节点度值进行有偏向转移,得到有偏向的重启随机游走相似性指标,然后运用到链路预测过程中.实验显示有偏向转移的预测算法比无偏向的预测效果好,且在最佳的偏向系数下,与其他局部和全局相似性指标对比,可以得到更好的预测效果.同样,为了扩大该算法的适用范围,根据随机游走的特点,将提出的相似性指标推广到有向网络中,发现有向网络中仍然存在偏向转移现象,并且有偏向的重启随机游走预测算法具有更好的预测能力.

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 研究背景及意义
•   1.2 国内外研究现状
•   1.3 论文创新点与研究内容
•   1.4 论文结构
• 第2章 相关理论基础
•   2.1 复杂网络的基本概念
•     2.1.1 网络的图表示
•     2.1.2 网络的基本特征量
•   2.2 随机游走理论
•   2.3 链路预测的基本概念
•     2.3.1 问题描述
•     2.3.2 评价指标
•   2.4 基于网络结构相似性的链路预测算法
•     2.4.1 基于局部网络结构的相似性指标
•     2.4.2 基于全局网络结构的相似性指标
•     2.4.3 相似性指标分析
•   2.5 本章小结
• 第3章 基于共同邻居和亲密度的链路预测算法
•   3.1 节点亲密度的概念
•   3.2 基于CNID的链路预测算法
•     3.2.1 CNID指标的提出
•     3.2.2 算法的描述
•     3.2.3 算法流程及复杂度分析
•   3.3 实验结果与分析
•     3.3.1 实验数据集
•     3.3.2 与其他基准指标的对比
•   3.5 CNID算法在加权网络中拓展
•     3.5.1 加权相似性指标
•     3.5.2 基于CNID指标改进的加权相似性指标
•     3.5.3 实验及结果分析
•   3.6 本章小结
• 第4章 基于有偏向随机游走的链路预测算法
•   4.1 有偏向的随机游走理论
•   4.2 基于BRWR的链路预测算法
•     4.2.1 BRWR指标的提出
•     4.2.2 算法的描述
•     4.2.3 算法流程及复杂度分析
•   4.3 实验结果与分析
•     4.3.1 实验数据集
•     4.3.2 偏向系数β对预测精度的影响
•     4.3.3 与其他基准指标的对比
•   4.4 BRWR算法在有向网络中拓展
•     4.4.1 有向相似性指标
•     4.4.2 有向网络中BRWR算法
•     4.4.3 实验及结果分析
•   4.5 本章小结
• 第5章 总结与展望
•   5.1 总结
•   5.2 展望
• 致谢
• 参考文献
• 攻读硕士学位期间获得的科研成果

文章来源

类型: 硕士论文

作者: 吕亚楠

导师: 韩华

关键词: 复杂网络,链路预测,网络结构,节点相似性,随机游走

来源: 武汉理工大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 武汉理工大学

分类号: O157.5

DOI: 10.27381/d.cnki.gwlgu.2019.001793

总页数: 63

文件大小: 1126K

下载量: 32