动态复杂网络的最短路径研究

论文摘要

随着信息技术的发展,人类社会已经逐步进入到复杂网络时代,现实中的各种人际关系、道路交通、互联通信等网络都可以抽象成为复杂网络,而随着复杂网络研究的逐步深入,大量的网络特性被逐步发现,而与这些网络特性相关问题的分析和研究很多都与网络的最短路径有关,例如节点的介数、网络的平均半径、网络的信息传播、城市道路的导航、疾病的传播、人际关系之间的影响等等问题都是与网络的最短路径息息相关的。复杂网络的最短路径研究目前主要针对基于静态网络和基于动态网络2个方面进行求解,基于静态网络的最短路径研究已经具有很多经典算法,如Dijkstra算法、Floyd-Warshall算法、Bellman-Ford算法等,虽然可以准确的求得网络的最短路径,但时间复杂度高,并不适用于规模巨大的复杂网络的最短路径的求解,更不能利用其对复杂网络的特性如介数中心性、接近中心性等以最短路径为基础的网络特性进行求解。随后衍生出了一系列适合大规模复杂网络最短路径的求解方法,如限制区域搜索方法、目标引导方法、层次划分方法、基于局部区域中心点等方法对大规模复杂网络进行简化并近似求解最短路径,在基于静态网络的最短路径求解方面取得的较好的研究成果。而在现实世界中,随着网络的规模日益增大,复杂网络越来越体现出动态性、随机性等特性,为了更好地解决动态复杂网络的最短路径求解及与其相关的网络特性求解,近年来涌现出一系列的近似求解算法。具有代表性的如动态最短路径树算法、分布式算法、基于图索引结构算法、启发式算法、改进的A*算法等,但是这些算法并没有完全考虑到复杂网络的自身结构特性,计算复杂度较高。本文在已有算法的基础上,提出了改进的动态复杂网络最短路径近似算法,结合节点的度和聚集系数,重新定义了局部区域中心点的度量方法,以便更准确的获取到局部区域中心点。同时,提出了区域的中继节点概念,可以对网络动态变化中的划分区域进行有效的分裂或者融合,减少了网络局部动态变化对整体变化的影响,加速了最短路径的近似求解过程。本文通过生成不同规模的模拟网络,对提出的算法进行了实验和分析,通过对比本文提出的最短路径近似求解方法与改进前的近似求解方法,可知本文提出的方法准确程度更高;同时,通过与具有代表性的动态复杂网络最短路径近似算法的实验对比,可知本文提出的方法计算复杂度较低,同时可以取得较好的最短路径近似结果。

论文目录

文章来源

类型: 硕士论文

作者: 郭阳

导师: 张昕

关键词: 复杂网络,动态区域划分,最短路径,节点重要性,近似计算

来源: 辽宁大学

年度: 2019

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

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

单位: 辽宁大学

分类号: TP301.6;O157.5

总页数: 70

文件大小: 2317K

下载量: 188

相关论文文献

• [1].营销的最短路径[J]. 销售与管理 2019(10)
• [2].动态网络中一种高效的最短路径树维护算法[J]. 计算机工程 2017(01)
• [3].稳定的最短路径树及其构造算法[J]. 计算机工程与科学 2016(03)
• [4].道路突发中断情况下实时最短路径快速求解算法[J]. 计算机应用 2016(S1)
• [5].“最短路径”问题的探究与思考[J]. 考试与评价 2017(01)
• [6].勾股定理、方程如影随形[J]. 中学生数理化(八年级数学)(配合人教社教材) 2017(03)
• [7].确定最短路径不能想当然[J]. 中学生数理化(八年级数学)(配合人教社教材) 2017(03)
• [8].谢谢你,姑,妈[J]. 意林(少年版) 2013(14)
• [9].基于规则的最短路径查询算法[J]. 软件学报 2019(03)
• [10].面向室内实时路径规划的最短路径缓存算法[J]. 电子技术与软件工程 2019(22)
• [11].基于遗传算法的送外卖最短路径研究[J]. 科技传播 2016(06)
• [12].初中数学中“平面展开最短路径”教学反思[J]. 中学生数理化(教与学) 2014(12)
• [13].最短路径[J]. 同学少年 2012(06)
• [14].基于复杂网络的城市公交网络的度和最短路径相关性的分析[J]. 科技通报 2013(02)
• [15].面向大规模道路网的最短路径近似算法[J]. 测绘学报 2019(01)
• [16].基于最短路径的求解与创新[J]. 科技创新导报 2012(29)
• [17].一种高效的最短路径树动态更新算法[J]. 计算机科学 2011(07)
• [18].适合复杂网络分析的最短路径近似算法[J]. 软件学报 2011(10)
• [19].具有多条最短路径的最短路问题[J]. 哈尔滨工业大学学报 2010(09)
• [20].基于扇形搜索的最短路径射线追踪方法探讨[J]. 红水河 2019(05)
• [21].道路交通网络最短路径关键转向研究[J]. 公路 2018(09)
• [22].一种个性化城市多目标最短路径随机优化算法[J]. 中国科技论文 2016(07)
• [23].化学GPS能快速找出两点间最短路径 速度快过电子GPS[J]. 黑龙江科技信息 2014(30)
• [24].这篇文章的解答值得商榷[J]. 中学生数学 2011(04)
• [25].城市交通时间最短路径计算模型及应用仿真[J]. 计算机仿真 2014(01)
• [26].交互网络上任意节点对的最短路径集解法[J]. 海军工程大学学报 2011(04)
• [27].一种灾害救援最短路径动态算法[J]. 沈阳建筑大学学报(自然科学版) 2011(05)
• [28].军事通讯网络的最短路径研究分析[J]. 数码世界 2019(07)
• [29].独立多约束最短路径选择[J]. 江西理工大学学报 2011(03)
• [30].基于人工免疫的N最短路径检索算法[J]. 山东大学学报(理学版) 2017(09)

标签：复杂网络论文;  动态区域划分论文;  最短路径论文;  节点重要性论文;  近似计算论文;