Anchored Maps: Visualization Techniques for Drawing
Bipartite Graphs
Kazuo Misue
Department of Computer Science, University of Tsukuba
1-1-1 Tennoudai, Tsukuba, 305-8573 Japanmisue@cs.tsukuba.ac.jp

Abstract. A method of drawing anchored maps for bipartite graphs ispresented. Suppose that the node set of a bipartite graph is divided into set A
and set B. On an anchored map of the bipartite graph, the nodes in A, which arecalled “anchors,” are arranged on the circumference, and the nodes in B, which
are called “free nodes,” are arranged at suitable positions in relation to theadjacent anchors. This article describes aesthetic criteria that are employedaccording to the purpose of drawing anchored maps and indices which are used
to arrange the anchors so that they satisfy the criteria. It also shows an exampleof taking overviews of networks by using the developed technique.
Keywords: graph drawing, anchored map, bipartite graph, knowledge mining.

1 Introduction
Information with network structures (we call it “network information”) can be seen invarious fields of the real world. In some fields of research, some of the networks are
the research objects such as communication networks and social networks. In recent
years, the approach on large-scale networks is active. However, the problem thatreadability is low in drawing on the networks is not solved still enough. It is an
critical problem we should challenge.
The purpose of this research is to develop visualization techniques to giveoverviews of networks with high readability for mining knowledge. We developed adrawing technique called “anchored map” [5] for the networks which are formalized
as bipartite graphs to achieve the purpose. The node set of a bipartite graph is divided
into two exclusive sets. Here, we call the nodes in one set “anchors,” and the nodes in
the other set “free nodes.” Our technique arranges anchors on the circumference andarranges free nodes at suitable positions in relation to the adjacent anchors. The
anchors are fixed on the circumference as their name suggests and give the effect likethe coordinate system to increase readability of the network diagrams. The name“anchored map” was given by the author, but similar representation techniques werealso used in some other tools, for example, Visual Who [1], which is a visualization
tool for communities and SQWID [3], which is a WWW search tool.
In this article, we describe the technique for drawing anchored maps. First we
explain the aesthetic criteria that are employed according to the map’s purpose and amethod to arrange anchors to fulfill the criteria. Then we propose indices which are
J. Jacko (Ed.): Human-Computer Interaction, Part II, HCII 2007, LNCS 4551, pp. 106–114, 2007.
© Springer-Verlag Berlin Heidelberg 2007

Anchored Maps: Visualization Techniques for Drawing Bipartite Graphs

107

used to arrange the anchors so that they satisfy the criteria and show some evaluation
results of their effectiveness. As an example of usage of anchored maps, we show
network diagrams which visualize relations between goods and time zones when the
goods sold.

2

Anchored Maps of Bipartite Graphs

An anchored map restricts somenodes to certain positions, but
leaves other nodes so they may bearranged freely.
The restricted
nodes are fixed like anchors, hence
the terms “anchors” and “freenodes.”

Table 1. Matrix Style of a Bipartite Graph
C1

C2

m01

1

1

m02

1

m03

2.1 Bipartite Graphs
In this paper, we focus on networks
which can be formalized as
bipartite graphs. Suppose thatG = ( A ∪ B, E ) is a bipartite graph.
A and B are finite sets of vertices,and A and B are disjoint. E is a
finite set of edges, and E is a subsetof A× B .

C3

1

m05

1

m06

1

1

1

1
1

1
1

1

1

m07

1

m08
m10

C5

1

m04

m09

C4

1
1

1

1
1

1

1
1

