摘要:个性化PageRank作为大图分析中的基本算法,在搜索引擎、社交推荐、社区检测等领域具有广泛的应用,一直是研究者们关注的热点问题.现有的分布式个性化PageRank算法均假设所有数据位于同一地理位置,且数据所在的计算节点之间具有相同的网络环境.然而在现实世界中,这些数据可能分布在跨洲的多个数据中心中,这些跨域分布(cross-geo-distributed)的数据中心之间通过广域网连接,存在网络带宽异构、硬件差异巨大、通信费用高昂等特点.分布式个性化PageRank算法需要多轮迭代,并在全局图上进行随机游走.因此,现有的分布式个性化PageRank算法不适用于跨域环境.针对此问题,提出了GPPR (cross-geo-distributed personalized PageRank)算法.该算法首先对跨域环境中的大图数据进行预处理,采用启发式算法映射图数据,以降低网络带宽异构对算法迭代速度的影响;其次,GPPR改进了随机游走方式,提出了基于概率的Push算法,通过减少工作节点之间传输数据的带宽负载,进一步减少算法所需的迭代次数.基于Spark框架实现了GPPR算法,并在阿里云中构建真实的跨域环境,在8个开源大图数据上,与现有的多个代表性分布式个性化PageRank算法进行了对比实验.结果显示,GPPR的通信数据量在跨域环境中比其他算法平均减少30%.在算法运行效率方面,GPPR比其他算法平均提升了2.5倍.