Fast Layout Computation of Hierarchically Clustered Networks: Algorithmic Advances and Experimental Analysis

Abstract

Fast computation of two-dimensional layouts of hierarchically clustered networks is a well-studied problem in graph visualization. We present algorithmic and experimental advances on the subject: (i) We propose a new drawing algorithm that combines space-filling and fast force-directed methods; it runs in O(nlogn+m) time, where n and m are the number of vertices and edges of the network, respectively. This running time does not depend on the number of clusters, thus the algorithm guarantees good time performances independently of the structure of the cluster hierarchy. As a further advantage, the algorithm can be easily parallelized. (ii) We present an experimental analysis aimed at understanding which clustering algorithms can be used, in combination with our visualization technique, to generate better quality drawings for medium and large networks with small-world and scale-free structure. As far as we know, no previous similar experiments have been done in this respect.