DEIM Forum 2019 F5-1

Clickcount-Weighted PageRank Algorithm for Finding High Quality
Documents
He LIU † and Mizuho IWAIHARA ‡† 早稲 田大 学 大学 院情 報生 産 シス テム 研 究科
‡808-0135 福 岡 県北 九 州 市若 松 区ひ び きの 2-7-N251
E-mail:†liuhe@akane.waseda.jp,‡iwaihara@waseda.jp

Abstract Finding high quality documents has been discussed, since users always want to not just relevant
documents, but those of high quality and informative. I ncoming links of a web document can be viewed as thequality assessment by document authors. On the other hand, detailed click count information on each page orlink can be viewed as popularity and informativeness judgement by site viewers (users).However, existing link
analysis algorithms, including HITS and PageRank, exploiting static link connectivity between pages, which is
not very adequate. In this paper, we propose an algorithm called CWPR (Clickcount -Weighted PageRank),
which extends the original PageRank algorithm by smoothly integrating link structure and click coun t
distribution, to score quality of documents. Our evaluations on finding featured articles and good articles ofEnglish Wikipedia show that our WPR algorithm shows better performance on a large Wikipedia corpus thanalgorithms that utilize link graphs or click counts only, and clickcount-weighted HITS algorithms.
Keyword Link analysis, Document assessment, Click graph, PageRankvarious versions of PageRank, such as Topic-sensitive

1. Introduction
Since information retrieval systems came into being,

PageRank, Weighted PageRank [9, 15], they do not utilize

ranking of retrieval results has always been a question for

counts on links, which can be viewed as the votes fromresearchers to solve. In modern information retrieval

users to a page. On the other hand, the link itself can besystems, the result of one web query can contain thousand

viewed as votes on pages by users who visited the same

millions of entries of pages, while in most cases, users can

page. By integrating the quality evaluations of pages

onl y read through or even looking through very a few ofthrough both link graph and click graph, the biases caused

them. Therefore, the ranking of retrieval result s is quite

by document authors can be reduced. So our method issignificant. With a good ranking, users can find articles of

expectedhigh quality and informativeness with less effort.

structure-based and click-based approaches. The clickto

exploitthebenefits

of

both

link

Many methods based on link analysis on web pages

count-weighted HITS algorithm [16] is the first attempt tohave been developed for evaluating the significance ofextend the HITS algorithm by integrating click counts andhyperlink structure [8, 13]. The HITS algorithm computes

link structure. This paper explores extension of PageRankhub and authority scores for each page through mutual

by these settings.

recursion [6]. The PageRank algorithm is based on the

For experimental evaluations, wechooseEnglishrandom surfer model and a PageRank score on a page

Wikipedia articles to observe the result of our algorithm

represents

page[5]. The English version Wikipedia holds over one million[7].However, only static link connectivity between pages

articles of different quality levels, where the quality

is not very adequate to acquire a very solid evaluation oncontrol is essential. In Wikipedia, high -quality articles

the quality of documents. Thus, in this paper, we discuss

assessed by Wikipedia editors will be selected as featured

smoothly integrating link structure and click countarticles by certain criteria [10]. Thus such featured

distribution to evaluate the quality of documents.

articles are chosen to be the gold standard for our quality

likelihood

that

a

user

is

on

the

To achieve this goal, we extend the original PageRank

evaluation of pages. Also, we use original PageRank andmodel by integrating link structure and click countthe click count -weighted HITS algorithm [16] to compare

distribution,with our proposed method.

and

we

proposed

CWPR(Clickcount -Weighted PageRank). Although there are

For click count data, we utilize publicly available

transition data from Wikipedia of May 2018[ 14]. Thisquality evaluation of articles

monthly-generated data is extracted from the server log

Wikipedia grading scheme.

isaccessible throughfor the English desktop version of Wikipedia, whichcontains aggregated and anonymized page requests in the

3. Proposed algorithm

form of (referrer, resource) -pairs. From the click data and3.1 Original PageRank algorithm

the dump xml file of English Wikipedia, we create

The original PageRank algorithm is based on a ver y

directed graphs - Wikipedia click graphs where nodes are

simple idea defined by a very concise formula. The idea isarticles, edges represent links between articles and click

