Diversity-Based HITS: Web Page Ranking by
Referrer and Referral Diversity
Yoshiyuki Shoji and Katsumi Tanaka
Department of Social Informatics
Graduate School of Informatics, Kyoto University
Kyoto, Japan{shoji, tanaka}@dl.kuis.kyoto-u.ac.jp

Abstract. We propose a Web ranking method that considers the diversity of linked pages and linking pages. Typical link analysis algorithms
such as HITS and PageRank calculate scores by the number of linking
pages. However, even if the number of links is the same, there is a big
difference between documents linked by pages with similar content andthose linked by pages with very different content. We propose two typesof link diversity, referral diversity (diversity of pages linked by the page)and referrer diversity (diversity of pages linking to the page), and use
the resulting diversity scores to expand the basic HITS algorithm. The
results of repeated experiments showed that the diversity-based method
is more useful than the original HITS algorithm for finding useful information on the Web.

1

Introduction

As the World Wide Web continues to rapidly expand, both Internet users andthe purposes of Web documents are becoming more extensive and diverse. Usersof the Web are not only computer specialists but also ordinary people, andthe content on the Web has accordingly become broader, including not justinformative documents but also many sub-products of communication, personal
diaries, and so on. This has made Web usage increasingly more complex.
Many major Web search engines use link analysis algorithms such as HITS
and PageRank to rank Web documents. For example, Google uses PageRank,
which calculates popularity scores. These methods focus on the number of linking
documents of each page. The popularity score is determined by recursive calculation using the simple hypothesis that pages linked by many popular pages are
popular pages. The HITS algorithm uses the number of linking and linked pages
to calculate the Hubs and the Authority. However, these methods focus only on
the number of linking pages and are therefore unsuitable for coping with thedemands of complex usages of the Web.
For example, when a novice user wants to know what a “compiler” is andinputs the query “compiler” to a search engine, the result contains many different kinds of pages, such as dictionary pages (e.g., thesaurus), encyclopedia

2

Yoshiyuki Shoji and Katsumi Tanaka

pages (e.g., Wikipedia), introductory articles, commercial sites about specialized compilers, academic articles, and so on. All of them are popular documents
and contain the term “compiler.” However, the most popular documents are
not necessarily useful for all users. In this case, dictionary, encyclopedia pages
and introductory articles would be useful for novice and general users, but otherpages would be more useful for a limited number of specialists. The problem
here is that the existing link analytic methods score every document based on
how many documents link to them instead of checking how it was linked. The
number of linking documents expresses how popular the document is, but does
not express why it is popular.
In this paper, we propose a new link analysis algorithm that considers not
only the number of linking pages but also the diversity of linking pages andlinked pages in order to consider the reason why the page is popular.

Different content
эHigh diversity

dog
pig
rat

cat

cat

cat

n

n

cat
cat
cat

Different content
э High diversity

rat
Out(n)

In(n)Similar content
э Low diversity

dog

cat

cat

cat

p

p

In(p)

Fig. 1. Referrer diversity.

cat

Similar content
эLowdiversitycatOut(p)

Fig. 2. Referral diversity.

Figure 1 shows an example of different ways a page is linked. There are two
pages about cats, both of which are linked by three pages. Page n is the firstpage about cats, which is referred by documents on three different topics: a pageabout dogs, a page about pigs, and a page about rats. Page p is also linked
by three pages, but all of them are about cats. Since each linking page has thesame popularity score, PageRank gives the same popularity score to page p andpage n because both of them are linked by the same number of pages. However,
we suspect there is a big difference in the reason behind their popularity. Pagen is linked by diverse pages. The authors of pages that link other pages may
just be readers of the latter, who create the link after viewing such pages andfinding them interesting. When the topic in the document reflects the interestof the author, a page linked by diverse pages must have a wide readership. An
article with a diverse readership is assumed to contain information that can beinteresting for many people: general information, universal information, and soon. Such information is useful not only for specialists but also for novice users.
In contrast, page p has a biased, non-diverse readership, making it suitable forcertain specialists or members of a specific community. The same can be saidDiversity-based HITS: Web Page Ranking by Referrer and Referral Diversity

