Key-node-Separated Graph Clustering contribute to understand how information spreads inand Layout for Human Relationshipsocial networks.
Graph Visualization
Often, nodes or substructures of a graph are agTakayuki Itoh, Ochanomizu University, Japan
Karsten Klein, Monash University, Australia

gregated for analysis and visualization based on either the structure or attributes, for example by hierarchical clustering. Various techniques on hierarchical graph visualization have been developed for suchgraph analysis tasks, because a hierarchical structureis useful for overview of and quick understanding of
the graph structures, and top-down operations forgraph exploration and navigation. Graph clustering
algorithms are often applied before applying hierarchical graph visualization. Many of them treat tightly
connected subregions of the graphs as clusters; however, that does not always work well for discovery of
key nodes and tight connections. Figure 1 illustrates
the problem of graph clustering. The red nodes in
Figure 1(a) are connected to a large number of nodes,
and therefore they are certainly important nodes inthis graph. However, they may belong to the cluster(1) because they form a tightly connected subgraphwith the ﬁve blue nodes, even though they also connect to many other nodes. In this case, the red nodes
are not very visible if the high-level structure of theclustered graph is drawn as Figure 1(b). Also, manyedges between blue and red nodes are not visible because they are drawn in a small region corresponding
to the cluster (1). Users may miss to ﬁnd these important connections while looking at the high-levelstructure. On the other hand, the red nodes will beseparated from this cluster if commonality of neighbor nodes or similarity of attributes are applied as
criteria of the clustering process. If the commonality of neighbor nodes is applied to the clustering, ﬁve
blue nodes form a cluster because they are connected
to just blue and red nodes, while two red nodes form
another cluster because they are connected to all colors of nodes. Or, if colors of the nodes represent their
attributes, the blue and red nodes can form separate
clusters. Figure 1(c) illustrates the result. A set ofconnections between blue and red nodes can be emphatically displayed by a thick bundle connecting thetwo clusters. In this case, the red node will be stillvisible when the high-level structure of the graph isdrawn as Figure 1(d). This structure is preferable forthe following reasons:

Abstract
Many graph drawing methods apply node clustering
techniques based on density of edges to ﬁnd tightly
connected subgraphs, and then hierarchically visualize the clustered graphs. On the other hand, users
may want to focus on important nodes (called key
nodes in this paper) and their connections to groupsof other nodes while using some applications. For thisrequirement, it is eﬀective to separately visualize thekey nodes detected based on adjacency and attributesof the nodes. This paper presents a graph visualization technique for attribute-embedded graphs whichapplies a graph clustering algorithm taking into account the combination of connections and attributes.
The graph clustering step divides the nodes according
to the commonality of connected nodes and similarity of feature value vectors. It then calculates the
distances between arbitrary pairs of clusters according to the number of connecting edges and similarityof feature value vectors, and ﬁnally places the clusters
based on the distances. Consequently, the techniqueseparates important nodes which have connections tomultiple large clusters, and improves the visibility ofconnections of such nodes. This paper presents examples with human relationship graph datasets, including a co-authorship and a Twitter communication
network dataset.

1

Introduction

Graphs are used to model relations between entities
in many real-world applications. Common tasks ofgraph analysis include understanding of correlations
between the connections and attributes of the entities, and discovery of key entities which have many
connections or many particular attributes. Humanrelationship is a typical information for which graphvisualization can be very useful for analysis purposes.
People in social networks have connections, so called
friendships, and the relations between subsets of people might form complex subnetworks. Understandingof correlations between the connection structures andattributes of the people, such as jobs, hometowns, andhobbies, may contribute to various social and business analytics. Also, discovery of key persons andanalysis of their positions and roles in a network may• Connectivity with important nodes and multiple
clusters will be comprehensive in the visualization results.
• Less edges will be tangled in the small regions ofdisplay spaces corresponding to clusters.
• Edge bundling algorithms can be easily applied1

