Abstract: Protein-protein interaction network refers a new research area of computer science.The distance metric in such setting is redefined by the network distance，which has to be computed by the expensive shortest path distance over the network．The existing methods are not applicable to such cases．Therefore，by exploiting unique features of networks，a new clustering algorithm is presented，which uses the information of nodes and edges in the network to prune the search space and avoid some unnecessary distance computations．The experimental results indicate that the algorithm achieve high efficiency for clustering nodes in real protein-protein interaction network.

Key words: data mining, protein-protein interaction networks, clustering algorithm, network distance, shortest path

摘要： 蛋白质相互作用网络是计算机科学技术的一个新研究领域。蛋白质相互作用网络中结点之间的距离度量需要通过基于网络的最短路径距离来重新定义，其计算代价高，这使得已有的基于欧几何距离的聚类算法不能直接运用到这种环境中。因此，通过蛋白质相互作用网络的特征提出了一种新的聚类算法。算法使用网络中的边和结点信息来缩减搜索空间，避免了一些不必要的距离计算。实验结果表明，算法对于真实的蛋白质相互作用网络中的结点聚类是高效的。

关键词: 数据挖掘, 蛋白质相互作用网络, 聚类算法, 网络距离, 最短路径