温菊屏，林冬梅

（1.佛山科学技术学院 电子与信息工程学院，广东 佛山528000；2.佛山科学技术学院 信息与教育技术中心，广东 佛山528000）

0 引 言

图聚类算法是一种分析社会关系网络的有效算法，它可以发掘社会关系网络中的子团体，对社会关系网络的分析有重大意义，包括提高互联网信息服务，发掘网络舆论导向等作用。图聚类有很多不同的方式，比较具代表性的有：Markov聚类［1］、谱聚类、基于密度的聚类［2］和基于划分的聚类［3］等。

本文主要研究基于划分的聚类算法，此算法使用距离来衡量点与点之间的相异度。由于社会关系网络图中的节点没有坐标值，所以只能采用具有坐标值无关特性的距离算法进行聚类，比如最短路径算法和随机漫步算法［4］等。其中，最短路径算法问题是图论研究中的一个经典算法问题，是本文研究的主要内容。

最短路径算法旨在寻找图（由结点和路径组成）中两结点之间的最短路径。其中，Dijkstra算法以及A＊［5］搜索都是很有代表性的最短路径算法，由于要遍历计算的节点很多，所以效率低。最短路径算法在交通网络中应用很广泛，比如google map、GPS，用户给定两个地点a、b，要求计算出这两点之间的最短路径，由于是在线查询，没有预存储阶段，所以在线查询时间很长。为了快速响应用户的请求，需要有更为高效的算法计算两点之间的距离。

文献 ［6］中提到了参考节点嵌入算法思想，该算法是从所有点中选择比较少量的参考点，预先将参考点与其他点之间的距离计算存储下来，在需要计算两点距离时，通过预先存储的距离，计算出两点之间近似估算距离。……