to large number of edges connecting to important ing a graph layout algorithm, and adjusts the posinodes such as the red node in Figure 1(d).
tions by triangular mesh smoothing algorithm, where
the mesh is generated by connecting centers of clusters by a Delaunay triangulation algorithm. Finally,(1)(2)
it calculates the positions of nodes in each of the clusters, applies an edge bundling technique to design the
shapes of edges, and draws all the nodes and edges.

2(3)(a) Clustering based on
density of connections(4)(b) High-level drawingof the clustered graph (a)Graph clustering partitions the nodes of a graph into
clusters, i.e. node sets that are usually disjoint, withthe goal of having many intra-cluster edges and few
inter-cluster edges. Graph clustering is useful not
only for visualization but also various analytic purposes, and actually large number of algorithms havebeen presented, as introduced by Schaeﬀer [10] or several other survey papers.
The most popular approach for graph clustering
is extraction of tightly connected subgroups of nodes.
Many graph clustering techniques using this approach
are based on agglomerative clustering algorithms.
Meanwhile, Schaeﬀer’s survey [10] also points that
there are various criteria to measure the distancesamong the nodes of graphs, including similarity offeature value vectors in the multidimensional Euclidean spaces, adjacency-based node similarity measurements, in addition to the tightness of the connections which can be measured as number of paths between two nodes. The presented technique calculates
distances among nodes as a combination of feature
value vector distances and adjacency-based dissimilarities.
Hierarchically clustered graphs are an eﬀective data
structure for information visualization because they
are suitable for overview, zoom, and ﬁltering operations. Node layout is deﬁnitely an important issue for comprehensive graph visualization. Many improvements in quality and computational eﬃciency
have been achieved in the development of forcedirected methods since Eades proposed his seminal
spring embedder model [4]. Better alternatives include multilevel approaches and recent advances instress-based layout computation [5], which basically
apply a multidimensional scaling. Meanwhile, several techniques [3] [8] eﬃciently visualize hierarchical graphs by applying space-ﬁlling layout techniquessuch as Treemaps.
Edge bundling has been an active topic since Holten[6] presented a technique which hierarchically bundles edges connecting nodes of tree structure levelby-level, and draws them as Spline curves. Edge
bundling is especially eﬀective coupling with the presented technique, because it clusters nodes based on

(5)

(7)
(6)
(c) Clustering based oncommonality of neighbors

Related Work(d) High-level drawingof the clustered graph (c)Figure 1: Clustering based on density of connections
or commonality of neighbors.
Key node ﬁnding is useful in many real world applications. Development of key-node-conscious graphvisualization techniques is therefore expected to be an
important contribution in many academic and business ﬁelds. Moreover, additional information suchas attributes of nodes have to be taken into accountin many applications. In case of human relationshipgraphs where nodes correspond to humans, we often
need to take into account preferences or charactersof humans as attributes of nodes. Their preferencesor characters can be often converted to numeric values by recent analysis techniques, including natural
language processing with the documents written by
the humans. Graph visualization featuring key-nodeidentiﬁcation combining topology and attribute based
clustering is therefore useful for these applications.
Also, this clustering will contribute to visible representation of the tight connections between key nodes
and their adjacent clusters.
This paper presents a graph visualization techniquethat features graph clustering based on a combination of structural neighborhood and attribute similarity. The technique supposes that each node of thegraph has a constant-sized feature vector representing
its attributes. It calculates distances between pairsof nodes according to similarity of feature vectors aswell as commonality of neighbor nodes, and generates
clusters of the nodes according to their distances. It
then calculates the initial positions of clusters apply2

