在基于图计算的数据分析应用中,如何衡量图中顶点之间的相似度是一个非常重要的课题,在很多领域有广泛的应用。SimRank是近年来比较流行的相似性度量,相比于其它相似度指标,它能更好地反映图的拓扑结构信息。然而它的计算代价较高,传统计算方法已经不适用于规模越来越大的图数据。另一方面,Spark作为一种分布式计算平台能够简化用户编写分布式应用的逻辑,自问世以来迅速在学术界和产业界得到广泛的使用。因此,基于Spark或类似平台设计高效的大规模图数据中点对SimRank相似度的分布式计算方法,有着重要的现实意义。本文针对上述问题展开了深入的研究,取得的主要成果有:1.针对单源点SimRank相似度计算问题,提出并实现了一种基于随机游走模型的分布式算法。算法通过减少随机游走的数量以及紧凑的中间数据表示来降低计算的时间和空间复杂度,通过将游走的匹配计算过程分发至整个集群达到高并行度,同时设计了动态规划技巧加速匹配过程。实验结果表明,算法将随机游走的数量降低了数百倍以上,同时表现出近乎线性的可扩展性。2.提出并实现了一种基于模块度优化的多层次分布式图划分方法,算法在划分过程中较好地保留了图中的稠密子结构,在考虑划分约束条件的情况下保证了顶点的均衡划分,并力求最小化各个分块之间的边割大小。实验结果表明,算法的划分质量可以媲美经典算法METIS,同时有较好的可扩展性。3.针对图中全点对相似度计算问题,提出并实现了一种基于分治思路的计算方法。该算法通过分别计算分块内点对的相似度以及分块本身的相似度,来计算所有点对的全局相似度。实验结果表明,本文的方法在有效性上完全可以媲美SimRank,但计算效率得到了数倍至数十倍(3-16倍)的提高。