基于节点重构思想的链路预测算法研究

基于节点重构思想的链路预测算法研究

论文摘要

现实生活中许许多多的复杂系统可以用网络加以描述。系统中的个体用网络节点表示,个体之间的联系和交互关系用连接边表示。一方面,由于采集成本、采集难度等因素,网络的结构信息往往是不完整的,因而存在未知链接。另一方面,绝大多数的网络都是动态的,会随着时间进行演化,产生新的连接边,称为未来链接。链路预测是一项挖掘网络信息的研究工作,它根据观察到的网络结构信息来预测网络的缺失链接(包含未知链接与未来链接)。链路预测问题不仅能帮助我们理解网络的演化机制,还能发掘网络中未知的、有价值的知识,因而具有重要的理论研究意义和应用价值。目前,基于相似性的链路预测算法通常只关注两个节点之间的相似性,没有做好相似度的分配工作。而“相近节点”和“热门节点”的存在,会使得高相似度节点之间包含大量的冗余信息,从而影响预测效果。针对信息冗余问题,本文提出了线性重构的方法计算相似度。首先,以节点的代数近邻作为线性重构的基,即通过节点的代数近邻去解释它的连边情况,以重构系数作为节点相似度。实验结果表明,虽然代数近邻是通过共同邻居指标筛选出来的,但经过线性重构的方法重新计算相似度后,其效果远远优于共同邻居指标,从而证实了线性重构思想的有效性。其次,考虑到在大多数网络中两个节点是否连边与其相似度有较大关系,本文将节点的一跳邻居(几何邻居)作为线性重构的基,利用线性重构的方法计算相似度。最后,通过线性加权的方法将代数近邻与几何邻居的信息结合,从而得到加权的线性重构相似度,再利用协同过滤的方法对链路进行预测评分,整个方法称为基于加权的线性重构相似度的协同过滤算法。基于加权的线性重构相似度的协同过滤算法包含两种形式:一般形式的WLRS算法、非负形式的WLRS-N算法。本文选取9种具有代表性的算法作为对照,在10个来自不同领域的真实网络进行了大量的数值实验。对算法的参数、收敛性、有效性、预测准确度、计算复杂度以及鲁棒性分别进行了讨论与分析。在预测效果上,WLRS、WLRS-N表现优秀,显著优于9种对比算法,大幅优于CN、AA、RA等传统算法。在计算复杂度上而言,WLRS算法的复杂度非常高,仅能用于理论研究,而改良的WLRS-N算法的复杂度大幅度降低,其复杂度高于CN、AA、RA等传统算法,略比结构微扰方法(SPM)高一点,但远比随机分块矩阵模型(SBM)低。在鲁棒性上,WLRS-N整体上具有较高的鲁棒性,优于CN、AA、RA、SBM、NMF等算法。总体来说,WLRS-N算法具有较高的精确度、适中的计算复杂度和较强的鲁棒性,而WLRS算法在理论分析上有重要的贡献。

