Force-Directed Methods вЂ” Drawing Undirected Graphs Force-Directed Methods вЂў Use a physical analogy to draw graphs вЂ“ How does the natural вЂњdrawвЂќ a graph? вЂў View a graph as a system of objects with forces acting between them. вЂў Assumption: a balanced system gives a good layout вЂў Specifically, a system configuration with locally minimal energy: вЂ“ The sum of the forces on each object is zero. Force-Directed Methods вЂў Vertex: вЂ“ Object of the system; вЂ“ Interacting with each other based on вЂњsomeвЂќ force(s). вЂў Edge: вЂ“ A different type of object; вЂ“ Not interacting with each other; вЂ“ Add new force(s) to vertex object. вЂў Equilibrium configuration: the sum of forces on each vertex object is zero There are many force directed methods. In general, they have two parts: model & algorithm вЂў The model: a force system defined by vertices & edges вЂў The algorithm: a technique for finding an equilibrium state, that is the sum of the forces on each vertex is zero (force system); or вЂ“ a technique for finding a configuration with locally minimal energy (energy system) Spring Methods вЂў Vertex: вЂ“ Electrically charged particles; вЂ“ Repel each other. вЂў Edge: вЂ“ Spring that connect particles; вЂ“ Attraction force when longer than the natural length; вЂ“ Repulsion force when shorter than the natural length. 1. 2. A Larger Example В© Sander 6 Many Variations 1. 2. 3. 4. 5. 6. Spring & electrical force Barycenter method Force simulating graph theoretic distance Magnetic field General energy function Constraints 1. Springs & Electrical Forces вЂў Use a combination of spring & electrical forces вЂ“ Edge: modeled as spring вЂ“ Vertex: equally charged particles which repel each other вЂў The force on v : F(v) = ОЈ f u,v + ОЈ g u,v (u,v)пѓЋE (u,v)пѓЋVxV вЂў f u,v : force on v by the spring between u an v : follow HookвЂ™s law (proportional to the difference between the distance between u and v and the zeroenergy length of the spring) вЂў g u,v : Electrical repulsion exerted on v by vertex u : follow inverse square law вЂў d(p,q) : Euclidean distance between points p and q вЂў pv = (xv, yv): position of vertex v вЂў x component of the force on v пѓҐk ( u , v )пѓЋ E 1 uv ( d ( p u , p v ) пЂ l uv ) xv пЂ xu d ( pu , pv ) пЂ« пѓҐ ( u , v )пѓЋV п‚ґV xv пЂ xu 2 k uv ( d ( p u , p v )) 2 пѓ— d ( pu , pv ) lu,v : natural (zero energy) length of the spring between u and v : if the spring has natural length lu,v, no force is exerted; k1u,v : stiffness of the spring between u and v : the larger k1u,v , the more tendency for the distance between u and v to be close to lu,v. k2u,v : the strength of the electrical repulsion between u and v Aim of the force model design: вЂў Spring force: вЂ“ Ensure the distance between adjacent vertices u and v is approximately equal to lu,v. вЂў Electrical force: вЂ“ Ensure vertices not too close to each other. вЂў One may choose parameters luv k1u,v k2u,v to customize for specific applications. вЂў There are many technique to find an equilibrium configuration (or minimum energy). вЂў Simple algorithm вЂ“ Initially at random location вЂ“ At each iteration: вЂў Force F(v) on each vertex is computed вЂў Each vertex v is moved in the direction of F(v) by a small amount proportional to the magnitude of F(v) вЂ“ Stops when equilibrium is achieved or some conditions are met. вЂў Not the fastest, but allow smooth animation. вЂў Calculating attractive forces only between neighbors: O(|E|) вЂў Calculating repulsive forces between all pair of vertices: O(|V|2) вЂ“ Bottleneck of the algorithm in general Spring Embedder [Eades84] вЂњLogarithmic springвЂќ вЂў Rather than HookвЂ™s law, the spring force is calculated as: F (v ) пЂЅ k 1 uv пѓ¦ d ( pu , pv ) log пѓ§пѓ§ l uv пѓЁ пѓ¶ xv пЂ xu пѓ· пѓ· d(p , p ) u v пѓё вЂў Hook Law (linear) spring is too strong when the vertices are far Advantages вЂў вЂў вЂў вЂў вЂў вЂў вЂў вЂў вЂў Relatively simple & easy to implement Good flexibility Heuristic improvements easily added Handle domain constraints Smooth evolution of the drawing into the final configuration helps preserving the userвЂ™s mental map Can be extended to 3D Often able to display symmetries Works well in practice for small graphs with regular structure Show some clustering structure Disadvantages вЂў Slow running time вЂў Results are acceptable, but not brilliant вЂў Few theoretical results on the quality of the drawings produced вЂў Difficult to extend to orthogonal & polyline drawings вЂў Limited constraint satisfaction capability 2. Barycenter Method [Tutte60,63] вЂў Use springs with natural length 0, and attractive force proportional to the length вЂў Pin down the vertices of the external face to form a given convex polygon (position constraint) вЂў Let the system goвЂ¦ пѓҐ k 1 uv ( d ( p u , p v ) пЂ l uv ) ( u , v )пѓЋ E xv пЂ xu пѓҐ пЂ« d ( pu , pv ) ( u , v )пѓЋV п‚ґV вЂў luv = 0, k1u,v = 1, no electrical force пѓҐ ( u , v )пѓЋ E d ( pu , pv ) пѓ— xv пЂ xu d ( pu , pv ) пЂЅ пѓҐ (x ( u , v )пѓЋ E вЂў Trivial solution pv = 0 for all v v пЂ xu ) 2 k uv ( d ( p u , p v )) 2 пѓ— xv пЂ xu d ( pu , pv ) вЂў Partition V into two sets: fixed vertex (at least 3, nailed down) and free vertex вЂў To achieve equilibrium, choose pv so that Fx(v) = 0 for all free vertices; вЂ“ Similarly, choose pv so that Fy(v) = 0 for all free vertices. Therefore, Fx (v ) пЂЅ пѓҐ (x ( u , v )пѓЋ E v пЂ x u ) пЂЅ deg( x ) пѓ— x v пЂ пѓҐx wпѓЋ N 0 ( v ) вЂў Where deg(v) is the degree of v, вЂўN0(v): set of fixed neighbor of v; вЂўN1(v): set of free neighbor of v. * w пЂ пѓҐx uпѓЋ N 1 ( v ) u пЂЅ0 deg( v ) x v пЂ пѓҐ xu пЂЅ uпѓЋ N 1 ( v ) пѓҐ x w , deg( v ) y v пЂ * wпѓЋ N 0 ( v ) пѓҐ yu пЂЅ uпѓЋ N 1 ( v ) пѓҐ * yw wпѓЋ N 0 ( v ) вЂў The equations are linear. вЂў The number of equations and the number of unknownvariables are both equal to the number of free vertices. вЂў Solving them equals to placing each free vertex at the barycenter of its neighbours. вЂ“ So the name вЂ�barycenter methodвЂ™. Algorithm Barycenter-Draw Input: partition of V, V0: at least 3 fixed vertices V1: set of free vertices Strictly convex polygon P with V0 vertices Output: position pv 1. Place each vertex u in V0 at a vertex of P and each free vertex at the origin 2. Repeat For each free vertex v do xv = _____ 1 S xu deg(v) (u,v)пѓЋE yv = _____ 1 S yu deg(v) (u,v)пѓЋE Until xv and yv converge for all free vertices v An Example 3. Force Simulating Graph Theoretic Distance [Kamada Kawai 89] вЂў Model graph-theoretic distance with Euclidean distance вЂ“ The forces try to place vertices so that their geometric distance in the drawing is proportional to their graph theoretic distance вЂў For each pair of vertices (u, v), Оґ(u,v) is the graph-theoretic distance between them; вЂ“ Number of edges on a shortest path between u and v. вЂў Aim: find a drawing such that for each pair of vertices, the Euclidean distance d(pu, pv) is approximately proportional to Оґ(u,v) вЂ“ i.e. system has a force proportional to d(pu, pv) - d(u,v) вЂў Potential energy in the spring between u and v: ВЅ kuv (d(pu, pv) - d(u,v))2 вЂў Choose stiffness parameter: springs between vertices that have small graph theoretic distance are stronger kuv = k / d(u,v)2 вЂў Thus, energy in (u, v): h = k/2 (d(pu, pv)/d(u,v) вЂ“ 1)2 вЂў Energy in the whole drawing is the sum of individual energies: h = k/2 S (d(pu, pv)/d(u,v) вЂ“ 1)2 u п‚№v пѓЋE вЂў Algorithm seek a position pv=(xv, yv), for each vertex v to minimize h вЂў п‚¶ h / п‚¶ xv = 0, п‚¶ h / п‚¶ yv = 0, v пѓЋ V : non linear equation вЂ“ Partial derivatives with respect to each xv and yv are zero вЂў However, iterative approach can solve the equation вЂў At each step, a vertex is moved to a position that minimizes energy, while other vertices remain fixed вЂў Choose a vertex that has the largest force acting on it, that is 2 пѓ¦ п‚¶h пѓ¦ п‚¶h пѓ¶ пѓ§ пѓ· пЂ« пѓ§пѓ§ пѓЁ п‚¶x пѓё пѓЁ п‚¶y is maximized for all v in V. пѓ¶ пѓ·пѓ· пѓё 2 4. Magnetic Fields [SM95] вЂў Variations: вЂ“ Some or all of the springs are magnetized вЂ“ There is a global magnetic field that acts on the spring вЂ“ Magnetic field can be used to control the orientation of edges вЂў 3 types of magnetic fields вЂ“ Parallel: all magnetic forces operate in the same direction вЂ“ Concentric: the force operates in concentric circles вЂ“ Radial: the forces operate radially outward from a point вЂў The three basic magnetic fields can be combined вЂ“ encourage orthogonal edges with a combination of parallel forces in the horizontal & vertical directions вЂў The springs can be magnetized in two ways: вЂ“ Unidirectional: the spring tends to align with direction of the magnetic field вЂ“ Bidirectional: the spring tends to align with the magnetic field, but in either direction вЂў A spring may not be magnetized at all вЂў The magnetic field induces a torsion or rotational force on the magnetic springs. вЂў For a unidirectionally magnetized spring representing (u,v), the force is proportional to d(pu, pv) aq b d(pu, pv): Euclidean distance between pu and pv q: angle between the magnetic field and the line from pu to pv a and b are constant Unidirectional magnetic spring Оё Direction of the magnetic field вЂў The magnetic forces are combined with the spring & electrical force вЂў Algorithm to find equilibrium: вЂ“ initially random position and at each iteration move the vertex to lower energy position вЂў Can handle directed graphs (unidirectional springs with one of the 3 fields) вЂ“ arcs point downward: downward parallel field вЂ“ Outward: radial field вЂ“ Counterclockwise: concentric field вЂў Can be applied to orthogonal drawings: combined vertical & horizontal field with bidirectional springs вЂў Applied with success to mixed graphs (graph with both directed & undirected edges) Two Examples Vertical magnetic field Vertical and horizontal magnetic field 5. General Energy Function вЂў Most of the energy function h is a simple continuous function of the location of vertices. However, many of aesthetic criteria are not continuous вЂў Including discrete energy function вЂ“ The number of edge crossings вЂ“ The number of horizontal & vertical edges вЂ“ The number of bends in edges вЂў general energy function h пЂЅ l 1 h 1 + l 2 h 2 + вЂ¦ + lk h k п‚– hi : a measure for an aesthetic criterion вЂ“ May include spring, electrical, magnetic energy [Davidson & Harel 96] energy function for straight line drawings h пЂЅ l1 h 1 + l2 h 2 + l3 h 3 + l4 h 4 h1 = Su,vпѓЋV (1/ (d(pu, pv))2 ) : similar to electrical repulsion (vertices do not come too close together) h2 пЂЅ пѓҐ (( 1 / ru ) пЂ« (1 / l u ) пЂ« (1 / t u ) пЂ« (1 / bu )) 2 2 2 2 u пѓЋV ru, lu, tu, bu: Euclidean distance between vertex u and the four side lines of rectangular area (vertices do not come too close to the border of the screen) h3 = S(u,v)пѓЋE (d(pu, pv))2 : edges do not become too long h4 : the number of edge crossings in the drawing вЂў Flexibility of general energy function: allow variety of aesthetics by adjusting li вЂ“ [BBS97]: user can choose & adjust system parameters вЂ“ [Mendonca94]: how these coefficients can be automatically adjusted to userвЂ™s preference вЂў Main problem: computationally expensive to find a minimum energy state (very slow) вЂ“ simulated annealing [DH96]вЂ¦.. вЂ“ Genetic algorithm [BBS97]вЂ¦ вЂў Flexibility ensures popularity [Davidson & Harel 96] simulated annealing вЂў Energy function takes into account vertex distribution, edge-lengths, and edge-crossings вЂў Given drawing region acts as wall вЂў Simulated annealing: flexible optimization technique вЂў Efficiency: very slow вЂў 30 nodes and 50 edges вЂў Able to deal with optimization problem in a discrete configuration space вЂў Aim: to minimize (or maximize) the cost function вЂў Using 3 different energy functions 6. Constraints вЂў Force-directed methods can be extended to support several types of constraints 6.1. Position constraints 6.2. Fixed-subgraph constraints 6.3. Constraints that can be expressed by force or energy function 6.1. Position constraints вЂў assign to a vertex a topologically connected region where the vertex should remain вЂ“ Single point: a vertex nail down at a specific location вЂ“ Horizontal line: group of vertices arranged on a layer вЂ“ A circle: set of vertices to be restricted to a distinct region вЂў [Ostry96]: constraints vertices to curves and 3D surfaces 6.2. Fixed subgraph constraints вЂў Assign prescribed drawing to a subgraph . вЂў May be translated or rotated, but not deformed. вЂў Considering the subgraph as a rigid body. вЂў For example, barycenter method is a force-directed method that constrains a set of vertices (fixed external vertices) to a polygon. 6.3. Constraints expressed by forces вЂў Constraints expressed by forces вЂ“ Orientation of directed edges: magnetic spring вЂ“ Geometric clustering of special set of vertices вЂ“ Alignment of vertices вЂў Clustering can be achieved [ECH97] вЂ“ For each set C of vertices, add a dummy attractor vertex vC вЂ“ Add attractive forces between an attractor vC and each vertex in C. вЂ“ Add repulsive forces between pairs of attractors and between attractors and vertices not in any cluster. Remark вЂў Improve the efficiency вЂ“ [FR91]: amenable force functions вЂ“ [FLM95, Tun92]: use randomization in S.A. вЂ“ [Ost96]: the equations describing the minimal energy states are stiff for some graphs of low connectivity. вЂ“ [HS95]: use combinatorial preprocessing step, good initial layout вЂў [BHR96] empirical analysis вЂ“ [FR91],[KK89],[DH96],[Tun92],[FLM95] вЂ“ No winner, try several methods and then choose the best Faster Spring methods вЂў Problem: Spring methods are too slow for huge graphs Computing the forces takes quadratic time 1. pu = some initial position for each node u; 2. Repeat 2.1 Fu := 0 for each node u; 2.2 For each pair u,v of nodes 2.2.1 calculate the force fuv betwe en u and v; 2.2.2 Fu += fuv; 2.2.3 Fv += fuv; 2.3 For each node u, pu += eFu; Until pu converges for all u; FADE [Quigley & Eades01] вЂў It is feasible to use 1. a spring method, then 2. a geometric clustering method to obtain a good graph clustering. Graph Clustered Graph Quadtree вЂў A tree data structure вЂў Each internal node has up to four children. вЂў Most often used to partition a two dimensional вЂ“ Recursively subdividing it into four quadrants or regions. вЂ“ Stops when each quadrant contains one point. вЂў In general, recursively partition the space into 2d subspace equally, where d is the dimension вЂ“ Known as Octree for 3D Barnes-Hutt method вЂў A method of computing forces between stars. вЂ“ Use Quadtree to cluster the stars вЂ“ Use the forces between the clusters to approximate the forces between individual stars. root a d c c TL b e a b BR d BL f e f Barnes-Hutt method вЂў The contents of a subtree of can be approximated by a mass at the centroid. root a d c c TL b es a b BR s d BL f e f Barnes-Hutt method вЂў The force that the subtree s exerts on the star x can approximate the sum of the forces that the nodes in s exert on x. root a d c c TL b es a b BR s d BL f e f FADE To compute the force on star x, we proceed from the root toward the leaves. ComputeForce(star x; treenode t) If the approximation is good then return the approximation; else return SsComputeForce(x, s), where the sum is over all children s of t. A simple method can be used to determine whether the approximation is good; it depends on the mass of nodes and the distance between x and s. w(t) / d(x,t) < c, w(t) the width of t; d(x,t) the distance between x and t, and c is a constant. FADE вЂў The Barnes-Hutt method is faster than the usual spring algorithm. 1. px = some initial position for each star x; 2. Repeat In practice, computing all the forces takes O(n log n) time 2.1 Build the quadtree; 2.2 Foreach star x ComputeForce(x,root); 2.3 Foreach star x, px += eFx; Until px converges for all x; FADE вЂў At each iteration, the node movements introduced in the previous step improves the quadtree clustering вЂ“ Makes the quadtre clustering (a geometric clustering) better reflects the graph clustering. 1. pu = some initial position for each node u; 2. Repeat Some nodes migrate from one cluster to the next 2.1 Build the quadtree; 2.2 Foreach node u ComputeForce(u,root); 2.3 Foreach node u, pu += eFu; Until pu converges for all u; FADE вЂў Observations вЂ“ The Quadtree provides a clustering of the data вЂ“ If the data is well clustered, then BH runs faster вЂў The approximated force is then more accurate вЂ“ The spring algorithm tends to cluster the data вЂў This means that we can: вЂ“ Use Barnes-Hutt to compute the clusters as well as the drawing вЂ“ Use the quadtree as the clustering for the clustered graph Experimental Result The error is the difference between the approximated force vector and the original one Visual abstraction Can we use other natural system analogy?