E = {e1 , ..., eNe }ni = {ai1 , ..., aiNa }the commonality of adjacent nodes, and consequently
it constructs hierarchy of the nodes so that large number of edges can be bundled.
It is often interesting to emphasize important nodes
in graphs. Ohsawa et al. [9] presented the KeyGraphconcept which features nodes bridging multiple subgraphs. Correa et al. [2] applied various schemes
to calculate centrality sensitivity to eﬀectively visualize social networks. Our study presented in thispaper takes into account the combination of neighborhoods and attributes of nodes diﬀerently from theabove techniques. Meanwhile, several graph drawing
techniques are suitable for key-node conscious drawing: for example, bipartite graphs. Hong et al. [7]visualized citation networks by dividing most cited
papers and others as diﬀerent types of nodes and applying a bipartite graph drawing technique, to focus
on the connections between important nodes and theothers. Our technique presented in this paper also
aims to focus on such connections; however, the technique can be combined with a variety of graph layout
algorithms.
Multivariate node attribute is also often taken into
account during the graph layout processes. Shneiderman et al. [12] presented an implementation
and a case study of graph visualization applying a
metaphor of substrates, which speciﬁes the positionsof nodes based on their attribute values. Shi etal. [11] presented a graph clustering scheme whichapplies attribute-based partitioning for higher-levelnodes and topology-based partitioning for lower-levelnodes. Our technique also takes into account both
attributes and topology; however, our technique is
diﬀerent from it since ours applies attribute-based
and adjacency-based metrics simultaneously in a single clustering process.

ei = {nj , nk }(1)Here, ni denotes the i-th node, ei denotes the i-thedges, aij denotes the value of the j-th dimensionof the i-th node, Nn denotes the number of nodes,
Ne denotes the number of edges, and Na denotes thenumber of dimensions.
The presented technique ﬁrst generates clusters of
nodes according to the similarity of feature vectors
and commonality of adjacent nodes. It then applies
a stress-minimizing graph layout algorithm to the setof clusters to calculate these initial positions. In thenext step, these positions are connected by a Delaunay triangulation algorithm, and a mesh smoothingalgorithm is applied to set apart the dense clusters
and maintain the preferable distances between them.
Finally, the technique draws the graph applying aBézier-curve-based edge bundling. Our current implementation speciﬁes the color of a node based on
the dimension which has the largest value in ai1 to
aiNa . Also, it optionally paints the triangular meshused for the cluster position arrangement as the background color by interpolating the colors of the nodes.
The following sections describe technical components of the presented technique.

3.2

Graph Clustering

The presented technique calculates two types of distances between all pairs of nodes: dissimilarity of feature vectors dvec , and discommonality of the adjacentnodes dadj . It deﬁnes the distance between a pair ofnodes asd = αdvec + (1.0 − α)dadj(2)

where α is a user-speciﬁed value satisfying (0.0 ≤α ≤ 1.0). Our implementation features a GUI slider
This section proposes the presented graph visualiza- widget so that users can freely adjust α and interaction technique and its components. This includes the tively look at various visualization results. The techclustering and layout methods, rendering, as well as nique then generates clusters of nodes by an agglomerative clustering algorithm with the furthest neighthe interaction concept.
bor method. The algorithm starts generating clusters
consisting of one node, and repeats the merge of clus3.1 Processing flow
ters until the minimum distance between two clusters
The presented technique supposes that all nodes have exceeds the user-deﬁned threshold. The two types ofthe same constant number for the dimension of the distances are calculated by the following process.
feature vector. The following is the supposed data
structure of an input graph G consisting of a set of
Dissimilarity of feature vectors
nodes N and edges E.
The technique calculates the similarity between the
G = {N, E}
two nodes as the inner product of the feature values.
N = {n1 , ..., nNn }We deﬁne the dissimilarity calculated from the inner

3

Presented Technique3

product as the distance between the two nodes dvec ,by the following equation.
dvec = 1.0 − inner
inner = ni · nj /|ni ||nj |the algorithm iteratively minimizes a stress function
on the nodes’ positions. Stress in the layout is deﬁned
here as
wuv (||pu − pv || − duv )2
(6)

(3)

u,v

