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

发布时间：2024-05-18 03:50

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

【文章页数】：67 页

【学位级别】：硕士

【部分图文】：

图2-12005年互联网部分地图快照

第2章相关工作征。2.动态变化：复杂网络中随时会增加或删除节点或连边，导致复杂结构也随之改变。3.连接多样：节点之间的连边的权值存在差异，连边类型可分为有边。4.节点多样：现实生活中的任何一种实体都可以抽象为复杂网络中的，表示人际关系的复杂网络每个节点代表一个人，表示....

图2-2k-shell分解示意图

络节点重要性指标k-shell图论中的一个经典概念，是一种粗粒化的节点重要度值为1的节点开始，首先删除联通图中度值等于计算剩余子图中节点的度值（剩余子图可能不是一为0的孤立节点），若剩余子图中仍然存在度值等执行上述步骤，直到图中已经不再存在度值小于或节点无论度值是多少....

图2-3Twitter和YouTube的k-shell分布图

第2章相关工作k-shell被广泛地应用到寻找重要节点的各种研究中[31~34]。如MaksimKi人在文献[35]中提出了节点的重要性依赖于其在整个网络中的位置的思想复杂网络的k-shell属性进行研究，证明节点的k-shell值越大，则该节点越网络的中心，....

图2-2（a）为例，图中的节点3和16的度值都是7，这两个节点是整个

第2章相关工作k-shell被广泛地应用到寻找重要节点的各种研究中[31~34]。如MaksimKi人在文献[35]中提出了节点的重要性依赖于其在整个网络中的位置的思想复杂网络的k-shell属性进行研究，证明节点的k-shell值越大，则该节点越网络的中心，....

本文编号：3976411