Dynamic Spectral Layout of Small Worlds

Spectral methods are naturally suited for dynamic graph layout, because moderate changes of a graph yield moderate changes of the layout under weak assumptions. We discuss some general principles for dynamic graph layout and derive a dynamic spectral layout approach for the animation of small-world models. 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 the adjacency or Laplacian matrix as coordinate vectors. See, e.g., [15] for an introduction. We argue that spectral methods are particularly suited for dy- namic graph layout both from a theoretical and practical point of view, because moderate changes in the graph naturally translate into moderate changes of the layout, and updates can be computed efficiently. This paper is organized as follows. In Sect. 2, we define some basic notation and recall the 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 → IR+, 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 (pv)v∈V of positions pv = (xv,yv). 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 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(G) of G, which is defined by elements lscriptv,w = braceleftBiggsummationtext u∈V ω(u,v) ,v = w , −ω(v,w) ,v negationslash= w , The rows of L(G) add up to 0, thus, the vector 1 = (1,...,1)T is a trivial eigenvector for eigenvalue 0. Since L(G) is symmetric all eigenvalues are real, and the theorem of Gershgorin [13] yields, that the spectrum is bounded to the interval [0,g], for an upper bound g ≥ 0. Hence, the spectrum can be written as 0 = λ1 ≤ λ2 ≤ ... ≤ λn ≤ g with corresponding unit eigenvectors 1/√n = v1,...,vn. Based on the Laplacian, a spectral layout is defined as p = (v2,v3), where v2 and v3 are unit eigenvectors to the...

Website: www.informatik.uni-konstanz.de | Filesize: -
No of Page(s): 12
Download Dynamic Spectral Layout of Small Worlds - CiteSeer.pdf