where wuv is a normalization constant set to2
1/sp(u,v) , the inverse of the square of the shortDiscommonality of adjacent nodes
est path between two nodes. This gives priority to
We deﬁne the discommonality of adjacent nodes by the error between nodes that have a small graph thethe number of commonly connected nodes. To spec- oretic distance compared to long range errors. p isu
ify the distance dadj between two nodes ni and nj , the position of node u in the layout, and d given
uv
the technique counts the number of nodes which are ideal distances between u and v. In graph layout alconnected to both ni and nj . It simply calculates the gorithms, these distances are usually set to the graphdistance as follows.
theoretic distance between the nodes. In order to apply the distance based method to the cluster graph,(4)
dadj = 1.0/(1 + nadj )we need to derive distances for the clusters similar toHere, nadj is the number of nodes connected to both the distance calculation for the nodes. In addition
to the distances, we would also like to take into acthe nodes.
count the cluster graph topology, i.e. the connectivity
between clusters. To this end, our current implemen3.3 Cluster Layout
tation deﬁnes a weight w for each bundle as
The presented technique then generates a cluster(7)w = βwbun + (1.0 − β)wvec
graph, consisting of vertices corresponding to the clusters of nodes, and bundles corresponding to sets of where wbun is proportional to the number of edges
edges connecting two nodes belonging to two diﬀer- belonging to the bundle. w
vec is calculated from inent clusters. Bundles are weighted according to the ner products of the average vector values of the two
number of edges.
clusters, similar to the equation (3). β is a userWe denote the cluster graph as
speciﬁed value satisfying (0.0 ≤ β ≤ 1.0). The obtained weights are reversed to obtain distances forthe layout algorithm, i.e. the larger the weight, thesmaller the ideal distance between the connected vertices. Based on these distances between adjacent vertices, all pairwise distances between clusters are calculated using all pairs shortest path computation.
It may happen that the layout algorithm places vertices too closely especially due to the dense connections. To relax such layout results, the technique thenforms a triangular mesh connecting the set of vertices
by applying the incremental Delaunay triangulation
algorithm, and moves the vertices by applying a meshsmoothing algorithm. The movement of the i-th vertex, movvi , is calculated by the following equation
while repeating the mesh smoothing algorithm.

CG = {V, B}
V = {v1 , ...}
B = {b1 , ...}
vi = {ni1 , ...}
bi = {ei1 , ...}

(5)

where CG is the cluster graph, V is the set of vertices,and B is the set of bundles. A vertex vi consists of aset of nodes nij belonging to the cluster corresponding to vi , and a bundle bi consists of a set of edges eij
connecting the pairs of nodes belonging to the corresponding same pair of clusters.
As our approach is based on the calculation of
distances between nodes, a distance-based layout
sumvi
method is a natural choice to calculate the layout
movvi = len1
for the cluster graph. In our implementation, we ap|sumvi |
ply the stress minimization layout algorithm from thesumvi =
distik1
Open Graph Drawing Framework OGDF to calcuk
late initial positions for the vertices. This algorithm
distik = 0 (if |vi − vk | ≥ len2 )tries to minimize the error between the geometric disvi − vktances between pairs of nodes in the drawing and(if |vi − vk | < len2 )distik = len2(8)|v
i − vk |given input distances. Starting from an initial drawing using the PivotMDS method as described in [1], Here, len is a constant value to keep the length of the
1
1 http://www.ogdf.net
movement vector constant. vi is the position of the4

i-th vertex. vk is the position of a vertex connected 4
Experiments
to vi by a bundle. len2 is the preferable distance between vi and vk . This algorithm attempts to keep This section introduces our experiments with twoconstant distances between adjacent vertices to avoid datasets. We set α in equation (2) to 0.5 for all exa too dense layout, while it does not attract far ver- amples shown in the ﬁgures.
tices.

4.1

Data