3of linking sites and navigating sites(see Fig. 2). In this case, the former linking
page may have been made by a user who has a broad outlook and the latterby one whose range of interest is narrow. These examples demonstrate thatby considering how the linking pages and linked pages are diverse, the searchalgorithm can create a ranking that depends on the reason behind the popularity.
We define diversity as the dispersion of a set of pages. When each page inthe set has a different topic, the diversity score is high, and when all pages
are similar, the diversity score is low. We expand the HITS algorithm, which isthe standard existing link analysis algorithm, with two types of diversity score:referrer diversity and referral diversity. Referrer diversity means how pages thatlink the page are diverse and referral diversity means how pages linked by thepage are diverse. The conventional HITS algorithm calculates Hubs, which means
how the page links many good authorities, and Authorities, which means how
the page is linked by many good hubs. We expand the concept of Hubs andAuthorities with diversity by two simple hypotheses:– The page linking diverse Authorities is a valuable Hub(This Hub can be created by a well-informed generalist who has a wide range
of interests.)– The page linked by diverse Hubs is a valuable Authority(It must be useful not only in a specific field.)
The rest of this paper is organized as follows. Section 2 describes related
work. In Section 3, we introduce the diversity-based link analysis algorithm wedeveloped. Section 4 describes our experiments, and Section 5 evaluates our
method in light of the experimental results. We conclude this paper in Section
6.

2

Related WorkIn this paper, we propose a link analysis ranking algorithm that considers thediversity of linking pages and linked pages to isolate general information. We
adduce three related previous studies. Section 2.1 describes research on diversity, section 2.2 describes other link analytic ranking algorithms, and section 2.3
describes methods to identify general information.
2.1

Diversity

Diversity in information science is a very active research topic. Collective intelligence is discussed particularly actively since the interactive usage of Web sites
has become more common. This is called Web 2.0. Surowiecki [1] presented conditions for data and methods to realize the wisdom of crowds in his 2005 book.
In his view, data need to meet three requirements: “Diversity of opinion,” “Independence” and “Decentralization.” When perfect data are available, they should
be handled with “Aggregation,” which means an algorithm to make up congregate data to knowledge. Link analytic ranking algorithms such as PageRank can

4

Yoshiyuki Shoji and Katsumi Tanaka

be assumed as a voting model of crowds that treat the link as an acceptance.
Thus, any discussion on diversity should consider the validity of the ranking.
Diversity has also been discussed in the field on Information Retrieval. Oneof the most active research topics in this area is the diversification of Web search
result pages. These studies tackle the problem of how many diverse pages canappear in the first result page [2] [3] [4]. The diversification of Web search results
can be classified by two features [5]:– Ambiguous query terms– Available information sources
For instance, the query “jaguar” is an ambiguous query in that it can have several
meanings, such as the car manufacturer, the animal, a personal name, and so on.
To diversify the search result of “jaguar,” ranking algorithms should rank thepages relevant to the different meaning of “jaguar,” alphabetically and without
overlaps. If the aim of the query is identified, it is a problem when the ranking
contains the same kind of information. Search algorithms should therefore create
rankings that cover different types of content.
The research areas that discuss diversity are not limited to information sciences but include sociology, ecology, life science, economics, and so on. Stirling[6] put forth three key factors on categorical diversity: “Variety,” “Balance” and“Disparity.” To come up with the optimal design for the calculation of diversity,
we need to place emphasis on these three factors.
2.2

Link Analysis Algorithms

