刘 冬，杜 明，王志军，周军峰

(东华大学 计算机科学与技术学院，上海 201620)

0 引言

在无向图G=(V,E)中，任意两个顶点u、v间的最短路径dist(u,v)指的是从u到v的路径的最小长度。从u出发的一条最长最短路径则是顶点u的偏心率，得知顶点的偏心率有助于分析图的其他特征，比如图的中心性、半径和直径等。顶点的偏心率越小，它在图中的中心性越高，表示该顶点距离其他顶点更近。在一些实际的应用场景里，偏心率求解是十分重要的，比如寻找社交网络中有影响力的人、流行病关系网络中的关键顶点或网络拓扑图中的重要站点等。

现有偏心率求解的算法主要分为近似算法[1-5]和精确算法[6-13]。针对精确算法，文献[13]提出了ECC算法，该算法在图中设置了参考顶点池，并构建参考顶点的全局BFS索引，计算顶点x的偏心率时，选取距离x最近的参考顶点，然后按照该参考顶点索引将所有顶点分为两个部分，最后分别计算出x对这两个部分的局部偏心率，局部偏心率的最大值则为x的偏心率。该算法虽然避免了使用大量的BFS遍历来求解偏心率，但由于其索引构建代价高和顶点计算规模大的问题，所以导致该算法在大图中计算效率较低。

针对上述算法中存在的问题，本文提出一种基于子图划分思想的偏心率求解算法。其主要思想是：首先选定K个参考顶点，将图划分为以这K个点为中心、互不相交的子图，并构建基于参考顶点的局部BFS索引。在计算前，利用顶点合并策略对图中的顶点进行合并以降低计算规模，并对参考顶点索引进一步优化。……