We applied our technique to the following datasets.
Our motivation to apply our method is to visually
After calculating the positions of vertices correspond- ﬁnd key persons, and explore the relationships being to the clusters, the technique assigns positions to tween the key persons and their adjacent persons.
nodes in each of the clusters. Our current implemen- This section demonstrates that our technique is able
tation just places nodes on the adequate number of to show the edges between key nodes and groups ofconcentric circles around the position of the cluster. their adjacent nodes.
It then applies a node swapping algorithm to reduce
the sum of edge lengths. The algorithm initially lets Set A: Co-authorship data. This dataset was
all the nodes in a cluster unﬁxed. It selects an unﬁxed created based on a publication bibliography from thenode, and calculates the sum of edges lengths for all NERC Biomolecular Analysis Facility (NBAF) 2 . Weedges connecting to the node, while traversing the downloaded the full NBAF bibliography for the years
positions of all unﬁxed nodes in the cluster. Once the 1998-2013, which contains 1821 authors and 564 pabest position is found, the process swaps the position per titles. We constructed a graph that models theof the current node as the best position and ﬁxes it. paper co-authorship, consisting of 1821 nodes and
The process repeats one-by-one for all the nodes in 11097 co-authorship edges, where each node has a
the cluster.
12-dimensional feature vector.
After the node placement we apply an edge
To construct the feature vectors, we ﬁrstly counted
bundling algorithm between pairs of clusters. Our the frequency of terms in all the paper titles, andimplementation applies Bézier curves between pairs of selected 20 terms from them. We then counted thenodes setting four control points, where two of them frequency of the selected terms in the paper titles forare placed at the position of two nodes, and others are each author, and speciﬁed the top one term as theplaced between them. This design is close to Holten’s corresponding term of an author. We counted thehierarchical edge bundling [6] that applied B-Spline number of authors for each term, and ﬁnally selectedcurves. Our design is simpler because we do not need the 12 terms covering a large number of correspondto consider the variety of depths of hierarchy.
ing authors. We counted the frequency of the selected
Our implementation assigns colors of nodes based 12 terms in the paper titles again, and treated thefrequency values as the 12-dimensional feature vecon either of the following procedure.
Distribution of feature vector values. The technique tor of an author. The selected terms were as follows:
assigns node colors according to the feature vector Genetic (red), Molecular (orange), Loci (yellow), Mivalues, to represent the relevancy among the connec- crosatellites (yellowish green), Isolation (green), Intions and features. One could assign either a color breeding (bluish green), Transcriptomics (sky blue),depending on all individual values per dimension, the Expression (blue), Bacterial (indigo), Breeding (purvariation of values, or just on the dominating dimen- ple), and Polymorphic (pink).
sion. Our current implementation simply assigns colors to each of the dimensions of the feature vector, Set B: Twitter communication data. Thisand selects the color of a node as the color of the dataset was published on the NodeXL Graph Gallery,dimension which has the largest value in the feature which records Twitter users whose tweets are related
vector of the node.
to food security, or who were replied to or menCentrality. The technique also assigns node colors ac- tioned in those tweets, on 17 September 2014 3 . We
cording to their centrality [2]. Our current implemen- constructed a graph that models the communication
tation just calculates colors based on their degree: it among Twitter users, consisting of 4973 nodes andassigns gray to low-degree nodes, and red to high- 4223 communication edges.
degree nodes. We would like to apply a variety of2 http://nbaf.nerc.ac.uk/support/publications
3 http://www.nodexlgraphgallery.org/Pages/Graph.
centrality metrics to calculate colors of nodes in later
aspx?graphID=28286
versions.

3.4

Graph Rendering

5

Similar to the set A, we ﬁrstly counted the frequency of terms in their tweets, and subjectively selected the 8 important keywords, Somalia, Africa,
Ebola, India, Mubasher lucman, PTI, and AMP, fromthe top 30 terms. We counted the frequency of theselected 8 terms again, and treated the frequency values as the 8-dimensional feature vector of a Twitter
user.

4.2

the same cluster and therefore it is diﬃcult to observe
the structure around the speciﬁed key node.
Table 1 shows the statistics of the clustering results,
where N umC denotes the number of clusters, N umN
denotes the number of nodes in the clusters which the
key nodes belong to, and N umIE denotes the number of edges inside the clusters (in other words, edges
connecting the nodes belonging to the same cluster).
This result demonstrates our technique successfully
divided such key nodes from large clusters As a result, we reduced the number of edges tangled inside
the cluster and therefore eﬀectively showed the connectivity between the key nodes and others. Thisvisualization represents the publication situation in
the area well, judging from the research community
information.
Next, we show the clustering and layout results using the dataset B. Figure 5 shows the comparison ofgraph clustering and layout results between our technique and the common comparison technique, where
nodes are colored based on centrality. The dataset
contains ﬁve users which have extremely large number of communications with other Twitter users, as
indicated by red circles in the results. Figure 5(a)demonstrates that our technique separated such key
nodes from large clusters. Also, the result eﬀectively
shows that the key nodes connected the large clusters
and other portions of the graph. On the other hand,
Figure 5(b) shows that the key nodes were swallowed
by large clusters when we applied a common clustering algorithm. Table 2 shows the statistics of theclustering results with the dataset B. Our techniquedrastically reduced the number of edges inside theclusters, where the result by our technique just contained 296 inside edges while the result by common
technique contained 6668 inside edges.