such that a page is important if it is pointed to by othercount of a link will be partly influence the link ’s edge

important pages [7]. The definition is:weight. Our evaluation on finding articles of high quality

PR 𝑖 =in English Wikipedia shows that our CWPR shows better

PR (𝑗 )
𝑗 ∈𝐵𝑖 L(𝑗 )(1)performance on the large corpus than the algorithms that

Here,PR 𝑖 is the PR value (or PageRank score) of node

utilized link graphs or click graphs only and the clicki. 𝐵𝑖 is the set of nodes having links pointing to node i.

count-weighted HITS algorithm.

L(j) is the number of the outgoing links from node j.

The rest of this paper is organized as below: In Secti on

To deal with the loop problem and other problems like

2, we introduce related work about ranking retrieval result.

dangling nodes, a random teleportation is added (theIn Section 3, we introduce our proposed method in details.

random surfer will not only follow the link structure but

In Section 4, we introduce our experiments on English

also may go to some node directly and randoml y).

Wikipedia datasets. In Section 5, we make a conclusion

Correspondingly, the PageRank score is modified to theand discuss our future work.

following:
PR 𝑖 =

2. Related work

1−𝑑
𝑁

+ 𝑑

PR (𝑗 )
𝑗 ∈𝐵𝑖 𝐿(𝑗 )(2)Many methods base on link analysis have been proposed.

Here, N is the number of nodes in the graph, and d is

The original HITS algorithm computes hub and authority

the damping factor. In this paper, d is set as thescores for each page through mutual recursion [6], while

recommended value 0.85. This is a normalized version,

the original PageRank algorithm computes PageRankmeaning that the PR value is the probability of finding thescore for each page according to the incoming link countrandom surfer on the node and the summation of the PRof the page iteratively.

value of all nodes are alwa ys 1.

There is also another approach of document qualit y

The PageRank algorithm is evaluated by the following:evaluation: by informativeness and comprehensiveness .

PR 𝑘+1 𝑖 =Through numerical features such as term distribution,
document length or relationships with other documents,
the quality of one document can be evaluated.
Blumenstock showed how word count can be utilized as

1−𝑑
𝑁

+ 𝑑

PR 𝑘 (𝑗 )𝑗 ∈𝐵𝑖 𝐿(𝑗 )(3)

The PR value of node i in the (k+1)-th iteration is
calculated by the PR values of nodes in 𝐵𝑖 in the k-th
iteration. The overall process is as follows:a proxy for article quality [2]. Calzadatried to evaluate the1)

Equally distribute the same PR value to all nodes;

quality of Wikipedia articles by authors and editing2)

Use (3) to calculate the PR value for each node;

history of articles [3]. Suzuki and Yoshikawa proposed a3)

Normalize the PR values of all nodes;

method to identify Wikipedia articles of good quality by

4)

Check if the whole result has reached the finish

mutually evaluating editors and texts [12]. De La Robertie

condition. If yes, to 2) again. Else, to 5);

proposed to use the collaboration network of Wikipedia

5)

articles to measure article quality [11].

Here, the finish condition depends on the task, either

However, these features ma y not lead to the same result
as readers’ perceptions. Here, the readers’ feedbacks areimportant indicators of document quality, which areavailable in various forms, such as click counts or pageviews, likes or comments and retweets [1]. In the case of

Rank the nodes by PR values;

max iteration limit or tolerance of difference between two
iteration is popularly used.
As the PR value becomes larger, the corresponding node
becomes more important.
3.2 Click count-weighted HITS

Wikipedia, since there exists publicly-available data such

We refer [16] for the definition of click count -weighted

as edit histories of articles, anonymized click counts, andHITS algorithm. In contrast to the original HITS algorithm

and other link analysis-based algorithms, this modified

𝐵𝑗 : The index of articles which have an outgoing link to

HITS algorithm uses both link and click counts for hub

article j.

and authority scores. So we compare this algorithm with

d: 0 < 𝑑 < 1 is a dumping factor.

our proposed method. According to [16], the ClickWith notations above, we now introduce our proposed

count-weighted HITS algorithms are defined as following:

method. Since the PageRank algorithm is based on the
random surfer model [7], we can understand it from the