论文目录

  • 摘要
  • ABSTRACT
  • 1 绪论
  •   1.1 研究背景
  •   1.2 研究意义
  •   1.3 国内外研究现状
  •   1.4 论文的组织结构
  • 2 链路预测问题概述及预备知识
  •   2.1 复杂网络基本概念
  •   2.2 网络的拓扑特征
  •   2.3 链路预测的问题描述及评价方法
  •     2.3.1 问题描述
  •     2.3.2 评价方法
  •   2.4 基于相似性的链路预测算法
  •     2.4.1 基于局部信息的相似性指标
  •     2.4.2 基于路径的相似性指标
  •     2.4.3 基于随机游走的相似性指标
  •   2.5 基于似然分析的链路预测算法
  •   2.6 基于结构微扰和矩阵分解的链路预测算法
  •     2.6.1 结构微扰模型
  •     2.6.2 LR矩阵分解法
  •     2.6.3 非负矩阵分解法
  •     2.6.4 核非负矩阵分解法
  •   2.7 本章小结
  • 3 基于加权的线性重构相似度的协同过滤算法
  •   3.1 协同过滤算法
  •   3.2 线性重构相似度算法(LRS)
  •     3.2.1 算法介绍
  •     3.2.2 求解方法
  •   3.3 带非负约束的线性重构相似度算法(LRS-N)
  •     3.3.1 算法介绍
  •     3.3.2 求解方法
  •   3.4 代数近邻与几何邻居
  •   3.5 WLRS与WLRS-N的算法描述
  • 4 数值实验及性能分析
  •   4.1 实验设计
  •     4.1.1 实验环境
  •     4.1.2 实验数据集
  •     4.1.3 对比算法
  •     4.1.4 实验流程
  •   4.2 实验结果与讨论
  •     4.2.1 算法表现
  •     4.2.2 性能比较
  •     4.2.3 鲁棒性分析
  •   4.3 本章小结
  • 5 总结与展望
  •   5.1 本文的工作总结
  •   5.2 未来的工作展望
  • 参考文献
  • 致谢
  • 文章来源

    类型: 硕士论文

    作者: 杨程炜

    导师: 李订芳

    关键词: 复杂网络,链路预测,线性重构,相似度,协同过滤

    来源: 武汉大学

    年度: 2019

    分类: 基础科学

    专业: 数学

    单位: 武汉大学

    分类号: O157.5

    总页数: 58

    文件大小: 5364K

    下载量: 16

    相关论文文献

    • [1].突发性地震发生后道路恢复重建成本预测算法研究[J]. 灾害学 2020(03)
    • [2].基于温度预测算法的智能粮仓温度预警系统[J]. 计算机技术与发展 2020(09)
    • [3].基于社团特性的链路预测算法的研究[J]. 广东技术师范学院学报 2015(02)
    • [4].浅析几种基本路段行程时间预测算法[J]. 青春岁月 2017(01)
    • [5].点击科学[J]. 中国科技教育 2017(03)
    • [6].基于随机序列的固有无序蛋白预测算法比较分析[J]. 生物学杂志 2020(03)
    • [7].一种基于局部社团和全局信息的链路预测算法[J]. 浙江工业大学学报 2017(01)
    • [8].改进的广义预测算法在过热气温控制中的应用[J]. 工业控制计算机 2013(11)
    • [9].复杂网络中集聚系数对链路预测算法的影响[J]. 科技视界 2014(12)
    • [10].针对通信社会网络的时间序列链接预测算法[J]. 计算机科学与探索 2010(06)
    • [11].面向车载自组织网络路由的轨迹预测算法[J]. 计算机研究与发展 2017(11)
    • [12].河北省风能特征及其对风速预测算法的改进[J]. 科技传播 2013(06)
    • [13].一种基于频率预测算法的快速锁定全数字锁相环[J]. 电子产品世界 2020(03)
    • [14].基于高阶近似的链路预测算法[J]. 计算机应用 2019(08)
    • [15].广义预测算法在综合减摇系统控制器设计中的应用[J]. 船舶工程 2013(06)
    • [16].二维空间中目标轨迹预测算法研究与分析[J]. 航空电子技术 2012(01)
    • [17].基于神经网络自适应预测算法的谐波检测[J]. 电工技术学报 2011(S1)
    • [18].链路预测算法在药物推荐中的应用研究[J]. 计算机与数字工程 2019(09)
    • [19].论提高装备故障预测准确度的方法途径——先进智能预测算法研究[J]. 电子技术与软件工程 2016(14)
    • [20].基于分离有限状态模型的呼吸预测算法[J]. 清华大学学报(自然科学版) 2015(03)
    • [21].基于试验设计的链路预测算法应用研究[J]. 数理统计与管理 2019(05)
    • [22].竞赛论文评分合成的协同修正预测算法[J]. 数学的实践与认识 2019(15)
    • [23].一种改进共同邻居的节点遍历链路预测算法[J]. 小型微型计算机系统 2018(02)
    • [24].基于链路预测算法分析虚假链接问题[J]. 云南民族大学学报(自然科学版) 2017(05)
    • [25].论提高装备故障预测准确度的方法途径——先进智能预测算法研究[J]. 价值工程 2016(32)
    • [26].分维权重样条插值预测算法及应用[J]. 数学的实践与认识 2014(24)
    • [27].灰色预测算法在铁路货运预警系统中的应用研究[J]. 铁道货运 2015(05)
    • [28].基于预测算法的认知网络的跨层研究[J]. 科技信息 2009(06)
    • [29].一种改进的复杂网络链路预测算法[J]. 小型微型计算机系统 2016(05)
    • [30].基于属性网络表示学习的链接预测算法[J]. 合肥工业大学学报(自然科学版) 2020(11)

    标签:;  ;  ;  ;  ;  

    基于节点重构思想的链路预测算法研究
    下载Doc文档

    猜你喜欢