Examples of Clustering and Layout Results

This section ﬁrst presents several clustering and layout results using the dataset A. Two of the nodes in
the graph have an extremely large number of connections; they are connected to 527 and 412 edges,
respectively. We will call these nodes key nodes in
the following.
Figure 2 shows an example of cluster layout andedge bundling. Nodes are colored according to theirfeature vector values. Edge bundling algorithm in
our implementation eﬀectively reduces the cluttering
among the nodes and edges. Edges of the speciﬁed
nodes can be highlighted by click operations to focus on the connectivity of particular important nodes.
Similarly colored nodes are more concentrated in thesame clusters if we use a larger α value, while more
key nodes tend to be outside the large clusters if we
use a smaller α value. We repeated the same processes
10 times with the same dataset to measure the computation time. On average, the technique required
2.496 seconds for graph clustering, 7.343 seconds forstress-minimizing layout, and 1.464 seconds for meshgeneration and smoothing, respectively.
Figure 3 shows the layout of clusters, where nodes
are colored based on centrality, while adjusting thethreshold for sizes of clustering. The key nodes were
not swallowed by large clusters, but belonged to thesmall clusters enclosed by red circles in this ﬁgure.
Figure 4 compares visualization results between ourand common techniques applying the same dataset
and dividing the nodes into approximately same numbers of clusters. Figure 4(a) is a result by our technique, where the two key nodes belonged to the same
small cluster indicated by a red circle. Figure 4(b)shows the result applying a common clustering algorithm for comparison (modularity clustering in thisexample), where the two key nodes belonged to larger
clusters indicated by red circles. Figures 4(c) and 4(d)compare the visibility of edges connected to the speciﬁed node. In Figure (c), most of edges are connected
to nodes in other clusters and therefore the edges are
more comprehensive. On the other hand, most ofedges shown in Figure (d) are connected to nodes in

4.3

Case Study: Paper Co-authorship
Network

This section introduces the knowledge discoveredfrom the visualization of the dataset A.
Figure 6 (Upper left) shows that many authors
which have common co-authors are associated to thecommon technical terms, and consequently formed
large clusters consisting of single colors. Then, we
turned the colors of nodes to their centrality, as shownin Figure 6 (Upper right). We clicked several key
nodes placed in the small clusters drawn in bright
red, and observed the co-authorship of such important authors. Other pictures in Figure 6 show theconnections of four important authors.
Here, the ﬁrst and second examples shown in Figure
6 (Center left) and 6 (Center right) represent the con6

nections of important two authors, T. Burke and D.
A. Dawson, belonging to the same cluster and havingvery similar co-authorships. We compared the small
diﬀerences of connections of these two authors. The
ﬁrst one had stronger connections with a few clusters of particular terms, such as Genetic. The second
one had relatively wide connections. She had connections with the clusters of terms Loci, Inbreeding, andIsolation, which the ﬁrst one did not have strong connections to. Our technique reduces the edges inside
the clusters as demonstrated in Tables 1 and 2, andtherefore the edges connecting to the speciﬁed nodes
get more visible in these visualization results rather
than the results by the common technique.
The third and fourth examples shown in Figure 6(Lower left) and 6 (Lower right) represent two otherimportant authors, A. R. Cossins and J. K. Chipman. The former author had connections with clusters of terms Molecular, Expression, and Bacterial,with which the ﬁrst and second authors did not havestrong connections. We found he was a certainly another key person who has diﬀerent specialty comparing with the ﬁrst and second persons. The latter
author had connections with clusters of terms Transcriptomics and Expression, and many other clusters
consisting of uncolored nodes. This visualization suggests that we may need to focus on several other terms
to understand the specialty of the fourth important
person and his related persons. Again, the edges connecting to the speciﬁed nodes are visible thanks tothe property of our technique.