Version1:

point of view of probability. In the normalized version of𝑛𝑎𝑢𝑡𝑕 𝑖 =𝑙𝑜𝑔(𝑕𝑢𝑏 𝑗 ∗ 𝑤 𝑗 𝑖 + 1)

PageRank, the PR value of a node is the probability of

𝑗 =1

finding the random surfer on the node. So the PageRank𝑛score of article i is:𝑕𝑢𝑏 𝑖 =

𝑙𝑜𝑔(𝑎𝑢𝑡𝑕 𝑗 ∗ 𝑤 𝑖 𝑗 + 1)

PR 𝑖 = 1 − 𝑑 𝑊(𝑖) + 𝑑

𝑗 =1

𝑗 ∈𝐵𝑖 𝑃 𝑖 𝑗

PR(𝑗)

(7)

Here the PR value of node j is distributed by P 𝑖 𝑗 , the(4)Here, some notations are introduced:

conditional probability of any user on j going to i, whichis estimated as:𝑎𝑢𝑡𝑕 𝑖 : the auth score of article i.

𝑃(𝑖|𝑗) =

𝑓 𝑗𝑖

(8)

𝑘 ∈𝐴 𝑗 𝑓𝑗𝑘

hub[i]: the hub score of article i.
𝑒𝑖𝑗 : the number of links from article i to article j.

Since the click count varies within a wide range in then: the number of nodes.

graph, we need to log-damp the click counts. We combine

w[i][j]: the click counts of a link from article i t o

the link counts and log-damped click counts with thearticle j, will be 0 if there is no link from i to j.

balancing factor 0 ≤ 𝛾 ≤ 1, as follows:
𝑓𝑗𝑖 = (1 − 𝛾) 𝑒𝑗𝑖 + 𝛾 𝑙𝑜𝑔(𝑐𝑗𝑖 + 1)

Version2:

For the teleportation pr obability, it is distributed by node𝑛𝑎𝑢𝑡𝑕 𝑖 =(𝑕𝑢𝑏 𝑗 ∗ 𝑒 𝑗 𝑖 + 𝑘 ∗ 𝑝 ∗ 𝑙𝑜𝑔⁡
(𝑤 𝑗 𝑖 + 1))

weight W(i), which is defined as follows:

𝑗 =1

𝑊 𝑖 =
𝑛

𝑕𝑢𝑏 𝑖 =

(9)(𝑎𝑢𝑡𝑕 𝑗 ∗ 𝑒 𝑖 𝑗 + 𝑘 ∗ 𝑝 ∗ 𝑙𝑜𝑔⁡
(𝑤 𝑖 𝑗 + 1))
𝑗 =1

𝑐𝑒𝑥 −𝑖𝑐𝑒𝑥

0.5∗ 0.5 + 𝑁

(10)

Here, the 𝑐𝑒𝑥 −𝑖 is the click counts of external links t onode i, 𝑐𝑒𝑥 is the total click counts of external links to the(5)graph.

Here, two new parameters k and p are introduced, such

4. Experimentsthat k is a coefficient determining how much the

4.1 Datasets

log-damped click count affects the final score and p is

4.1.1 Click count information

defined as following:

For the click count information, we choose the tsv file1𝑛𝑝 = 𝐴𝑉𝐺 (log ⁡(𝑤 𝑖 𝑗 +1))

(6)

𝑖𝑗

of the clickstream file generated in May 2018[17].This
monthly-generated data file is extracted from the server

3.3Clickcount-Weighted PageRank(CWPR)

log for the English desktop version of Wikipedia, which

The original PageRank is based on link graph only, whichcontains aggregated and anonymized page requests in theis not ideal in a situation where click count distribution isform of (referrer, resource) -pairs. Also, the times ofavailable. Thus, we extend the original PageRank b yoccurrence of pairs are recorded, while records caused bysmoothly integrating link counts and click counts.

bots and web crawlers, as well as transitions occurring

Before introducing the proposed method, we first need toless than 10 times, are removed. There are three types of

introduce several notations and definitions.

(referrer, resource) -pairs as follows:

𝐿 = [𝑒𝑖𝑗 ]: Link adjacency matrix. The element 𝑒𝑖𝑗 ≥ 0

