Dynamic Spectral Layout with an Application to Small Worlds

Spectral methods are naturally suited for dynamic graph layout be- cause, usually, moderate changes of a graph yield moderate changes of the layout. We discuss some general principles for dynamic graph lay- out and derive a dynamic spectral layout approach for the animation of small-world models. Article Type Communicated by Submitted Revised Regular paper P. Eades and P. Healy January 2006 January 2007 U. Brandes et al., Dynamic Spectral Layout, JGAA, 11(2) 325–343 (2007) 326 1 Introduction The main

problem in dynamic graph layout is the balance of layout quality and mental-map preservation [17]. Typically, the problem is addressed by adapting a static layout method such that it produces similar layouts for successive graphs. While these adaptations are typically ad-hoc [8], others [2, 1] are based on the formally derived method [3] of integrating difference metrics [5] into the static method. See [4] for an overview of the dynamic graph drawing problem. Spectral layout denotes the use of eigenvectors of graph-related matrices such as adjacency or Laplacian matrix as coordinate vectors. See, e.g., [15] for an introduction. We argue that spectral methods are naturally suited for dynamic graph layout both from a theoretical and practical point of view. Usually, moderate changes in the graph yield moderate changes of the layout, such that updates of spectral layouts can be computed efficiently. This holds in particular for small worlds (see Sect. 5), where the initial ring structure provides stability of the layout, see Fig. 9. This paper is organized as follows. In Sect. 2, we define some basic nota- tion and recall principles of spectral graph layout. The dynamic graph layout problem is reviewed briefly in Sect. 3, and methods for updates between layouts of consecutive graphs are treated in more detail in Sect. 4. In Sect. 5, our ap- proach for small worlds is introduced, and we conclude with a brief discussion in Sect. 6. 2 Preliminaries For ease of exposition we consider only two-dimensional straight-line represen- tations of simple, undirected graphs G = (V,E) with positive edge weights ω: E → R+, although most techniques and results in this paper easily carry over to other classes of graphs. In straight-line representations, a two-dimensional layout is determined by a vector parenleftbigp(v)parenrightbigv∈V of positions p(v) = parenleftbigx(v),y(v)parenrightbig. Most of the time we will reason about one-dimensional layouts x that represent the projection of p onto one component. For any graph-related matrix M(G), a (two-dimensional) spectral layout of G is defined by two eigenvectors x and y of M(G). For simplicity, we will only consider layouts derived from the Laplacian matrix L = L(G) of G, which is defined by elements Lv,w := summationtext u∈V ω(u,v) if v = w , −ω(v,w) if v negationslash= w , 0 otherwise. The rows of L(G) add up to 0, thus, the vector 1 := (1,...,1)T is a trivial eigenvector for eigenvalue...

Website: jgaa.info | Filesize: -
No of Page(s): 19
Download Dynamic Spectral Layout with an Application to Small Worlds.pdf