A Force-directed Graph Drawing based on the Hierarchical Individual Timestep Method

Authors: T. Matsubayashi, T. Yamada

Abstract:

In this paper, we propose a fast and efficient method for drawing very large-scale graph data. The conventional force-directed method proposed by Fruchterman and Rheingold (FR method) is well-known. It defines repulsive forces between every pair of nodes and attractive forces between connected nodes on a edge and calculates corresponding potential energy. An optimal layout is obtained by iteratively updating node positions to minimize the potential energy. Here, the positions of the nodes are updated every global timestep at the same time. In the proposed method, each node has its own individual time and time step, and nodes are updated at different frequencies depending on the local situation. The proposed method is inspired by the hierarchical individual time step method used for the high accuracy calculations for dense particle fields such as star clusters in astrophysical dynamics. Experiments show that the proposed method outperforms the original FR method in both speed and accuracy. We implement the proposed method on the MDGRAPE-3 PCI-X special purpose parallel computer and realize a speed enhancement of several hundred times.

Keywords: visualization, graph drawing, Internet Map

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084524

References:

[1] Eades, P.: A heuristic for graph drawing, Congresses Numerantium, 42, 149-160 (1984)
[2] Kamada, T., and Kawai, S.: An algorithm for drawing general undirected graphs, Information Processing Letters, 12, 31, 7-15 (1989)
[3] Fruchterman, T. M. J., and Reingold, E. M.: Graph Drawing by Forcedirected Placement, Software - Practice and Experience, 11, 21, 1129- 1164 (1991)
[4] Quigley, A., and Eades, P.: FADE:Graph Drawing, Clustering, and Visual Abstraction, Proceedings of Graph Drawing 2000, Lecture Notes in computer Science, 1984, 183-196 (2001)
[5] Barnes, J., and Hut, P.: A hierarchical O(N logN) force-calculation algorithm, Nature, 04, 324, 446-449 (1986)
[6] Adai, A. T., Date, S. V.,Wieland, S., and Marcotte, E. M.: LGL: Creating a map of protein function with an algorithm for visualizing very large biological networks. Journal of Molecular Biology, 340(1):179?190, June 2004.
[7] Lyon, B.: The Opte Project(2005) http://www.opte.org/
[8] Ahmad, A., and Cohen, L.: A numerical integration scheme for the Nbody gravitational problem, Journal of Computational Physics, 12, 389 (1973)
[9] McMillan, S. L. W.: The Vectorization of Small-N Integrators, Lecture Notes in Physics, 267, 156 (1986)
[10] Makino, J.: A Modified Aarseth Code for GRAPE and Vector Processors, Publications of the Astronomical Society of Japan, 43, 859-876 (1991)
[11] Narumi, T., Ohno, Y., Okimoto, N., Koishi, T., Suenaga, A., Futatsugi, N., Yanai, R., Himeno, R., Fujikawa, S., Ikei, M., and Taiji, M.,: A 55 TFLOPS Simulation of Amyloid-forming Peptides from Yeast Prion Sup35 with the Specialpurpose Computer System MDGRAPE-3, Proceedings of the SC06 (High Performance Computing, Networking, Storage and Analysis), CDROM, Tampa, USA, Nov. (2006)