2.2 Expression Styles ofBipartite Graphs
Table 1 and Fig. 1 show variationsof expression styles of bipartite
graphs. Virtual data is used as an
example. Suppose that there is abipartite graph that represents
relationships
betweenfivecommunities (C1, ..., C5) and ten
members (m01, …, m10). Table 1
Fig. 1. Anchored-map Style of a Bipartite
shows the matrix representation.
Graph
Each row corresponds to acommunity, and each column
corresponds to a member. A “1” in a cell indicates that a member belongs to acommunity; for example, member m01 belongs to communities C1 and C2. Thismatrix cannot intuitively show relational structures because it is not visual.
Figure 1 shows the same bipartite graph shown in Table 1 in an anchored-map
style. The communities are arranged on the vertices of a pentagon as anchors, andmembers are arranged at a suitable position to represent their relationship to the108

K. Misuecommunities as free nodes. The distinction of the nodes is clear, and it is easy to see
the relations between members.
2.3

Drawing Procedure of Anchored Maps

An anchored map is laid out in two steps:(Step 1) Arrange anchors on the circumference at equal intervals. The size (i.e.,
radius) of the circumference is decided according to the size of thedrawing area (i.e., window), and the order of the anchors on thecircumference is decided.
(Step 2) Fix the anchors, and arrange the free nodes at the positions in which theirrelationships to the anchors are appropriately expressed.
The length of the circumference doesn't influence the quality of the layout; it
influences only the size of the drawing. On the other hand, the order of the anchors
has a large influence on the quality of the layout. We do not need to worry about
routing of edges since the edges are drawn as straight line segments.

3 Aesthetic Criteria of Anchored Maps
We should provide aesthetic criteria of drawings of networks and develop drawing
methods which follow the criteria to enable automatic drawing of networks. We
employed the following aesthetic criteria for our anchored map drawing method.
(R1) Nodes are separated mutually more than the lowest distance.
(R2) Nodes connected to each other are laid out as closely as possible (minimize
the total length of edges).
(R3) The number of crossings among edges is minimized.
(R4) Anchors connected to common free nodes are laid out as closely as possible.
(R5) Free nodes connected to common anchors are laid out as closely as possible.
(Free nodes belonging to the same cluster are laid out as closely as possible;
free nodes do not belong to the same cluster are not laid out closely).
The drawing rules (R1), (R2) and (R3) are also employed in many other drawing
methods. We also judged them to be important in consideration of the adaptability tothe purpose of drawing of anchored maps. The rules (R4) and (R5) are specific to theanchored maps. We show formal description of them in the following part of thissection.
3.1 Preparation
Suppose that M is the number of anchors, that is, M =| A | . The anchors are arrangedon the vertices of a regular M-gon (a polygon with M vertices). The vertices of the
M-gon are labeled clockwise from 1 to M. It doesn’t matter which vertex is chosen
to be 1.
Suppose that p (a ) is the position of anchor a and that A( f ) is the set of anchors

which connect to free node f, that is, A( f ) = {a ∈ A | (a, f ) ∈ E} .

Anchored Maps: Visualization Techniques for Drawing Bipartite Graphs

109

3.2 (R4) Closeness of Anchors Connected to Common Free Nodes

Rule (R4) is to minimize d (F ) expressed byd (F ) = ∑ d ( f )
f ∈F

(1)

Here, d (F ) represents closeness between anchors connected to free node f. Definitionof d (F ) is described later.
Clockwise Distance. The “clockwise distance” between the i-th vertex and the j-thvertex is the number of vertices we meet when we trace the vertices of the M-gonfrom the i-th to the j-th clockwise. The clockwise distance l M is defined asl M (i, j ) = ( j − i + M ) mod M(2)

Gap. We introduce a “gap” for every anchor connected to a certain free node.
Suppose that f is a free node and A′ = {a1 , a2 , , ak } is a set of anchors connected to f.

Moreover, suppose that a1 ,, ak have been sorted by the numbers of vertices of the

M-gon. In other words, p(as ) < p(at ) if s < t . The gap for each anchor is theclockwise distance between one node and the next node (the next of a k is a1 ). The
gap g (as ) of node as is defined asg (a s ) = l M ( p(a s ), p(a ( s +1) mod M ))(3)