Here, we present the new link analysis-based algorithm we developed. There aremany past examples that expand PageRank and HITS for each aspect.
For instance, the topic sensitive PageRank [7] deals with the topic of thequery and documents. The TrustRank [8] algorithm uses PageRank for spam
filtering on the basis of the simple theory that spam pages link to both good andspam pages but good pages link only to good pages. Another idea is building
the concept of time and space into PageRank to measure the historic impact [9].
Alternative approaches featuring Web graph analysis have been proposed.
The HITS algorithm [10] uses the link structure on the Web to locate communities in the Web graph. It models the Web graph as a bipartite graph andcalculates the importance of Web pages by convergence calculation. It uses two
types of scores: a Hub score and an Authority score. Authorities are pages thatshow good information, and they obtain a higher score if the page links manyhighly scored Hub pages. Hubs are pages that link to good Authority sites. A
typical example of a good Hub site is a linking site or a good search result page.
The generalized co-HITS algorithm [11] is a HITS-based algorithm that extends
the conventional HITS algorithm from Web links to general bipartite graphs
such as a paper-and-author pair. SALSA [12] has similar algorithms and makes
bipartite graphs based on Hubs and Authorities and has a score calculated basedon random walk. Fast random walk with restart [13] is similar, too, and is used
to compute the similarity between nodes.

Diversity-based HITS: Web Page Ranking by Referrer and Referral Diversity

5

Our algorithm is a HITS-based algorithm with weighting. The unique partis that it defines the weight of the nodes depending on the diversity.
2.3

Finding Information for Novice Users

The aim of this research is to enable novice users to find useful information on
the Web. There are a few previous studies that focus on the comprehensibilityor specialty of a given document. Our method finds the information for beginners by means of a link analytic approach. There has also been much researchon estimating the specialty of a document by a content analysis approach. In
particular, estimating the specialty of terms included in documents is a hot topic.
In the field of natural language processing, several methods that extract
the special terms (i.e., technical terminology and jargon) from documents havebeen proposed. Nakatani et al. [14] proposed a link analytic method using the
Wikipedia category structure to extract special terms. These studies used big
corpora or document sets of limited specialized fields and structural information
to measure the specialty of a term. Our method does not aim to find special terms
but rather special Web pages without using particular datasets. The existing
methods can be used to increase the accuracy of our method in a complementarystyle. There is a previous similar study that aims to find comprehensible Web
pages by the link analytic approach. Akamatsu et al. [15] proposed a TrustRankbased method built on one simple rule: comprehensible pages are more likely tolink comprehensible pages. General pages that we want to find are similar tocomprehensible pages, but this method is based on PageRank, which focuses
only on the number of links and not on how they link.

3

Proposed Method

In this section, we explain our link analysis method based on diversity in detail.
The proposed method is composed of two parts. The first is calculating thediversity of the set of pages. For this part, we propose a method to quantify
how each page in the set is different from the others. This quantification method
creates a feature vector of each page with LDA and then uses the sum of the
distance between the centroid and each page in the set. The second part is
expanding the HITS algorithm by using the diversity of the referrer and referral
documents of each document. The method calculates the diversity of document
links to the document as the “referrer diversity” and of the document linked by
the document as the “referral diversity.” We set these two diversity scores in the
HITS algorithm as the weight of the edge.
The purpose of the proposed method is to find pages that are useful foreveryone: not only specialists but novice users as well. We assume a simple
HITS-based hypothesis: the Hub page that links to diverse Authorities and the
Authority page that is linked by diverse Hubs must feature a wide readershipand widespread interest and therefore be of general interest to everyone.

6

3.1

Yoshiyuki Shoji and Katsumi Tanaka

Determining Diversity

