Automatic Construction of Web Directoryusing Hyperlink and Anchor Text
Yusuke Suzuki†, Shigeki Matsubara‡ and Masatoshi Yoshikawa‡†

Graduate School of Information Science, Nagoya University, Furo-cho, Chikusa-ku, Nagoya‡
Information Technology Center, Nagoya University, Furo-cho, Chikusa-ku, Nagoya
Email: suzuki@dl.itc.nagoya-u.ac.jp

Abstract- This paper proposes a technique for automaticallyconstructing Web directories from several sites. To construct thehierarchical structure of the directories, the technique finds Web
pages with a super-sub relation, which are connected byhyperlinks, and replaces the relation with a super-sub
hierarchical relation between directories. The techniqueconstructs hierarchical directories by iterating the integration of
directories. As a result of an experiment using five Web sites, it
was possible to construct hierarchical directories containing
Web pages from several sites.

I.

INTRODUCTION

To find target information on the WWW efficiently, it isideal that the Web pages should be organized in advance.
Link collections help users to efficiently access target sites.
Web directories such as Yahoo! 1 and Google 2 are also
considered as hierarchical link collections. However, manylink collections collect only the top pages of Web sites. In
such traditional link collections, when users want to browse
particular pages on several sites, for example, deadlines forpaper submissions to academic conferences or service
contents provided by Internet service providers, they have tobother to seek their target pages by following several links
from the top pages on each site.
Therefore, in order to access to target pages more
effectively, it is hopeful that not only top pages on sites but
also individual pages on sites are also linked. One method is
to put the pages existing in several sites into contents-basedhierarchical directories. For example, for several sites
belonging to academic societies, a directory structure such as
Fig. 1 is constructed. The advantage here is that users caneasily browse pages featuring similar contents in several sites
and grasp the entire contents in related sites. However,
because the desired directory structures vary according totarget category, a large amount of labor is required to design ahierarchical structure and to categorize pages into directories
manually.
This paper proposes a technique for automaticallyconstructing a Web directory consisting of pages in several

1

http://dir.yahoo.com/

2

http://www.google.com/dirhp/

Fig.1. Hierarchical structure of Web directory

related sites. The technique produces the directory structureby extracting the semantic relations between Web pages andclustering them according to their contents. Then, it
constructs hierarchical directory structures by integrating
directories with similar contents.
There are several studies on automatic generation of linkcollections [3], [4]. These studies generate automatically linkcollections by giving a category word to each category.
However, such link collections link to only top pages on sites.
Our study constructs a Web directory from related sites
selected by such method or manual method. Kojima et al.
have formulated a technique for grouping pages in a sitehierarchically by regarding the Web as a directed graph anddecomposing the pages in the site into strongly connectedcomponents [5]. However, this study does not target thegrouping of pages across sites and therefore differ from ourstudy, in which we organize pages from several sites.
We have evaluated the feasibility of our technique. As aresult of an experiment using five Web sites, we constructedhierarchical directory structures containing pages in thesesites. Therefore, we have confirmed the technique to befeasible for automatic construction of Web directories.
This paper is organized as follows: Section 2 describes theconcept of constructing the hierarchical directory structures

Fig.2. Overview of the proposed methodfrom the Web. Section 3 explains the method of constructing
the directory structures. In Section 4, we evaluate our
proposed method experimentally, and after concluding
remarks in Section 5.
II.

OUTLINE OF OUR METHOD

To construct a hierarchical Web directory automatically, it
is necessary to create super-sub relations between directories
and to categorize Web pages into those directories.
Assume that, in Fig. 1, the Web pages on several sites
belonging to academic societies are categorized into two
directories with the super-sub relations: “conference” and“submission.” In this case, it is thought that a semantic supersub relation exists in advance between pages in the superdirectory “conference” and pages in the “submission” subdirectory. This shows that in order to construct a hierarchicalstructure, it is only necessary to extract pages with a semantic
super-sub relation from Web sites. Links might exist between
pages in such a semantic relation. For example, a page
belonging to the directory “conference” links to a“submission” page via a hyperlink. If Web pages with asuper-sub relation can be specified by a hyperlink, the supersub relation between two directories can also be produced byreplacing a super-sub relation between the pages with a supersub relation between the directories. In addition, the Web
pages can be categorized into the directories at the same time.
Figure 2 shows an overview of the proposed method.
A.

Super-sub Relation between Web Pages