Closeness of Anchors. When k anchors are connected with a certain free node f, asequence of k gaps is obtained. Removing the maximum gap from the sequence
leaves k-1 smaller gaps. The closeness of anchors is defined by the sum of powers of
k-1 gaps and represented by d ( f ) . Suppose that f is a free node and g1 , g 2 , … , g k −1
is the remainder sequence that excludes the maximum gap from the gap sequence of
the anchors connected to f. The closeness of anchors connected to free node f isrepresented by d ( f ) and is expressed as
k −1

d ( f ) = ∑ g iq

(4)

i =1

For reason why the parameter q is introduced, please access [4].
Small d ( f ) indicates that the anchors connected to the same free node should bearranged close to each other.
3.3 (R5) Closeness of Free Nodes Connected to Common Anchors

It is an intuitive and simple rule to make free nodes which connect to the sameanchors close to each others. When there are two free node f and g, which connect tothe same anchor set, the two free nodes should be arranged close to each other.

110

K. MisueHowever, if there is another free node h, which connects to similar anchor set, we
may want to place h a little closer to f and g than the other free nodes which connect
completely difference anchors. So we defined similarity between two free nodes byusing similarity of sets of anchors connect to the free nodes. The similarity of freenodes f and g is represented by s ( f , g ) and is expressed ass( f , g ) =| A( f ) ∩ A( g ) || A( f ) ∪ A( g ) |(5)

Rule (R5) can be formalized as to increase correlation between “similarities” and“distance,” here similarities are similarities between free nodes and distance is
Euclidean distance between the free nodes.

4 How to Decide the Order of Anchors
We employed numeric indices which can be used as replacement of aesthetic criteria(drawing rules) and conducted the experiment that evaluates the effectiveness of theindices. We have introduced an index in [4]. In this paper, we introduce otherpromised indices and show exhaustive evaluation results.
The distance between adjacent nodes (length of the edges) and the number of edge
crossings are essentially influenced by the order of the anchors. However, thesefeatures are not deterministically decided from only the anchor order. The springembedding in Step 2 and the initial positions of the free nodes also influence thedistance. However, spring embedding has negligible influence compared with the
influence of the anchor order.
4.1 Indices to Decide Anchor Order

The order of the anchors is the most critical for anchored maps. We can evaluate thegoodness of a certain order only after the spring embedding has been processed for acertain anchor arrangement, but to do this for all the possible candidate orders would
require too much computing time. Thus, we need an alternative index that iscomputable in a deterministic way and with a low computing cost.
As such the indices we considered to use drawing rules which can be evaluatedbefore arranging anchors. Rules we considered are (R2), (R3) and (R4), and Penalty2,
Penalty3 and Penalty4, which described in the followings, are indices correspond to
the rules respectively.
(Penalty2) Total length of edges when all free nodes are placed at the barycentersof anchors connected to the free nodes (R2).
(Penalty3) The number of crossings among edges when all free nodes are placedat the barycenters of anchors connected to the free nodes (R3).
(Penalty4) The distance along the circumference between anchors connected tothe same free nodes (R4).
We cannot use the drawing rules (R2) and (R3) as they are as indices because both
two drawing rules can be evaluated only after the positions of free nodes has beenAnchored Maps: Visualization Techniques for Drawing Bipartite Graphs

111

decided. So, we use the values (edge lengths and number of crossings) which supposethat all free nodes are placed at the barycenters of anchors in definition of Penalty2
and Penalty3. Penalty4 is the same as the Penalty proposed in [4].
4.2 Evaluation of Indices