1.

equals the number of links from article i to article j.
N: The number of articles in the dataset.
𝐶 = [𝑐𝑖𝑗 ]: Click count matrix.

and the referrer article have a link to the resource.
2.

Here, 𝑐𝑖𝑗 ≥ 0 is the countof clicks on the link from article i to article j.

Link: if the referrer and resource are both articles
External: if the referrer host does not match the
URI pattern en(.m)?.wikipedia.org.

3.

Other: if the referrer and resource are both articles

𝐴𝑗 : The index of articles which have an incoming link

but the referrer does not link to the resource. This

from article j.

can happen when clients search or spoof theirrefer.

For evaluationof ranked results, we utilize theHere, we only utilize (referrer, resource) -pairs whose

NDCG@k (normalized discounted cumulative gain) score.

type is “Link” or “External”, which means that onl y click

For the rank parameter k of NDCG@k, we set two values:

counts of links within English Wikipedia and click counts

fixed value(1000) and relative value(top 1% of the totalof links from external sites are taken into consideration.

nodes), to evaluate both the top part and the overall

The counts of links within English Wikipedia areutilized to determine the weights of edges while the counts

ranking result(viewing the 1% top part as the sample) .
NDCG@k score is defined as follows :of external links are utilized to determine the weights ofnodes. The total click graph extracted from this data file is𝐺𝑤𝑕𝑜𝑙𝑒 −𝑐 .

𝐷𝐶𝐺@𝑘

𝑁𝐷𝐶𝐺@𝑘 =(11)

𝑖𝐷𝐶𝐺@𝑘Here, DCG@k is given below with generalized rank:

4.1.2 Article sets

𝐷𝐶𝐺@𝑘 =We extracted 100 sub-graphs of 10 groups from the𝑔(𝑖)𝑘
𝑖=0 𝑙𝑜𝑔 (𝑖+1)

(12)

2

graph 𝐺𝑤𝑕𝑜𝑙𝑒 −𝑐 of different sizes. For each group i,

Here, k is the rank range, and i is the rank of a node.

i=0,…,9, we set a minimum node count min i and a

Similarly, iDCG@k is calculated with the same formula

maximum node count max i , such that max i = min i +50000

with an ideal rank result.

and min i =100000*i. For each group, 10 sub-graphs of the

4.2.1 Editorial Team Assessment of the WikiProject

node count range [min i , max i ] are generated, by the

Since the NDCG@k score requires an ideal ranking,following process:here we use the manually assessment result of articles

1)

Choose a root node by random.

from Wikipedia Edit orial Team Assessment as our golden

2)

By breadth-first-search, nodes adjacent to thestandard [1]. There are totally 5694854 articles assessedcurrent node set are added, until the node countand classified into 7 classes. To observe the rank result of

becomes between min i and max i , or no more nodes

articles of all quality level, the gain score g(i) is set as

can be added.

follows:

3)

If there are not enough nodes, go back to Step 1.

The set of the sub-graphs of group i is represented as 𝑆𝑖 .
The largest sub-graph used in our experiments contains
about one million nodes.
4.1.3 Link information
Since the click count file only contains links counted atleast once, links not clicked during the collection period
are not included. Also, there exist parallel links between
two articles. To correctly count links between articles into
ei j , we use the widely used tool Wiki-extractor, which canpreserve the link tags in the “Lead” and “Body” parts of a
Wikipedia page. Thus, the link counts of our dataset

Table1: gain score scheme for NDCG@k score
Quality level of article i

Gain score g(i)FA(Featured Article)
A(A-class article)&
GA(Good Article)
B(B-class article)

4

C(C-class article)
Start(Start-class article)&
Stub(Stub-class article)&
Unassessed

1

3
2

0

reflect all the links in the “Lead” and “Body” parts.
Here, we use the page structure from [4].

4.2.2NDCG@k(part) score
To observe the rank result of article of high quality, here
we use another kind of relevance score scheme to calculate
the NDCG@k(part) score. In this case, only the rank ofarticles of FA, GA, A quality level can influence the
NDCG@k score. Here is the scheme:
Table 2: gain score scheme for NDCG@k(part) score

