A              Method for Cluster-based Graph Browsing - ClusterNavigator

A.1          Basic Information

The Cluster Navigator serves as front-end used for visualization of graphs[1]. Graph over this document refer to directed, labeled graphs. On the back-end side the Clusterer tool handles the requests of Cluster Navigator. Cluster Navigator aims to support the user in navigation. The visualized network is usually only a part of the whole network. On the back-end side Clusterer serves the wished part of the network. The network is organized into hierarchical clusters by Clusterer. The visualized part of the network is clickable, the user can embed to a cluster represented by a node or it can emerge from a cluster. The tool is domain independent.

A.1.1      Basic Terms

Cluster

Compact part of the network, a cluster contains nodes and edges between the nodes; not exact definition exists, usually nodes are more interconnected among each other inside the cluster then they are with nodes outside the cluster.

Network/cluster visualization

Layouting of the nodes in the network/cluster in a two dimensional space; attaching coordinates the vertices that results an intuitive view of the network.

Cluster hierarchy

Recursive application of clustering (process yielding clusters of the network) results identification of subclusters identified clusters. Cluster-subcluster relationship forms a tree like structure.

Cluster annotation

Attaching a text into the cluster; annotations should reflect the content of the cluster as much as it is possible as the user decides where to navigate based on the annotations.

 

A.1.2      Method Description

The method is based on a client-server serving of the network’s parts. The network parts are visualized using known and verified methods for network visualization. The tool aims to ease the navigation of the user in a huge set of data by interactions through clicking on nodes in the visualized networks. Here is a scenario for illustration of the interactions:

1.    cluster Navigator visualizes the clusters on the top layer of the cluster hierarchy

2.    the user based on the cluster annotations chooses a cluster; the cluster is selected by a mouse click

3.    Cluster Navigator sends a request to Clusterer for the selected cluster

4.    Clusterer sends the cluster and Cluster Navigator visualizes it

5.    the user can decide whether the visualized cluster is the one she wished to see, if she is satisfied a information space can be further cut by choosing a further cluster

6.    Cluster Navigator send the choice to Clusterer, the returned graph is visualized

7.    if the user is not satisfied, she can move back up in the cluster hierarchy

A.1.3      Scenarios of Use

The tool has one ultimate usage: supporting navigation in the cluster hierarchy. An interaction between the user, Cluster Navigator and Clusterer is outlined in the previous section.

A.1.4      External Links and Publications

§  György Frivolt. Cluster Navigator: Identification of Graph Clusters. In Pavol Návrat, Pavol Bartoš, Mária Bieliková, Ladislav Hluchý, and Peter Vojtáš, editors, Proceedings in Informatics and Information Technologies: Tools Acquisition, Organisation and Presenting of Information and Knowledge, pages 90-100, Bystrá dolina, Nízke Tatry, Slovakia, September 2006. Vydavateľstvo STU.

§  György Frivolt and Ondrej Pok. Comparison of Graph Clustering Approaches. In Mária Bieliková, editor, IIT.SRC 2006: Student Research Conference, pages 168-175. Faculty of Informatics and Information Technologies, Slovak University of Technology in Bratislava, April 2006.

A.2          Integration Manual

Cluster Navigator is a java applet communicating with the server through sockets.

A.2.1      Dependencies

A graphic web browser[2] with java runtime environment 5 or latter is required. All packages are downloaded when the page with the applet is opened. Cluster navigator uses Prefuse[3] for visualization of networks.

A.2.2      Installation

Proper configuration of the web browser is needed in order to execute the Cluster Navigator’s java applet.

A.2.3      Configuration

Web browser supporting graphics with installed Java Runtime Environment 5 or later is necessary. No special permissions are necessary to set. The applet communicates with the server where it was retrieved from; in such case no permissions for enabling socket communication is needed.

The applet receives the following parameters:

§  server – IP address or name of the server which  the applet connects to;

§  port – the port number of the server;

§  usrId – string identifying the user who is using the server for navigation.

Here is snippet of an applet invoking code:

<APPLET CODE="sk/fiit/clustnav/gui/ClusterNavigatorApp.class" CODEBASE= "clustnav" WIDTH=600 HEIGHT=400>

  <PARAM NAME=server VALUE="clustnavserver.org"/>

  <PARAM NAME=port VALUE="9090"/>

  <PARAM NAME=usrId VALUE="http://joe.openid.com/"/>

