基于k-shell的多维网络最短路径近似算法研究

作     者：严沛 

作者单位：辽宁大学 

学位级别：硕士

导师姓名：张昕

授予年度：2019年

学科分类：07[理学] 08[工学] 070104[理学-应用数学] 0701[理学-数学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：复杂网络 多维网络 k-shell 节点回退值 双向剪枝策略 

摘      要：随着社会的发展和研究的深入,对复杂网络的研究逐渐从单维网络转向多维网络,多维网络节点之间的连边包含多个维度的权值,多维网络最短路径的计算需要综合考虑多个维度上的权值,通过给定的评分函数计算得到路径的具体代价。单维网络最短路径的计算方法都基于Dijkstra算法的子路径性质,而若多维网络的评分函数是非线性函数,子路径性质并不适用,因此单维网络最短路径算法并不适用于多维网络。目前对多维网络最短路径的研究依然较少,现有方法的适用性较差,计算效率和准确率不能满足大规模多维网络最短路径计算的需求。本文在现有研究的基础上,提出了一种基于k-shell的多维网络最短路径近似算法。算法根据节点k-shell值将网络分为高层和低层区域,搜索过程中使用双向搜索树进行搜索,利用节点k-shell值控制搜索方向以及两棵搜索树的切换,从低层向着高层方向交替搜索节点对之间的最短路径,当搜索队列都为空或者都到达高层区域时搜索过程结束,并选择一条评分函数下代价最小的路径作为近似最短路径。算法向着当前节点的高k-shell值邻居节点方向进行搜索,同时综合考虑节点k-shell值以及邻居节点k-shell值对节点的影响,提出了节点回退值来衡量节点在最短路径搜索过程中的重要性,通过节点回退值进行适当的回退搜索提高算法的准确率,并且通过调节回退阈值,使算法满足不同的计算效率和准确率的需求,使算法适用于不同类型的网络。在最短路径搜索过程中给出一种快速计算初始搜索阈值的方法,并且基于双向搜索过程给出一种适合本文算法的双向剪枝策略,更加快速准确地剪除不可能出现在最短路径上的子路径,提高算法的计算效率。本文首先在相同网络上验证了在最短路径搜索过程中根据节点回退值进行回退搜索可以有效地提高算法的准确率,然后在不同类型的复杂网络上验证了本文算法对不同类型的复杂网络有很好的适用性,最后将本文算法与同类算法进行对比实验分析,验证了本文算法在多维网络最短路径计算中具有较高的计算效率和准确率。