# WikiLinkGraphs: A Complete, Longitudinal and Multi-Language Dataset of the
Wikipedia Link Networks

Cristian Consonni
DISI, University of Trento
<EMAIL_ADDRESS>David Laniado
Eurecat, Centre Tecnològic de Catalunya
<EMAIL_ADDRESS>Alberto Montresor
DISI, University of Trento
<EMAIL_ADDRESS>
###### Abstract

Wikipedia articles contain multiple links connecting a subject to other pages
of the encyclopedia. In Wikipedia parlance, these links are called internal
links or _wikilinks_. We present a complete dataset of the network of internal
Wikipedia links for the $9$ largest language editions. The dataset contains
yearly snapshots of the network and spans $17$ years, from the creation of
Wikipedia in 2001 to March 1st, 2018. While previous work has mostly focused
on the complete hyperlink graph which includes also links automatically
generated by templates, we parsed each revision of each article to track links
appearing in the main text. In this way we obtained a cleaner network,
discarding more than half of the links and representing all and only the links
intentionally added by editors. We describe in detail how the Wikipedia dumps
have been processed and the challenges we have encountered, including the need
to handle special pages such as _redirects_ , i.e., alternative article
titles. We present descriptive statistics of several snapshots of this
network. Finally, we propose several research opportunities that can be
explored using this new dataset.

## Introduction

Wikipedia111https://www.wikipedia.org is probably the largest existing
information repository, built by thousands of volunteers who edit its articles
from all around the globe. As of March 2019, it is the fifth most visited
website in the world (?). Almost 300k active users per month contribute to the
project (?), and more than 2.5 billion edits have been made. The English
version alone has more than 5.7 million articles and 46 million pages and is
edited on average by more than 128k active users every month (?). Wikipedia is
usually a top search-result from search engines (?) and research has shown
that it is a first-stop source for information of all kinds, including
information about science (?; ?), and medicine (?).

The value of Wikipedia does not only reside in its articles as separated
pieces of knowledge, but also in the links between them, which represent
connections between concepts and result in a huge conceptual network.
According to Wikipedia policies222In what follows, we will refer to the
policies in force on the English-language edition of Wikipedia; we will point
out differences with local policies whenever they are relevant. (?), when a
concept is relevant within an article, the article should include a link to
the page corresponding to such concept (?). Therefore, the network between
articles may be seen as a giant mind map, emerging from the links established
by the community. Such graph is not static but is continuously growing and
evolving, reflecting the endless collaborative process behind it.

The English Wikipedia includes over 163 million connections between its
articles. This huge graph has been exploited for many purposes, from natural
language processing (?) to artificial intelligence (?), from Semantic Web
technologies and knowledge bases (?) to complex networks (?), from controversy
mapping (?) to human way-finding in information networks (?).

This paper presents a new dataset, WikiLinkGraphs, that makes the networks of
internal links in the nine largest editions of Wikipedia available to
researchers and editors, opening new opportunities for research. Most previous
work on the Wikipedia link graph relies on wikilink data made accessible
through the Wikipedia API333Hyperlinks in the current version of Wikipedia are
available through the ”Link” property in the Wikipedia API:
https://www.mediawiki.org/wiki/API and through database
dumps444https://meta.wikimedia.org/wiki/Data˙dumps These data include also all
transcluded links, i.e. links automatically generated by templates defined in
another page; templates typically add all possible links within a given group
of articles, producing big cliques and inflating the density of connections.

Figure 1:  A portion of the navigational template {{Computer science}} from
English Wikipedia as of revision no 878025472 of 12 January 2019, 14:12. The
dashed line indicates that a portion of template has been stripped for reasons
of space.

Inserting a template in Wikipedia merely amounts to writing a small snippet of
code, which in the final article is rendered as a collection of links. Figure
1 shows a rendering of the navigation template {{Computer
science}}555https://en.wikipedia.org/wiki/Template:Computer˙science from
English Wikipedia, which produces a table with 146 links to other articles
within the encyclopedia. Navigation templates are very general by design serve
to group links to multiple related articles. They are not specific to a given
page: in fact, the content of a template can be changed independently from
editing the pages where it is included.

We argue that considering only the links explicitly added by editors in the
text of the articles may provide a more trustful representation of semantic
relations between concepts, and result in a cleaner graph by avoiding the
cliques and other potential anomalous patterns generated by transcluded links.

The aim of this work is to build a dataset of the graph of the specific link
between Wikipedia articles added by the editors. The WikiLinkGraphs dataset
was created by parsing each article to extract its links, leaving only the
links intentionally added by editors; in this way, we discarded over half of
the overall links appearing in the rendered version of the Wikipedia page.

Furthermore, we tracked the complete history of each article and of each link
within it, and generated a dynamic graph representing the evolution of the
network. Whilst the dataset we are presenting in this paper consists of yearly
snapshots, we have generated several supporting dataset as well, such as a
large collection tracking the timestamp in which each occurrence of a link was
created or removed.

Redirects, i.e. special pages representing an alternative title for an
article, are a known issue that was shown to affect previous research (?). In
our dataset, we tracked the redirects over time, and resolved all of them
according to the corresponding timestamp. The complete history of all
redirects is made available as well.

The code used to generate the dataset is also entirely made available on
GitHub, so that anybody can replicate the process and compute the wikilink
graphs for other language editions and for future versions of Wikipedia.

## The WikiLinkGraphs Dataset

This section describes how we processed the Wikipedia dumps of the complete
edit history to obtain the dataset.

### Data Processing

The WikiLinkGraphs dataset was created from the full Wikipedia revision
history data dumps of March 1, 2018666All files under ”All pages with complete
edit history (.7z)” at https://dumps.wikimedia.org/enwiki/20180301/. Wikipedia
dumps are available up to 3 months prior to the current date, so those
specific dumps are not available anymore. However, any dump contains the whole
Wikipedia history dating from 2001 onwards. So our results can be replicated
with any dump taken later than March 1st, 2018., as published by the Wikimedia
Foundation, and hence includes all entire months from January 2001 to February
2018.

These XML dumps contain the full content of each Wikipedia page for a given
language edition, including encyclopedia articles, talk pages and help pages.
Pages are divided in different _namespaces_ , that can be recognized by the
prefix appearing in the title of the page. The encyclopedia articles are in
the _main namespace_ , also called namespace 0 or ns0. The content of the
pages in Wikipedia is formatted with _Wikitext_ (?), a simplified syntax that
is then rendered as HTML by the MediaWiki
software777https://www.mediawiki.org. For each edit a new _revision_ is
created: the dump contains all revisions for all pages that were not deleted.

lang |  size (GB) | files | pages | revisions
---|---|---|---|---
de | 33.0 | 109 | 3,601,030 | 113,836,228
en | 138.0 | 520 | 13,750,758 | 543,746,894
es | 27.0 | 68 | 3,064,393 | 77,498,219
fr | 26.0 | 95 | 3,445,121 | 99,434,840
it† | 91.0 | 61 | 2,141,524 | 68,567,721
nl | 7.4 | 34 | 2,627,328 | 38,226,053
pl | 15.0 | 34 | 1,685,796 | 38,906,341
ru | 24.0 | 56 | 3,362,946 | 63,974,775
sv | 9.0 | 1 | 6,139,194 | 35,035,976
Table 1:  Statistics about the processed Wikipedia dumps: size of the
dowloaded files and number of processed pages and revisions for each dump. (†)
the Italian Wikipedia dumps were downloaded in .bz2 format.

Table 1 presents the compressed sizes for the XML dumps that have been
downloaded and the number of pages and revisions that have been processed. We
extracted all the article pages. This resulted in 40M articles being analyzed.
In total, more than 1B revisions have been processed to produce the
WikiLinkGraphs dataset.

#### Link Extraction

Wikipedia articles have _revisions_ , which represent versions of the Wikitext
of the article at a specific time. Each modification of the page (an _edit_ in
Wikipedia parlance) generates a new revision. Edits can be made by _anonymous_
or _registered_ users.

A revision contains the wikitext of the article, which can have sections, i.e.
header titles. Sections are internally numbered by the MediaWiki software from
$0$, the _incipit_ section, onwards. As for HTML headers, several section
levels are available (sections, subsections, etc.); section numbering does not
distinguish between the different levels.

While a new visual, WYSIWYG editor has been made available in most Wikipedia
editions starting since June 2013 (?), the text of Wikipedia pages is saved as
_Wikitext_. In this simplified markup language, internal Wikipedia links have
the following format `[[title|anchor]]`; for example,

[[New York City|The Big Apple]]

This wikitext is visualized as the words `The Big Apple` that gets translated
into HTML as:

The Big Apple

pointing to the Wikipedia article _New York City_. If the page exists, as in
this example, the link will be blue-colored, otherwise it will be colored in
red, indicating that the linked-to page does not exist (?). The anchor is
optional and, if it was omitted, then the page title, in this case `New York
City`, would have been visualized.

