Asyn-SimRank一种异步执行的大规模SimRank算法.PDF

第??卷 第?期 计 算 机 学 报 Vol. ?? No. ? 20??年？月 CHINESE JOURNAL OF COMPUTERS ???. 20?? Asyn-SimRank:一种异步执行的大规模SimRank 算 法 1) 2) 2) 1) 3) 王春磊 , 张岩峰 , 赵长宽 于戈 , Lixin Gao 1) (东北大学计算机软件与理论研究所，沈阳 中国 100819) 2) (东北大学计算中心，沈阳 中国 100819) 3) (University of Massachusetts，Amherst 美国 01002) 摘要 SimRank 算法利用网络结构来评估网络中任意两点的相似性，它被广泛应用于社交网络和链接预测等诸多领域中。近 年来，随着大数据技术的发展，SimRank 算法处理的数据不断增大，人们利用MapReduce 等分布式计算模型设计实现分布 式的大规模SimRank 算法来适应大数据处理的需求。但是，由于SimRank 算法包含开销较大的迭代过程，每次迭代之后都 需要一个全局同步，且每次迭代的计算复杂度高、通信量大，使得 SimRank 算法的分布式实现效率很低。本文提出 Asyn-SimRank 算法，该算法异步执行 SimRank 的核心迭代过程，避免了大规模分布式计算中的大量同步开销。并且 Asyn-SimRank 算法采用累积- 迭代的方式完成迭代计算，可以有效降低计算量并减少通信开销。本文严格证明了 Asyn-SimRank 算法的正确性和收敛性，分析了其优点，并且在支持异步迭代的分布式框架 Maiter 上实现了 Asyn-SimRank 算法。实验结果显示Asyn-SimRank 算法大大加速了算法收敛，相比较于传统的Hadoop 上实现的SimRank 算法，Asyn-SimRank 最高可加速130 倍。 关键词 异步计算；迭代计算；Asyn-SimRank ；相似度；大数据；MapReduce ； 中图法分类号 TP391 Asyn-SimRank: An Asynchronous Large-Scale SimRank Algorithm Wang Chunlei1) , Zhang Yanfeng2) , Zhao Changkuan2),Yu Ge1) , GAO Lixin3) 1) (Northeastern University Institute of Computer Software and Theory, Shenyang China 100819) 2) (Northeastern University Computer Center, Shenyang China 100819) 3)(University of Massachusetts，Amherst USA 01002) Abstract SimRank algorithm, which exploits network structure to measure the similarity between node pairs, has been widely used in many areas, such as online social networks and link prediction. In recent y