To calculate diversity, each document has to be expressed as a feature vector.
In our method, we take topics from the main text of the document and define
the diversity as how different the topics of a page set are. The most simple
way to express the document as the vector is just counting all the terms in themain text, but when the number of documents increases, the number of vector
dimensions explodes. We used LDA (Latent Dirichlet Allocation) to compress thedimension. Each term in the dataset is assumed to belong to one topic of i typesof topics based on the topic model, where i is the given number of dimensions.
LDA classifies terms into the topics to which they belong. The frequency of topic
occurrence in each document is used as the feature vector of the document. Eachdocument can be expressed by an i-dimensional vector. The length of documentsin the dataset is not constant, so the feature vector has to be normalized.
Note that to create a feature vector, we can use other information in addition
to the topic of the main text, such as the degree of confirmation or denial, thestance of the author, sentiments, and so on [5]. If another kind of diversity isneeded, the algorithm can deal with it by switching function just as well basedon a differently constructed feature vector.
We propose a diversity function d(P ) to calculate the diversity of the document set P . This function takes a high value when each document in P has adifferent topic and a low value when all documents have a similar topic.
Every document is defined as n = (n1 , n2 , n3 , n4 , . . . , nk ), that is, documentsin the dataset are explained as a k dimension feature vector based on the frequency of the topic found in their main text. The diversity, which means how
the documents in the set P are diverse, is defined asd(P ) =

1 X
dist(p, mean(P )),
|P |

(1)

p∈P

where mean(P ) is the arithmetic mean of the set of documents P and dist(a, b)
is the Euclidean distance between vectors a and b. mean(P ) ismean(P ) =

1 X
p,
|P |

(2)

p∈P

and dist(a, b) isvu kuXdist(a, b) = t (a − b )2 ,
i

i

(3)

i=1

where a and b are vectors expressed as a = (a1 , a2 , a3 , . . . , ak ), b = (b1 , b2 , b3 , . . . , bk ).
The definition of d(P ) in our method is the normalized sum of the difference between each page in P and its mean. When the dispersion of√ the documents in
P is high, this value become high. The value drops into [0, 22 ] when the normof the feature vectors is normalized to 1. d(P ) gets its maximum value when all
the articles in P have a different topic and gets its minimum value, 0, when all

Diversity-based HITS: Web Page Ranking by Referrer and Referral Diversity

7

documents in P have the same content or the number of documents in P is lessthan two. We call d(In(n)) the referrer diversity of n, which means how pages
linking n are diverse, where In(n) is the set of pages that link to n. Likewise, wecall d(Out(n)) the referral diversity of n, which means how pages linked by pagen are diverse, where Out(n) is the set of pages linked by n. It is important tonote that this calculus equation is not so novel. You can see the same equationin the K-means clustering as the value to minimize. It is used to express the cohesiveness of the cluster. When the dimension of the vector is one, this equationmeans the variance.
3.2

Diversity-Based HITS Algorithm

In this section, we explain the method to calculate the Hub score and the Authority score by using the diversity-based HITS algorithm considering referral
diversity and referrer diversity.
First, we have to prepare the root set that is used for the result page of thegiven query. We also need a graph for the link analysis, so a base set was createdas the sum set of the root set itself, linking document set and linked document
set of the root set.
The original HITS algorithm defines Hubs and Authorities by mutual recursion, asX
hub(p) =auth(q)(4)q,p→qauth(p) =X

hub(q),

(5)

q,q→p

where both p and q is a page in the base set. It can be expressed as matrix
calculation below:
h = Aa(6)

a = AT h,(7)

where A is the adjacency matrix of the data set and h and a are the vectors ofthe Hubs and Authorities, respectively.

1 if i links j
(8)
Aij =
0 otherwise.
In this case, Aij means the link between node j and node i.
Our method modifies this HITS calculation by using diversity-based factorsd(In(p)) and d(Out(p)) asX
dhub(p) = d(Out(p))
dauth(q)(9)
q,p→q

dauth(p) = d(In(p))

X

q,q→p

dhub(q),(10)

8

Yoshiyuki Shoji and Katsumi Tanaka