</APPLET>

 

A.2.4      Integration Guide

Cluster Navigator is tool providing simple way of navigation in the cluster hierarchy. There are two types of moving in the cluster hierarchy:

§  Moving down in the hierarchy – choosing a node in the visualized network results that the cluster represented by the node will be visualized;

§  Moving up – by pushing button move up the user gets to the super cluster

 

Figure 1.  Navigation in the cluster hierarchy: Clicking on the node brings the user the subcluster

 

The clusters are visualized as it is depicted on Figure 1. The related nodes are rendered closer to each other. Cluster Navigator renders two layers of clusters at the same time. The first layer is drawn in bubbles; the inner ones are depicted as nodes with annotations. The user can move the nodes or the clusters packed together in bubbles if she wants to order the layout.

A.3          Development Manual

Cluster Navigator is implemented in Java 5. Knowledge of Prefuse is inevitable for extending the visualization part of the tool. Otherwise no special knowledge except of the basic java packages is required.

A.3.1      Tool Structure

The tool consists of the following packages:

sk.fiit.clustnav.applet

 

Package contains the applet visualized by the browser.

sk.fiit.clustnav.clustering.local

 

Local clustering algorithms, useful when the network is too big for visualization.

sk.fiit.clustnav.clustering.snn

 

Implementation of shared neighborhood clustering algorithm.

sk.fiit.clustnav.server

 

Contains server of local clustering networks.

 

A.3.2      Method Implementation

We discuss the communication between the server and applet front-end in this section. The communication is realized using GraphML[4], which is a markup language designed for describing graphs. The nodes in the GraphML file contain a special attribute clusterId, which is used for separation of the nodes into bubbles (see Figure 1). An extra node is added to the GraphML with ID -1, which holds the number of the current cluster. This node is not viewed in the visualization.

We list a short example of the sent GraphML file:

<graphml xmlns="http://graphml.graphdrawing.org/xmlns/graphml"  xmlns:xsi="http:                                                                             //www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns/graphml">

<key id="d0" for="node" attr.name="text" attr.type="string"></key>

<key id="d1" for="node" attr.name="type" attr.type="string"></key>

<key id="d2" for="node" attr.name="uri" attr.type="string"></key>

<key id="d4" for="node" attr.name="clusterId" attr.type="string"></key>

<key id="d5" for="node" attr.name="ID" attr.type="string"></key>

<graph edgedefault="undirected">

<node id="1">

<data key="d0">Peter</data>

<data key="d1">1</data>

<data key="d2">http://www.namedays.com/name/Peter</data>

<data key="d4">2463</data>

<data key="d5">2460</data>

</node>

<node id="2">

<data key="d0">Lisa</data>

<data key="d1">1</data>

<data key="d2"> http://www.namedays.com/name/Lisa</data>

<data key="d4">2463</data>

<data key="d5">2454</data>

</node>

<edge source="1" target="2" directed="true"></edge>

<node id="-1">

<data key="d4">432</data>

</node>

</graph>

</graphml>

A.3.3      Enhancements and Optimizing

Compared to other visualization tools, Cluster Navigator visualizes clusters on two levels at the same time. This is realized by exploiting the feature of library Prefuse to visualize aggregates. The aggregates are rendered as bubbles.

For the number of nodes in the network which is understandable to the user (no more 40 nodes), the visualization works smoothly. Cluster Navigator is intended for visualizing relatively small graphs. A bottleneck can be at the server side, which might handle big graphs. However, the possible slowdown in serving the clusters is tackled by off-line clustering of huge networks, thus the request coming from the client can be served immediately.

A.4          Manual for Adaptation to Other Domains

Cluster Navigator is a domain independent tool and can be simply used for any domain, by changing the data being served by the server. The server can be also very different as the currently used. For instance, instead of serving disjunctive hierarchical clusters, overlapping clusters or local cluster might be served.

A.4.1      Configuring to Other Domain

If the data set is changed for other domain, no change is need on the client side; the change affects only the server. Changing the server can be performed by changing the applet parameter server, see section A.2.3.

A.4.2      Dependencies

No change in dependencies on libraries appears when moving to another domain.

 

 



[1] We use expression graphs instead of networks, which is often used in similar tools.

[2] Text browsers such as lynx are not supported.

[3] http://prefuse.org/

[4] http://graphml.graphdrawing.org/