图作为一种表达对象与对象之间抽象关系的非线性数据结构,具有更加一般化的表达能力,在我们现实生活中扮演者重要的角色。近年来,随着互联网、云计算、物联网等技术的高速发展,数据增长的规模正在以前所未有的速度增加,“大数据”给各行各业带来了很大的机遇和挑战,同时图数据的规模也随着个性化推荐、信息检索、社交网络分析等应用的蓬勃发展变得越来越大。随着图数据规模的增大,人们发现庞大的图数据中蕴含着巨大的商业价值,基于图结构的各种互联网应用在近些年来层出不穷,在这些应用中,最典型和最基本的一类任务就是计算对象和对象之间的相似度。SimRank是一种非常流行的基于图拓扑结构信息来衡量任意两个对象之间相似程度的模型,其核心的思想为:一个对象应该与自身最相似,如果两个对象都被相似的对象所引用,那么这两个对象也相似。然而,由于SimRank定义的递归依赖性,导致了SimRank计算的时空复杂度很大,图数据规模的增大在另一方面也使得问题更加突出。在本文中,我们主要针对单源节点SimRank的计算,即给定一个查询顶点,返回该节点与所有其他节点间的相似度,提出并实现了一种称之为ProbeWalk的高度并行的算法。我们的方法是基于随机游走模型改进并优化的,它由离线索引过程和在线查询过程组成。通过两个过程的组合可以将传统的双向随机游走过程转化为单向随机游走过程,索引阶段的处理需要消耗线性的时间和空间,而单源节点的查询阶段只消耗常数时间和空间。我们将算法部署到流行的分布式计算平台Spark上,结果表明了我们的算法具有较高的准确性和高效性。更进一步,相似度度量是协同过滤中的重要组成部分,为了解决传统的相似度度量方法在协同过滤中效果较差和SimRank不能直接应用于带权二部图的问题,本文进一步将SimRank++引入到协同过滤中,提出了一种基于两阶段蒙特卡洛模拟的随机游走方法,使其能够在较大规模协同过滤问题中进行应用。实验表明,基于SimRank++的协同过滤在MovieLens数据集上的评分预测误差要优于Pearson相关系数和Cosine相似度度量方法。