It is important to identify Web pages with a semantic
super-sub relation because Web pages connected by links do
not necessarily have a super-sub relation.
When building a Web site, creators put Web pages into
folders and locate them on the server. The operations are done
based on the desires of the sites' creators. For example,
creators tend to put related Web pages into the same folder
and put pages containing more detailed contents into thelower folder. Therefore, we think that Web pages with asuper-sub relation can be identified by using their individual
location on a server.
To utilize such knowledge of Website creators, weinvestigated the relevance between a super-sub relation of
Web pages connected by links and the location of Web pages
on a server. We extracted 200 links from each of four sites at
Nagoya University 3, and judged whether linking pages andlinked pages have a super-sub relation. Then, we classified
the links into four groups according to the relative location
relations of linked pages to linking pages, and investigated
the rate of super-sub relations in each location relation. Figure
3 shows the location relations on a server of the linked pages
to the linking pages.
Table Ⅰ shows the results. The total number of links is
reduced in order to remove the dead links. “Rate” represents
the rate of links connected the Web pages with a super-sub
relation in each of the location relations; 97.5% of the links
belong to “descendant folder” or “same folder.” In addition,
we investigated the relevance to identify the links in a supersub relation in “same folder.” The total number of such links
for which the linking page in “same folder” is “index.html” is
41 and the percentage of these links in a super-sub relation is
85.3%.
B.

Representing Super-pages and Sub-pages

We use an anchor text to represent a super-page and a subpage in a super-sub relation. Because an anchor text is set by
the creators to lead the users into a linked page, it is often abrief description representing the whole contents of the linked
page. We think that characterizing a Web page by the anchor
texts enables clearer representation of the super-sub relation
than characterizing by the contents of the page itself because
the type of contents or the text size may vary from page to
page. Therefore, we represent each page of the super-sub3

http://www.nagoya-u.ac.jp/en/

1.

Fig.3. Location relation of two pages on a server

Both the linking page and the linked page exist on thesame server.
2. The linked page exists in the same folder as the folder
containing the linking page, or in the folder located in adescendant position to the folder containing the linking
page.
3. In the first case in 2., if the page “index.html” exists inthe folder, the linking page is “index.html.” If not, thelinking page is a page that links to the most pages in thesame folder.
Here after, when the superior page is defined as dsup andthe inferior page is defined as d inf , any page-pair p with asuper-sub relation is represented as ( dsup , dinf ) . Also, dsup
refers to a super-page and d inf refers to a sub-page.
B.

TABLE IRATE OF SUPER‑SUB RELATIONS
Location of linked pages

Link

Rate (%)

Descendant folder

136

91.9

Ancestral folder

151

0.7

Same folder

246

58.1

0thers

232

2.6

Total

765

36.0

relations using anchor texts. If the anchor texts are referenceterms such as “Back,” they are excluded as a stopword so as
not to represent the contents of the linked page.
III.

CONSTRUCTING WEB DIRECTORIES

Below we explain the process of constructing Web
directories from several sites.
1. Extracting the super-sub relation between Web pages
connected by links.
2. Clustering the common super-sub relations.
3. Replacing a super-sub relation between Web pages witha super-sub structure between directories, andconstructing hierarchical directory structures byintegrating the directories.
4. Naming each directory.
A.

Extracting the Super-sub Relations

For links connecting pages in a site, Web pages with asuper-sub relation are extracted as pairs of Web pages.
Whether the Web pages are in a super-sub relation or not isdetermined based on the investigation in Section II-A. That is,
if Web pages connected by a link fulfill all of the following
conditions, they are extracted as page-pairs.

Clustering Super-Sub Relations

For the super-sub relations we extracted from several sites, thecommon super-sub relations are clustered. Here, a common supersub relation means that both the contents of the super-pages and thecontents of the sub-pages are similar. The similarity between the
Web pages is calculated by Dice coefficient [1] between the anchor
texts used for the link to each page. That is, when the anchor text inthe link to page d i is ai (1 ≤ s ≤ m) and the anchor text in theslink to page d j is a j (1 ≤ t ≤ n) , the similarity between pagest
di and d j is defined assim(d i , d j ) = max (1≤ s ≤ m ,1≤t ≤ n

2 M is jt
M is + M jt)

(1)

where M is is the number of nouns of ais and M is jt is thenumber of nouns cooccurring to ais and a jt .
The similarity between the super-sub relations isrepresented by the similarity between the super-pages andbetween the sub-pages. The similarity simsup ( pi , p j )between the super-pages and the similarity siminf ( pi , p j )between the sub-pages to the page-pair pi and p j (i ≠ j )are calculated as Eqs. (2) and (3), respectively.

simsup ( pi , p j ) = sim(d isup , d jsup )(2)siminf ( pi , p j ) = sim(diinf , d jinf )(3)

The clustering is done based on the similarities between the
super-sub relations. First, a cluster Ci consisting of a page-pairpi is made as an initial cluster. The integrated clusters are required
to fulfill the following conditions: 1) that both the similarity between
the super-pages and between the sub-pages exceed the thresholdvalue α , and 2) that the average of their similarities is maximal.
The calculation of the similarity between the clusters is applied to acomplete linkage method [6]. The similarity simsup (Ck , Cl )

