Link analysis methods are used to estimate importance in graph-structured data. In that realm, the PageRank algorithm has been used to analyze directed graphs, in particular the link structure of the Web. Recent developments in information retrieval focus on entities and their relations (i. e. knowledge graph panels). Many entities are documented in the popular knowledge base Wikipedia. The cross-references within Wikipedia exhibit a directed graph structure that is suitable for computing PageRank scores as importance indicators for entities. In this work, we present di erent PageRank-based analyses on the link graph of Wikipedia and according experiments. We focus on the question whether some links - based on their position in the article text - can be deemed more important than others. In our variants, we change the probabilistic impact of links in accordance to their position on the page and measure the e ects on the output of the PageRank algorithm. We compare the resulting rankings and those of existing systems with pageview-based rankings and provide statistics on the pairwise computed Spearman and Kendall rank correlations.
Entities are omnipresent in the landscape of modern information extraction and
retrieval. Application areas range from natural language processing over
recommender systems to question answering. For many of these application areas it
is essential to build on objective importance scores of entities. One of the most
successful amongst di erent methods is the PageRank algorithm [
In this work we investigate on di erent link extraction3 methods that address the root causes for the e ects stated above. We focus on the question whether some links - based on their position in the article text - can be deemed more important than others. In our variants, we change the probabilistic impact of links in accordance to their position on the page and measure the e ects on the output of the PageRank algorithm. We compare these variants and the rankings of existing systems with page-view-based rankings and provide statistics on the pairwise computed Spearman and Kendall rank correlations. 1 Articles that link to \Carl Linnaeus" { https://en.wikipedia.org/wiki/
Special:WhatLinksHere/Carl_Linnaeus 2 Template:Taxobox { https://en.wikipedia.org/wiki/Template:
Taxobox 3 With \link extraction" we refer to the process of parsing the wikitext of a Wikipedia article and to correctly identify and lter hyperlinks to other Wikipedia articles.
In this section we provide additional background on the used PageRank variants, link extraction from Wikipedia, and redirects in Wikipedia. 2.1
The PageRank algorithm follows the idea of a user that browses Web sites by
following links in a random fashion (random surfer). For computing PageRank,
we use the original PageRank formula [
{ Original PageRank [
X
wn2l(w0)
pr(wn)
c(wn)
{ Weighted Links Rank (WLRank) [
X wn2l(w0) pr(wn) lw(link(wn; w0)) Pwm lw(link(wn; wm)) The link weight function lw is de ned as follows: lw(link(w1; w2)) = 1 f irst occurrence(link(w1; w2); w1) jtokens(w1)j (1) (2) (3) For tokenization we are splitting the article text in accordance to white spaces but do not split up links (e. g., [[brown bear|bears]] is treated as one token). The token numbering starts from 1, i. e. the rst word/link of an article. The method f irst occurrence returns the token number of the rst occurrence of a link within an article.
Both formulas (1) and (2) are iteratively applied until the scores converge. The variable d marks the damping factor: in the random surfer model, it accounts for the possibility of accessing a page via the browser's address bar instead of accessing it via a link from another page.
For reasons of presentation, we use the non-normalized version of PageRank in both cases. In contrast to the normalized version, the sum of all computed PageRank scores is the number of articles (instead of 1) and, as such, does not re ect a statistical probability distribution. However, normalization does not in uence the nal ranking and the resulting relations of the scores. 2.2
In order to create a Wikipedia link graph we need to clarify which types of
links are considered. The input for the rankings of [
DEF considers only these two types of links and not any additional ones that result from the rendering of an article. It also has to be noted that DEF does not consider links from category pages. This mostly a ects links to parent categories as the other links that are presented on a rendered category page (i. e. all articles of that category) do not occur in the wikitext. As an e ect, the accumulated PageRank of a category page would be transferred almost 1:1 to its parent category. This would lead to a top-100 ranking of things with mostly category pages only. In addition, DEF does not consider links in references (denoted via <ref> tags).
In this work, we describe how we performed more general link extraction from Wikipedia. Unfortunately, in this respect, DEF exhibited certain in exibilities as it processes Wikipedia articles line by line. This made it di cult to regard links in the context of an article as a whole (e. g., in order to determine the relative position of a link). In consequence, we reverse-engineered the link extraction parts of DEF and created the SiteLinkExtractor7 tool. The tool enables to execute multiple extraction methods in a single pass over all articles and can also be extended by additional extraction approaches. 2.3
DBpedia o ers two types of page link datasets:8 one in which the redirects are resolved and one in which they are contained. In principle, also redirect chains of more than one hop are possible but, in Wikipedia, the MediaWiki software is con gured not to follow such redirect chains (that are called \double redirect" 4 DBpedia Extraction Framework {
extraction-framework/wiki 5 Wikipedia dumps { http://dumps.wikimedia.org/ 6 Template inclusions are marked by double curly brackets, i. e. ff and gg. 7 SiteLinkExtractor { https://github.com/TBritsch/SiteLinkExtractor 8 DBpedia PageLinks { http://wiki.dbpedia.org/Downloads2015-04 https://github.com/dbpedia/
P L
P LR in Wikipedia)9 automatically and various bots are in place to remove them. As such, we can assume that only single-hop redirects are in place. However, as performed by DBpedia, also single-hop redirects can be resolved (see Figure 1). Alternatively, for various applications (especially in NLP) it can make sense to keep redirect pages as redirect pages also have a high number of inlinks in various cases (e. g. \Countries of the world")10. However, with reference to Figure 1 and assuming that redirect pages only link to the redirect target, B passes most of its own PageRank score on to C (note that the damping factor is in place). 3
We implemented ve Wikipedia link extraction methods that enable to create di erent input graphs for the PageRank algorithm. In general we follow the example of DEF and consider type 1 and 2 links for extraction (which form a subset of those that occur in a rendered version of an article). The following extraction methods were implemented: All Links (ALL) This extractor produces all type 1 and 2 links. This is the reverse-engineered DEF method. It serves as a reference.
Article Text Links (ATL) This measure omits links that occur in text that is provided to Wikipedia templates (i. e. includes type 1 links, omits type 2 links). The relation to ALL is as follows: AT L ALL.
tracts all links from the Wikipedia text (type 1 links) and produces a score for the relative position of each link (see Formula 3). In e ect, the link graph ATL-RP is the same as ATL but uses edge weights based on each link's position.
Abstract Links (ABL) This measure extracts only the links from Wikipedia abstracts. We chose the de nition of DBpedia which de nes an abstract as 9 Wikipedia: Double redirects { https://en.wikipedia.org/wiki/Wikipedia:
Double_redirects 10 Inlinks of \Countries of the world" { https://en.wikipedia.org/wiki/
Special:WhatLinksHere/Countries_of_the_world
Redirects are not resolved in any of the above methods. We execute the introduced extraction mechanisms on dumps of the English (2015-02-05) and German (2015-02-11) Wikipedia. The respective dates are aligned with the input of DEF with respect to DBpedia version 2015-04.12 Table 1 provides an overview of the number of extracted links per link graph. 4
In our experiments, we rst computed PageRank on the introduced link graphs. We then measured the pairwise rank correlations (Spearman's and Kendall's )13 between these rankings and the reference datasets (of which three are also based on PageRank and two are based on page-view data of Wikipedia). With the resulting correlation scores, we investigated on the following hypotheses: H1 Links in templates are created in a \please ll out" manner and rather negatively in uence on the general salience that PageRank scores should represent.
H2 Links that are mentioned at the beginning of articles are more often clicked and correlate with the number of page views that the target page receives. H3 The practice of resolving redirects does not strongly impact on the nal ranking in accordance to PageRank scores. 4.1
We computed PageRank with the following parameters on the introduced link
graphs ALL, ATL, ATL-RP, ABL, and TEL: non-normalized, 40 iterations,
damping factor 0:85, start value 0:1.
11 DBpedia abstract extraction { http://git.io/vGZ4J
12 DBpedia 2015-04 dump dates {
http://wiki.dbpedia.org/servicesresources/datasets/dataset-2015-04/dump-dates-dbpedia-2015-04
13 Both measures have a value range from 1 to 1 and are speci cally designed for
measuring rank correlation.
DBpedia PageRank (DBP) The scores of DBpedia PageRank [
the same way as DBP but uses the \DBpedia PageLinks Unredirected" dataset.14 As the name suggests, Wikipedia redirects are not resolved in this dataset (see Section 2.3 for more background on redirects in Wikipedia). We use the 2015-04 version of DBP-U.
SubjectiveEye3D (SUB) Paul Houle aggregated the Wikipedia page views of the years 2008 to 2013 with di erent normalization factors (particularly considering the dimensions articles, language, and time)15. As such, SubjectiveEye3D re ects the aggregated chance for a page view of a speci c article in the interval years 2008 to 2013. However, similar to unnormalized PageRank, the scores need to be interpreted in relation to each other (i. e. the scores do not re ect a proper probability distribution as they do not add up to one).
Wikipedia Ranking"16 provides scores on page views. The data is described as \the number of page views in the last year" on the project's Web site.
The two page-views-based rankings serve as a reference in order to evaluate the di erent PageRank rankings. We show the amount of entities covered by the PageRank datasets and the entity overlap with the page-view-based rankings in Table 2. 4.3
We used MATLAB for computing the pairwise Spearman's and Kendall's correlation scores. The Kendall's rank correlation measure has O(n2) complexity and takes a signi cant amount of time for large matrices. In order to speed this up, we sampled the data matrix by a random selection of 1M rows for 14 DBpedia PageLinks Unredirected { http://downloads.dbpedia.org/201504/core-i18n/en/page-links-unredirected_en.nt.bz2 15 SubjectiveEye3D { https://github.com/paulhoule/telepath/wiki/
SubjectiveEye3D 16 The Open Wikipedia Ranking { http://wikirank.di.unimi.it/ Kendall's . The pairwise correlation scores of and are reported in Tables 3 and 4 respectively. The results are generally as expected: For example, the pageview-based rankings correlate strongest with each other. Also DBP-U 2015-04 and ALL have a very strong correlation (these rankings should be equal).
H1 seems to be supported by the data as the TEL PageRank scores correlate
worst with any other ranking. However, ATL does not correlate better with SUB
and TOWR-PV than ALL. This indicates that the reason for the bad correlation
might not be due to the \bad semantics of links in the infobox". With random
samples on ATL - which produced similar results - we found that the computed
PageRank values of TEL are mostly a ected by the low total link count (see
Table 1). With respect to the initial example, the PageRank score of \Carl
Linnaeus" is reduced to 217 in ATL. However, a general better performance of
ATL is not noticeable with respect to the comparison to SUB and TOWR-PV.
We assume that PageRank on DBpedia's RDF data results in similar scores
as TEL as DBpedia [
Indicators for H2 are the scores of ABL and ATL-RP. However, similar to
TEL, ABL does not produce enough links for a strong ranking. ATL-RP, in
contrast, produces the strongest correlation with SUB. This is an indication
that - indeed - articles that are linked at the beginning of a page are more often
clicked. This is supported by related ndings where actual HTTP referrer data
was analyzed [
With respect to H3, we expected DBP-U 2015-04 and DBP 2015-04 to correlate much stronger but DEF does not implement the full work ow of Figure 1: although it introduces a link A ! C and removes the link A ! B, it does not remove the link B ! C. As such, the article B occurs in the nal entity set with the lowest PageRank score of 0:15 (as it has no incoming links). In contrast, these pages often accumulate PageRank scores of 1000 and above in the unredirected datasets. If B would not occur in the nal ranking of DBP 2015-04, it would not be considered by the rank correlation measures. This explains the comparatively weak correlation between the redirected and unredirected datasets. 4.4
Whether links from templates are excluded or included in the input link graph does not impact strongly on the quality of rankings produced by PageRank. WLRank on articles produces best results with respect to the correlation to page-view-based rankings. In general, although there is a correlation, we assume that link and page-view-based rankings are complementary. This is supported by Table 5 which contains the top-50 scores of SUB, DBP 2015-04, and ATL-RP: The PageRank-based measures are strongly in uenced by articles that relate to locations (e. g., countries, languages, etc.) as they are highly interlinked and referenced by a very high fraction of Wikipedia articles. In contrast, the pageview-based ranking of SubjectiveEye3D covers topics that are frequently accessed and mostly relate to pop culture and important historical gures or events. We assume that a strong and more objective ranking of entities is probably achieved by combining link-structure and page-view-based rankings on Wikipedia. In general, and especially for applications that deal with NLP, we recommend to use the unredirected version of DBpedia PageRank.
This work is in uenced and motivated by an initial experiment that was
performed by Paul Houle: In the Github project documentation of SubjectiveEye3D
he reports about Spearman and Kendall rank correlations between
SubjectiveEye3D and DBpedia PageRank [
Comparing ranks on Wikipedia is an important topic and with our contribution we want to emphasize the need for considering the signals \link graph" and \page views" in combination. 6
In this work, we compared di erent input graphs for the PageRank algorithm, the impact on the scores, and the correlation to page-view-based rankings. The main ndings can be summarized as follows: 1. Removing template links has no general in uence on the PageRank scores. 2. The results of WLRank with respect to the relative position of a link indicate a better correlation to page-view-based rankings than other PageRank methods. 3. If redirects are resolved, it should be done in a complete manner as otherwise entities get assigned arti cially low scores. We recommend using a unredirected dataset for applications in the NLP context.
Currently, we use the link datasets and the PageRank scores in our work on entity
summarization [
Acknowledgement. The authors would like to thank Thimo Britsch for his contributions on the rst versions of the SiteLinkExtractor tool. The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement no. 611346 and by the German Federal Ministry of Education and Research (BMBF) within the Software Campus project \SumOn" (grant no. 01IS12051).