where In(p) is the set of pages that links page p, and Out(p) is the set ofpages linked by page p. Two scores: dhub(p) and dauth(p) mean diversity-based
Hubs and diversity-based Authorities. We call d(In(p)) as “referrer diversity” ofpage p, and d(Out(p)) as “referral diversity” of page p. This formula supports
the two diversity-based hypotheses above, that is, “The Hub that links diverse
Authorities is a good Hub” and “The Authority that is linked by diverse Hubs
is a good Authority.”
We can replace the adjacency matrix A of the HITS algorithm. We propose
two diversity-based adjacency matrixes. One is based on referral diversity andthe other on referrer diversity. The expanded adjacency matrix taking referral
diversity is as below:d(In(j)) if i links j
Nij =
(11)
0
otherwise,
where In(j) is the set of pages that links page j. In this matrix, links to the
document that are linked by many different documents are weighted highly andreceive a higher score. In contrast, a higher score is not correlated with pages
linked by many similar pages. The other diversity-based adjacency matrix, O,
which takes the referral diversity, isd(Out(i)) if i links j
(12)
Oij =
0
otherwise,
where Out(i) is the set of pages linked by page i. This matrix means that theweight of the link from the page linking diverse pages become high, and theweight of the link becomes low when the link is from a page linking similar
pages. To consider referral diversity, A should be replaced with O. A can be
replaced with N to consider referrer diversity.
dh = Oda

(13)

T

(14)

da = N dh,

where da and dh are the vectors of the diversity-based Hubs and diversitybased Authorities, respectively. In the original HITS algorithm, the coefficientof propagation is the same with the Hubs to Authorities propagation and the
Authorities to Hubs propagation. The proposed method replaces A and AT
individually with diversity-based matrixes. It makes an asymmetric link weighted
bipartite graph (see Fig.3). To calculate diversity-based HITS, it uses referral
diversity score for back link propagation from Authority page to Hub page, andreferrer diversity score for link propagation from Hub page to authority page.
The expanded HITS algorithm with a diversity-based adjacency matrix canbe solved by the power method.
dh = ON T dh
da = N T Oda.

(15)
(16)

Vectors da and dh converge to Authorities and Hubs when they are normalizedby every phase. Authority-based ranking can be used to find documents andHub-based ranking can be used to find good linking sites or navigating sites.

Diversity-based HITS: Web Page Ranking by Referrer and Referral Diversity
1
Link

i

1
Original HITS

9d(out(i))
j

i

Link

j

d(in(j))Expanded HITS

Fig. 3. Asymmetric propagation value.

4

Experiment

To compare the methods explained in section 3 with the original HITS algorithmand variant methods, we conducted an experimental Web ranking evaluation.
The pages for the given query were sorted by the Authority score of each method
as a search result ranking. Each of these rankings was evaluated by bucketbased evaluation. As stated previously, the aim of the proposed method is toenable both novice and expert users to find information that is useful. We used
one participant who played a novice and classified documents sampled by eachranking into useful and useless documents after reading the main text.
4.1

Variant Methods

To clarify the effect of referral diversity and referrer diversity particularly, we
have prepared two variant methods.
One is the referral diversity-based method. It replaces A with O, and AT isunchanged. It considers only referral diversity and not referrer diversity. This
supports the hypothesis that the “The Hub that links diverse Authorities is agood Hub.”Another one is the referrer diversity-based method. It replaces AT with N T ,and A is unchanged. It considers only the referrer diversity. This supports the
hypothesis that the “The Authority that is linked by diverse Hubs is a good
Authority.”
We compared them to proposed method as baseline methods.
4.2

Data Set

We used The ClueWeb09-JA Dataset, which contains over 67 million pages with
400 million links between them. We prepared eight queries, shown in Table 1.
These included two types of query: those about difficult topics and those about
easy topics. The top 1,000 pages on BM25 sorted ranking were extracted by eachquery as the root set. Pages linking to a page included in the root set and linked
by pages in the root set were used as the base set. The root set was then sorted
by each method. The page evaluated by the participant is a sample of the rootset.
We compared four methods below.

10

