Extracting Topic Maps from Web browsing histories
Motohiro Mase1 and Seiji Yamada2
1
CISS, IGSSE, Tokyo Institute of Technology
4259 Nagatsuta, Midori, Yokohama, Japan
2
National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda, Tokyo, Japan{m mase, seiji}@nii.ac.jp
Abstract
In this paper, we propose a method of clustering
to extract Topic Map from the Web browsing history.
The our method is based on the traditional agglomerative clustering with the constraint of the Web structure
and the weight of link relation. Topic Map shows 2Dvisualized overview graph of the Web browsing history,
and the relations between the topics that are gathered
by a user and extracted from the pages around the history pages. Using the Web browsing history, we experimentally evaluate the extracted Topic Maps.

from Web browsing and the information of pages in thesurroundings. Topic Map provides overview of a Webgraph that includes history path, discovery of topic
that has not been seen, and relations between the topics. In this paper, we propose a new method that uses
traditional clustering method with constraint by web
structure to construct Topic Map. Finally, we conduct
preliminary experiments to evaluate our system.

2
2.1

1

Introduction

Information gathering using a huge amount of Web
pages is very useful, and essential for users. The Web
pages increase every year, and exceed at least 11.5 billion in January, 2005[1]. It is very diﬃcult to look for
information that agrees with user’s purpose from Web.
In many cases, users ﬁnd target information by using asearch engine such as Google. On the one hand, users
have the problems that revisiting a page visited once isa diﬃcult task. In 10th GVU WWW User Survey[2],547 of 3,291 users regarded not being able to return
to a page once visited as one of the biggest problems
in using the Web, and 908 of 3,291 users regarded not
being able to eﬃciently organize the information gathered as the biggest problems. Users typically have tolook for a target page from bookmarks or favorites andbrowsing history manually. It is therefore necessary tosupport revisiting pages and organizing the information gathered from Web.
We propose the system that makes visualization ofuser’s Web browsing history clustered by the topic ofpages. Our system shows Topic Map that indicates
2D-visualized graph of Web browsing history, and relation between the information that a user acquired

Related WorkWeb history visualization

Many researches have been reported in the area of
Web history visualization. Domain Tree Browser[3]and Zooming Web Browser[4] provide 2D visualized
history tree by Web browsing with thumbnail imagesof Web pages. VISVIP[5] visualizes user’s path as 2Dgraph that node represents a Web page and an edge
represents link between pages. WebPath[6] visualizes
browsing history path as 3D graph. Browsing Icons[7]shows a task and a session based 2D graph that dynamically draws Web history path. These researches
basically visualize user’s Web browsing history. Our
research, however, classiﬁes the information gatheredfrom Web by topics and provides relations between the
topics in addition to visualization.

2.2

Clustering

Clustering is division of data set into groups of similar data. Hierarchical agglomerative clustering and kmeans clustering[8] are some of basic clustering methods. In hierarchical clustering, data set is recursively
merged into clusters in descending order of similarity
until the number of clusters in one. In k-means clustering, the data set is divided into k clusters desired.
These methods are based on similarity between two

Figure 1: The relaxation of the constraint

data. In a data set that linked as network graph, Girvan and Newman have reported the methods based on
network graph theory[9][10]. Our method is based on
the hierarchical clustering method.

3
3.1

Proposed Method
Topic Maps

Topic Maps provide clusters that classiﬁed by topics of pages and relation between topics in addition touser’s Web browsing history. The methods categorize
pages according to the topics of pages include clustering. Clustering methods that based on only similarity
between Web pages exclude the relation between pages
on Web. We focus link structure on Web that authorsof pages set, and introduce following two ideas to clustering methods.
Web structure The ﬁrst one is constraint by the
Web structure. This means the cluster can be madeonly from the pages linked mutually. It is necessarythat Topic Maps show not only relation between topics but also overview of user’s Web browsing history
path. Classifying Web pages by topics leaving the link
structure of Web pages is suitable to purpose of Topic
Maps. Since original Web link structure is a strong
constraint, we relaxed the constraint by putting a link
between the pages that are reachable within two steps.
This intends to prevent the clusters that are dissimilar in topics from merging into a cluster. Figure 1
shows the relaxation of the constraint. Extending the
Web structure allows page A and page C that havethe same topic to merge into a cluster without making
the cluster which has variation with page C such as

