GPPR: Geo-distributed Personalized PageRank Algorithm

Personalized PageRank, as a basic algorithm in large graph analysis, has a wide range of applications in search engines, social recommendation, community detection, and other fields and it has been a hot problem of interest to researchers. The existing distributed personalized PageRank algorithms assume that all data are located in the same geographic location and the network environment is the same among the computing nodes where the data are located. However, in the real world, these data may be distributed in multiple data centers across continents, and these geo-distributed data centers are connected to each other through WANs, which are characterized by heterogeneous network bandwidth, huge hardware differences, and high communication costs. Moreover, the distributed personalized PageRank algorithm requires multiple iterations and random walk on the global graph. Therefore, the existing distributed personalized PageRank algorithms are not applicable to the geo-distributed environment. To address this problem, the GPPR (Geo-distributed Personalized PageRank) algorithm is proposed in this paper. The algorithm first preprocesses the big graph data in the geo-distributed environment and maps the graph data by using a heuristic algorithm to reduce the impact of network bandwidth heterogeneity on the iteration speed of the algorithm. Secondly, GPPR improves the random walk approach and proposes a probability-based push algorithm to further lower the number of iterations required by the algorithm by reducing the bandwidth load of data transmission between working nodes. We implement the GPPR algorithm based on the Spark framework and build a real geo-distributed environment in AliCloud to conduct experiments comparing the GPPR algorithm with several existing representative distributed personalized PageRank algorithms on eight open-source big graph datasets. The results show that the communication data volume of GPPR is reduced by 30% on average in the geo-distributed environment compared with that of other algorithms. In terms of algorithm running efficiency, GPPR improves by an average 2.5 factor compared with other algorithms.