图是一种非线性数据结构,可以表示现实世界中许多关系复杂的数据,比如现实地图、神经元网络、社交网络等。偏心率可以用来描述图中顶点的重要程度,一个顶点偏心率指的是从该顶点出发的最长最短路径的长度,得知顶点的偏心率有助于分析图的其他特征,比如图的中心性、半径和直径等。本文针对现有偏心率求解算法存在的索引构建代价高的问题展开研究,研究内容如下。首先,提出基于子图划分的索引构建策略及相应的算法。和已有算法在全局图上构建索引不同,本文算法的基本思想是,首先选定K个顶点,以这K个点为中心向外扩展,直到覆盖图中所有的顶点,就可得到以这K个点为中心、互不相交的子图。对每个子图,构建基于中心顶点的索引,用于计算偏心率时的剪枝条件。其次,基于子图划分的思想,提出了相应的偏心率求解算法Ecc Comp。该算法利用子图划分所构建的参考顶点索引,先得出待计算顶点x对于每个子图的局部偏心率范围,然后基于索引进行剪枝,在较小范围内计算偏心率。该算法在一定程度上减少了平均查找代价,提高了计算效率。进一步,提出了单支路径顶点合并策略以及参考顶点索引优化策略,进一步降低了索引规模,改进了偏心率计算的效率。最后,在多个真实数据集上进行实验。实验结果从偏心率计算的总时间、参考顶点索引平均查找长度和参考顶点索引规模等方面验证了本文提出算法的高效性。