Figure 2: types of link relations

the index page. In that case, we treat a Web graph as
an undirected graph for simpliﬁcation.
Link relations The second one is weighting by kindof link between Web pages. The links are due to the intention of authors of Web pages. Therefore, the links
have some meanings. Parasite[11] categorized links
based on hierarchical relations of directory including
linked pages, and introduced heuristics to estimate
meanings of the links. In this research, we use thecharacterization of link relations based on hierarchicalrelations of linked pages, and hierarchical diﬀerence.
Figure 2 shows relations of linked pages. We classiﬁed link relation into the following three types.
• up/downThis type is relation between a page in the upper directory and a page in the lower directoryin the same Web site. The number in parentheses is depth that shows hierarchical diﬀerence between directories of the two pages. Topic of pagein lower directory means specialization of topic
of page in upper. The similarity of topics thatthe linked pages have is inversely proportional tohierarchical diﬀerence.
• cross
This type is relation between pages in diﬀerent
directories in same Web sites. The number inparentheses is depth that shows hierarchical difference between directories of pages. (For Figure 3, depth from ’/foo/bar/’ to ’/foo/’ and from’/foo/’ to ’/foo/baz/’ are (1) and (2).) The similarity of topics that linked pages have is inversely
proportional to hierarchical diﬀerence.

Each page of the page set is an initial cluster. The
following two evaluations are calculated for all pair ofclusters that have link relations. The ﬁrst is similarityof clusters, and the second is cluster cohesiveness.
similarity of clusters Similarity of clusters is
weighted liner sum of these two values. The ﬁrst issimilarity of contents between clusters, and the second is cohesiveness of cluster. Here is description of
the values.
• similarity of contents

Figure 3: usage of link relations• out
This type is relation between pages in other Web
sites. Both pages have similar topics, basically.
Our method is not simply clustering method basedon only similarity but characterized by constraint oflink structure and weight of link relation in addition
to similarity. Figure 3 shows the example of usageof link relation. Topics of page B and page C are
subtopic of the topic on page A. In this case, page
B and page C are ﬁrst merged into cluster D thathas topic A . Next, page A and cluster E are merged
into cluster E with topic A. Such accumulation orderof pages provides the pseudo hierarchical relation of
topics. When there is little diﬀerence of similarities
between pages, the usage of correction with weightthat gives priority to relation between page B and page
C more than relation between page A and page B
result in the order.

3.2

Clustering algorithm

3.2.1

Preprocessing

We extract Topic Maps from a Web page set that isuser’s Web browsing history pages and pages aroundthe history pages. The page set is history pages andpages that are accessible by expanding outbound links
and inbound links from history pages within n steps.
As shown in section 3.1, pages that are reachable
within two steps on Web undirected graph are linked
on top of the pages linked on original Web graph. Only
these linked pages merge into clusters.

Web pages are characterized by terms and weightof terms in vector space.The terms and weight
are extracted by Chasen and TermExtract fromHTML ﬁles that removed tags, and corrected byinverted document frequency. Then, the document vector of page s is deﬁned as: ds =(w0 , w1 , ..., wN ), where wi is weight of term i.
Therefore, similarity between page p and page q
is deﬁned as the following equation.
simc (p, q) =dp · dqdp  × dq 

Similarity between clusters are similarly calculated by above-mentioned equation.
• weight of link relation
Weight value of link relation between pages aredeﬁned by kind of the relation. The value between
page p and page q is deﬁned as the following threeequations.
weightlr (p, q) =weightlr (p, q) =weightlr (p, q) =