Figure 1 : Visual s tr uc tur e o f a t ypi cal W ikipedia pa ge

4.2 Evaluation

Quality level of article i

Gain score g(i)FA(Featured Article)
A(A-class article)&
GA(Good Article)

43

B(B-class article)
C(C-class article)
Start(Start-class article)&
Stub(Stub-class article)&
Unassessed
4.3 Parameter setting
For the CWPR, we setγ

0

For the click count -weighted HITS ver2, we set its k0taking values of {0.01, 0.1, 1, 10, 50, 100};
4.4 Result0

We try different k values for the click count-weighted
HITS ver2. Here, for easy to read, we only show the
representative result graph with part of the methods.
4.4.1 NDCG@k score result

taking values of {0.0, 0.2, 0.5,

Since the NDCG@k score considers the rank of articles

0.7, 0.9, 1.0}. Here the CWPR(0) is actually the originalof all quality levels, this result in Figure2 shows the

PageRank and for the CWPR(1.0) only click counts affects

performance of the overall ranking result.

the factor f;

Figure2: Group Average NDCG@1000 score among different groups
The Figure2 is the group average NDCG@1000 score.

Among CWPRs, the performance improves first as γ

Each node is the average NDCG score for one group by

increases and get worse as γ

one method setting. From the Figure2, we can find: theWhile CWPR(0), which is original PageRank, shows

HITS_ver2 algorithm with big parameter k(10,100) show

almost the worst result.

better results than the CWPRs while the HITS_ver2 withsmall k(0.01,0.1,1) show worse results than the CWPRs.

becoming larger than 0.7.

Also the group average NDCG score with k = 1% nodecount results are shown in Figure3.

Figure3: Group Average NDCG@1% score among different groups
In Figure3, we can find the CWPR with big γ values(0.7,

4.4.2 NDCG@k(part) score result0.9) have a lower decreasing tendency as the node countOn the other hand, the NDCG@k(part) score only cares

increases and shows

better performance than otherabout the articles of high quality levels (FA,GA,A class),

methods as the node count exceeds 800000, which means

thus this result in Figure 4 and Figure 5 focus more on the

CWPR can achieve better results on large graph with big

performance of the ranking of high quality article s.

γ values(0.7, 0.9).

Figure 4: Group Average NDCG@1000(part)score among different groupstheHITS_ver2 with big k parameters while the bottom purple

NDCG(part)@1000 scores of different methods are very

From

the

Figure4,

we

can

find

that

lines are the results of the HITS_ver2 with small kclose to each other. The top deep blue lines are theparameters. The CWPRs are at the middle part of thefigure. However, the performance among CWPRs withdifferent γ values is a little different. The performance of
CWPR improves as the γ

The group average NDCG(part) score with k = 1% nodecount results are shown in Figure5.

increases.

Figure 5:Group Average NDCG@1% (part) score among different groups
From the Figure5, we can find that although the CWP RCWPR algorithm, which extends the original PageRankwith different γ values show little difference between

algorithm by integrating smoot hing link counts and clickeachthan thecounts. We use the English Wikipedia as our dataset and

HITS_ver2 with its parameter k = 10, 100. The CWPR

the manual quality assessment result from Editorial Teamperform better than all other cases. This means the CWPR

Assessment of WikiProject as our evaluation golden

showstandard. And by NDCG@k score, we evaluate the result

other

betterand showworse

stability a ndcanperformance

almost

get

a

good

NDCG@1%(part) score.

of ranking.
From the result of NDCG@k score and NDCG@k(part)

4.5 Result Analysis
Combining Figure2 and Figure3, we can find that: forscore, we can find that the CWPR with bigγ values can

the top part, the CWPR can get good results b ut still aalways achieve good results and can outperform thelittle worse than the HITS_ver2 with big k parameters. For

original PageRank. It can also outperform other methods

the overall ranking, the CWPR with big γ values(0.7, 0.9)

including the click count-weighted HITS algorithm in

can outperform other methods as the graph becomes large.

giving a good ranking of articles in English Wikipedia

Also, from the performance among CWPR with different

according to their quality, especially when the graph size

γ values, we can find there is a trade -off for the effect of

