CORE Analysis for Efficient Shortest Path Traversal Queries in Social Graphs

The shortest path traversal queries require to scan the entire graph. The repetitive scans make it hard to answer the traversal queries in a reasonable time. Many traversal algorithms imply precomputed information to speed up the run-time query process. However, computing effective auxiliary data at pre-processing stage is still an active problem. It is useful but non-trivial to determine the occurrence of vertices or edges during shortest path computations. In this paper, we empirically analyze the continuous overlapped regions (COREs) to articulate the behavior of shortest path traversals on different real life social graphs. First, we compute the shortest paths between a set of vertices. Each shortest path is considered as one transaction. Second, we utilize the pattern mining approach to identify the frequency of occurrence of the vertices appear together. Further, we evaluate the results in terms of network properties, i.e. Degree distribution, average shortest path, and clustering coefficient, along with the visual analysis.