基于随机游走路径的分布式SimRank算法  

Distributed Sim Rank Algorithm Based on Random Walk Path

作　　者：刘恒[1] 寇月[1] 申德荣[1] 王泰明[1] 于戈[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110004

出　　处：《计算机科学与探索》2014年第12期1422-1431,共10页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金;国家重点基础研究发展计划(973计划);中央高校基本科研业务费专项基金;高等学校博士学科点专项科研基金;教育部-英特尔信息技术专项科研基金~~

摘　　要：SimRank算法是一种常用的相似性度量模型,它基于图的拓扑结构信息来衡量任意两个对象之间的相似程度。随着数据规模的不断增大,集中式SimRank算法已不适用,而已有的分布式Sim Rank算法在运行效率和扩展性等方面存在缺陷。针对上述问题,提出了一种两阶段的基于随机游走路径的分布式Sim Rank算法。第一阶段基于BSP(bulk synchronous parallel)模型建立随机游走路径索引信息,支持新路径的动态添加,并通过阈值过滤尽可能减少生成路径的数量;第二阶段利用第一阶段生成的索引信息,提出了基于MapReduce的分布式SimRank算法。最后,通过实验验证了算法的可行性和有效性。SimRank is a widely used model for computing similarity, it measures similarity between objects based on graph topology. With the rapid increase of data, the way of centralized SimRank is not applicable and current distributed SimRank approaches have some drawbacks in efficiency and scalability. This paper presents a two-stage distributed SimRank algorithm based on random walk path. The first stage is data preprocessing and a Find-K-Paths algorithm based on BSP （bulk synchronous parallel） model is proposed. The algorithm can effectively build the index information of random walk path and support the dynamic adding of new paths. The number of the generated paths can be reduced by threshold filtering. In the second stage, based on the index information, a distributed SimRank algorithm is proposed under MapReduce. The experiments demonstrate the feasibility and effectiveness of the proposed algorithm.

关 键 词：分布式SimRank 随机游走路径 BSP模型 MAPREDUCE 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]