becomes very large, which is often the case for web graph .

link counts and click counts.

So that suggests our proposed method is more suitable for

Combining the Figure4 and Figure5, we can find that :large web graph ranking.

for the top part, the click counts have absolute advantage

5.2 Future workin finding high quality articles than the link counts. For

For future work, we plan to enlarge our dataset andthe overall ranking, the trade-off between the effect ofintegrate some other features relative to the content of thelink counts and click counts still exists .

articles into our current methods which can also reflect the

5. Conclusion &Future work

quality of articles.

References

5.1 Conclusion
In this paper, we proposed a new algorithm called[1]

E. Agichtein, C. Castillo, D. Donato, A. Gionis, and
G. Mishne,“Finding high -quality content in social

media,” Proceedings of the 2008international
conference on web search and data mining, ACM,
February.2008, pp. 183-194[2] J. E. Blumenstock, “Automatically Assessing the
Quality of WikipediaArticles,” unpublished.
[3] G. De la Calzada, and A. Dekhtyar, “On measurin g
the quality ofWikipedia articles,” Proceedings of the
4th workshop on Informationcredibility, ACM, April.
2010, pp. 11-18.
[4] Dimitar Dimitrov, Philipp Singer, Florian Lemmerich,Markus Strohmaier, “Visual Positions of Links andClicks on Wikipedia”, Proceedings of the 25th
International Conference Companion on World Wide
Web WWW’16 Companion, April 11–15, 2016,
http://dx.doi.org/10.1145/2872518.2889388.
[5] J. Kamps and M. Koolen, “Is wikipedia link
structuredifferent?” Proceedings of the second ACM
international conference on Web search and data
mining, ACM, February, 2009, pp. 232 -241.
[6] J. M. Kleinberg, “Authoritative sources in a
hyperlinked environment,” Journal of the ACM(JACM), 1999, 46(5), 1999, pp. 604 -632.
[7] Amy N. Langville， Carl D. Meyer， James Hendler,“Google’s PageRank and Be yond: The Science of
Search Engine Rankings”.
[8] R. Lempel， S. Moran,“The stochastic approach forlink-structure analysis (SALSA) and the TKC effect ”,
Computer Networks Volume 33, Issues 1 –6, June
2000, pp. 387-401.
[9] Xuebo Liu,
Shuang Ye,
Xin Li,
Yonghao Luo,
Yanghui Rao “ZhihuRank: A Topic-Sensitive Expert
Finding
Algorithm
inCommunity
Question
Answering Websites”, ICWL 2015: Advances in
Web-Based Learning -- ICWL 2015, pp. 165-173.
[10] N. Lipka and B. Stein, “Identifying featured articles
in Wikipedia:writing style matters,” Proc. 19th Int.
Conf. World Wide Web, ACM,April. 2010, pp.
1147-1148.
[11] B. de La Robertie， Y. Pitarch， O. Teste, “Measurin g
Article Quality in Wikipedia using the Collaboration
Network”, Proceedings of the 2015 IEEE/ACM
International Conference on Advances in Social
Networks Analysis and Mining 2015,pp. 464-471.
[12] Y. Suzuki and M. Yoshikawa, “Mutual evaluation of
editors and textsfor assessing quality of Wikipedia
articles,”ProceedingsoftheEighthAnnual
International Symposium on Wikis and OpenCollaboration,ACM, Aug. 2012, pp. 18.
[13] M. Thelwall, ed, “Link analysis: An information
science approach”, Emerald Group Publishin g
Limited, 2004.
[14] E. Wulczyn and D. Taraborelli, Wikipedia
clickstream.
figshare,2015,doi:10.6084/m9.figshare.1305770.
[15] W. Xing, A. Ghorbani, “Weighted PageRankalgorithm”, Proceedings. Second Annual Conference
on Communication Networks and Services Research,
2004.
[16] Linfeng Yu and Mizuho Iwaihara, “Finding highquality documents through link and click graphs ”,
Proc. 9th International Conference on E -Service andKnowledge Management (ESKM 2018), Yonago, Jul y2018 .
[17] https://dumps.wikimedia.org/other/clickstream/2018 -05/clickstream-enwiki-2018-05.tsv.gz