基于EIN覆盖网的复杂网络最短路径近似算法

摘要

在网络规模远超出最短路径经典算法适用范围的情况下,最短路径近似算法成为有效的替代解决方案。针对现有近似算法存在的预处理阶段计算效率低、算法性能受网络规模影响较大等问题,提出一种基于EIN覆盖网络的大规模复杂网络最短路径近似算法。算法基于边递归网络(The network created by edge iterations, EIN)的生成和标号方式在实际复杂网络上抽象出具有确定性拓扑结构的标号覆盖网络,结合覆盖网络标号节点间确定的位置信息快速推导出实际复杂网络中最短路径的近似解,在确定性网络层面高效解决非确定性复杂网络的最短路径问题。真实网络数据集上的实验结果表明,所提方法在大规模复杂网络上能保证较高精确度的同时,大幅度降低计算成本。