Requirements to methods of graph clustering at the aim of solving the shortest path problem

Abstract

In this paper we considered utilization of graph clustering results in scope of solving all-pairs shortest path problem by means of blocked all-pairs shortest paths algorithm with unequally sized blocks. We defined a set of requirements for the results of graph clustering based on the inner working of the blocked algorithm. We have done an analysis of two existing, well-known graph clustering algorithms (Walktrap and Spinglass) to verify if existing clustering algorithm can produce results consumable by blocked all-pairs shortest path algorithm with unequally sized blocks. Our experiments show, that both algorithms can be used to produce compatible results, however, in dif erent contexts.