0.25
× Clt
(up/down)(depth + 1)
0.5
× Clt
(cross)(depth + 1)⎧
0.4 × Clt⎪⎪⎨
(out, τsim ≤ simc (p, q))0⎪⎪⎩(out, simc (p, q) ≤ τsim )Clt shows type of link. Clt is 2 if the type is twoway on the Web graph, and if the type is one-way
on the Web graph, Clt is 1, and if type is theextended link, Clt is 0.5. τsim is average of all
simc of links that are ’out’ type.
The weight between cluster s and cluster t is average of all weightlr of pages that are a page belong
to cluster s and a page belong to cluster t whichhave link relation.

The similarity of clusters is deﬁned as the following
equation.
f (p, q) = α×simc (p, q)+(1−α)×weightlr(0 ≤ α ≤ 1)

Cohesiveness of cluster Cohesiveness of a cluster
is average of similarities between the cluster and pages
belong to the cluster. The cohesiveness is deﬁned as
the following equation.
Nsimc (s, i)c=Ni is a page belong to a cluster s. N is number ofpages that are attached to cluster s.

3.3

Clustering algorithm

Our method is based on the agglomerative clustering with the constraint of the Web structure and theweight of link relation. The following is the procedureof our clustering method. τc is threshold of cluster
cohesiveness and running from 0 to 1.
1. Initialize
Calculate all similarities between two clusters
having link relation. A threshold of cluster cohesiveness τc is set to β.
2. Select a pair of clusters
Select a pair of clusters that have the highest similarity.
3. Merge the clusters
Merge the selected clusters merge into a new cluster. The document vector of the new cluster ismade by composition of the vectors of the clusters and normalization. The link relations of thecluster are total of the link relations of the clusters.

The procedure for clustering provides Topic Map
with the parameter that τc is β. The procedure canprovide Topic Map of other τc recursively with theclusters remaining and the new value of cohesiveness.

4

Extracted Topic Maps

We conduct preliminary experiments to evaluate
our proposed method. A Web page set is obtainedby expanding outbound and inbound links from the
Web history pages by n steps. The number of thelinks expanded in each step is b. The links are selected at random. In the following experiments, n andb are set to 4 and 3. The method extracts Topic Maps
from the Web browsing histories. Topic Maps show
the graph generated from clusters and edges by springmodel method. The weight of edge is based on similarity between clusters. A node represents a cluster.
The scale of a node is based on the number of pages
belong to a cluster. A node with ring has the history
pages. A label of a node shows upper three words ofthe vector.

4.1

Test 1 : Searching the font settings of
Meadow

This browsing history is searching the font settingsof Meadow (Emacs editor on Windows OS). The total of history pages is 5. Figure 4 shows Topic Map
which is extracted from the history by clustering in
twice. τc is 0.5 and 0.4. The nodes which have relevant topics is basically around the ringed nodes. The
node in the center is interesting. The node of topic
is Cygwin (Linux-like environment for Windows). Although the similarity of the contents between Cygwin
and Meadow is not apparent, the graph shows theirrelevance.

4. Calculate CohesivenessCalculate cohesiveness of the new cluster. If thevalue of cohesiveness is lower than the thresholdτc , exclude the cluster from a candidate for merging and go to step 6
5. Recalculate new similarities
Recalculate all new similarities between the newcluster and clusters linking to the cluster.
6. Check state
Check whether pairs of the clusters remain. If thepairs remain, return to step 2, if not so clustering
is done.

4.2

Test 2 : Searching the simple backup
systemThis browsing history is searching the backup system. The total of history pages is 5. Figure5 shows
Topic Maps which is extracted from the history byclustering in twice. τc is 0.5 and 0.4. The backup
system pdumpfs is based on dumpfs on Plan9 OS andmounted by Ruby scripting language. Then, the nodes
including these topics are adjoining. The nodes at theright of the graph are closely linked. The topics ofthese nodes include OpenSSH and OpenBSD roughly.
The fact that OpenSSH is primarily developed by theFigure 4: Test1. Searching the font settings of Meadow