Fig.4. Integration of the directories

Fig.5. Construction of the directory structure

between the super-pages and the similarity siminf (Ck , Cl )between the sub-pages to the cluster Ck and Cl are calculated as
Eqs. (4) and (5), respectively.

Here, Fij is the frequency of a noun e j in Ai . Then, afeature vector of a directory Di is represented as
xi = ( wi1, wi 2 , , wiN ) . By the Eq. (6), the feature vector
xisup of the super-directory Disup and the feature vector xiinfof the sub-directory Diinf
in the directory-pair
Pi = ( Disup , Diinf ) are calculated in turn.
The similarity between directories Di and D j (i ≠ j ) isdefined by Eq. (7).

simsup (Ck , Cl ) =siminf (Ck , Cl ) =max ( simsup ( pi , p j ))(4)max ( siminf ( pi , p j ))(5)

pi ∈Ck , p j ∈Cl

pi ∈Ck , p j ∈Cl

When the cluster whose similarity exceeds threshold αdisappears, the clustering is stopped. If the number of Web
pages belonging to a cluster is less than m , its cluster is
excluded.
C.

Sim( Di , D j ) =xi i x j(7)

xi x jConstructing a Hierarchical Structure

The clustered super-sub relations are replaced by a supersub directory structure. This is achieved in the following way:
First, the super-pages d isup and the sub-pages d iinf of thepage-pair pi in cluster C are each distributed to thedirectory Dsup and Dinf . Then, the super-sub structure
between the directories is represented as the directory-pair
P = ( Dsup , Dinf ) . Here after, Dsup refers to a superdirectory and Dinf refers to a sub-directory.
The hierarchical directory structure is constructed byintegrating each directory in sequence. For example, when the
super-directories of the directory-pairs are integrated, thedirectory structure which is in a parent-child relation is
produced, as Fig. 4(a) shows. On the other hand, when the
super-directory and the sub-directory are integrated, thedirectory structure which has the third-generation relation is
produced as show in Fig. 4(b).
In integrating the directories, the similarity between the
directories is calculated by using a vector space model [2].
When a set of anchor texts linking to the Web pages in a
directory Di is defined as Ai , the directory Di isrepresented as a feature vector weighted by the frequency ofnouns in Ai . Let a set of nouns be {e1 eN } and a weightwij of a noun e j be given by Eq. (6).

wij = Fij

(6)

Equation

(7)

is

used

to

calculatethesimilarity

Sim( Disup , D jsup ) between the super-directories and thesimilarity Sim( Disup , D jinf ) between the super-directory andthe sub-directory in the directory-pair Pi and Pj .

The directories are integrated by integrating the directories
satisfying the nature of a tree structure in descending order ofsimilarity between the directories. Figure 5 illustrates thisprocess. First, the method calculates all the similarity
Sim( Disup , D jsup|inf ) between the directories that are a part ofthe directory-pair Pi and Pj . Second, it finds the directorypairs Pk and Pl in which the similarity between the
directories is maximal and more than a threshold value β ,and evaluates whether an integration of them will be valid. Ifthey are valid, the directories Dksup and Dlsup|inf in the
directory-pairs Pk and Pl are integrated.
Here, validity of the integration assures that the constructed
directory structure satisfies the nature of a tree structure. The
directories are integrated so that the constructed directory
structure fulfills the following conditions:
1. Each directory has at most one parent directory.
2. The directory structure is a noncyclic structure.
If the directories are integrated or the validity of integration
is not satisfied, the method shifts to the directory-pairs thathave the highest next similarity between directories.
Repeating this operation until the maximal similarity between

the directories is less than a threshold value β , the method
constructs hierarchical directory structures.
When the maximal value of the similarity becomes lessthan the threshold value, the method merges the integrated
directories and creates a new directory. When the integrated
directories are defined as D1 , , Dn and the new directory isdefined as Dr and a set of Web pages in a directory Di isdefined as Wi , then a set of Web pages in the new directory
Dr is defined as Eq. (8).

TABLE IISITES EXAMINED AND THEIR DATA
ID
I
II

Site
Graduate School of Engineering

4

Graduate School of Environmental Studies
6

III

Graduate School of Information ScienceIV

Graduate School of Science

V

5

7

Graduate School of Economics

8

Pages

Links

126

276

281

1192

106

267

280

887

605

3288

n

Wr = ∑ ∪Wi

(8)

IV.

i =1

A.
D.

Deciding Directory Names

