Information Technology Reference
In-Depth Information
6.3
Compound Representation
To find an algorithm that gives good results (in term of computation time,
aesthetic criteria and information emphasized) for arbitrary networks is a very
difficult problem. One of the most popular approaches to drawing such general
graphs, namely the force-directed approach, which produces visually pleasant and
structurally significant results (e.g., Frick et al. , 1995 ; Fruchterman & Reingold ,
1991 ; Gajer & Kobourov , 2002 ; Hachul & Junger , 2005 ; Lauther , 2007 ).
Even if fast graph layout algorithms can scale up to thousands of elements,
two important issues still remain: cluttering and slow rendering. The clutter (node-
node overlaps, node-edge overlaps and edge-edge crossings) increases with the size
and complexity of the graph, resulting in unreadable visualizations. Additionally,
displaying a large number of elements may lead to slow rendering and thereby
hinder interactive exploration. Therefore, both cluttering and slow rendering make
the analysis task harder for end-users and must be avoided.
An effective way to reduce the visual complexity of the representation, thereby
reducing visual clutter and speeding up the rendering process, is to build an
abstraction of the original graph. That abstraction is then displayed on the screen
and the user can explore his/her data via a dedicated interactive system that allows
the end-user to reduce/increase the level of detail.
6.3.1
Building an Abstraction
To build an abstraction, one usually applies clustering algorithms that group together
similar elements of the network (e.g., Auber, Chiricota, Jourdan, & Melançon , 2003 ;
Dongen , 2000 ; McSherry , 2004 ; Newman & Girvan , 2004 ; Schaeffer , 2005 ). After
the first partition of the elements is computed, two options are offered: either refine
each cluster by applying the clustering algorithm, or contract each cluster into a
single node and apply the clustering algorithm to the resulting graph. If the first
partition of a few clusters contains many elements, then the first option should be
preferred. On the contrary, if the partition of many clusters contains only a few
elements, then the second option will increase the level of abstraction. In Fig. 6.4 a,
one can see the result of an iterative decomposition of an illustrative network. The
network has been first decomposed into three clusters (green, pink and yellow)
and then the yellow cluster has been refined and a brown cluster has been found.
In Fig. 6.4 b, one can see the usual data structure that was used to represent that
hierarchical partition of the nodes.
Once the hierarchical partition has been computed, the abstraction of the network
(according to that partition) is then built by replacing each cluster of nodes with a
single node (called a metanode), replacing all edges linking two of these subsets
with a single edge (called a metaedge), and linking the corresponding metanodes.
This operation reduces the number of displayed nodes and edges and, therefore,
Search WWH ::




Custom Search