Table 3 shows the statistic of the answers of theparticipants. The result denotes that many participants rated our technique to be better to explore theconnection of key nodes, even though many of themfelt it was easier to ﬁnd key nodes by using the common technique. Several participants mentioned that
it was easier to focus on larger clusters in the visualization results, and therefore it was also easier toﬁnd key nodes in the large clusters. Meanwhile, theyalso mentioned that the key nodes visualized by ourtechnique were more interesting because it is easier toﬁnd how they are connected to other clusters. Several
participants also mentioned that it was diﬃcult to understand how many nodes are connected to key nodes
by the common technique, because many of the edges
connected the key nodes were inside the large cluster. The result suggests that our technique is betterto observe the connection of the key nodes comparedto the common technique.

5

Conclusions and future work

This paper presented graph clustering and layout
techniques for visualization of feature vector embedded graphs, which improves the visibility of importantnodes by separating them from large clusters. The paper showed the experimental result that the presented
technique well separated the important nodes whichhave extremely large number of edges from large clusters, and reduced the number of inner cluster edges,
comparing with more common clustering algorithm.
4.4 User Evaluation
The paper also introduced a case study with a coauthorship network dataset.
We conducted a subjective user evaluation with 13
The way the attribute values are used, for example
university student participants majoring computer
regardingthe coloring, is biased towards the largest
science, not limited to graph drawing or information
value
in
the
feature vector, even when it is not domvisualization. We showed the two sets of visualizainatingtheothers.
For two vectors where the entries
tion results shown in Figures 4 and 5, and asked the
are
quite
similarandlargely diﬀering, respectively,
participants to compare the results by our and comthe
same
value
might
be
picked, which is not always
mon techniques. We also asked them to answer thedesirable.
We
will
investigate
further approaches tofollowing questions.
use the attribute values, tailored to the application
Q1: Which result do you feel is easier to ﬁnd key area and task at hand. In addition, it will be interesting to explore the impact of using diﬀerent meanodes?
sures for distances and importance, e.g. taking into
Q2: Which result are you interested in the key nodes account neighborhood structures. We also started toinvestigate the value of diﬀerent layout methods inand want to click them?
our approach.
Q3: Which result do you feel is better to ﬁnd thenumber of clusters connected to the key nodes?
Acknowledgments This research was partly supQ4: Which result do you feel is better to understand ported by the Australian Research Council throughhow many nodes are connected to the key nodes? Discovery Project grant DP140100077.
7

References[12] B. Shneiderman, A. Aris, Network Visualization by Semantic Substrates, IEEE Transactions[1] U. Brandes, C. Pich, Eigensolver Methods foron Visualization and Computer Graphics, 12(5),Progressive Multidimensional Scaling of Large733-740, 2006.
Data, The 14th International Symposium on
Graph Drawing GD, 42–53, 2006.
[2] C. Correa, T. Crnovrsanin, K.-L. Ma, Visual
Reasoning about Social Networks Using Centrality Sensitivity, IEEE Transactions on Visualization and Computer Graphics, 18(1), 106–120,
2012.
[3] W. Didimo, F. Montecchiani, Fast layout computation of clustered networks: Algorithmic advances and experimental analysis, Information
Sciences, 280, 185–199, 2014.
[4] P. Eades, A Heuristics for Graph Drawing, Congressus numerantium, 42, 146–160, 1984.

