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

来源：计算机研究与发展杂志2015年第7期北京时间：

作者：王春磊,张岩峰,鲍玉斌,赵长宽,于戈,高立新,

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

关键词：异步计算, 迭代计算, Asyn-SimRank算法, 相似度, 大数据, MapReduce模型, Maiter框架,