Shortest path analysis for efficient traversal queries in large networks
Waqas Nawaz, Kifayat Ullah Khan, Young-Koo Lee · Contemporary Engineering Sciences · 2014
The shortest path problem is among the most fundamental combinatorial optimization problems to answer reach-ability queries. A single pair shortest path computation using Dijkstra’s algorithm requires few seconds on a very large social network. Many traversal algorithms imply precomputed information to speed up the runtime query process. However, computing eective auxiliary data in a reasonable time is still an active problem. It is hard to determine which vertices or edges are visited during shortest path traversals. In this paper, we provide an empirical analysis on how traversal algorithms behave on dierent real life networks. 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 coecient, along with the visual analysis.