OpenBSD Project causes the close link relation on theWeb.

5Discussion

As shown by the experiments, use of the link relations on the Web enlarges the relations of the topics extracted by the only similarities. Basically, thelink relations on the Web are set by the authors of
the pages. Then, the expansion by the relations is
adoption of a new viewpoint. In section 4.1, Linking
Meadow and Cygwin is the viewpoint that they are
UNIX tools on Windows. This viewpoint in the Web
structure is concern to users. Topic Map helps users
with discovering the viewpoint. In our method, thecalculation of the similarities is limited to the linked
clusters. Then, the method is capable of reduction in
the calculation cost based on the number of links, although the method of the computational complexity isO(n2 ) as well as the traditional hierarchical clustering.
On the one hand, the constraint of the Web structure
allows only the linked clusters to merge into a clusterin our method. Therefore, the cluster that has various
topics is merged, if the pages with several independent

topics or multiple topics are adjacent. It causes thenoise though the relaxation of the constraint reduces
it. In addition, our method employs the weights of
the link relations based on the hierarchical diﬀerenceof the directories with pages. Then, the method cannot be very eﬀective in clustering the pages that are
dynamically generated such as Wiki pages; the pages
are basically in the same directory and distinguishedby query words.

6

Conclusion

We proposed a new clustering method with a constraint of the Web structure and a weight based ona link relation. The constraint of the extended structure prevent clusters that are dissimilar in topics frommerging into a new cluster, leaving the Web structure.
Applying the weight to a traditional clustering provides a cluster that has few diﬀerences. The method
extracts Topic Map from a Web page set based on abrowsing history. We conducted preliminary experiments to evaluate the method and veriﬁed that Topic
Maps show useful relations between topics.

Figure 5: Test2. Searching the simple backup system

References[1] Gulli, A.,Signorini, A. The Indexable Web is Morethan 11.5 Billion Pages, Proceedings of the 15th
WWW conference, 2005.
[2] GVU’s WWW Surveying Team, GVU’s 10th
WWW User Survey: Problem Using the Web,
Gerogia Tech, Atlanta, GA, 1998.
[3] Gandhi, R., Kumar, G., Bederson, B. B., Shneiderman, B., Domain Name Based Visualiazation of
Web Histories in a Zoomable User Interface, Proceedings of WebVis2000, pp. 591-598, 2000
[4] Benjamin B. Bederson, James D. Hollan, Jason
Stewart, David Rogers, Allison Druin, David Vick,
A Zooming Web Browser, Proceedings of 9th Annual ACM Symposium on User-Interface Software
and Technology, 1996.
[5] Cugini and J. Scholtz, VISVIP: 3D Visualizationof Paths through Web Sites, Proceedings of the International Workshop on Web-Based Information
Visualization (WebVis’99), pp. 259-263, 1999.

[6] Frecon, E., Smith, G., WebPath - A Three Dimensional Web History,Proceedings of Information Visualization Symposium (InfoVis98),pp 3-10, 1998.
[7] Matthias, M., Benjamin, B, B., Browsing Icons:
A Task-Based Approach for a Visual Web History, HCIL-200119, CS-TR-4308, UMIACS-TR2001-85, HCI Lab, University of Maryland, Maryland, USA, 2001.
[8] A. K. Jain., R. C. Dubes., Algorithms for Clustering Data, Prentice Hall, 1998.
[9] Michelle, G., M. E. J. Newman, Community structure in social and biological networks, Proc. Natl.
Acad. Sci. USA, Vol. 99, No. 12, pp. 7821-7826,
2002.
[10] M. E. J. Newman, Fast algorithm for detecting
community structure in networks, Phys. Rev. E
69, 066133, 2004.
[11] Spertus, E., ParaSite: Mining Structural Information on the Web, Proceedings of the 6th WWW
Conference, 1997.