复杂网络k阶无重复路径算法及其应用

论文摘要

复杂网络作为当前研究的热门领域,引起了众多研究人员的兴趣和关注。不仅仅是因为复杂网络基础理论研究取得了突破性进展,也因为复杂网络在生活中的应用变得越来越广泛。现实世界中,复杂系统遍及各个角落,和人们的生活密切相关,如计算机相互连接而成的计算机系统,神经元相互联系而成的神经系统,传染病扩散形成的病毒传播系统等。将复杂系统抽象为复杂网络,通过研究模型的拓扑结构和功能对现实复杂系统的特性进行更加深入的理解,为后续的改造和利用提供便利和支持。复杂网络中,关于k阶无重复路径数目的研究相对匮乏,然而对于网络中信任的传播,分析节点的相似性等都具有极大地意义。现有方法中,根据邻接矩阵幂乘计算节点间的路径数目,由于包含了有环路径和部分重复路径,造成了结果的不准确问题。因此本文研究的就是复杂网络中的k阶无重复路径数目问题。具体工作如下:1.基于节点度的k阶无重复路径计算。本文介绍了复杂网络的研究背景,通过分析复杂网络中对于拓扑结构特性的相关描述,提出了可用度的概念。并结合度信息提出了基于节点度的无重复路径计算方法。本文利用复杂网络的局部特征信息,将起始节点的出度和终端节点的入度纳入考虑范围,对节点间的路径数目进行验证分析,并得到了一个理论最大值。实验结果表明,不论复杂网络的节点规模大小,该方法都能基于网络的节点度信息快速的给出无重复路径数目。2.基于最优路径的k阶无重复路径计算。本文研究了复杂网络中的k阶无重复路径计算问题,在分析了目前复杂网络中关于路径方面的研究和现实生活的需求特征后,提出了基于最优路径的k阶无重复路径算法。在算法的处理过程中,从起始节点和终端节点的交叉集合中选取关键点搜寻最优路径,并利用路径有效拼接的方法,得到k阶路径,数次迭代后得到k阶无重复路径总数。实验结果表明,该方法和传统算法相比计算结果有了很大的改善,展现了算法的潜在能力。3.基于无重复路径的信任传播和相似度计算。将提出的k阶无重复路径算法应用于网络中信任值的传播和节点相似度的计算。本文提出了基于无重复路径的复杂网络信任传播模型,在k阶无重复路径的基础上,计算信任值的传播信息,利用节点最初的连接状态比值作为阈值,计算最终的节点可信度,并将预测错误率作为判断算法有效性的标准。通过在信任网络数据集的对比实验,表明了在给定的网络数据集上,该算法的错误率有了明显的下降。在求解复杂网络节点相似性方面,相似度是分析复杂网络拓扑结构的基础,对于社区发现,网络演化和链路预测等具有重要的意义。传统Katz指标使用矩阵幂估算节点间的路径数目。本文将无重复路径计算方法应用到Katz指标中,通过在空手道俱乐部网络的对比实验,验证了这种方法的合理性和准确性。

论文目录

• 摘要
• ABSTRACT
• 符号对照表
• 缩略语对照表
• 第一章 绪论
•   1.1 复杂网络的研究背景
•   1.2 复杂网络的基本特性
•     1.2.1 基本表示
•     1.2.2 平均距离
•     1.2.3 集聚系数
•     1.2.4 节点的度
•     1.2.5 节点间路径
•   1.3 无重复路径研究
•   1.4 信任传播研究
•   1.5 相似度研究
•   1.6 主要工作和结构安排
• 第二章 基于节点度的k阶无重复路径计算
•   2.1 引言
•   2.2 相关工作
•     2.2.1 深度优先策略
•     2.2.2 URW策略
• *策略'>    2.2.3 AA^*策略
•   2.3 节点度算法
•   2.4 仿真网络
•   2.5 实验仿真与结果分析
•     2.5.1 实验结果
•     2.5.2 结果分析
•   2.6 本章小结
• 第三章 基于最优路径的k阶无重复路径计算
•   3.1 引言
•   3.2 相关工作
•     3.2.1 宽度优先算法
•     3.2.2 矩阵幂估计算法
•     3.2.3 去环路径算法
•   3.3 k阶无重复路径算法
•   3.4 实验仿真与结果分析
•     3.4.1 实验结果
•     3.4.2 结果分析
•   3.5 本章小结
• 第四章 基于无重复路径的信任传播和相似度计算
•   4.1 引言
•   4.2 信任传播模型
•     4.2.1 Beth模型
•     4.2.2 概率传播模型
•     4.2.3 矩阵幂传播模型
•   4.3 基于无重复路径的信任传播
•   4.4 节点相似度计算
•     4.4.1 评价指标
•     4.4.2 基于无重复路径的相似度计算
•   4.5 仿真网络
•   4.6 实验仿真及结果分析
•   4.7 本章小结
• 第五章 总结与展望
•   5.1 研究结论
•   5.2 研究展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 硕士论文

作者: 周超杰

导师: 吴建设,唐磊

关键词: 复杂网络,无重复路径,节点度,信任传播,相似度

来源: 西安电子科技大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 西安电子科技大学

分类号: TP301.6;O157.5

DOI: 10.27389/d.cnki.gxadu.2019.002252

总页数: 85

文件大小: 5164K

下载量: 24