基于k-core分区域的复杂网络最短路径近似算法研究.pdf

申请辽宁大学硕士学位论文


基于 k-core 分区域的复杂网络
最短路径近似算法研究

Research On Approximate Shortest Path Algorithm
For Complex Network Based On k-core Region








作 者： 吕 剑
指导教师： 张 昕 副教授
专 业： 软 件 工 程
答辩日期： 二○一七年五月二十二日



二○一七年五月·中国辽宁
摘 要
摘 要
最短路径计算一直以来是复杂网络中重要的研究内容，近年来，随着研究
的日益深入，复杂网络中许多特征量的计算及问题的解决越来越多的依赖于最
短路径的计算。经典算法无论是在算法复杂度还是在效率上都已不适用于计算
具有大规模节点和连边的复杂网络，而目前一些常见近似计算算法也因其适用
性受限、算法效率与准确率不理想等因素而不能满足复杂网络最短路径计算的
应用需求，因此，近似算法要如何在计算延迟、内存占用率和准确性之间做到
最好的平衡及其如何增强网络适用性已经成为算法研究者们追逐的重要目标。
本文在相关算法研究的基础上，提出了基于 k-core 分区域的最短路径近似
算法。算法在真实的大规模社会网络、Web 社交平台网络及互联网络中保持了
较高的计算效率和准确率。算法首先基于 k-core 将网络水平划分成若干个 k-shell
子网络，然后根据节点 k-shell 值将包含不同节点重要性的 k-shell 子网络划分为
高层、边缘层和中间层三个区域，最后在计算最短路径时，对于高层区域，由
于节点规模较小且连边比较密集，故精确计算其所有节点对的最短路径；对于
边缘层区域，节点度比较小，依据 k-shell 作为节点重要性，每次搜索只搜索 k-shell
值大于等于当前节点的邻居节点，达到限制节点搜索区域的目的；对于中间层
区域，由于所包含 k-shell 子图之间的连边密集，故对 k-shell 子网内部节点进行
超点聚合，搜索时只利用超点的中心节点与其它区域节点的连边关系已达到提
高搜索效率的目的，其搜索过程同边缘层区域。算法使用 k-core 作为网络划分
及搜索目标引导依据更具一般性，利用超点聚合处理 k-shell 子网大幅降低了路
径搜索中遍历节点的规模，并且合理使用预处理、双向搜索树和优先队列技术
对路径搜索过程进行优化和加速，大大提高了算法的计算效率和准确率。
本文使用现实中不同规模大小的网络数据集，对所述算法进行了实验和分
析，实验数据表明算法在网络适用性、计算效率和准确率上明显优于 CDZ 算法。
例如，在 com-DBLP 社区网络中（规模为约 30 万节点、100 万连边的无向图），
节点对最短路径的平均计算时间只需几十毫秒，正确率能够达到 99%；在不同
幂律指数的无标度网络仿真模型中，算法也表现出了非常好的适用性和效率。

关键词：复杂网络，最短路径，k-core，层次划分网络，目标引导
I
Abstract
ABSTRACT
The shortest path calculation has always been an important research