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

International Journal of Electronics, Circuits and Systems, 1, 2, 17, 116-121 (2007) [PDF]
T. Matsubayashi, and 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 timestep, and nodes are updated at different frequencies depending on the local situation. The proposed method is inspired by the hierarchical individual timestep 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.

Introduction

In many scientific and engineering domains, complicated relational data structures are frequently represented by networks or, equivalently, graphs. For example, WWW (World Wide Web) sites are often represented by hyperlink networks, with pages as nodes and hyperlinks between pages as edges, the interactions between genes, proteins, metabolites and other small molecules in an organism are represented by gene regulatory networks, and the relationships between people and other social entities are characterized by social networks. This popularity is because network representations often provide important insights to researchers in understanding the intrinsic data structure with the help of some mathematical tools such as graph theory, as well as by examining an embedded layout in a low-dimensional Euclidean space. Embedding a graph in a low-dimensional Euclidean space, which is called graph-drawing, is especially useful when the graph is sparse as most of the real world graph data are.

In this paper, we propose a fast and efficient method for drawing undirected large-scale graph data based on the force-directed method proposed by Fruchterman and Rheingold (1991). In their method, an optimal layout is obtained by iteratively updating node positions to minimize the potential energy. Here, the all positions of the nodes are updated in every step at the same time. Our proposal, on the other hand, gives each node its own individual time and timestep, and nodes are updated with a different frequency depending on the local situation. The proposed method is inspired by the hierarchical individual timestep method used in astrophysical dynamics. We have implemented the proposed method on the MDGRAPE-3 PCI-X special purpose parallel computer, and succeeded in achieving a speedup of several hundred times. Thus, the proposed method with parallel processing enables us to visualize graphs that have more than 10^4 nodes N and edges E.

Opte project
This graph(?) is by far our most complex. It is using over 5 million edges and has an estimated 50 million hop count. We will be producing more maps like this on a dialy basis. We still have yet to fix the color system, but all in due time.
Graph Colors:

Asia Pacific - Red
Europe/Middle East/Central Asia/Africa - Green
North America - Blue
Latin American and Caribbean - Yellow
RFC1918 IP Addresses - Cyan
Unknown - White