基于重叠节点的社会网络最短路径算法

朱恺骋,　程　华

(华东理工大学信息科学与工程学院,上海 200237)



基于重叠节点的社会网络最短路径算法

朱恺骋,程华

(华东理工大学信息科学与工程学院,上海 200237)

通过路径发现和分析可以挖掘社会网络中人与人之间的关系及其连接特性,特别是在犯罪网络的应用中具有重要意义。通过社区发现算法获得社区间的重叠节点,并构造目标网络的分层网络模型; 基于社会网络的高聚集系数特性及幂律分布拓扑特征,提出了基于重叠节点的分层网络路径发现(HOLN)算法,以核心节点距离代替社区间距,优化路径搜索方向; 优先搜索重叠节点,简化对节点的遍历,实现源与目标间最短路径的快速发现。实验结果表明,本文提出的HOLN算法在计算精度和运行效率上都有令人满意的表现。

社会网络; 最短路径; 重叠节点; 分层网络

面向社会网络的挖掘和分析是目前的研究热点,通过路径的发现和分析可以挖掘社会网络中人与人之间的关系及其连接特点,特别是在恐怖袭击网络、犯罪网络中的应用中具有重要意义。最短路径算法是路径发现的基础算法,在一定网络规模下具有高精度、高复杂度的特点。互联网环境下社会网络往往具有较大的规模,导致经典算法由于计算复杂度急剧升高难以有效运用,可采用优化算法结构的方法降低算法的计算复杂度或采用启发式方法限定搜索空间获得近似计算最短路径。

CDZ算法[1]基于实际网络的拓……