Laplacian-based Dynamic Graph Visualization

In this work, we propose a new strategy for preserving the mental map of the dynamic graph drawing. Based on Laplacian constrained distance embedding(LCDE), our strategy contains two steps for each time step. First, a static graph layout algorithm is applied to a snapshot, disregarding the graph layout results before it. After that, we obtain an initial layout with aesthetic. The second step is shape adjustments. By running LCDE algorithm, we refine the initial layout and force nodes to generate overall shapes appeared in the previous snapshot, so that users can easily build connections of the same graph component between adjacent snapshots.

Comparing with existing dynamic graph layout algorithms, our strategy has two distinct advantages. First, our LCDE method is a post-processing step, so that our strategy can fully take advantage of the rich set of existing static layout algorithm. Second, our stragety maintains the graph component shapes instead of the absolute positions of nodes. Thus nodes have more freedom to move during the adjustment, and users still can easily recognize the layout result.

The example is showed to demonstrate the effectiveness of our algorithm.

The case is Newcomb`s fraternity data[1], which represents friendship relations between college students. The figure is the comparison between our method (the top) and Frishman et al.`s algorithm[2](the bottom). From the figure, we can see that our layout is significantly more stable than Fishman et al.`s result. For example, in the whole sequence, the green subgrph is kept very stable by our algorithm, despite all the edges added to it or removed from it. In contract, the layout changes dramatically in Frishman et al.`s result. For the orange subgraph, it is clear that the T3 is the turning point for our algorithm and Frishman et al.`s. However, the change in our layout is considerably smoother, as the contour shrinks smoothly. In contract, the orange subgraph in Frishman et al.`s result is abrupt and hard to track.


[1]T. M. Newcomb. The acquaintance process. In Holt, Rinehart and Winston, 1961

[2]Y. Frishman and A. Tal. Online dynamic graph drawing. IEEE Transactions on Visualization and Computer Graphics, pages 727–740, 2008.



Limei Che, Jie Liang, Xiaoru Yuan, Jianping Shen, Jinquan Xu, and Yong Li. Laplacian-based Dynamic Graph Visualization. Proceedings of IEEE Pacific Visualization Symposium (PacificVis 2015), pages 69-73, (Notes), Hangzhou, China, Apr. 14-17, 2015.