Table 2 shows the size of the five bipartite graphs used for the evaluation. Table 3 andTable 4 show summary of the evaluation results; Table 3 and Table 4 show the resultsof Penalty2 and Penalty4 respectively. Both tables show correlations of the penalty
with drawing rules and ranks of optimal solution (order) for the indices concerning
drawing rules. More precisely, ranks represent the rank of the best anchor order for
the indices in all possible orders,that is, 181,440 (= (10-1)! / 2)
Table 2. Size of the graphs used for the
combinations. There are threeevaluation
values at fields of (R2) and (R3) in
|A|
|B|
|E|
the row of G1 in Table 4. It is
G1
10
16
65
because that there are three bestorders for Penalty4. We had
G2
10
19
84
expected that Penalty2 was
G3
10
40
182
advantageous to (R2) and Panalty4
G4
10
48
251
was advantageous to (R4).
G5
10
98
473
Moreover, we found that Penalty2
was effective for (R3) too.

5 Overview of Network Information
We show an example of overview of network information extracted from an actual
database to explain the effectiveness of the anchored maps.
5.1 Database

A sales database is exploited. Table 5 shows a part of the database. One transaction isrepresented as one record, and one record has purchase date, time, customer name,goods name, goods category and price. We could not get any database of real shops,
so we used a sales database managed in our laboratory. It is not a database of a realshop but the transactions in the database are real. We started to use the database inJune 2006, and 2652 purchases are recorded for half a year until the end of 2006.
Various relations can be extracted from the database. For example, if we focus on
the goods, we can extract relations goods and customers who bought the goods,
relations goods and day when the goods was bought, and relations goods and time
when the goods was bought. Besides, we can extract relations customers and day
when the customers bought, and relations customers and time when the customers
bought. Furthermore, we can extract relations customers who bought similar goods,
and relations customers who bought at similar time.

112

K. MisueTable 3. Evaluation Result of Penalty2
Correlation with Rules

Ranks of Solutions

(r2)

(r3)

(r4)

(r2)

(r3)

G1

0.9996

0.93590.8949

1

1

㧔㨞
㧠㧕
4

G2

0.9997

0.94630.8873

2

1

756

G3

0.99980.97630.8912

1

1

657

G4

0.99970.97090.8416

1

2

62

G5

0.99930.99160.90251

51

Table 4. Evaluation Relust of Penalty4
Correlation with Rules

Ranks of Solutions

(r2)

(r3)

(r4)

(r2)

(r3)

G1

0.89610.83151.00002,25,244

5,53,566

G2

0.88720.82401.0000

8

27

1

G3

0.88800.85921.0000

36

20

1

G4

0.8364

0.79691.0000

273

680

1

G5

0.91220.89541.0000

1

5

1

㧔㨞
㧠㧕
1

Table 5. Database of Sales (portion)
DATE

TIME

CUSTOMERGOODS (in Japanese)

CATEGORY

PRICE

2006/6/2

22:32:24

Szyuࡎ࡯ࡓ࡜ࡦイ㢚ࠟ࡜㉟ᴤ

convenience food100

2006/6/5

20:42:47

Masaඦᓟߩ⚃⨥ࡒ࡞ࠢ࠹ࠖ࡯

soft drink

100

2006/6/5

20:37:35

Nagaࠨ࠶ࡐࡠ৻⇟Ⴎࠄ࡯߼ࠎ

convenience food100

2006/6/5

20:31:20

KSthࠬ࡯ࡄ࡯ࠞ࠶ࡊ୚Ớࠦࠢߣࠎߎߟ

convenience food100

2006/6/5

19:39:50

Yukiᤄߥ߇ࠄߩ࠰࡯ࠬ὾߈ߘ߫

convenience food100

2006/6/5

17:59:05

Shujࠞ࠶ࡊ࠿࡯࠼࡞ࠞ࡟࡯

convenience food100

2006/6/5

16:50:14

Mhro

Όஜ⟤⨥

tea

100

2006/6/5

16:49:36

Mhroࠦࠕ࡜ߩࡑ࡯࠴࠴࡚ࠦ࡟࡯࠻

sweet

100

2006/6/5

15:09:38

