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

The Approximate Shortest Path Algorithm for Complex Networks Based on EIN Overlay Network

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

Abstract: The shortest path approximation algorithm becomes an effective alternative solution when the network scale is far beyond the scope of the classical shortest path algorithm. Aiming at the problems existing in the existing approximation algorithms, such as low computational efficiency in the preprocessing stage, and the algorithm performance that is greatly affected by the network scale, a shortest path approximation algorithm for large-scale complex networks based on EIN overlay network is proposed. The algorithm abstracts the label overlay network with deterministic topology structure on the actual complex network based on the generation and labeling method of EIN (The network created by edge iterations), and quickly deduces it by combining the location information determined between the label nodes of the overlay network. The approximate solution of the shortest path in the actual complex network can efficiently solve the shortest path problem of the non-deterministic complex network at the deterministic network level. The experimental results on real network datasets show that the proposed method can greatly reduce the computational cost while ensuring high accuracy on large-scale complex networks.