Yoshiyuki Shoji and Katsumi Tanaka– Both is the proposed method based on both diversity factors. Pages areranked by the Authority score calculated by Eqn. 9. It uses the referrer
diversity to calculate Authorities and the referral diversity to calculate Hubs.
– Referrer is the variant method based only on referrer diversity. It uses thereferrer diversity factor on the propagation from Authorities to Hubs.
– Referral is the variant method based only on referral diversity. It uses thereferral diversity factor on the propagation from Hubs to Authorities.
– HITS is the baseline method. It is the original HITS algorithm.
Each method is compared using the Authority-based score because in this experiment we want to find the document but not the linking page.
To compare rankings by these methods, we evaluated sample pages of eachranking. First, we split the ranking into 5 buckets: the top 10 pages and pages
ranked from 11―50, 51―200, 201―500, and 501―1,000. We took 10 sample
pages from each bucket. The sampling rate of each bucket was not constant: theupper part of the ranking was sampled in high density and the bottom part was
sampled coarsely. All of the top 10 pages were evaluated by one participant, but
only 2 % of the bottom pages were evaluated. The total number of evaluatedpages was 1,366 by 8 queries and 5 methods after removing duplicates. The
participant evaluated each document in terms of whether or not it was useful fora novice user. Sample pages were sorted randomly for every query. Each page inthe dataset was shown as plain text.
We used GibbsLDA++1 as an implementation of LDA. We classified theterms in the dataset into 100 topics. The LDA sampling was iterated 2,000
times.
QueriesType
Postal service privatization
Easy
Easy
France trip
Easy
The Sagrada Familia
Fish called by different names in life stage Easy
Specialist
Parkinson’s disease
Specialist
Game theory
Specialist
Compiler
Machine learning
Specialist
Table 1. Queries.

4.3

Result

The results are shown in Table 2 and Fig. 4. The original HITS method ranked
many correct pages in the middle of the ranking. All expanded methods were1

http://gibbslda.sourceforge.net/

Diversity-based HITS: Web Page Ranking by Referrer and Referral Diversity

11

influenced by the original method. In the ideal case, it is hoped that many
correct pages appear in the top part of the ranking and that a small number ofcorrect pages appear in the bottom. The both method, which uses both typesof diversity, found more useful pages for novices in the top part of the ranking
than the other methods. The referrer method seems a little bit better thanthe original HITS method in the top part of ranking, but it ranks many correct
pages in the bottom part. The referral method had almost the same accuracy
as the original HITS method. The ratio of correct pages in the data set was 0.22
through all queries.

Precision

0.350
0.300
0.250
HITS

0.200

Both
0.150

Referrer
Referral

0.100
0.050
0.000
1–10

11–50

51–200

201–500

Bucket HITS Both Referrer Referral
1–10
0.175 0.225
0.188
0.175
0.213 0.238
0.213
0.213
11–50
0.225
0.300
51–200 0.325 0.250
201–500 0.213 0.225
0.225
0.213
0.250
0.175
500–1000 0.200 0.225

500–1000

Fig. 4. Results for all queries.

Table 2. Precision of each bucket throughall queries.

The eight queries used in the experiment can be separated into easy queries
and specialist queries. Figure 5 shows the results for two types of query. In theeasy query case, the ratio of correct pages is high: 0.35 through 4 queries. Whenthe search task was easy, the search result contained useful pages for novice
users. Each method had similar precision in the buckets of the upper part of
the ranking. The both method found more correct pages than other methods inthe middle part of the ranking. The referral method had findings throughout
the ranking. The referrer method performed worse than the original HITS. In
the specialist query case, the total number of correct pages in the dataset was
small, with a ratio of just 0.09. It is assumed that pages on specialist topics arecommonly not written in a language easy enough for novice users to understand.
On the whole, the both method, which uses both referral and referrer diversity, works well, especially when the query is specialist. The HITS algorithm
ranked correct pages in the middle part of the ranking, and the two referral orreferrer methods used the original adjacency matrix A. They were influenced
strongly by original HITS result. Although the total number of correct pages
was small, the both method ranked many correct pages in the top part of the
ranking and not many of them in the bottom.

12

Yoshiyuki Shoji and Katsumi Tanaka

Precision

Easy queries

Precision

0.500

Specific queries

