图直径是图的一个非常重要的基本属性,代表了连通图中顶点间最短距离中最长者的长度,它度量了图的大小、稀疏性及延展性。由于传统的单机串行最短路径算法的高计算复杂度,随着数据规模的扩大,现有的串行计算算法在时间效率上存在巨大的挑战。其中一种解决方法是采用并行和近似计算,将计算任务分配给多个处理器并以精度换取更低的计算复杂度,这可以提升图直径计算的效率。而近来也相继提出了相关的并行图近似直径算法,其中基于随机K中心点聚类（RK-CC）的图简化算法获得了 O（log3n）-近似直径,并且具有较低的计算时间复杂度。但是对于同样的输入,它无法获得确定的输出结果,这不便于利用多次的结果对同个数据进行分析。并且在选择中心点进行图简化和计算近似直径时,没有考虑中心点对直径的影响,导致了近似直径误差较大的问题,因此基于RK-CC的图简化近似直径算法存在改进的空间。本文首先分析了基于RK-CC的图简化近似直径算法,发现随机选择中心点的方法会导致结果的不确定并使得近似直径误差较大。我们分析了在图简化中产生近似直径误差的原因:（1）中心点在簇集扩张和收缩的过程中,增大了原图顶点间最短路径的大小;（2）在利用直径近似公式计算时,中心点构建的簇集的半径会引起不必要的误差。因此我们认为通过选择合适的中心点,能够降低图简化算法得到的近似直径误差。为了在图简化近似直径算法中获取确定的近似直径结果,并且具有高效的效率和更高的精确度,我们结合图简化中簇集扩张的特性,利用顶点的一步邻居信息设计中心性度量方法limcluc,对顶点在图简化算法中的扩张效率和降低误差的能力进行度量;在对顶点完成度量之后,根据Top-K中心性选择策略,在每轮中心点选择中按照中心性从高到低依次选取K个顶点作为中心点,提出了基于Top-K中心点聚类（TK-CC）的图简化算法,使图简化算法能够提供确定的输出,并且在利用合适的顶点度量方法下能取得更低的近似直径误差。其次,在基于TK-CC的图简化算法中,中心点聚集导致在道路交通网络中存在簇集扩张效率不高,因此我们设计了基于裁剪的Top-K中心性选择策略,利用顶点的一步邻居信息对中心点聚集的情况进行裁剪,然后将裁剪后的Top-K中心性顶点作为中心点,提出了基于裁剪的Top-K中心点聚类（rTK-CC）的图简化算法,这种方法提高了在道路交通网络图中的簇集扩张效率,同时保持相应的低近似直径误差。最后,我们利用真实大规模网络数据集进行实验,得出的结果验证了本文提出的基于TK-CC的图简化算法不仅能够提供确定的输出,在合理选择中心性度量方法的情况下,还能够降低近似直径误差。在基于TK-CC的方法中,本文提出的中心性度量方法limcluc在所有结果中拥有几乎最优的近似率以及比RK-CC更低的近似直径误差,对比RK-CC最多降低了 24.7%的近似率和95%的平均绝对误差;同时它在TK-CC的方法中获得了较好的扩张效率,对比RK-CC,在社交网络中最多降低了 15.9%的耗时,在道路交通网络中耗时最多只增加了 32.5%。在道路交通网络中,我们提出的rTK-CC对比TK-CC最多提升了 21.7%的簇集扩张效率,在商图规模较小时能够有效降低执行时间,同时保持了与TK-CC相近的近似直径准确率和稳定性。