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

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

Shortest Path Algorithm of Social Network Overlapping Nodes

By path analysis,the relationship and connecting characteristic in social networks can be discovered,especially,in criminal networks.In this paper,the community discovery algorithm is utilized to obtain the overlapping nodes and construct the hierarchical network model of real social network.And then,by considering the high clustering coefficient and power law distribution of social network,this paper proposes an overlapping-nodes-based hierarchic path algorithm,HOLN,in which the core node distances are used to stand for community space and the overlapping nodes are searched preferentially to simplify node traversal.By the comparison experiment in the scientific cooperation network,it is shown that HOLN algorithm can attain satisfactory performance on the both accuracy and efficiency.