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