Information Technology Reference
In-Depth Information
Fig. 1. Untangling a graph layout on the tiled wall display
3.1
Graph Clustering
Allowing the user to move larger chunks of the graph at a time can help to reduce this
effort in case these chunks are specified in a way that supports the user's untangling
process. Graph clustering partitions the nodes of the graph into clusters, that is, disjoint
node sets, aiming to have high cohesion (that is, many intra-cluster edges), and low
coupling (that is, few inter-cluster edges).
Many different clustering algorithms are available. We use a fast and simple clus-
tering method based on random walks [2]. This algorithm aims to detect dense local
substructures using a random walk based graph traversal. Roughly speaking, random
walks tend to stay within a highly cohesive substructure with a high probability [2].
This algorithm allows to influence the number of clusters over parameter settings; this
property is helpfulfortuning the interaction fidelity. As the cluster boundaries created
by the random walk approach can be somewhat fuzzy, we apply a Kernigan-Lin style
postprocessing technique [18] that flips the cluster affiliation of single nodes that are
connected more strongly to a different cluster than to the cluster they are affiliated with.
Clusters as Rigid Bodies: Each cluster in the graph is represented as a polygonal
rigid body. The polygon shape is calculated by taking the convex hull of the vertices
in the cluster, and then simplifying the polygon down to a maximumofeight vertices.
This simplification greatly improves the performance of the simulation at runtime. The
polygon is given physical properties that drive the simulation: 1) Damping reduces the
velocity of rigid bodies when in motion. 2) Density determines the mass of the poly-
gon, and thus its momentum when in motion. 3) Static Friction prevents rigid bodies
from movingunless a minimum threshold force is applied. This is important in limiting
the number of nodes that move in response to the movement of a node. 4) Collision
In most physics simulations, rigid bodies can collide. For ourpurposes, collisions are
disabled and bodies can pass through each other. Physics engines such as that provided
by Box2D allow specification of control parameters for the above properties; for GION,
we chose values for these parameters from experience.
 
Search WWH ::




Custom Search