Shuj$ NGPF[

coffee100

2006/6/5

14:42:52

Jacqᷓ޿๧ࠊ޿⧯ᱞ⠪tea

100

2006/6/5

14:35:13

Snji

ࠦࠞࠦ࡯࡜

soft drink

100

2006/6/5

13:39:50

Kazuඦᓟߩ⚃⨥ࠬ࠻࡟࡯࠻࠹ࠖ࡯

soft drink

100

2006/6/5

12:52:02

Naga

Όஜ⟤⨥

tea

100

2006/6/5

12:36:17

Snji

Όஜ⟤⨥

tea

100

2006/6/5

11:21:57

Mhroඦᓟߩ⚃⨥ࡒ࡞ࠢ࠹ࠖ࡯

soft drink

100

5.2 Overview by Using Anchored Maps

Fig. 2(a) shows networks which represent relations between goods and time zone
when the goods were bought. Time zones are placed as 24 anchors. Time zone has
cyclic order, so they placed in there proper order. From this map, we find at once that.

Anchored Maps: Visualization Techniques for Drawing Bipartite Graphs

113(a) 24 time zones are placed as anchors(b) Goods are placed as anchors
Fig. 2. Anchored Maps Showing Relations Goods and Time Zone

the activity of the students is very low in the morning. Furthermore, we find that foodsuch as the curries and spaghettis were bought in specific time zone while the canned
coffee and sweets were possibly not depend at specific time zone.

114

K. Misue

In Fig. 2(b), goods are placed as anchors. Goods have no proper orders, so we use
the technique described in Section 4 to decide the order of anchors. We see thefollowing clusters in the map.
(1) Early morning 1: 04h, 05h and 06h(2) Early morning 2: 07h and 08h (no nodes = no activities)(3) Morning: 09h, 10h and 11h(4) Lunch time: 12h, 13h and 14h(5) Evening ~ night: 15h ~ 03h
It might be possible to find such the clusters without the overview of the networks
even by the clustering techniques that already exist. The advantage of overview of
network information is that we can see grounds and the background that compose theclusters as some connecting lines between nodes. By using such the maps we canroughly observe the existence of the clusters at first. Then we understand the reason
where those clusters exist by touching a virtual physical model of relations.

6

Conclusions

We explained an anchored map drawing technique which we developed to increase
readability of network information. We proposed some indices to find good anchor
orders effectively and explained effectiveness of the indices by using evaluation
results. Moreover, we showed an example of overview of network information
extracted from an actual database to illustrate capability of anchored maps at an earlystage of observation of network information.
In the example we found some clusters of time zones from the viewpoint ofactivities of buying. If we would get more rich database we could find more useful
relations and background of the relations; relations between goods and area, relations
between goods and ages, relations between goods and occupation, and so on.
Acknowledgements. The author thanks Mr. Yu Suzuki and Mr. Hirohisa Miyazaki ofthe Interactive Programming Laboratory at the University of Tsukuba for their help indeveloping the sales database and in the experimental evaluation of the indices.

References
1. Donath, J.S.: Visual Who: Animating the affinities and activities of an electronic
community, ACM Multimedia 95. In: Electronic Proceedings (1995)
2. Eades, P.: A Heuristic for Graph Drawing. Congressus Numerantium 42, 149–160 (1984)
3. McCrickard, S.D., Kehoe, C.: Visualizing Search Results using SQWID. In: Proceedings ofthe sixth International World Wide Web Conference (WWW6) (1997)
4. Misue, K.: Drawing Bipartite Graphs as Anchored Maps. In: Proceedings of Asia-PacificSymposium on Information Visualization (APVIS 2006), pp. 169–177 (2006)
5. Misue, K., Watanabe, I.: Visualization of Keyword Association for Text Mining. In: IPJSSIG Technical Report, -FI-55-8, Information Processing Society of Japan, (in Japanese) pp.
65–72 (1999)