Analysis of Subgraph-Centric Distributed Shortest Path Algorithm

Path-based graph algorithms are key building blocks for several link prediction and spatial mining applications. As the sizes of social, transport and communication networks expand, performing scalable traversal algorithms like SSSP are critical. While there is heightened interest in vertex-centric platforms for scalable graph analysis, there is limited literature on understanding the behavior of distributed algorithms designed using them. Consequently, it is often difficult to offer a tight bound on their algorithm´s complexity. Here, using SSSP as a canonical algorithm on a sub graph-centric abstraction, we perform an algorithmic analysis of its characteristics using meta-graph sketches. We then analyze its empirical performance using real-world graphs to correlate the expected and observed outcomes. Our analysis shows that the runtime behavior of the SSSP algorithm meets the expected behavior, and confirms the bounds on the number of times Dijkstra´s is performed, based on the traversal visit of the meta-graph.