Asyn-SimRank:一种可异步执行的大规模SimRank算法

SimRank算法利用网络结构来评估网络中任意2点的相似性,它被广泛应用于社交网络和链接预测等诸多领域中.近年来,随着大数据技术的发展,SimRank算法处理的数据不断增大,人们利用MapReduce等分布式计算模型设计实现分布式的大规模SimRank算法来适应大数据处理的需求.但是,由于SimRank算法包含开销较大的迭代过程,每次迭代之后都需要一个全局同步,且每次迭代的计算复杂度高、通信量大,SimRank算法不能在分布式环境下高效地实现.1)提出Asyn-SimRank算法,该算法采用迭代-累积的方式完成迭代计算,异步执行SimRank的核心迭代过程,避免了大规模分布式计算中的大量同步开销,同时有效降低计算量并减少通信开销;2)提出关键点优先调度计算,提升了AsynSimRank算法的全局收敛速度;3)证明了Asyn-SimRank算法的正确性和收敛性以及关键点优先调度计算的有效性;4)支持异步迭代的分布式框架Maiter上实现了Asyn-SimRank算法.实验结果显示,相比较于Hadoop,Spark上实现的SimRank算法和Delta-SimRank算法,Asyn-SimRank算法大大提升了算法的计算效率,加速了算法收敛.