[5] E. R. Gansner, Y, Hu, S. North, A MaxentStress Model for Graph Layout, IEEE Transactions on Visualization and Computer Graphics,
19(6), 927–940, 2013.
[6] D. Holten, Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data,
IEEE Transactions On Visualization And Computer Graphics, 12(5), 741–748, 2006.
[7] S. Hong, W. Huang, K. Misue, W. Quan, A
Framework for Visual Analytics of Massive Complex Networks, International Conference on Big
Data and Smart Computing (BIGCOMP), 15–
17, 2014.
[8] T. Itoh, C. Muelder, K.-L. Ma, J. Sese, A Hybrid
Space-Filling and Force-Directed Layout Method
for Visualizing Multiple-Category Graphs, IEEE
Pacific Visualization Symposium, 121–128, 2009.
[9] Y. Ohsawa, N. E. Benson, M. Yachiba,
KeyGraph:
Automatic Indexing by Cooccurrence Graph based on Building Construction Metaphor, IEEE International Forum on
Research and Technology Advances in Digital
Libraries, 1998.
[10] S. E. Schaeﬀer, Graph Clustering, Comuter
Schience Review, 1(1), 27–64, 2007.
[11] L. Shi, Q. Liao, H. Tong, Y. Hu, Y. Zhao, C.
Lin, Hierarchical Focus+Context Heterogeneous
Network Visualization, IEEE Paciﬁc Visualization Symposium, 89-96, 2014.
8

Table 1: Clustering result while adjusting the threshold for sizes of clusters using the dataset A.
N umC
813
354
264
170
159

Our (Figure 3 (a))
Our (Figure 6 (Upper right))
Our (Figure 3 (b))
Our (Figure 4 (a))
Common (Figure 4 (b))

N umN
4,4
4,4
4,4
9,9
33,54

N umIE
5946
5421
5868
6141
8214

Table 2: Clustering result while adjusting the threshold for sizes of clusters using the dataset B.

Our (Figure 5 (a))
Common (Figure 5 (b))

N umC
2117
2076

N umIE
296
6668

Table 3: Subjective evaluation results with datasets A and B.

Question
Q1
Q2
Q3
Q4

dataset A
Our Common
6
7
9
4
9
4
10
3

9

dataset B
Our Common
2
11
10
3
7
6
8
5

Figure 2: An example. (Upper-left) Cluster layout. Rectangular regions are manually overlaid to show
zooming views. (Upper-right) Drawing all the edges without bundling. (Lower-left) Drawing all the edges
with bundling. (Lower-right) Highlight the edges connected to the particular node clicked by a user.

10

(a)

(b)

Figure 3: Clustering and layout result while adjusting the threshold for sizes of clusters. Red circles aremanually drawn to specify that key nodes connected to extremely large number of other nodes are containedin the small clusters. (a) Divided to 813 clusters. (b) Divided to 264 clusters.
11

170 clusters, by our algorithm

159 clusters, by common algorithm

(a)

(b)

(c)

(d)

Figure 4: Comparison of visualization results between our and common techniques. Rectangular regions aremanually overlaid to show zooming views. Red circles are manually drawn to indicate key nodes. (a) Result
by our technique. Two key nodes connected to extremely large number of other nodes remain in the small
cluster. (b) Result applying a common clustering algorithm. The key nodes are enclosed to a large cluster
as indicated by red circles.. (c) One of the key nodes visualized by our technique is clicked. Most of edges
are connected to nodes in other clusters and therefore the edges are more comprehensive. (d) The key nodevisualized by a common technique is clicked. Most of the edges are connected to nodes in the same cluster
and therefore it is diﬃcult to observe the structure around the clicked key node.

12

(a)

(b)

Figure 5: Comparison of graph clustering and layout of Twitter communication data. Rectangular regions
are manually overlaid to show zooming views. Red circles are manually drawn to indicate key nodes. (a) Our
technique well separates the key nodes, painted in red, from large clusters. We can observe that key nodes
connect to large clusters, or bridge many clusters. (b) Clustering by a common technique. The key nodes
are hidden in large clusters. It is diﬃcult to observe the connection between the key nodes and others.
13Expression

Polymorphic
Molecular
Genetic
Isolation

Figure 6: Case study with a co-authorship network.Rectangular regions are manually overlaid to show zooming views. (Upper left) Cluster layout. (Upper right) Importance representation. Important nodes are placedin the small clusters indicated by red circles. (Others) Co-authorship of important persons.

14