0.250
0.200

0.400
0.300

HITS

0.150

HITS

0.200

Both

0.100

Both

0.100

Referrer

0.050

Referrer

Referral

0.000

0.000

ReferralFig. 5. Results by two types of queries.

5

Discussion

The proposed method works better when the query is specific. For example,
when the query is “machine learning,” the proposed method finds three suitable
documents while basic HITS can not find any suitable documents. The detailof pages judged as correct document are online dictionary sites, or introductory
works written by academic society. Dictionary sites and encyclopedia sites are
frequently linked by many individual personal blogs. The author of each blog has
different interests. Authors that are incidentally interested in “machine learning”
will create links to those pages. Another day, they write about their interests,
and link other interested pages. Then these pages have links not only to “machinelearning” pages.
On the other hand, pages judged as not suitable are documents deemed too
difficult, low-quality pages, spam and pages not relevant to the query. In thiscase, some social bookmarking sites were found in the top part of the basic HITS
ranking. They do not contain useful information. These sites strongly connectedwith themselves by internal links. They are characterized by a high score for theboth Hubs and Authority. The basic HITS algorithm is weak to such kind oflink structures. Pages from social bookmarking services feature a similar design
template. Our method estimated their topics as similar to each other.
The proposed method did not work well when the query was easy. The number of correct pages found is same to HITS in the top part of ranking. Our
method found more correct page in the middle and bottom part of ranking. On
this task, the number of pages suitable for novice users is inherently large. Whenthe query is general, relevant pages are general too. For instance, when the querywas “France trip,” each method yielded results mostly containing content frommajor travel agency sites, all of which are about hotels, touristic hot spots oritineraries. When a judgment is determined only by the relevancy between thequery and page, HITS-based algorithms may not be suitable even if it was expanded. There is a possibility that the diversity factor couses reverse effect, thatis, the document linked only by documents about a trip may be relevant to thetrip. Then, non-diverse tight links provide higher relevancy.
The graph of basic HITS algorithm has its peak in the middle of the ranking,where it scores good pages. In the bottom of ranking, there are many pages

Diversity-based HITS: Web Page Ranking by Referrer and Referral Diversity

13

linked by few pages. Most of these pages are spam pages, low-quality pages, orminor pages. In the top part of ranking, a lot of individual pages of major online
service sites appeared. They are linking to each other. Some of them have nocontent inside, i.e., private pages in social bookmarking websites, message pages
in online fora with the aim to drive communication, product introduction pagesof big company websites and so on. These pages are perceived as spam, or are
not relevant to the query.
Even though our method works better than original HITS algorithm in thisexeriment, it’s accuracy is not high enough yet. The method has to be optimized
by fixing and tuning parameters. For instance, the method used in this expetiment are not tuned, so it did not take into account the weight of propagation
score and diversity score, the distribution of diversity score, the tuning of LDA
and so on.

6Conclusion

We proposed a diversity-based Web ranking method that expands on the HITS
algorithm to include two diversity-based hypothesis: 1) that a page linking diverse Authorities is a valuable Hub, and 2) that a page linked by diverse Hubs isa valuable Authority. The objective of the diversity-based HITS algorithm is toenable not limited specialist users but general users to find suitable documents,that is, documents that are useful for novice users. We defined diversity as how
the topic of each document in a set of documents is different from the topicsof the other documents. We call the diversity of pages linking to the page referrer diversity and the diversity of pages linked by the page referral diversity.
We expanded the HITS algorithm by replacing the adjacency matrix with twodiversity-based matrixes. The proposed methods were compared with the original HITS algorithm by their authority scores in terms of finding useful pages
for novice users. The method that uses both referral and referrer diversity could
rank more good pages high, especially when the search query was specific.
As future work, we intend to expand the diversity-based methods further. Our
method abandoned many factors to simplify the model. Of course, the method
itself is built around the idea of diversity, not popularity, so it is necessary to
focus on the number of linking documents, the amount of information, and thepower of influence pages. Moreover, diversity can be defined not only from the
topic of pages: for example, we can define it as authors’ property, sentiment of
documents, temporal-spatial metadata, and so on. We will tackle these issues
with additional diversity-based methods.