The directory names are decided based on a set of theanchor texts linking to the Web pages in the directory. The
policy of deciding a directory name is that a directory namebe a phrase appearing in common with a set of anchor texts
representing the directory and having a certain length.
First, the method extracts any morphological sequence sijfrom a set of anchor texts, Ai = {ai1 , , aiM } , which
represents a directory Di and makes them the candidates for
its directory name. Second, for each morphological sequencesij , the inclusion rate Cover ( sij , aik ) to the anchor text aik
in Ai is calculated using Eq. (9). Finally, the average
inclusion rate Coverave ( sij , Ai ) is calculated with Eq. (10),and the morphological sequence sij whose value is maximal
constitutes directory name.

⎧ Fjki( sij ≤ F jki )⎪Cover ( sij , aik ) = ⎨ aik⎪⎩ 0 (otherwise)(9)M∑ Cover (s , a )Coverave ( sij , Ai ) = k =1

ij

ik

(10)

M
i

Here, aik is the number of morphemes in aik , F jk denotes
the number of common morphemes in sij and aik , sijrepresents the number of morphemes in sij , and M is thenumber of anchor texts in Ai .

4

http://www.engg.nagoya-u.ac.jp/

5

http://www.env.nagoya-u.ac.jp/

6

http://www.is.nagoya-u.ac.jp/

7

http://www.sci.nagoya-u.ac.jp/

8

http://www.soec.nagoya-u.ac.jp/

EVALUATION

Outline of the Experiment

We evaluated the feasibility of our method for constructing
hierarchical directory structures from several sites. In thisexperiment, we used five sites operated by graduate schools at
Nagoya University, which were made independently. Table IIdisplays an outline of the sites. “Pages” represents the numberof Web pages in each site and “Links” represents the numberof links to pages in each respective site. We gathered anchor
texts that represent the Web pages from each site. In setting
the threshold value, parameter α (used for clustering thesuper-sub relations) was 0.5, and parameter β (used forconstructing the directory structure) was 0.6. Clusters whose
the number of members is less than 2 were excluded. We used
Chasen [7] to conduct a morphological analysis in Japanese.
B.

Experimental Results

Figure 6 shows a sample output of the constructedhierarchical directory structures. Figure 6 represents a part ofthirteen directory structures that were produced by integrating
the directories at least once. Each number in Fig. 6 represents
the following: 1) a list of the root directories in theconstructed directory structure, 2) an overall view of thespecific directory structure, and 3) links to the Web pages
belonging to the specific directory.
Tables III and IV show examples of the directory structures.
“Level” represents the hierarchical level of the directory
structure and “Page” represents the number of Web pages inthe directory. Also, “Page” is distributed to each site and each“ID” in “Page” corresponds to the ID in Table II. We can see
from these tables that the pages on several sites are
categorized into a directory structure and that a super-sub
structure, which is valid to some extent, is produced. Fromthese results, we were able to confirm the feasibility of our
method.

V.

CONCLUDING REMARKSIn this paper, we have proposed a method for constructing
hierarchical directory structures from several sites andcategorizing Web pages into them based on hyperlinks andanchor texts. We described an evaluation experiment using
five sites. In the experiment, we were able to constructdirectory structures into which pages on several sites werecategorized, and as a result we confirmed the feasibility of
our method.
In future, in order to construct more valid super-sub
structures, it will be necessary to represent super-sub relations
by using additional information other than anchor texts.
Furthermore, we will examine the practicality of our methodby increasing the amount of experimental data.
Fig.6. Example of system output

ACKNOWLEDGEMENTTABLE IIIThe authors would like to thank all members of theinformation distribution working group in Nagoya University
for their helpful comments.

CONSTRUCTED DIRECTORY STRUCTURE (1)REFERENCES
[1]
[2]

[3]

[4]

[5]
[6]

TABLE IVCONSTRUCTED DIRECTORY STRUCTURE (2)[7]

G. Salton and M. J. McGill: Introduction to Modern Information
Retrieval. McGraw-Hill, 1983.
G. Salton, A. Singhal, C. Buckley and M. Mitra, “Automatic Text
Decomposition Using Text Segments and Text Themes,” In
Proceedings of Hypertext 96, pp. 53-65, 1996.
S. Sato and M. Sato, “Toward Automatic Generation of Web
Directories,” In Proceedings of International Symposium on Digital
Libraries 1999, pp. 127-134, 1999.
O. Segawa, J. Kawai and K. Sakauchi, “Automatic Generation of Link
Collections and their Visualization,” In Proceedings of The 14th
International World Wide Web Conference, pp. 942-943, 2005.
S. Kozima, A. Takasu and J. Adachi, “Structural analysis and groupingof Web pages,” NII Journal, No. 4, pp. 23-35, 2002.
P. Willett, “Recent trends in hierarchic document clustering: a criticalreview,” Information Processing and Management, 24(5), pp. 577-597,
1988.
Y. Matsumoto, A. Kitauchi, T. Yamashita and Y. Hirano, JapaneseMorphological Analysis System Chasen version 2.0 Manual. NAIST
Techinical Report, NAIST-IS-TR99009, 1999.