基于路径和非对称聚类系数的链路预测算法研究

论文摘要

复杂网络直观上说是类似互联网一样具有很高复杂度的一种网络,通过复杂网络进行建模分析研究实际系统的内在规律,从而找到一些实际问题的理论依据和解决方案。链路预测是当前复杂网络中一个重要的研究方向,它是利用已知网络中一些节点局部信息,路径中包含的网络结构特征等来恢复网络中所缺失的链接或预测两个未链接节点产生连边的概率,来判断未来网络中的整体结构。因此链路预测这个方向得到了广泛关注。已有相似性算法主要是基于节点局部属性和路径信息。基于节点局部属性的算法计算简单,但在网络结构不全的情况下精确度会受很大影响;基于路径的算法虽然包含了大量网络结构信息,但计算复杂度相对较高。在本文中,重点提出了基于网络局部结构的链路预测算法,主要是利用有效短路径信息和节点相关聚类系数分别提出了3种相关的链路预测算法。本文的主要工作和成果如下:1.提出了基于节点和路径强弱影响和社区信息的链路预测算法。针对在网络结构不全的时候通过节点属性计算精确度不高和提取高阶路径信息计算复杂度大的问题,本文将节点属性和有效路径结合起来,强调短路径的影响,并在最后使用社区信息提高精确度,算法通过和其他指标的对比表明了其合理性。2.提出了基于自适应度惩罚和非对称边聚类的链路预测算法。针对节点局部属性如聚类系数不能区分链路两端节点因重要性不同对链接所做出的贡献也会不同的问题,本文将焦点从节点转移到链路,提出了非对称边聚类系数,且在不同网络中通过平均聚类系数对节点共同邻居进行自适应度惩罚,实验表明该算法有效地提高了精确度。3.提出了基于节点引力的链路预测算法。本文将万有引力定律运用到社交网络预测上,根据节点重要性和路径长度来衡量质量和距离,节点无论相隔有多远,它们之间都存在一种引力来促进发生链接。针对度小的节点在稀疏网络中对低聚类系数的敏感性问题,本文使用了节点的度聚类系数来判断节点的重要性,实验表明基于节点引力的算法能够有效得用于社交网络预测。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 国内外研究现状
•   1.3 研究目标和内容
•   1.4 论文组织架构
• 第二章 链路预测的相关工作
•   2.1 问题描述
•   2.2 数据集划分
•     2.2.1 随机抽样
•     2.2.2 逐项遍历
•     2.2.3 k-折叠交叉检验
•     2.2.4 滚雪球抽样
•     2.2.5 熟识者抽样
•     2.2.6 随机游走抽样
•     2.2.7 基于路径抽样
•   2.3 评价指标
•     2.3.1 AUC
•     2.3.2 精确度
•   2.4 经典链路预测指标
•     2.4.1 基于节点局部信息的相似性指标
•     2.4.2 基于路径信息的相似性指标
•   2.5 无向网络基本静态几何特征
•     2.5.1 网络直径和平均距离
•     2.5.2 度分布
•     2.5.3 网络的聚类系数
•     2.5.4 介数
•     2.5.5 网络的同配系数
•     2.5.6 网络的度异质性
• 第三章 基于节点路径强弱影响和社区信息的链路预测算法
•   3.1 引言
•   3.2 相关定义
•   3.3 算法步骤
•   3.4 实验结果分析
•     3.4.1 实验数据集
•     3.4.2 对比算法与评价指标
•     3.4.3 可调参数α的最优值
•     3.4.4 实验结果和分析
•   3.5 本章总结
• 第四章 基于自适应度惩罚和非对称边聚类的链路预测算法
•   4.1 引言
•   4.2 自适应度
•     4.2.1 度惩罚与网络结构的关系
•     4.2.2 自适应度惩罚
•   4.3 非对称边聚类（ALC）系数
•   4.4 基于自适应度非对称边聚类系数指标（DPALC）与算法步骤
•   4.5 数据集和对比算法
•     4.5.1 数据集介绍
•     4.5.2 对比算法
•   4.6 实验结果分析
•   4.7 本章小结
• 第五章 基于节点引力的链路预测算法
•   5.1 引言
•   5.2 方法的提出
•     5.2.1 牛顿万有引力
•     5.2.2 度相关聚类系数
•     5.2.3 节点引力的链路预测指标（NP）
•   5.3 算法步骤
•   5.4 数据集和对比算法
•     5.4.1 数据集介绍
•     5.4.2 对比算法
•   5.5 实验结果分析
•   5.6 本章总结
• 第六章 结论与展望
• 参考文献
• 致谢
• 作者简介
•   1 作者简历
•   2 攻读硕士学位期间发表的学术论文
•   3 参与的科研项目及获奖情况
•   4 发明（申请）专利
• 学位论文数据集

文章来源

类型: 硕士论文

作者: 杨旭华

导师: 杨旭华

关键词: 链路预测,有效路径,不对称链路聚类,节点局部信息,节点引力

来源: 浙江工业大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 浙江工业大学

分类号: O157.5

DOI: 10.27463/d.cnki.gzgyu.2019.000510

总页数: 73

文件大小: 4149K

下载量: 27