For each revision of each page in the Wikipedia dump, we used the following
regular expression in
Python888https://github.com/WikiLinkGraphs/wikidump/blob/70b0c7f929fa9d66a220caf11c9e31691543d73f/wikidump/extractors/misc.py#L203
to extract _wilinks_ :

1\\[\\[2(?P<link>3 [^\n\|\\]\\[\<\>\\{\\}]{0,256}4)5(?:6 \|7 (?P<anchor>8
[^\\[]*?9 )10)?11\\]\\]

Line 1 matches two open brackets; then, Lines 2–4 capture the following
characters in a named group called `link`. Lines 5–10 match the optional
anchor: Line 5 matches a pipe character, then Lines 6–8 match non-greedily any
valid character for an anchor saving them in a named group called `anchor`.
Finally, Line 10 matches two closed brackets. The case of links pointing to a
section of the article is handled _a posteriori_ , after the regular
expression has captured its contents. When linking to a section, the link text
will contain a pound sign (`#`); given that this symbol is not allowed in page
titles, we can separate the title of the linked page from the section.

##### The RawWikilinks Dataset.

Figure 2:  The process to produce the WikiLinkGraphs dataset from the
Wikipedia dumps. In bold and italics the name of the intermediate datasets
produced.

The link extraction process produces a dataset with the following information:

  * •

`page_id`: an integer, the page identifier used by MediaWiki. This identifier
is not necessarily progressive, there may be gaps in the enumeration;

  * •

`page_title`: a string, the title of the Wikipedia article;

  * •

`revision_id`: an integer, the identifier of a revision of the article, also
called a _permanent id_ , because it can be used to link to that specific
revision of a Wikipedia article;

  * •

`revision_parent_id`: an integer, the identifier of the parent revision. In
general, each revision as a unique parent; going back in time before 2002,
however, we can see that the oldest articles present non-linear edit
histories. This is a consequence of the import process from the software
previously used to power Wikipedia, MoinMoin, to MediaWiki;

  * •

`revision_timestamp`: date and time of the edit that generated the revision
under consideration;

  * •

`user_type`: a string (”registered” or ”anonymous”), specifying whether the
user making the revision was logged-in or not;

  * •

`user_username`: a string, the username of the user that made the edit that
generated the revision under consideration;

  * •

`user_id`: an integer, the identifier of the user that made the edit that
generated the revision under consideration;

  * •

`revision_minor`: a boolean flag, with value 1 if the edit that generated the
current revision was marked as _minor_ by the user, 0 otherwise;

  * •

`wikilink.link`: a string, the page linked by the
wikilink;

  * •

`wikilink.tosection`: a string, the name of the section if the link points to
a section;

  * •

`wikilink.anchor`: a string, the anchor text of the _wikilink_ ;

  * •

`wikilink.section_name`: the name of the section wherein the _wikilink_
appears;

  * •

`wikilink.section_level`: the level of the section wherein the _wikilink_
appears;

  * •

`wikilink.section_number`: the number of the section wherein the _wikilink_
appears.

#### Redirects and Link Resolution

A redirect in MediaWiki is a page that automatically sends users to another
page. For example, when clicking on a _wikilink_`[[NYC]]`, the user is taken
to the article _New York City_ with a note at the top of the page saying:
”(Redirected from NYC)”. The page _NYC_
999https://en.wikipedia.org/w/index.php?title=NYC&redirect=no contains special
Wikitext:  #REDIRECT [[New York City]] which defines it as a redirect page and
indicates the target article. It is also possible to redirect to a specific
section of the target page. Different language editions of Wikipedia use
different
words101010https://github.com/WikiLinkGraphs/wikidump/blob/70b0c7f929fa9d66a220caf11c9e31691543d73f/wikidump/extractors/redirect.py#L14,
which are listed in Table 2.

lang | words
---|---
de | `#WEITERLEITUNG`
en | `#REDIRECT`
es |  #REDIRECCIÓN, `#REDIRECCION`
fr | `#REDIRECTION`
it |  `#RINVIA`, `#RINVIO`, `#RIMANDO`
nl | `#DOORVERWIJZING`
pl |  `#PATRZ`, `#PRZEKIERUJ`, `#TAM`
ru‡ |  `#PERENAPRAVLENIE`, `#PERENAPR`
sv | `#OMDIRIGERING`

Table 2:  Words creating a redirect in MediaWiki for different languages.
``#REDIRECT— is valid on all languages. (‡) For Russian Wikipedia, we present
the transliterated words.

In general, a redirect page can point to another redirect page creating a
chain of multiple redirects111111For example, a live list of pages creating
chains of redirect on English Wikipedia is available at
https://en.wikipedia.org/wiki/Special:DoubleRedirects.. These pages should
only be temporary and they are actively eliminated by Wikipedia volunteers
manually and using automatic scripts.

Despite the name, redirects are served as regular pages by the MediaWiki
software so requesting a redirect page, for example by visiting the link
https://en.wikipedia.org/wiki/NYC, returns an HTTP status code of 200.

#### Resolving Redirects

We have extracted one snapshot per year on March, 1st from the RawWikilinks
dataset. The creation of a snapshot for a given year entails the following
process:

  1. 1.

we list all _revisions_ with their timestamps from the dumps;

  2. 2.

we filter the list of revisions keeping only those that existed on March 1st,
i.e. the last revision for each page created before March 1st;

  3. 3.

we resolve the redirects by comparing each page with the list of redirects
obtained as described above;

At the end of this process, we obtain a list of the pages that existed in
Wikipedia on March, 1st of each year, together with their target, if they are
redirects. We call this dataset ResolvedRedirects.

It should be noted that even if we resolve redirects, we do not eliminate the
corresponding pages: in fact, redirects are still valid pages belonging to the
namespace 0 and thus they still appear in our snapshots as nodes with one
outgoing link, and no incoming links.

#### Link Snapshots

We then process the RawWikilinks dataset and we are able, for each revision of
each page, to establish whether a wikilink in a page was pointing to an
existing page or not. We add this characteristics to the RawWikilinks dataset
in the field `wikilink.is_active`: a boolean representing whether the page
pointed to by the link was existing in that moment or not. Revisions are then
filtered so to obtain the lists of links existing in each page at the moment
of interest; we call this new dataset WikiLinkSnapshots.

#### Graph Snapshots (WikiLinkGraphs)

Armed with the WikiLinkSnapshots and the ResolvedRedirects dataset we can
extract the WikiLinkGraphs as a list of records with the following fields:

  * •

`page_id_from`: an integer, the identifier of the source article.

  * •

`page_title_from`: a string, the title of the source article;

  * •

`page_id_to`: an integer, the identifier of the target article;

  * •

`page_title_to`: a string, the title of the target article;

If a page contains a link to the same page multiple times, this would appear
as multiple rows in the WikiLinkSnapshots dataset. When transforming this data
to graph format we eliminate these multiple occurrences, because we are only
interested in the fact that the two pages are linked. Wikipedia policies about
linking (?) state that in general a link should appear only once in an article
and discourage contributors to put multiple links to the same destination. One
clear example is the page _New York City_ where, for example, the expression
_“United States”_ is used to link to the corresponding article only once, at
the first occurrence. For these reasons, we do not think it is justified to
assign any special meaning to the fact that two page have multiple direct
connections between them.

Figure 2 summarizes the steps followed to produce the WikiLinkGraphs from the
Wikipedia dumps with the intermediate datasets produced.

### Dataset Description

date | de | en | es | fr | it
---|---|---|---|---|---
N | E | N | E | N | E | N | E | N | E
2001-03-01 | 0 | 0 | 37 | 31 | 0 | 0 | 0 | 0 | 0 | 0
2002-03-01 | 900 | 1,913 | 27,654 | 223,705 | 1,230 | 2,664 | 55 | 53 | 0 | 0
2003-03-01 | 14,545 | 126,711 | 118,946 | 1,318,655 | 2,786 | 13,988 | 6,694 | 58,027 | 1,036 | 9,695
2004-03-01 | 63,739 | 794,561 | 248,193 | 3,170,614 | 17,075 | 162,219 | 28,798 | 338,108 | 6,466 | 97,721
2005-03-01 | 244,110 | 3,659,389 | 624,287 | 8,505,195 | 43,114 | 457,032 | 96,676 | 1,238,756 | 32,834 | 355,197
2006-03-01 | 474,553 | 7,785,292 | 1,342,642 | 18,847,709 | 112,388 | 1,351,111 | 283,831 | 3,926,485 | 149,935 | 1,434,869
2007-03-01 | 775,104 | 11,946,193 | 2,425,283 | 34,219,970 | 253,569 | 3,327,609 | 555,471 | 7,900,561 | 302,276 | 3,960,767
2008-03-01 | 1,063,222 | 15,598,850 | 3,676,126 | 50,270,571 | 452,333 | 6,292,452 | 1,113,622 | 12,546,302 | 507,465 | 7,239,521
2009-03-01 | 1,335,157 | 19,607,930 | 4,848,297 | 61,318,980 | 762,234 | 9,504,039 | 1,369,619 | 16,546,043 | 693,445 | 10,713,417
2010-03-01 | 1,603,256 | 23,834,140 | 5,937,618 | 71,024,045 | 1,159,567 | 12,844,652 | 1,632,118 | 21,064,666 | 877,089 | 14,120,469
2011-03-01 | 1,879,381 | 28,457,497 | 7,027,853 | 82,944,163 | 1,693,815 | 17,454,997 | 1,890,614 | 25,704,865 | 1,043,648 | 17,496,901
2012-03-01 | 2,163,719 | 33,036,436 | 7,922,426 | 93,924,479 | 1,944,529 | 21,167,388 | 2,137,209 | 30,422,158 | 1,213,961 | 21,069,750
2013-03-01 | 2,461,158 | 37,861,651 | 8,837,308 | 105,052,706 | 2,198,429 | 24,314,571 | 2,369,365 | 34,791,331 | 1,377,144 | 24,694,404
2014-03-01 | 2,712,984 | 42,153,240 | 9,719,211 | 116,317,952 | 2,409,026 | 27,090,659 | 2,594,282 | 39,257,288 | 1,511,827 | 26,821,204
2015-03-01 | 2,933,459 | 46,574,886 | 10,568,011 | 127,653,091 | 2,561,516 | 29,529,035 | 2,809,572 | 43,831,574 | 1,643,387 | 29,867,490
2016-03-01 | 3,155,927 | 50,904,750 | 11,453,255 | 139,194,105 | 2,728,713 | 32,633,513 | 3,037,908 | 48,659,900 | 1,802,952 | 32,521,188
2017-03-01 | 3,372,406 | 55,184,610 | 12,420,400 | 150,743,638 | 2,881,220 | 35,546,330 | 3,239,160 | 53,126,118 | 1,917,410 | 35,158,350
2018-03-01 | 3,588,883 | 59,535,864 | 13,685,337 | 163,380,007 | 3,034,113 | 38,348,163 | 3,443,206 | 57,823,305 | 2,117,022 | 37,814,105
Table 3: Number of nodes $N$ and edges $E$ for each graph snapshot of WikiLinkGraphs dataset obtained for the English (en), German (de), Spanish (es), French (fr), and Italian (it) Wikipedia editions. date | nl | pl | ru | sv
---|---|---|---|---
N | E | N | E | N | E | N | E
2001-03-01 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
2002-03-01 | 368 | 728 | 698 | 1,478 | 0 | 0 | 122 | 184
2003-03-01 | 5,182 | 41,875 | 8,799 | 68,720 | 108 | 239 | 6,708 | 33,473
2004-03-01 | 23,059 | 225,429 | 24,356 | 299,583 | 1,600 | 3,927 | 22,218 | 171,486
2005-03-01 | 62,601 | 669,173 | 61,378 | 779,843 | 11,158 | 63,440 | 66,673 | 651,671
2006-03-01 | 169,193 | 1,850,260 | 234,506 | 2,218,720 | 64,359 | 422,903 | 163,988 | 1,605,526
2007-03-01 | 338,354 | 3,746,141 | 395,723 | 4,575,510 | 246,494 | 1,849,540 | 269,599 | 2,627,901
2008-03-01 | 523,985 | 6,037,117 | 546,236 | 7,151,435 | 459,863 | 3,762,487 | 370,569 | 3,746,860
2009-03-01 | 667,311 | 7,900,852 | 690,887 | 9,663,964 | 703,316 | 6,395,215 | 452,132 | 4,841,861
2010-03-01 | 764,277 | 9,467,588 | 822,868 | 11,776,724 | 962,680 | 9,881,672 | 542,900 | 5,856,848
2011-03-01 | 879,062 | 11,120,219 | 953,620 | 13,959,431 | 1,295,284 | 13,955,827 | 712,129 | 6,922,100
2012-03-01 | 1,358,162 | 14,255,313 | 1,091,816 | 15,813,952 | 1,562,821 | 17,882,908 | 800,776 | 7,945,812
2013-03-01 | 1,550,027 | 16,241,260 | 1,208,355 | 17,405,307 | 1,862,035 | 21,724,380 | 1,424,006 | 16,812,447
2014-03-01 | 2,332,477 | 19,940,218 | 1,322,701 | 19,244,972 | 2,098,071 | 25,100,193 | 2,422,972 | 26,497,619
2015-03-01 | 2,424,624 | 21,638,960 | 1,414,645 | 20,838,508 | 2,350,262 | 28,242,878 | 3,218,352 | 33,025,219
2016-03-01 | 2,500,880 | 23,252,874 | 1,513,239 | 22,445,122 | 2,782,155 | 31,467,831 | 4,470,345 | 38,864,469
2017-03-01 | 2,569,547 | 24,691,572 | 1,597,694 | 24,238,529 | 3,094,419 | 34,441,603 | 6,062,996 | 51,975,115
2018-03-01 | 2,626,527 | 25,834,057 | 1,684,606 | 25,901,789 | 3,360,531 | 37,394,229 | 6,131,736 | 52,426,633
Table 4: Number of nodes $N$ and edges $E$ for each graph snapshot of
WikiLinkGraphs dataset obtained for the Dutch (nl), Polish (pl), Russian (ru),
and Swedish (sv) Wikipedia editions.

The WikiLinkGraphs dataset comprises data from $9$ Wikipedia language
editions: German (de), English (en), Spanish (es), French (fr), Italian (it),
Dutch (nl), Polish (pl), Russian (ru), and Swedish (sv). These editions are
the top-$9$ largest editions per number of articles, which also had more than
$1,000$ active users (?). We excluded Cebuano Wikipedia, because
notwithstanding being at the moment the second-largest Wikipedia, its
disproportionate growth with respect to the number of its active users has
recently been fueled by massive automatic imports of articles. For fairness,
we note that also the growth of Swedish Wikipedia has been led in part by
automatic imports of data (?), but we have decided to keep it in given it has
a reasonably large active user-base.

The WikiLinkGraphs dataset comprises $172$ files for a total of $142$ GB; the
average size is $244$ MB and the largest file is $2.4$ GB. For each of the $9$
languages, $18$ files are available with the snapshots of the _wikilink_ graph
taken on March, 1st from 2001 to 2018. As specified in Section Graph Snapshots
(WikiLinkGraphs), these are CSV files that are later compressed in the
standard gzip format. The remaining $10$ files contain the hash-sums to verify
the integrity of files and a README.

#### Where to Find the WikiLinkGraphs Dataset and Its Supporting Material

The WikiLinkGraphs dataset is published on Zenodo at
https://zenodo.org/record/2539424 and can be referenced with the DOI number
10.5281/zenodo.2539424. All other supporing datasets are available at
https://cricca.disi.unitn.it/datasets/. The code used for data processing has
been written in Python 3 and it is available on GitHub under the
_WikiLinkGraph_ organization https://github.com/WikiLinkGraphs.

All the datasets presented in this paper are released under the _Creative
Commons - Attribution - 4.0 International_ (CC-NY 4.0)
license121212https://creativecommons.org/licenses/by/4.0/; the code is
released under the GNU General Public License version 3 or
later131313https://www.gnu.org/licenses/gpl-3.0.en.html.

#### Basic statistics

Tables 3 and 4 present the number of nodes ($N$) and edges ($E$) for each
snapshot included in the WikiLinkGraphs dataset. The number of nodes is much
larger that the number of “content articles” presented in the main pages of
each Wikipedia version. For reference, in March, 2018 English Wikipedia had
5.6M articles (?), however in our snapshot there are more than 13.6M nodes.
This is due to the fact that we have left in the graph redirected nodes, as
described above, whilst we have resolved the links pointing to them; redirects
remain as orphan nodes in the network, receiving no links from other nodes,
and having one outgoing link.

Figure 3 shows a plot of the growth over time of the number of links in the
WikiLinkGraphs of each language we have processed. The plot is drawn in linear
scale to give a better sense of the relative absolute proportions among the
different languages. After the first years all language editions exhibit a
mostly stable growth pattern with the exception of Swedish, that experienced
anomalous growth peaks probably due to massive bot activity.

Figure 3:  Overview of the growth over time of the number of links in each
snapshot in the WikiLinkGraphs dataset.

## Analysis and Use Cases

In this Section we analyse the WikiLinkGraphs dataset to provide some useful
insights in the data that will help to demonstrate the opportunities opened by
this new dataset.

#### Comparison with Wikimedia’s pagelinks Database Dump.

To start, we compare our dataset with an existing one provided by the
Wikimedia Foundation: the pagelinks table dump.141414For the latest versions
of the database dumps, all Wikipedia hyperlinks are available in the
”pagelinks” files at https://dumps.wikimedia.org/. This table tracks all the
internal links in a wiki (?), whether they are links in non-articles pages,
link pages across different namespaces, or if they are _transcluded_ in a page
with a template151515We take the occasion to point out that throughout this
paper we refer to ”internal links” or _wikilinks_ only as links between
articles of the encyclopedia, however Wikipedia guidelines use the term more
interchangeably to refer both to ”links between articles” and ”all the links
that stay within the project”, i.e. including links in other namespaces or
that go across namespaces. Whilst it seems that the same confusion exists
among the contributors of the encyclopedia, we have decided here to adopt the
view for which the proper _wikilinks_ are only the links between articles of
the encyclopedia.. The table presents information about the source page
identifier and namespace, and the linked-to article title and namespace. There
are no duplicates of the same combination of source page id, source page
namespace and target title. For this reason, only distinct links in a page are
recorded in the table. When updating this table, MediaWiki does not check if
the target page exists or not.

lang | pagelinks all | pagelinks ns0 | WLG
---|---|---|---
de | 156,770,699 | 106,488,110 | 59,535,864
en | 1,117,233,757 | 476,959,671 | 163,380,007
es | 88,895,487 | 51,579,346 | 38,348,163
fr | 270,129,151 | 144,469,298 | 57,823,305
it | 187,013,995 | 118,435,117 | 37,814,105
nl | 88,996,775 | 66,606,188 | 25,834,057
pl | 131,890,972 | 79,809,667 | 25,901,789
ru | 152,819,755 | 108,919,722 | 37,394,229
sv | 133,447,975 | 111,129,467 | 52,426,633

Table 5:  Comparison of the number of links between articles in the ns0 as
they result from Wikimedia’s pagelinks database table dump (pagelinks ns0) and
from the WikiLinkGraphs dataset (WLG). The total number of rows, counting
links between other namespaces is given in (pagelinks all).

Table 5 present a comparison of the number of links extracted from the
pagelinks table and the WikiLinkGraphs.

Links in WikiLinkGraphs are much less because links transcluded from templates
are not considered. Given the specific research question or application under
consideration, it may be more suitable to include or exclude the links that
were added to the page by templates; for example, to reconstruct navigational
patterns it may be useful not only to consider links from templates, but also
links in the navigational interface of MediaWiki.

# | de | en | es | fr | it
---|---|---|---|---|---
article |  score ${\scriptscriptstyle(\times 10^{-3})}$ | article |  score ${\scriptscriptstyle(\times 10^{-3})}$ | article |  score ${\scriptscriptstyle(\times 10^{-3})}$ | article |  score ${\scriptscriptstyle(\times 10^{-3})}$ | article |  score ${\scriptscriptstyle(\times 10^{-3})}$
1 | Vereinigte Staaten | 1.646 | United States | 1.414 | Estados Unidos | 2.301 | France | 2.370 | Stati Uniti d’America | 3.076
2 | Deutschland | 1.391 | World War II | 0.654 | España | 2.095 | États-Unis | 2.217 | Italia | 1.688
3 | Frankreich | 1.020 | United Kingdom | 0.618 | Francia | 1.281 | Paris | 1.228 | Comuni della Francia | 1.303
4 | Zweiter Weltkrieg | 0.969 | Germany | 0.557 | Idioma inglés | 1.073 | Allemagne | 0.977 | Francia | 1.292
5 | Berlin | 0.699 | The New York Times | 0.527 | Argentina | 0.955 | Italie | 0.812 | Germania | 1.257
6 | Österreich | 0.697 | Association football | 0.525 | Alemania | 0.909 | Royaume-Uni | 0.773 | Lingua inglese | 1.228
7 | Schweiz | 0.691 | List of sovereign states | 0.523 | Latín | 0.867 | Anglais | 0.764 | Roma | 0.961
8 | Englische Sprache | 0.620 |  Race and ethnicity in the United States Census | 0.500 | Animalia | 0.866 | Français | 0.748 | Centrocampista | 0.861
9 | Italien | 0.614 | India | 0.491 | México | 0.853 | Espèce | 0.731 | Europa | 0.805
10 | Latein | 0.599 | Canada | 0.468 | Reino Unido | 0.820 | Canada | 0.710 | 2004 | 0.778

Table 6:  Top-10 articles with the highest Pagerank score computed over the
most recent snaphost of the WikiLinkGraphs dataset (2018-03-01).

# | nl | pl | ru | sv
---|---|---|---|---
article |  score ${\scriptscriptstyle(\times 10^{-3})}$ | article‡ |  score ${\scriptscriptstyle(\times 10^{-3})}$ | article‡ |  score ${\scriptscriptstyle(\times 10^{-3})}$ | article |  score ${\scriptscriptstyle(\times 10^{-3})}$
1 | Kevers | 3.787 | Stany Zjednoczone | 2.763 | Soedinjonnye Shtaty Ameriki | 3.290 | Familj (biologi) | 5.489
2 | Vlinders | 3.668 | Polska | 2.686 | Sojuz Sovetskih Socialisticheskih Respublik | 2.889 | Släkte | 5.184
3 | Dierenrijk | 3.294 | Francja | 2.360 | Rossija | 2.233 | Nederbörd | 4.696
4 | Vliesvleugeligen | 3.084 | Jezyk angielski | 2.110 | Francija | 1.190 | Grad Celsius | 4.144
5 | Insecten | 2.164 | Łacina | 1.914 | Moskva | 1.135 | Djur | 4.114
6 | Geslacht (biologie) | 2.101 | Niemcy | 1.698 | Germanija | 1.080 | Catalogue of Life | 3.952
7 | Soort | 1.954 | Włochy | 1.229 | Sankt-Peterburg | 0.881 | Årsmedeltemperatur | 3.878
8 | Frankrijk | 1.932 | Wielka Brytania | 1.124 | Ukraina | 0.873 | Årsnederbörd | 3.366
9 | Verenigde Staten | 1.868 | Wieś | 1.095 | Velikobritanija | 0.811 | Växt | 2.810
10 | Familie (biologie) | 1.838 | Warszawa | 1.083 | Italija | 0.763 | Leddjur | 2.641

Table 7:  Top-10 articles with the highest Pagerank score computed over the
most recent snaphost of the WikiLinkGraphs dataset (2018-03-01). (‡) Russian
and Polish Wikipedia article titles are transliterated.

In this sense, WikiLinkGraphs provides a new facet of the links in Wikipedia
that was not readily available before. These two dataset can be used in
conjunction, also taking advantage of the vast amount of metadata available
accompanying the WikiLinkGraphs dataset, such as the RawWikilinks and
ResolvedRedirects datasets.

### Cross-language Comparison of Pagerank Scores

A simple, yet powerful application that can exploit the WikiLinkGraphs dataset
is computing the general Pagerank score over the latest snapshot available
(?). Pagerank borrows from bibliometrics the fundamental idea that being
linked-to is a sign of relevance (?). This idea is also valid on Wikipedia,
whose guidelines on linking state that:

> “Appropriate links provide instant pathways to locations within and outside
> the project that are likely to increase readers’ understanding of the topic
> at hand.” (?)

In particular, articles should link to articles with relevant information, for
example to explain technical terms.

Tables 6 and 7 presents the Pagerank scores obtained by running the
implementation of the Pagerank algorithm from the igraph
library161616https://igraph.org/c/doc/igraph-Structural.html#igraph˙pagerank.

Across $7$ out of the $9$ languages analysed, the Wikipedia article about the
_United States_ occupies a prominent position being either the highest or the
second-highest ranked article in direct competition with articles about
countries were the language is spoken. In general, we see across the board
that high scores are gained by articles about countries and cities that are
culturally relevant for the language of the Wikipedia edition under
consideration.

Remarkably, Dutch and Swedish Wikipedia present very different types of
articles in the top-10 positions: they are mainly about the field of biology.
A detailed investigation of the results and the causes for these differences
is beyond the scope of this paper, but we can hypothesize differences in the
guidelines about linking that produce such different outcomes.

## Research Opportunities using the WikiLinkGraphs Dataset

The WikiLinkGraphs dataset and its supporting dataset can be useful for
research in a variety of contexts. Without pretending to be exhaustive, we
present here a few examples.

#### Graph Streaming.

Stream data processing has gained particular consideration in recent years
since it is well-suited for a wide range of applications, and streaming
sources of data are commonplace in the big data era (?). The WikiLinkGraphs
dataset, together with the RawWikilinks dataset, can be represented as a graph
stream, i.e. a collection of events such as node and link additions and
removals. Whilst other datasets are already available for these kind of
problems, such as data from social networks, WikiLinkGraphs, being open, can
facilitate the reproducibility of any research in this area and can be used as
a benchmark.

#### Link Recommendation.

? (?) have studied the problem of identifying missing links in Wikipedia using
web logs. More recently, ? (?) have demonstrated that it is possible to
produce personalized article recommendations to translate Wikipedia articles
across language editions. The WikiLinkGraphs dataset could be used in place of
the web logs for a similar study on recommending the addition of links in a
Wikipedia language edition based on the fact that some links exist between the
same articles in other Wikipedia language editions.

#### Link Addition and Link Removal.

The problem of predicting the appearance of links in time-evolving networks
has received significant attention (?); the problem of predicting their
disappearance, on the other hand, is less studied. Preusse and collaborators
(?) investigated the structural patterns of the evolution of links in dynamic
knowledge networks. To do so, they adapt some indicators from sociology and
identify four classes to indicate growth, decay, stability and instability of
links. Starting from these indicators, they identify the underlying reasons
for individual additions and removals of knowledge links. Armada et al. (?)
investigated the link-removal prediction problem, which they call the _unlink
prediction_. Representing the ever-evolving nature of Wikipedia links, the
WikiLinkGraphs dataset and the RawWikilinks datasets are a natural venue for
studying the dynamics of link addition and link removal in graphs.

#### Anomaly Detection.

A related problem is the identification of spurious links, i.e., links that
have been erroneously observed (?; ?). An example of the application of this
approach is the detection of links to spam pages on the Web (?). Similarly,
the disconnection of nodes has been predicted in mobile ad-hoc networks (?).

#### Controversy mapping.

Given the encyclopedic nature of Wikipedia, the network of articles represents
an emerging map of the connections between the corresponding concepts.
Previous work by ? (?) has shown how a subportion of this network can be
leveraged to investigate public debate around a given topic, observing its
framing and boundaries as emerging from the grouping of concepts in the graph.
The availability of the WikiLinkGraphs dataset can foster controversy mapping
approaches to study any topical subpart of the network, with the advantage of
adding a temporal and a cross-cultural dimension.

#### Cross-cultural studies.

More than 300 language editions of Wikipedia have being created since its
inception in 2001 (?), of which 291 are actively maintained. Despite the
strict neutral point of view policy which is a pillar of the project (?; ?),
different linguistic communities will unavoidably have a different coverage
and different representations for the same topic, putting stronger focus on
certain entities, and or certain connections between entities. As an example,
the articles about bullfighting in different languages may have a stronger
connection to concepts from art, literature, and historical figures, or to
concepts such as cruelty and animal rights (?). Likewise, the networks from
different language versions give prominence to different influential
historical characters (?; ?). The WikiLinkGraphs dataset allows to compare the
networks of $9$ editions of Wikipedia, which are not only big editions, but
have a fairly large base of contributors. In this paper, we have presented a
simple comparison across the $9$ languages represented, and we have found an
indicator of the prominence of the United States and the local culture almost
across the board. Many more research questions could be addressed with the
WikiLinkGraphs dataset.

## Conclusions

The dataset we have presented, WikiLinkGraphs, makes available the complete
graph of links between Wikipedia articles in the nine largest language
editions.

An important aspect is that the dataset contains only links appearing in the
text of an article, i.e. links intentionally added by the article editors.
While the Wikimedia APIs and dumps provide access to the currently existing
wikilinks, such data represent instead all hyperlinks between pages, including
links automatically generated by templates. Such links tend to create cliques,
introducing noise and altering the structural properties of the network. We
demonstrated that this is not an anecdotal issue and may have strongly
affected previous research, as with our method we obtain less than the half of
the links contained in the corresponding Wikimedia pagelinks dump.

Another limitation of the Wikimedia dumps is that data are available only for
the current version of Wikipedia or for a recent snapshot; the WikiLinkGraphs
dataset instead provides complete longitudinal data, allowing for the study of
the evolution of the graph over time. We provided both yearly snapshots and
the raw dataset containing the complete history of every single link within
the encyclopedia.

The WikiLinkGraphs dataset is currently made available for the nine largest
Wikipedia language editions, however we plan to extend it to other language
editions. As the code of all steps is made available, other researchers can
also extend the dataset by including more languages or a finer temporal
granularity.

Beyond the opportunities for future research presented above, we believe that
also research in other contexts can benefit from this dataset, such as
Semantic Web technologies and knowledge bases, artificial intelligence and
natural language processing.

## Acknowledgements

The authors would like to thank Michele Bortolotti and the team of “Gestione
Sistemi” at the University of Trento for their support with the HPC cluster.

This work has been supported by the European Union’s Horizon 2020 research and
innovation programme under the EU Engineroom project, with Grant Agreement no
780643.

## References

  * [Alexa Internet, Inc. 2018] Alexa Internet, Inc.  2018\.  The top 500 sites on the web.  https://www.alexa.com/topsites.  [Online; accessed 28-December-2018].
  * [Aragon et al. 2012] Aragon, P.; Laniado, D.; Kaltenbrunner, A.; and Volkovich, Y.  2012\.  Biographical social networks on Wikipedia: a cross-cultural study of links that made history.  In Proceedings of the eighth annual international symposium on Wikis and open collaboration, 19.  ACM.
  * [Armada de Oliveira, Cerqueira Revoredo, and Ochoa Luna 2014] Armada de Oliveira, M.; Cerqueira Revoredo, K.; and Ochoa Luna, J. E.  2014\.  Semantic unlink prediction in evolving social networks through probabilistic description logic.  In Intelligent Systems (BRACIS), 2014 Brazilian Conference on, 372–377.  IEEE.
  * [Benczur et al. 2005] Benczur, A. A.; Csalogany, K.; Sarlos, T.; and Uher, M.  2005\.  Spamrank–fully automatic link spam detection work in progress.  In Proceedings of the first international workshop on adversarial information retrieval on the web.
  * [Borra et al. 2015] Borra, E.; Weltevrede, E.; Ciuccarelli, P.; Kaltenbrunner, A.; Laniado, D.; Magni, G.; Mauri, M.; Rogers, R.; and Venturini, T.  2015\.  Societal controversies in Wikipedia articles.  In Proceedings of the 33rd annual ACM conference on human factors in computing systems, 193–196.  ACM.
  * [Brin and Page 1998] Brin, S., and Page, L.  1998\.  The anatomy of a large-scale hypertextual web search engine.  Computer networks and ISDN systems 30(1-7):107–117.
  * [Capocci et al. 2006] Capocci, A.; Servedio, V. D.; Colaiori, F.; Buriol, L. S.; Donato, D.; Leonardi, S.; and Caldarelli, G.  2006\.  Preferential attachment in the growth of social networks: The internet encyclopedia wikipedia.  Physical review E 74(3):036116.
  * [De Rosa, Malizia, and Mecella 2005] De Rosa, F.; Malizia, A.; and Mecella, M.  2005\.  Disconnection prediction in mobile ad hoc networks for supporting cooperative work.  Pervasive Computing, IEEE 4(3):62–70.
  * [Eom et al. 2015] Eom, Y.-H.; Aragón, P.; Laniado, D.; Kaltenbrunner, A.; Vigna, S.; and Shepelyansky, D. L.  2015\.  Interactions of cultures and top people of Wikipedia from ranking of 24 language editions.  PloS one 10(3):e0114825.
  * [Franceschet 2010] Franceschet, M.  2010\.  Pagerank: Standing on the shoulders of giants.  arXiv preprint arXiv:1002.2858.
  * [Guimerà and Sales-Pardo 2009] Guimerà, R., and Sales-Pardo, M.  2009\.  Missing and spurious interactions and the reconstruction of complex networks.  Proceedings of the National Academy of Sciences 106(52):22073–22078.
  * [Hill and Shaw 2014] Hill, B. M., and Shaw, A.  2014\.  Consider the redirect: A missing dimension of Wikipedia research.  In Proceedings of The International Symposium on Open Collaboration, 28.  ACM.
  * [Karimov et al. 2018] Karimov, J.; Rabl, T.; Katsifodimos, A.; Samarev, R.; Heiskanen, H.; and Markl, V.  2018\.  Benchmarking distributed stream processing engines.  arXiv preprint arXiv:1802.08496.
  * [Laurent and Vickers 2009] Laurent, M. R., and Vickers, T. J.  2009\.  Seeking health information online: does wikipedia matter?  Journal of the American Medical Informatics Association 16(4):471–479.
  * [Lewandowski and Spree 2011] Lewandowski, D., and Spree, U.  2011\.  Ranking of wikipedia articles in search engines revisited: Fair ranking for reasonable quality?  Journal of the American Society for Information Science and Technology 62(1):117–132.
  * [Lü and Zhou 2011] Lü, L., and Zhou, T.  2011\.  Link prediction in complex networks: A survey.  Physica A: statistical mechanics and its applications 390(6):1150–1170.
  * [Markusson et al. 2016] Markusson, N.; Venturini, T.; Laniado, D.; and Kaltenbrunner, A.  2016\.  Contrasting medium and genre on Wikipedia to open up the dominating definition and classification of geoengineering.  Big Data & Society 3(2):2053951716666102.
  * [MediaWiki developers 2018] MediaWiki developers.  2018\.  English Wikipedia, Special:Statistics.  https://en.wikipedia.org/wiki/Special:Statistics.  [Online; accessed 28-December-2018].
  * [MediaWiki 2019] MediaWiki.  2019\.  Manual:pagelinks table — mediawiki, the free wiki engine.  [Online; accessed 15-January-2019].
  * [Navigli and Ponzetto 2012] Navigli, R., and Ponzetto, S. P.  2012\.  Babelnet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network.  Artificial Intelligence 193:217–250.
  * [Pentzold et al. 2017] Pentzold, C.; Weltevrede, E.; Mauri, M.; Laniado, D.; Kaltenbrunner, A.; and Borra, E.  2017\.  Digging Wikipedia: The Online Encyclopedia as a Digital Cultural Heritage Gateway and Site.  Journal on Computing and Cultural Heritage (JOCCH) 10(1):5.
  * [Presutti et al. 2014] Presutti, V.; Consoli, S.; Nuzzolese, A. G.; Recupero, D. R.; Gangemi, A.; Bannour, I.; and Zargayouna, H.  2014\.  Uncovering the semantics of wikipedia pagelinks.  In International Conference on Knowledge Engineering and Knowledge Management, 413–428.  Springer.
  * [Preusse et al. 2013] Preusse, J.; Kunegis, J.; Thimm, M.; Staab, S.; and Gottron, T.  2013\.  Structural dynamics of knowledge networks.  In ICWSM.
  * [Spoerri 2007] Spoerri, A.  2007\.  What is popular on wikipedia and why?  First Monday 12(4).
  * [West and Leskovec 2012] West, R., and Leskovec, J.  2012\.  Human wayfinding in information networks.  In Proceedings of the 21st international conference on World Wide Web, 619–628.  ACM.
  * [West, Paranjape, and Leskovec 2015] West, R.; Paranjape, A.; and Leskovec, J.  2015\.  Mining missing hyperlinks from human navigation traces: A case study of wikipedia.  In Proceedings of the 24th international conference on World Wide Web, 1242–1252.
  * [Wikipedia contributors 2018a] Wikipedia contributors.  2018a.  Help:wikitext — Wikipedia, the free encyclopedia.  https://en.wikipedia.org/w/index.php?title=Help:Wikitext&oldid=866759011.  [Online; accessed 28-December-2018].
  * [Wikipedia contributors 2018b] Wikipedia contributors.  2018b.  History of wikipedia — Wikipedia, the free encyclopedia.  https://en.wikipedia.org/w/index.php?title=History˙of˙Wikipedia&oldid=875601169.  [Online; accessed 28-December-2018].
  * [Wikipedia contributors 2018c] Wikipedia contributors.  2018c.  List of wikipedias — Wikipedia, the free encyclopedia.  https://en.wikipedia.org/w/index.php?title=List˙of˙Wikipedias&oldid=873324169.  [Online; accessed 28-December-2018].
  * [Wikipedia contributors 2018d] Wikipedia contributors.  2018d.  Wikipedia:five pillars — Wikipedia, the free encyclopedia.  https://en.wikipedia.org/w/index.php?title=Wikipedia:Five˙pillars&oldid=869228495.  [Online; accessed 28-December-2018].
  * [Wikipedia contributors 2018e] Wikipedia contributors.  2018e.  Wikipedia:manual of style/linking — Wikipedia, the free encyclopedia.  https://en.wikipedia.org/w/index.php?title=Wikipedia:Manual˙of˙Style/Linking&oldid=875531776.  [Online; accessed 28-December-2018].
  * [Wikipedia contributors 2018f] Wikipedia contributors.  2018f.  Wikipedia:neutral point of view — Wikipedia, the free encyclopedia.  https://en.wikipedia.org/w/index.php?title=Wikipedia:Neutral˙point˙of˙view&oldid=871557947.  [Online; accessed 28-December-2018].
  * [Wikipedia contributors 2018g] Wikipedia contributors.  2018g.  Wikipedia:red link — Wikipedia, the free encyclopedia.  https://en.wikipedia.org/w/index.php?title=Wikipedia:Red˙link&oldid=858691658.  [Online; accessed 29-December-2018].
  * [Wikipedia contributors 2018h] Wikipedia contributors.  2018h.  Wikipedia:visualeditor — Wikipedia, the free encyclopedia.  https://en.wikipedia.org/w/index.php?title=Wikipedia:VisualEditor&oldid=869507404.  [Online; accessed 29-December-2018].
  * [Wulczyn et al. 2016] Wulczyn, E.; West, R.; Zia, L.; and Leskovec, J.  2016\.  Growing wikipedia across languages via recommendation.  In Proceedings of the 25th International Conference on World Wide Web, 975–985.  International World Wide Web Conferences Steering Committee.
  * [Yasseri et al. 2014] Yasseri, T.; Spoerri, A.; Graham, M.; and Kertész, J.  2014\.  The most controversial topics in wikipedia: A multilingual and geographical analysis.  In P.Fichman, and Hara, N., eds., Global Wikipedia: International and Cross-Cultural Issues in Online Collaboration. Scarecrow Press.
  * [Yeh et al. 2009] Yeh, E.; Ramage, D.; Manning, C. D.; Agirre, E.; and Soroa, A.  2009\.  Wikiwalk: random walks on wikipedia for semantic relatedness.  In Proceedings of the 2009 workshop on graph-based methods for natural language processing, 41–49.  Association for Computational Linguistics.
  * [Zachte 2018] Zachte, E.  2018\.  Wikimedia stats.  [Online; accessed 30-December-2018].
  * [Zeng and Cimini 2012] Zeng, A., and Cimini, G.  2012\.  Removing spurious interactions in complex networks.  Physical Review E 85(3):036101.


# Beyond the shortest path: the path length index as a distribution

Leonardo B. L. Santos<EMAIL_ADDRESS>Luiz Max Carvalho  Giovanni G.
Soares  Leonardo N. Ferreira  Igor M. Sokolov  National Center for Monitoring
and Early Warning of Natural Disasters (Cemaden), Brazil  School of Applied
Mathematics (EMAp), Getulio Vargas Foundation (FGV), Brazil  National
Institute of Space Research (INPE), Brazil  Center for Humans and Machines,
Max Planck Institute for Human Development, Germany  Humboldt University of
Berlin, Germany

††journal: Journal Name

##  1 Motivation

Traversing graphs is a fundamental question in Graph Theory and an important
consideration when dealing with complex networks. The traditional complex
network approach considers only the shortest paths from one node to another
[1], and does not take into account several other possible paths. This
limitation is significant, for example, in urban mobility studies [2, 3],
where it important to consider alternative routes between locations.

As mentioned by Lima et al. (2016), in urban mobility settings users choose
multiple routes over origin-destination pairs, and those choices often deviate
from the shortest time path. Galbrun et al. (2016) highlight that chosen
routes may be associated with diverse factors, for instance public safety.
Tomas et al. (2022) further support these claims by showing that exceptional
events, such as urban floods, may lead users to deviate from routes previously
defined to risk-less (and potentially longer) ones.

Estrada and Hatano (2008) proposed the Communicability Index, a number
(scalar) that takes into account not only the shortest paths but also all the
walks from one node to another. Their approach was based on walks. In
contrast, here we are interested in paths due to the urban mobility motivation
context.

On one hand, the number of walks between each pair of nodes in a simple graph
is known analytically [6]. On the other hand, the analogous problem for paths
is NP-hard [7]. Roberts and Kroese (2007) presented an stochastic algorithm to
estimate the solution of that problem using a sequential importance sampling.

In this short report, as the first steps, we present an exhaustive approach to
address the problem of finding all paths between two nodes. We show one can go
beyond the shortest path but we do not need to go so far: we present an
interactive procedure and an early stop possibility. We apply our ideas to the
well-known Zachary’s karate club graph [8]. We do not collapse the
distribution of path lengths between a pair of nodes into a scalar number;
instead we look at the distribution itself - taking all paths up to a pre-
defined path length (considering a truncated distribution), and show the
impact of that approach on the most straightforward distance-based graph
index: the walk/path length.

##  2 Preliminaries: definitions and notation

In this section, we give a few definitions and results from elementary graph
theory to facilitate the understanding of the new results presented herein.
Most of the following discussion is standard and can be found in [1, 6].

We start by defining a graph (Definition 2.1) and then a simple graph
(Definition 2.2), which will be the main objects of interest in this paper.

######  Definition 2.1 (Graph).

A graph $G=(V,E)$ is a set of nodes and edges, where $V$ is the set of $|V|$ =
$N$ nodes and $E$ is the set of $|E|$ = $M$ edges.

An edge (also called link or connection) $(i,j),i,j\in V$ connects two nodes
$i$ and $j$. A self-connection or a loop is a link $(i,i)$ that connects node
$i$ to itself. Multiple edges are two or more edges that connect the same two
vertices.

A link can be undirected or directed. In an undirected graph, all edges
$(i,j)$ connect $i$ to $j$ and vice-versa. A directed graph has directed edges
(also called arcs) $(i,j)$, that connect $i$ to $j$, but not $j$ to $i$, i.e.,
$(i,j)\neq(j,i)$. A link can also have an associated weight, which is a
numeric value.

######  Definition 2.2 (Simple Graph).

A graph $G=(V,E)$ is a simple graph if, and only if, it is undirected, there
are no self-connections in $G$, no multiple edges or weights.

A helpful object for characterizing a graph is its adjacency matrix, whose
definition is given in Definition 2.3.

######  Definition 2.3 (Adjacency matrix).

The adjacency matrix $\boldsymbol{A}$ of a graph $G=(V,E)$ is the $N\times N$
matrix whose entries $A_{ij}$ are given by

$A_{ij}=\begin{cases}1,\>\text{if}\quad i,j\in V\>\text{share an edge};\\\
0,\>\text{otherwise}.\end{cases}$

In this paper, we are concerned with traversing the graph, i.e., starting from
a source node $i\in V$, visiting a collection of nodes, and arrive a target
node $j\in V$, where $i=j$ is a possibility. Here we distinguish between
trajectories that allow multiple visits to the same node (and associated)
edges, called walks (Definition 2.4); and trajectories where each node and
vertex can only be visited once, called paths, presented in Definition 2.5.

We start our discussion with trajectories that can visit the same node
multiple times, called walks:

######  Definition 2.4 (Walk).

Consider a simple graph $G=(V,E)$ and a pair of nodes $i,j$ in $V$. A walk $w$
in $G$ from $i$ to $j$ is an alternating sequence of edges and nodes from $i$
(node of origin/source) to $j$ (node of destination/target).

With this definition in hand, we are prepared to state Theorem 2.1, which
tells us that the number of walks of a given (finite) length is finite so long
as $|V|$ is finite.

######  Theorem 2.1 (Finite number of walks).

Consider a simple graph $G=(V,E)$. Take $i,j\in V$, the number of walks of
length $l$ between $i$ and $j$ is given by

$f_{W}^{ij}(l)=\left(A^{l}\right)_{ij},$

where $A_{ij}$ is the corresponding entry in the adjacency matrix of $G$ – see
Definition 2.3.

###### Proof.

This is a well-known result. See Lemma 2.5 in [6]. ∎

Now, consider trajectories in a graph without ever visiting any node twice.
Such a trajectory is called a path:

######  Definition 2.5 (Path).

Consider a simple graph $G=(V,E)$ and a pair of nodes $i,j$ in $|V|$. A path
$p_{ij}$ in $G$ from $i$ to $j$ is an open ($i\neq j$) walk from $i$ to $j$,
and with no repeated edges or nodes.

As Definition 2.5 makes clear, paths are specializations (restrictions) of
walks. This might prompt the reader to think that one can study paths by
considering restrictions to results about walks. As we will show later on,
this is not always the case. Our approach is somehow similar to Self Avoiding
Walks (SAW) [9], but we fix not only the source but also the target for each
path.

In this paper, we will devote attention to connected graphs (Definition 2.6),
that is, graphs for which there exists at least one path for every pair of
vertices $i,j\in V$.

######  Definition 2.6 (Connected Graph).

A simple graph $G=(V,E)$ is connected if for every pair of vertices $i,j$ one
can construct a subset $C_{ij}\subseteq V$, with $|C_{ij}|=K$ where the
vertices $c_{1},\ldots,c_{K}\in C_{ij}$ are such that $i$ and $c_{1}$ share
and edge as do $j$ and $c_{K}$ and also $c_{k}$ and $c_{k+1}$ share an edge,
for $2\leq k\leq K-1$. In other words, $G$ is connected if and only if one can
always construct at least one path between $i,j\in V$, for every such pair.

The number of vertices visited in the path $p_{ij}$ is the path length
(Definition 2.7), and the shortest such path (Definition 2.8) is usually of
great interest as it is related to many optimization problems, such as the
traveling salesman problem. We now state a few more definitions related to
traversal of graphs, which will be useful in the remainder of the paper.

######  Definition 2.7 (Path Length).

Consider a simple graph $G=(V,E)$. The number of edges on the path from $i$ to
$j$ is the path length ($l^{\prime}$) of that path.

######  Definition 2.8 (Shortest Path Length).

Consider a simple graph $G=(V,E)$. The number of edges on the shortest path
from $i$ to $j$ is the shortest path length ($s^{\prime}$) of that path. The
$s^{\prime}$ is a number associated with the pair $i$-$j$: for each pair
$i$-$j$ there is one and only one $s^{\prime}$: $s^{\prime}$(i,j).

######  Remark 2.1 (Shortest Path).

Consider a simple graph $G=(V,E)$. For any two vertices $i,j\in V$ there is at
least one path from $i$ to $j$ which the path length is the shortest possible.

##  3 Main problem: computing the frequency and length of walks and paths

First, let us take a look at the number of walks: in a simple graph $G=(V,E)$,
for any two vertices $i,j\in V$, there is an infinite number of walks from $i$
to $j$, which holds even for finite graphs. However, if we take a finite path
length, the number of walks with that path length is finite, and it is given
by $f(l_{ij})=(A^{n})_{ij}$, with $n=l_{ij}$. One might now ask what the
expected value for $l_{ij}$ is. As we can always get a walk longer than any
other, we cannot define a normalized probability measure; thus, this
expectation does not exist.

Let us define the shortest walk length from $i$ to $j$, $s_{ij}$, as the
minimum value of $l_{ij}$ \- obviously that the walk associated with this
length is a path. Then, once any (finite) $l_{ij}$ can be expressed as
$l_{ij}$ = $s_{ij}$ \+ $k$, $k\geq 0$, $k\in N$, and, therefore, a “truncated”
expected value, under a k-th order approximation, is:

$\mathbb{E}[l]=\frac{\sum_{n=s_{ij}}^{n=s_{ij}+k}n(A^{n})_{ij}}{\sum_{n=s_{ij}}^{n=s_{ij}+k}(A^{n})_{ij}}.$
(1)

Now, let us move from walks to paths. Between any pair of nodes $i$-$j$ in
$G$, there is at least one path $p$, from $i$ to $j$ \- we are considering a
single connected component in $G$. While # $p$ is finite, the problem of
counting the number of s-t (source-destination) paths in a graph is NP-
complete [7].

Here we propose a $k$-th order approximation for the case of paths. The length
of $p_{ij}$ is $l^{\prime}_{ij}$, and it is between $1$ and $N-1$. Let us
define the shortest path length from $i$ to $j$, s$l^{\prime}$, as the minimum
value of $l^{\prime}_{ij}$. Any $l^{\prime}_{ij}$, therefore, can be expressed
as $l^{\prime}_{ij}=s^{\prime}_{ij}+k$, for a finite value of $k\leq N-2$.
Finally, the expected value, under the k-th order approximation, is:

$\mathbb{E}[l^{\prime}]=\frac{\sum_{n=s^{\prime}_{ij}}^{n=s^{\prime}_{ij}+k}nf(n)}{\sum_{n=s^{\prime}_{ij}}^{n=s^{\prime}_{ij}+k}f(n)},$
(2)

where $f(n)$ is the frequency of a $l^{\prime}_{ij}$=n.

There is no analytical expression for $f(n)$ in the literature. Finding all
paths in a graph can be very computationally expensive - $O(N!)$ in the worst
case: a complete graph with order $N$. Here we perform a depth-limited search
(DLS) in order to find $f(n)$, which can found
here.111https://github.com/gioguarnieri/all_paths222We discussed “to go beyond
the shortest path” in 2018 and implemented the first complete version of this
code in August 2019. The COVID-19 pandemic has changed research agendas
worldwide. We resume this paper in 2022..

It is worth highlighting we do an exhaustive search - finding all possible
paths from a node to another. However, the main insight is that we do not need
to go so far beyond the shortest paths - in order words: we do not use a so
much high value of $k$ in the $k$-th order approximation.

##  4 Results

In this section, we present an analytical result considering complete graphs
(4.1), and, based on a depth-limited Search, results for the Zachary’s Karate
Club graph (4.2).

###  4.1 Complete graphs

In a complete graph all nodes are directly connected to all others
($s^{\prime}_{ij}$=1, $\forall$ i,j). The number of paths between any pair of
nodes is a combinatorial result based on the arrange of N-2 nodes in a path of
length $l^{\prime}$.

######  Theorem 4.1 (Number of paths in a complete graph).

Let $G$ be a complete simple graph. Then the number of paths of length $k+1$
is

$f(k+1)=\begin{cases}1,\quad k=0,\\\ \prod_{r=2}^{r=k+1}N-r,\quad 0<k<N-1,\\\
0,\quad k\geq N-1\end{cases}$

It is possible to note that, in a simple but complete graph, between any pair
of nodes:

  * 1.

There is only one walk (and path) of length 1;

  * 2.

The number of walks grows exponentially with the number of nodes;

  * 3.

The number of paths grows with the number of nodes, but at a rate inversely
related to the number of nodes;

  * 4.

The most frequent path length are the longest ones (lengths N-1 and N-2);

  * 5.

It is always possible to get a walk longer than a previous one;

  * 6.

There is no path of length longer than N-1.

Figure 1 illustrates this result for the a complete graph with $10$ nodes
(C-10).

Figure 1: Number of walks (blue squares) and paths (red circles) from 0 to 1,
in the C10 graph, for each path length.

###  4.2 Zachary’s Karate Club

Zachary’s Karate Club graph is a well known graph [8, 10], with $N=34$,
$M=78$, 1 connected component. Figure 2 shows the Zachary’s Karate Club graph,
with numerated nodes.

Figure 2: Zachary’s Karate Club graph [8] has with $N=34$ vertices and $M=78$
edges and a single connected component.

Figure 3 shows the distribution of the number of walks and paths with specific
lengths from node 0 to node 1 in the Zachary’s Karate Club graph. Considering
walks and paths between nodes $0$ and $1$, it is possible to note that:

  * 1.

There is an edge connecting nodes $0$ and $1$, so, $A_{01}=1$.

  * 2.

As $(A^{1})_{01}=A_{01}=1$, there is only $1$ walk from $0$ to $1$ with length
$1$.

  * 3.

That walk is a path as well.

  * 4.

The shortest path length between nodes $0$ and $1$ is $1$:
$s^{\prime}_{01}=1$.

  * 5.

As $(A^{2})_{01}=7$, there are $7$ walks from $0$ to $1$ with length $2$.

  * 6.

All those walks are paths as well.

  * 7.

As $(A^{3})_{01}=37$, there are $37$ walks from $0$ to $1$ with length $3$.

  * 8.

However, only $13$ of those $37$ walks are paths as well.

  * 9.

The length of the longest path between nodes 0 and 1 is 18.

The number of paths is calculated using the Depth-limited search (DLS),
setting the path length as the limit of the DLS. The longer the path length,
the more significant the difference between the number of walks and paths
between a pair of nodes. There are infinite walks between nodes 0 and 1, but
precisely 8.854.467.719.776.520.000 ($\approx$ 8E18) walks with lengths up to
18. The number of paths between nodes 0 and 1 is 80.137 ($\approx$ 8E4).

Figure 3: Number of walks (blue squares) and paths (red circles) from node 0
to node 1, in the Zachary Karate Club graph, for each path length.

Going beyond the shortest path, let us calculate the expected value for $l$,
under the k-order approximation:

$\mathbb{E}[l_{ij}]=\frac{\sum_{n=s}^{s+k}n(A^{n})_{ij}}{\sum_{n=s}^{s+k}(A^{n})_{ij}}.$
(3)

The expected value for $w_{01}$, under the k=17-order approximation is, thus:

$\mathbb{E}[l_{01}]=\frac{\sum_{n=1}^{18}n(A^{n})_{01}}{\sum_{n=1}^{18}(A^{n})_{01}}.$
(4)

On the other hand, the expected value for $l^{\prime}$, under the k-order
approximation is:

$\mathbb{E}[l^{\prime}_{ij}]=\frac{\sum_{n=1}^{s^{\prime}_{ij}+k}nf_{P}^{(ij)}(n)}{\sum_{n=1}^{s^{\prime}_{ij}+k}f_{P}^{(ij)}(n)}$
(5)

So, the expected value for $l^{\prime}_{01}$, under the k=17-order
approximation:

$\mathbb{E}[l^{\prime}_{01}]=\frac{\sum_{n=1}^{18}nf_{P}^{(ij)}(n)}{\sum_{n=1}^{18}f_{P}^{(ij)}(n)}$
(6)

Figure 4 shows our “delta measure”: $\mathbb{E}[w_{01}]-sw_{01}$ (for walks),
$\mathbb{E}[l^{\prime}_{01}]-sl^{\prime}_{01}$ (for paths), for each value of
$k$.

Figure 4: $\mathbb{E}[w_{01}]-sw_{01}$ (blue squares) and
$\mathbb{E}[l^{\prime}_{01}]-sl^{\prime}_{01}$ (red circles), in the Zachary
karate club graph, for different k-order approximations

It is essential to highlight that difference, for the walks-case, grows
indefinitely. However, in the case of the paths, it converges: it happens
because when we allow longer paths, although the numerator increases (path
length), that increment decreases - once, in a non-complete graph, the number
of paths with a length close to the longest possible is smaller than the
number of paths with intermediate lengths.

Considering all origins and destinations (all the nodes), we notice that the
largest number of paths are between nodes 16 to 25, with 4319868 paths, going
from length 4 to 23. This is interesting since node 16 appears in every case
where the shortest path length is equal to the diameter of the network, is on
the top of the mean length of paths, and has the highest mode. Node 16 seems
the most unapproachable from the network by looking at these data. To access
the table containing the statistics of all paths click
here333https://github.com/gioguarnieri/Pesquisa_Doutorado/blob/master/all_paths_data.md.

##  5 Conclusions

This short report presents an original idea about going “beyond the shortest
path”. After presenting some fundamental concepts in graph theory, we
presented an analytical solution for the problem of counting the number of
possible paths between two nodes in complete graphs, and a depth-limited
approach to get all possible paths between each pair of nodes in a general
graph. Using the simple and well-known Zachary’s karate club graph, we showed
the distribution of walks and path lengths.

The most important result is that we can go beyond the shortest path (facing
an NP-hard problem), but (fortunately) we do not need to go so far: there is a
convergence/saturation value for the path-length expected value - once, in a
non-complete graph, the number of paths with a length close to the longest
possible is smaller than the number of paths with intermediate lengths. The
value of that control parameter ($k$ \- number of edges beyond the shortest
path length) can be even smaller when considering penalties for longer paths.

In future work we plan to apply those ideas to a real-world problem,
addressing urban mobility-related problems.

## References

  * Barabási and Pósfai [2016] A.-L. Barabási, M. Pósfai, Network science, Cambridge University Press, Cambridge, 2016. URL: http://barabasi.com/networksciencebook/.
  * Lima et al. [2016] A. Lima, R. Stanojevic, D. Papagiannaki, P. Rodriguez, M. C. González,  Understanding individual routing behaviour,  J. R. Soc. Interface 13 (2016) 20160021. URL: https://royalsocietypublishing.org/doi/10.1098/rsif.2016.0021.
  * Galbrun et al. [2016] E. Galbrun, K. Pelechrinis, E. Terzi,  Urban navigation beyond shortest route: The case of safe paths,  Information Systems 57 (2016) 160–171. URL: https://www.sciencedirect.com/science/article/pii/S0306437915001854. doi:https://doi.org/10.1016/j.is.2015.10.005.
  * Tomas et al. [2022] L. R. Tomas, G. G. Soares, A. A. S. Jorge, J. F. Mendes, V. L. S. Freitas, L. B. L. Santos,  Flood risk map from hydrological and mobility data: a case study in são paulo (brazil),  Transacitons in GIS - accepted for publication (2022). URL: https://onlinelibrary.wiley.com/doi/10.1111/tgis.12962.
  * Estrada and Hatano [2008] E. Estrada, N. Hatano,  Communicability in complex networks,  Physical review. E, Statistical, nonlinear, and soft matter physics 77 (2008) 036111\. URL: https://arxiv.org/abs/0707.0756.
  * Biggs [1974] N. Biggs, Algebraic graph theory, Cambridge university press, 1974.
  * Roberts and Kroese [2007] B. Roberts, D. P. Kroese,  Estimating the number of s-t paths in a graph,  Journal of Graph Algorithms and Applications 11 (2007) 195–214. URL: https://jgaa.info/accepted/2007/RobertsKroese2007.11.1.pdf.
  * Zachary [1977] W. W. Zachary,  An information flow model for conflict and fission in small groups,  Journal of Anthropological Research 33 (1977) 452–473. URL: https://www.jstor.org/stable/3629752.
  * Herrero [2005] C. P. Herrero,  Self-avoiding walks on scale-free networks,  Phys. Rev. E 71 (2005) 016103. URL: https://link.aps.org/doi/10.1103/PhysRevE.71.016103. doi:10.1103/PhysRevE.71.016103.
  * Girvan and Newman [2002] M. Girvan, M. E. Newman,  Community structure in social and biological networks,  Proceedings of the national academy of sciences 99 (2002) 7821–7826.