Acknowledgments
This work was supported in part by the following projects: Grants-in-Aid for
Scientific Research (Nos. 24240013) from MEXT of Japan and by JSPS Fellows(24 · 5417).

14

Yoshiyuki Shoji and Katsumi Tanaka

References
1. Surowiecki, J.: The wisdom of crowds. Anchor (2005)
2. Carbonell, J., Goldstein, J.: The use of mmr, diversity-based reranking for reordering documents and producing summaries. In: Proceedings of the 21st annualinternational ACM SIGIR conference on Research and development in information
retrieval. SIGIR ’98, New York, NY, USA, ACM (1998) 335–336
3. Wang, J., Zhu, J.: Portfolio theory of information retrieval. In: Proceedings ofthe 32nd international ACM SIGIR conference on Research and development in
information retrieval. SIGIR ’09, New York, NY, USA, ACM (2009) 115–122
4. Capannini, G., Nardini, F.M., Perego, R., Silvestri, F.: Efficient diversification of
web search results. Proc. VLDB Endow. 4(7) (April 2011) 451–459
5. Minack, E., Demartini, G., Nejdl, W.: Current approaches to search result diversification. In: Proceedings of The First International Workshop on Living Web at
the 8th International Semantic Web Conference (ISWC). (Oct. 2009)
6. Stirling, A.: A general framework for analysing diversity in science, technology andsociety. Journal of the Royal Society Interface 4(15) (2007) 707–719
7. Haveliwala, T.: Topic-sensitive pagerank: a context-sensitive ranking algorithm
for web search. Knowledge and Data Engineering, IEEE Transactions on 15(4)(july-aug. 2003) 784 – 796
8. Gyöngyi, Z., Garcia-Molina, H., Pedersen, J.: Combating web spam with trustrank.
In: Proceedings of the Thirtieth international conference on Very large data bases- Volume 30. VLDB ’04, VLDB Endowment (2004) 576–587
9. Takahashi, Y., Ohshima, H., Yamamoto, M., Iwasaki, H., Oyama, S., Tanaka, K.:
Evaluating significance of historical entities based on tempo-spatial impacts analysis using wikipedia link structure. In: Proceedings of the 22nd ACM conference
on Hypertext and hypermedia. HT ’11, New York, NY, USA, ACM (2011) 83–92
10. Kleinberg, J.M.: Authoritative sources in a hyperlinked environment. J. ACM
46(5) (September 1999) 604–632
11. Deng, H., Lyu, M.R., King, I.: A generalized co-hits algorithm and its application
to bipartite graphs. In: Proceedings of the 15th ACM SIGKDD international
conference on Knowledge discovery and data mining. KDD ’09, New York, NY,
USA, ACM (2009) 239–248
12. Lempel, R., Moran, S.: The stochastic approach for link-structure analysis (salsa)
and the tkc effect. Computer Networks 33(1 – 6) (2000) 387–401
13. Tong, H.: Fast random walk with restart and its applications. In: In ICDM
06: Proceedings of the 6th IEEE International Conference on Data Mining, IEEE
Computer Society (2006) 613–622
14. Nakatani, M., Jatowt, A., Ohshima, H., Tanaka, K.: Quality evaluation of search
results by typicality and speciality of terms extracted from wikipedia. In: Proceedings of the 14th International Conference on Database Systems for Advanced
Applications. DASFAA ’09, Berlin, Heidelberg, Springer-Verlag (2009) 570–584
15. Akamatsu, K., Pattanasri, N., Jatowt, A., Tanaka, K.: Measuring comprehensibility of web pages based on link analysis. In: Proceedings of the 2011
IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent
Agent Technology - Volume 01. WI-IAT ’11, Washington, DC, USA, IEEE Computer Society (2011) 40–46