A fast estimation of shortest path distance for power-law network predominant cloud service

The estimation of the shortest path between two vertices in a network graphs is an important issue for many applications in the real world, which may be road networks, social collaboration networks, biological networks and so forth. The short response time, the less space cost and the high accuracy are three critical evaluation metrics in the approximate calculation of the shortest path. To achieve a quick and accurate calculation of an approximate shortest path distance, the typical method that takes a non-trivial approach calculates the distance between every pair of vertices in advance and records the calculation results with an n×n matrix, where n is the number of vertexes in the network graph. Unfortunately, it hard for this method function because it is difficult to sustain the huge amount of storage space and time consuming preprocessing for the big size of the network graph in practice. Unlike many efforts that have been made to minimize the costs of time and space in enhancing the accuracy of the shortest path calculation, this paper proposes an estimation scheme of the shortest path calculation for power-law graphs, due to the fact that many networks in the real applications are power-law networks. The theoretical analysis indicates that the schema is successfully optimized so that the query time can be an approximation constant and the calculation result of the approximate shortest path distance is almost 2 to 3 times as long as the actual shortest path distance between a pair of vertices. A simulation experiment also validates the analysis and demonstrates the feasibility of the proposed scheme.

I. Introduction

In most cases, cloud computing has the advantage over handling data intensive applications as large size graph processing. With storage becoming cheaper and the need to store and retrieve large amounts of graph data, developing systems to handle trillions of graph data requiring tera/peta bytes of disk space is no longer a distant prospect. As yet, many efforts have been done in this aspect. Lichtenwalter presented the design and implementation of a master-worker framework for easily computing distributed graph issues [1]. The framework automatically divides and distributes the workload and manages completion using an arbitrary number of heterogeneous computational resources. Jiang described a system, Extended MATE or Ex-MATE, which supports this alternate API with reduction objects of arbitrary sizes [2]. He evaluated this system using three graph mining applications and compare its performance to that of PEGASUS, a graph mining system implemented based on the original map-reduce API and its Hadoop implementation. Yang proposed a unified distributed method in solving some critical graph mining problems on top of a cluster system with the help of MapReduce [3]. These problems include graph transformation, sub-graph partition, maximal clique enumeration, connected component finding and community detection. Liu et. al. used Hadoop, an open source implementation of MapReduce, to conduct a series of analyses on large-scale social networks including several distributions, clustering coefficient and diameter [4].