# Wikipedia Reader Navigation: When Synthetic Data Is Enough

Akhil Arora  EPFL<EMAIL_ADDRESS>,  Martin Gerlach  Wikimedia Foundation
<EMAIL_ADDRESS>,  Tiziano Piccardi  EPFL<EMAIL_ADDRESS>,
Alberto García-Durán  Atinary Technologies<EMAIL_ADDRESS>and  Robert West
EPFL<EMAIL_ADDRESS>
(2022)

###### Abstract.

Every day millions of people read Wikipedia. When navigating the vast space of
available topics using hyperlinks, readers describe trajectories on the
article network. Understanding these navigation patterns is crucial to better
serve readers’ needs and address structural biases and knowledge gaps.
However, systematic studies of navigation on Wikipedia are hindered by a lack
of publicly available data due to the commitment to protect readers’ privacy
by not storing or sharing potentially sensitive data. In this paper, we ask:
How well can Wikipedia readers’ navigation be approximated by using publicly
available resources, most notably the Wikipedia clickstream data? We
systematically quantify the differences between real navigation sequences and
synthetic sequences generated from the clickstream data, in 6 analyses across
8 Wikipedia language versions. Overall, we find that the differences between
real and synthetic sequences are statistically significant, but with small
effect sizes, often well below $10\%$. This constitutes quantitative evidence
for the utility of the Wikipedia clickstream data as a public resource:
clickstream data can closely capture reader navigation on Wikipedia and
provides a sufficient approximation for most practical downstream applications
relying on reader data. More broadly, this study provides an example for how
clickstream-like data can generally enable research on user navigation on
online platforms while protecting users’ privacy.

††journalyear: 2022††copyright: acmlicensed††conference: arXiv e-print;
††booktitle: ;††doi: 10.1145/3488560.3498496

##  1\. Introduction

Wikipedia has become one of the largest platforms for open knowledge in the
world with more than 56M articles in 300+ languages and approximately 250K new
articles added each month. However, the knowledge is not just the sum of the
individual articles. In fact, articles in Wikipedia are connected via an
extensive network of hyperlinks; e.g., English Wikipedia’s roughly 6M articles
are connected by more than 400M hyperlinks (45). These hyperlinks allow
readers to navigate from one page to another, find related information, or
discover new topics.

But how do readers use this network to navigate the information contained in
Wikipedia? Insights into patterns of navigation are extremely important for
identifying content that is missing or hard-to-find in order to address
knowledge gaps (78). For example, the gender gap in Wikipedia, which is
commonly associated with an under-representation of biographies on women (53),
is also reflected in structural properties such as lower centrality and
visibility in the network (30; 40). This in turn has been shown to lead to
biases in the navigation of readers (44), adding to observations on gender
disparities in Wikipedia readership (37). A better understanding of navigation
in this context could also help empower readers to find content more easily,
or to organize lists of articles when learning about a specific topic in the
form of a curriculum (57).

The phenomenon of navigating through different topics when browsing Wikipedia
has been colloquially described as a “rabbit hole” (3; 2). However, in
quantitative terms, our understanding of the learning pathways that readers
are actually following is still extremely limited. There have been extensive
studies of navigation on Wikipedia in game-like settings (e.g. Wikigame or
Wikispeedia), where the aim is to find paths between two given articles (74).
However, results from targeted navigation cannot be expected to apply in the
same way to “navigation in the wild” (51).

One of the main limitations to address these questions is the lack of publicly
available data. The raw webrequest logs (26), which capture all requests to
Wikimedia’s servers (including IP addresses), are considered extremely
sensitive. The Wikimedia Foundation’s commitment to protect readers’ privacy
(22) requires this data to remain private and, in fact, to be completely
purged after 90 days. In an effort to accommodate research interests,
anonymized and/or aggregated derived datasets are kept for longer time spans
and shared publicly. For example, the pageview dumps (25) provide timeseries
of the number of pageviews per article per hour. These provide some proxy for
article popularity (see, e.g., the pageviews tool (23)) as well as collective
attentions more generally (54).

In the same vein, the clickstream dataset (18) has been released as a public
resource capturing some aspects of navigation on Wikipedia. It contains the
counts of source–target pairs of articles (i.e., how often a link from one
page to another page was clicked by readers) in a given month. It has not only
been used to study the popularity of links (17), but also for generating
synthetic reading pathways to infer properties of navigation patterns (55).

Here, for the first time, we address the question of how much of the
complexity of reader navigation on Wikipedia can be captured by the publicly
available clickstream data. More precisely, we systematically compare
ensembles of real and synthetically generated navigation sequences via two
studies empirically characterizing the sequences and four downstream tasks
across eight different languages. We find that differences are statistically
significant but absolute effect sizes are small, establishing quantitative
confidence in the utility of clickstream data to study navigation more
generally.

##  2\. Related Work

In this section, we review works studying readers on Wikipedia and their
navigation, as well as navigation on the web more generally.

Wikipedia readers’ pageviews. Wikipedia’s publicly available pageviews-data
(19) (i.e. how often individual pages are viewed) serves as a common proxy to
measure collective attention to, e.g., news or popular topics (27; 54). Other
use cases involve the detection of misalignment between supply and demand to
content by comparing pageviews to quality ratings (72). Furthermore,
individual studies have measured the dwell-time, that is how much time readers
actually spend on a given page, finding substantial differences across
geographic regions (70). More generally, Shaw and Hargittai (62) propose a
model for online participation in the form of a pipeline, where being a reader
is one of many steps for a user to become an active contributor. Thus, readers
have been considered a core-dimension in recent efforts to systematically
approach knowledge gaps in Wikipedia (53).

Navigation on Wikipedia. Only few studies have characterized the navigation of
readers on Wikipedia since data from webrequest-logs is not public. Halfaker
et al. (34) analyzed the distribution of inter-activity times (i.e. the time
between two pageviews by the same user) to determine a threshold when
constructing reading sessions. Lehmann et al. (41) identify four different
types of reading patterns by performing a k-means clustering of reading
sessions obtained (with consent) from anonymized activity log data via the
Yahoo-toolbar. Lydon-Staley et al. (43) found $2$ different types of
curiosity-seeking behavior when looking at the knowledge networks created from
the browsing sessions of $\approx 150$ volunteers. Two recent studies
investigated why readers visit Wikipedia (66; 42) and correlated responses to
surveys on motivation, information need, and prior knowledge with features
from reading sessions such as session length. Paranjape et al. (47) showed
that navigation traces provide a strong signal to predict new useful links
among Wikipedia articles. Furthermore, reading sessions can be used to
construct article embeddings—where similarity captures articles that are read
in close succession (76)—that have been used for building alternative visual
representations of the semantic space of Wikipedia (61).

Applications of clickstream data. Due to lack of availability of data on
Wikipedia’s webrequest-logs, several studies have used the clickstream dataset
as a proxy to characterize navigation. While the latter contains only
aggregate counts of the number of times a given link from a source- to a
target-page was clicked, these studies already provide important insights into
readers’ behavior. While generally only a small fraction of existing links is
used, it was found that popularity of links depends strongly on different
properties of the article (e.g. in-/out-degree, centrality) or the placement
of links within the article (e.g. whether they occur in the lead section) (17;
39). Comparing the incoming and outgoing clicks of a page allows for a
classification of pages based on usage, e.g. into sources/sink or bottlenecks
(29; 15). Other approaches used the clickstream data to assess whether some
articles should be read before others when learning about a specific topic
(57), to detect structural biases in content (44), extract semantic
relationships between articles (14), as a ground-truth for other tasks (59;
12), or to study how the structure of the page influences the links clicked by
the readers (16). Finally, Rodi et al. (55) characterized search strategies in
synthetic data generated from clickstream, however, not without making strong
assumptions about the underlying process of navigation.

Targeted navigation. The most detailed studies on navigation on Wikipedia come
from experiments such as Wikigame (10) or Wikispeedia (73; 75), where
participants are asked to find a path between two given articles using the
hyperlinks. Several studies developed models to assess the order of the Markov
process (65; 50), or assess other hypothesis about the navigation (such as
decentralized search) (35; 64). Empirical approaches aimed at characterizing
different properties of the navigation traces, such as the evolution of step
sizes (74) or why users stop (58). However, conclusions from studies on
targeted navigation do not apply in the same way to “navigation in the wild”
(51).

Navigation in general. Understanding navigation on the web and online
platforms has been a long-standing problem (8). Some of the common approaches
include, e.g., identification of specific patterns (69; 5), development of
generative models (9; 28), or the characterization of the overall
predictability (38).

##  3\. Problem and Notation

In this section, we formalize the problem of assessing the utility of the
public Wikipedia clickstream data (18) to characterize the navigation of
readers in Wikipedia.

We start from the set of real navigation sequences containing the sequences of
pageviews by the same user (indexed by $i$),

(1)
$\mathcal{S}=\left\\{(X_{1}^{(i)},X_{2}^{(i)},\ldots,X_{n_{i}}^{(i)})\right\\}_{i=1,\ldots,N},$

with $n_{i}$ being the length (or the number of pageviews) of the sequence
$i$. Next, we generate a set of synthetic navigation sequences based on the
clickstream data with similar properties,

(2)
$\hat{\mathcal{S}}=\left\\{(X_{1}^{(i)},\hat{X}_{2}^{(i)},\ldots,\hat{X}_{n_{i}}^{(i)})\right\\}_{i=1,\ldots,N},$

where $\hat{X}_{j}^{(i)}$ with $j=2,\ldots,n_{i}$ are pageviews generated via
a random walk on the network of Wikipedia articles.

Given the sets $\mathcal{S}$ and $\hat{\mathcal{S}}$ of navigation sequences,
we conduct multiple analyses and experiments: i) summary statistics derived
from empirical characterization of the sequences (cf. Sec. 5), and ii)
performance-metrics in downstream tasks (cf. Sec. 6), and leverage the
observables to quantify the difference between $\mathcal{S}$ and
$\hat{\mathcal{S}}$.

##  4\. Data and Resources

In this section, we describe in detail the datasets used for the analysis of
reader navigation in Wikipedia. We consider 8 different language versions of
Wikipedia for which clickstream data is available, namely—English (EN),
Japanese (JA), German (DE), Russian (RU), French (FR), Italian (IT), Polish
(PL), and Persian (FA). Additionally, this choice covers languages from
different families. The dataset statistics are presented in Table S1. All the
publicly accessible resources required to reproduce the experiments in this
paper are available at https://github.com/epfl-dlab/wikinav-approx.

Next, we describe the procedure for constructing the five different types (cf.
Table 1) of navigation sequences analyzed in this work, as well as all
auxiliary resources.

###  4.1. Real navigation sequences

We construct navigation sequences for readers of Wikipedia articles using
Wikipedia’s Webrequest server logs from March, 2021. We only consider internal
navigation, i.e., navigation to/from websites external to Wikipedia are
ignored.

Webrequest logs (26). The webrequest logs contain an entry for each HTTP
request to Wikimedia servers, specifying information, including, but not
limited to, timestamp, requested URL, referrer URL, client IP address, and
user agent information.

Constructing navigation sequences. Real navigation sequences are constructed
following the approach proposed by Paranjape et al. (47). As a first step, we
construct navigation sessions for each Wikipedia reader. Note that a reader
may visit multiple pages from a given page by opening different browser tabs,
and thus, navigation sessions are innately trees and not chains. We construct
navigation trees by stitching together pageviews using the referrer
information. From this, we obtain navigation sequences by sampling, uniformly
at random, one root-to-leaf path from each navigation tree with at least 2
nodes. Note that we do not consider all root-to-leaf paths in a tree, as that
would lead to navigation sessions with more complex trees to be over-
represented when compared to those with a simple tree. We observed that most
sequences are short, however, long sequences do exist. For instance, $75\%$
($600M$) of the sequences in the English Wikipedia are of length $2$, but only
$0.5\%$ ($4M$) are of length $10$ or more.

###  4.2. Synthetic navigation sequences

We construct synthetic navigation sequences using the Wikipedia clickstream
and the hyperlink graph from March, 2021.

Wikipedia hyperlink graph. We construct the ‘directed’ hyperlink graph from
the links contained in the main text of Wikipedia articles available via the
XML dumps (21) released by Wikipedia on a monthly basis. We perform link
extraction based on the approach described in (11). To align the article
versions with the webrequest logs and the clickstream data from March 2021, we
use the dumps dated ‘2021-04-01’.

Clickstream dataset. The Wikipedia clickstream (77) contains the counts of
links (i.e. pairs of source-target pages) clicked by Wikipedia readers. The
data is generated from the webrequest logs, and is published on a monthly
basis as dump files (18) for $11$ different language versions of Wikipedia.
There are several pre-processing steps and filters; most importantly, the
removal of links with $10$ or fewer observations for protecting the privacy of
readers.

Table 1.  An overview of the type of navigation sequences analyzed in this
work.

Dataset | Type | Main Characteristics
---|---|---
Logs | Real | Human navigation on Wikipedia.
Clickstream-Priv | Synthetic | Markov-1, biased random walks using private Clickstream.
Clickstream-Pub | Synthetic | Markov-1, biased random walks using public Clickstream.
Clickstream-Pub (I) | Synthetic | Markov-1, biased random walks using public Clickstream,
with a different intrinsic stopping criterion (55).
Graph | Synthetic | Markov-1, unbiased random walks on Wikipedia hyperlink graph.

Generating Markovian navigation sequences. We generate four different types of
synthetic navigation sequences closely mimicking the overall statistics of the
real sequences, by ensuring: i) for each generated sequence the same starting
article and length111If the random walker reaches an isolated node prior to
reaching the desired sequence length, we back-track and restart the walk from
the parent. This step is performed until the desired length is reached. as its
corresponding real sequence, and ii) the number of generated sequences to be
the same as the total number of real sequences. With these constraints in
place, we generate sequences by performing random walks with the following
three different transition probabilities between articles in the Wikipedia
hyperlink graph:

  * •

Clickstream-Priv: weights proportional to the number of clicks between two
articles obtained from the webrequest logs, which is similar to Clickstream-
Pub, except that it also includes pairs of articles with $10$ or fewer
observations.

  * •

Clickstream-Pub: weights proportional to the number of clicks between two
articles obtained from the publicly available clickstream data.

  * •

Graph: weights are uniform over all outgoing links from the Wikipedia
hyperlink graph.

Note that Clickstream-Pub (I) uses the same transition probabilities as
Clickstream-Pub. The only difference is that the former not only decides the
next step but also takes the decision to stop at a given node based on the
pairwise transition probabilities (55) (“intrinsic stopping”). Thus, unlike
other strategies that use extrinsic stopping, the length constraint is not
enforced for navigation sequences obtained using Clickstream-Pub (I).
Additionally, note that the state space for the random walker is all the
articles in the Wikipedia hyperlink graph and not just the ones observed in
the webrequest logs or clickstream. While the unobserved articles would never
be visited via the weighted random walker, the unbiased random walker would
visit them.

###  4.3. Auxiliary resources

For the empirical analysis and downstream tasks we use multiple additional
resources, which are described as follows.

Figure 1. Mixing of flows: Cumulative distribution of AMI values for all pages
$m$ with more than $100$ sequences passing through them (left). Examples of
sequences with strong mixing (middle, $AMI\approx 0.1$) and weak mixing
(right, $AMI\approx 0.6$)

Semantic embedding. The semantic embeddings are learned from textual content
of Wikipedia articles, thereby possessing the ability to capture the inter-
article semantic similarity. The representation for each article in a given
language is obtained by averaging the representations of the words—using pre-
trained FastText (31) word embeddings with $300$ dimensions in the respective
language (6)—appearing in the first paragraph of the article. Similar to Sec.
4.2, we use the XML dump (21) dated ‘2021-04-01’. We use this resource for
performing the semantic diffusion analysis in Sec. 5.2.

Navigation embedding. As the name implies, the navigation embeddings are
learned from the navigation sequences described in Secs. 4.1 and 4.2, thereby
possessing the ability to capture semantic relatedness between the concepts
that different articles represent. Analogous to text-based embeddings, the
navigation sequences (sentences) are ordered collections of pageviews of
articles (words). That said, following convention in the network
representation learning literature (49), we train $128$-dimensional article
embeddings from each of the real and synthetic navigation sequence
datasets—with sequences of at least 2 pageviews—using FastText with the
default hyperparameter settings prescribed in (7). We refrain from
hyperparameter tuning, since i) it captures the typical use-case, and ii) we
are not interested in the absolute performance but only in the relative
difference of the embeddings generated from the respective datasets. We use
this resource for the semantic similarity/relatedness (Sec. 6.3) and topic
classification (Sec. 6.4) tasks.

Added-links data. This data consists of new links added to Wikipedia in April
2021. Following the procedure described in Paranjape et al., we obtain the
added links by computing the set difference of links existent in Wikipedia in
April and March 2021, respectively. Next, we restrict ourselves to added links
possessing at least $10$ indirect paths between them observed in the real
navigation sequences. We denote this set of links as positive examples
$(s,t)\in\mathcal{L}$. We also identify a set of negative examples
$\tilde{\mathcal{L}}$, i.e., a set of links that were not added in the
corresponding period. Please see Appendix A.3 for details around the
aforementioned construction. This dataset is used for the link prediction task
in Sec. 6.2.

Similarity/Relatedness data. We use the WikiSRS data (68) as a ground-truth
for capturing the relationships between articles. It contains the similarity
and relatedness judgments (on a scale of $0\ldots 100$) for 688 pairs of
Wikipedia entities (people, places, and organizations), as assigned by 5
different Amazon Mechanical Turk workers. We map the entities to the
corresponding language version of Wikipedia using the sitelinks from its
Wikidata-item. As a result, a pair is not available for evaluation in a given
language if at least one of the articles does not exist in that language. We
use this dataset for evaluating the navigation sequence-based article
representations through the semantic relatedness task in Sec. 6.3.

Topic-labels data. As a ground-truth for topic assignments to Wikipedia
articles, we use the dataset described by Johnson et al. (36). A Wikipedia
article can belong to one or more of 64 topics (such as ‘Mathematics’,
‘Entertainment’, ‘Politics and Government’, etc.). The annotations come from
editors interested in specific topics who are organized in the so-called
WikiProjects and manually label relevant articles. The more than $2000$
different WikiProjects labels are aggregated to a set of 64 topics using a
taxonomy (33) derived from a hierarchy developed by the editor community (24).
We extract WikiProjects labels for articles in English Wikipedia (almost all
articles have at least one label). For articles in other languages, we apply
the labels from the corresponding article in English. This dataset is used in
the topic classification task described in Sec. 6.4.

##  5\. Empirical Characterization

In this section, we empirically characterize two key aspects of real
navigation sequences that help us to distinguish them from synthetic
navigation sequences. By construction, the synthetic sequences follow a Markov
process of order 1, i.e. when generating a synthetic sequence, the probability
for the next article only depends on the current article and not on any of the
previously visited articles. Therefore, our aim is to quantify the degree to
which previously visited articles affect the probability for the next article
in real navigation sequences, and thus, differs from model selection
approaches that fit Markov models of fixed order (9; 65; 50). First, we
quantify the mixing of incoming and outgoing navigation flows when passing
through a given article using information-theoretic measures (Sec. 5.1).
Second, we quantify how much faster synthetic navigation sequences diffuse in
an abstracted semantic space using an article-embedding (Sec. 5.2).

###  5.1. Mixing of flows

We assess the degree to which the flow of real navigation sequences is mixing
when passing through a specific article (56). For navigation sequences passing
through a given article $m$, we quantify the relation between incoming traffic
(source $s$) and outgoing traffic (target $t$). By construction, the synthetic
navigation sequences exhibit full mixing due to the fact that incoming and
outgoing traffic are completely uncorrelated.

We calculate the adjusted mutual information (AMI) (71). For navigation
sequences passing through $m$, the mutual information (MI) measures the
average amount of information (in bits) about the target-page $t$ when knowing
the source-page $s$. The advantage of AMI is that it is normalized between 0
(full mixing, no information about $t$) and 1 (no mixing, full information
about $t$) and takes into account non-zero values of the MI from finite-size
effects. Please see Appendix A.4 for the mathematical formulation of AMI.

Figure 2. Diffusion in semantic space: Mean cosine distance between the first
article and the article after (Left) $k$-steps ($1\leq k\leq 9$) for EN; and
(Right) $2$-steps for other languages.

Fig. 1 demonstrates that most pages show a very high degree of mixing: the
distribution of AMI values is peaked around $0$ with an exponential decay and
no further mode. In fact, less than $10\%$ of pages have an AMI $>0.1$ and
fewer than $0.1\%$ of pages exhibit AMI $>0.6$. In order to interpret these
numbers, Fig. 1 also shows two visual examples of pages with low and high AMI,
respectively. Qualitatively, we can see that for AMI $\approx 0.1$ the flows
overlap substantially such that starting from a given source $s$ (left), one
can end up in virtually any of the targets $t$ (right) with similar
probability when passing through $m$ (middle). In contrast, for AMI $\approx
0.6$ flows virtually do not overlap such that choosing the source $s$ strongly
determines the target $t$. We find a similar pattern for all 8 languages. We
find no statistically significant correlation between the number of
observations (i.e. number of sequences passing through an article) and the
value of AMI (Spearman’s $\rho=0.0005$, $p=0.80$).

###  5.2. Diffusion in semantic space

Next, we assess whether a similar effect holds for sequences more generally,
not just focusing on groups of sequences passing through a specific article.
For this, we quantify the diffusion of navigation sequences in a low-
dimensional vector space obtained from the text of the articles. For the
latter, we use the Semantic embedding described in detail in Sec. 4.3
capturing how semantically similar articles are. We then map the navigation
sequence into this space and measure the cosine-distance between the starting
article and the article reached after $k$ steps in Fig. 2. Increasing the step
size $k$, we see that the average distance increases for the synthetic
clickstream sequences, however, staying close to the value observed from the
real navigation sequences. As stated in Sec. 1, while all the differences are
statistically significant (measured using bootstrapped 95% confidence
intervals), the effect sizes are small. Specifically, the difference between
Logs and Clickstream-Pub is $<10\%$ until $k=4$, and only for $k>5$, we
observe larger effect sizes, however, we note that those sequences are very
rare. Additionally, these findings hold across different languages. Moving
beyond averages, we also analyze the entire distribution of semantic distances
in Fig. S1. Please see Appendix B for details.

Table 2. Quantitative analysis for assessing the utility of five different
types of navigation sequences across the eight Wikipedia language versions
considered in this study using downstream tasks: (a) Next-article prediction,
(b) Semantic relatedness/similarity, and (c) Topic classification. The best
performance (higher numbers are better) is shown in bold.

|  | All Queries | Filtered Queries
---|---|---|---
Type | Dataset | EN | JA | DE | RU | FR | IT | PL | FA | EN | JA | DE | RU | FR | IT | PL | FA
Real | Logs | 0.369 † | 0.315 † | 0.275 † | 0.317 † | 0.316 † | 0.347 † | 0.302 † | 0.388 † | 0.595 † | 0.615 † | 0.646 † | 0.644 † | 0.690 † | 0.686 † | 0.693 † | 0.666 †
Synthetic | Clickstream-Priv | 0.325 | 0.273 | 0.249 | 0.286 | 0.279 | 0.307 | 0.277 | 0.361 | 0.541 | 0.557 | 0.593 | 0.587 | 0.625 | 0.618 | 0.634 | 0.623
Synthetic | Clickstream-Pub | 0.316 | 0.258 | 0.238 | 0.259 | 0.266 | 0.278 | 0.247 | 0.270 | 0.541 | 0.561 | 0.592 | 0.589 | 0.629 | 0.618 | 0.641 | 0.642
Synthetic |  Clickstream-Pub (I) | 0.288 | 0.222 | 0.197 | 0.214 | 0.212 | 0.236 | 0.191 | 0.221 | 0.537 | 0.557 | 0.591 | 0.586 | 0.625 | 0.618 | 0.642 | 0.639
Synthetic | Graph | 0.017 | 0.017 | 0.019 | 0.024 | 0.015 | 0.020 | 0.029 | 0.050 | 0.018 | 0.022 | 0.026 | 0.028 | 0.020 | 0.024 | 0.040 | 0.062

(a) Next-article prediction (MRR)

|  | Relatedness | Similarity
---|---|---|---
Type | Dataset | EN | JA | DE | RU | FR | IT | PL | FA | EN | JA | DE | RU | FR | IT | PL | FA
Real | Logs | 0.769 | 0.728 | 0.693 | 0.704 | 0.697 | 0.710 | 0.691 | 0.665 | 0.722 | 0.703 | 0.648 | 0.677 | 0.662 | 0.665 | 0.630 | 0.621
Synthetic | Clickstream-Priv | 0.764 | 0.689 | 0.673 | 0.688 | 0.714 | 0.703 | 0.700 | 0.595 | 0.711 | 0.662 | 0.633 | 0.623 | 0.672 | 0.652 | 0.637 | 0.539
Synthetic | Clickstream-Pub | 0.749 | 0.625 | 0.653 | 0.655 | 0.647 | 0.643 | 0.597 | 0.541 | 0.703 | 0.626 | 0.621 | 0.612 | 0.620 | 0.619 | 0.520 | 0.530
Synthetic |  Clickstream-Pub (I) | 0.715 | 0.619 | 0.632 | 0.613 | 0.586 | 0.592 | 0.592 | 0.480 | 0.653 | 0.571 | 0.574 | 0.573 | 0.513 | 0.540 | 0.530 | 0.444
Synthetic | Graph | 0.771 | 0.750 | 0.709 | 0.685 | 0.723 | 0.703 | 0.691 | 0.677 | 0.734 | 0.691 | 0.674 | 0.638 | 0.661 | 0.666 | 0.619 | 0.633

(b) Semantic relatedness/similarity (Spearman’s $\rho$)

|  | Micro Aggregates | Macro Aggregates
---|---|---|---
Type | Dataset | EN | JA | DE | RU | FR | IT | PL | FA | EN | JA | DE | RU | FR | IT | PL | FA
Real | Logs | 0.628 † | 0.667 | 0.621 | 0.633 † | 0.618 | 0.623 | 0.633 | 0.589 | 0.569 † | 0.567 † | 0.547 † | 0.563 † | 0.560 † | 0.557 † | 0.541 † | 0.496
Synthetic | Clickstream-Priv | 0.597 | 0.646 | 0.595 | 0.609 | 0.589 | 0.594 | 0.609 | 0.571 | 0.544 | 0.547 | 0.523 | 0.539 | 0.532 | 0.531 | 0.512 | 0.477
Synthetic | Clickstream-Pub | 0.586 | 0.618 | 0.575 | 0.586 | 0.556 | 0.562 | 0.587 | 0.549 | 0.531 | 0.513 | 0.491 | 0.506 | 0.496 | 0.489 | 0.478 | 0.446
Synthetic |  Clickstream-Pub (I) | 0.524 | 0.561 | 0.495 | 0.522 | 0.449 | 0.461 | 0.502 | 0.453 | 0.464 | 0.431 | 0.396 | 0.436 | 0.378 | 0.375 | 0.387 | 0.335
Synthetic | Graph | 0.625 | 0.666 | 0.636 † | 0.628 | 0.625 † | 0.621 | 0.639 | 0.600 † | 0.563 | 0.543 | 0.535 | 0.547 | 0.555 | 0.543 | 0.526 | 0.499

(c) Topic classification ($F_{1}$-score)

  * †

Indicates statistical significance ($p<0.05$) between the best and the second-
best method using bootstrapped 95% confidence intervals.

##  6\. Downstream Tasks

The empirical observations in the previous section suggest that synthetic
navigation sequences from clickstream data are very similar to real navigation
sequences. In this section, we investigate the implications of the
aforementioned finding for practical downstream applications. For this, we
consider four tasks relevant in the context of reader navigation or for which
navigation sequences have been shown to provide useful signals: predicting the
next article in the navigation sequence (Sec. 6.1), predicting new links to be
added (Sec. 6.2), inferring semantic similarity/relatedness between entities
(Sec. 6.3), and classifying articles into topics (Sec. 6.4). In each case, the
goal is not to propose new methods to achieve state-of-the-art performance in
these tasks. Rather, we are interested in assessing the relative difference in
performance when using synthetic instead of real navigation sequences.

###  6.1. Next-article prediction

We predict the next article in the navigation sequence following typical setup
in sequence-based recommendation tasks (52). Training a model on each of the
different datasets (real and synthetic navigation sequences), we evaluate
their ability to predict the next article in real navigation sequences. The
main idea is that differences between training and test data should be
reflected in a decrease in the prediction score.

Specifically, we use triples of consecutively read articles,
$(s_{1},s_{2},t)$, sampled uniformly from the navigation sequences. For the
training, we select $80\%$ of the triples as training data and train a
separate Markov chain model of order 2 for each of the 4 datasets,
respectively. For the evaluation, we select $10\%$ of the triples each for the
validation- and test-set from the real navigation sequences for all four
cases. For each triple $(s_{1},s_{2},t=t^{*})$ in the test-set, we use the
trained model to compute a ranked list of candidate targets linked from the
sources $(s_{1},s_{2})$ using their predicted likelihoods $P(t|s_{1},s_{2})$,
and then determine the rank of the true target $r(t^{*})$. We evaluate the
predictions using mean reciprocal rank (MRR) (we also measured Recall@k
yielding similar results, not shown).

In Table 2a we observe that, as expected, training the model on synthetic
sequences leads to a decrease in the prediction score. While the performance
using synthetic sequences from the unbiased random walk is extremely poor,
synthetic sequences from clickstream yield an MRR within a relative difference
of $10-20\%$ when compared to the real navigation sequences. Interestingly,
for languages with less data (in terms of the number of navigation sequences),
the performance of the public clickstream becomes substantially worse than the
private clickstream. This suggests that $k$-anonymity (only links with more
than $10$ clicks are included in Clickstream-Pub) plays a larger role than the
restriction to first-order transitions. This is further corroborated when
looking at a set of filtered queries, where we prune all queries that lack
observations in the training set for any one of the four types of navigation
sequences. In addition to yielding overall higher (almost double) values of
MRR, the difference between private and public clickstream virtually
disappears.

###  6.2. Link prediction

We predict new links $(s,t)$ in the Wikipedia graph from a source page $s$ to
a target page $t$ following the approach by Paranjape et al. (47), who showed
that navigation sequences contain a useful signal for the prediction of new
links in Wikipedia. From the Added links data we obtain a labeled dataset of
links consisting of positive $\mathcal{L}$ examples (links that were added)
and negative $\bar{\mathcal{L}}$ examples (links that were not added). Using
real and synthetic navigation sequences, respectively, we calculate the path
proportion for each link $(s,t)\in\mathcal{L},\bar{\mathcal{L}}$ according to
$p(s,t)=N(s,t)/N(s)$, where $N(s,t)$ is the number of sequences from $s$ to
$t$ and $N(s)$ are all sequences starting in $s$. We rank all links according
to $p(s,t)$ in descending order and calculate the precision@k, i.e. what
fraction of the top-k ranked links correspond to positive examples.

In Fig. 3 we see that precision@k decreases with $k$ in most cases from $1$
($k=1$) to $\approx 0.4$ ($k=1000$). The only exception are the predictions
from the synthetic sequences based on the unbiased random walk, which yields a
poor performance. More importantly, the performance from the synthetic
sequences based on the clickstream is comparable with the real navigation
sequences for all values of $k$. In most cases the relative difference is less
than $10\%$. Interestingly, for small $k$ Clickstream-Pub performs slightly
better than Clickstream-Priv, possibly due to filtering of negative low-
probability pairs from the k-anonymity threshold for the former.

###  6.3. Semantic similarity/relatedness

We evaluate how well navigation sequences can be used to infer relationship
between entities. Following the approaches in (67; 14)), we first generate an
embedding of articles from navigation sequences for the real and the synthetic
datasets, respectively. We then compare the cosine-similarity between articles
in this representation with a ground-truth dataset (Similarity/Relatedness
data) containing human-annotated ratings for similarity and relatedness for a
selected set of pairs. Specifically, we calculate Spearman’s $\rho$ between
the two ranked lists of pairs of articles.

Figure 3. Link prediction task: Performance measured using precision@k on five
different types of navigation sequences across the eight Wikipedia language
versions considered in this study. Predictions cannot be made (indicated by
truncated precision curves) for links where no path was observed in the
navigation sequences.

In Table 2b we see that the synthetic sequences from Clickstream-Priv yield
values for $\rho$ that are compatible with the ones obtained from real
navigation sequences. In contrast, values for $\rho$ from the synthetic
sequences from Clickstream-Pub are substantially lower, though the relative
difference is still well within $10-20\%$. Similar to the task of next-article
prediction, this suggests that the $k$-anonymity (only links with more than
$10$ clicks are included in Clickstream-Pub) play a larger role than the
restriction to first-order transitions. This is further corroborated by the
results of the synthetic navigation sequences from the unbiased random walk
which yield values for $\rho$ that are similar or sometimes better than the
real navigation sequences. We note that this finding is consistent with
previous findings reported in (67; 14)) and that the reported values of $\rho$
are on-par with the state-of-the-art results from the study introducing the
ground-truth dataset (46). One interpretation of these observations is that
many of the existing links, even if they are rarely or never used, are crucial
for capturing the complexity in the relationships between entities when
learning representations.

###  6.4. Topic classification

We predict topics of articles in a supervised classification task using the
embeddings obtained from the different navigation sequences. We follow the
approach described in (4; 36), who used embeddings generated from the content
of the articles (text or links) as features to predict labels from topic
annotations of editors.

We use (Navigation embeddings) as features, i.e. the embeddings generated from
the real and synthetic navigation sequences, respectively. We perform
supervised classification of the topic labels from the Topic-labels data,
where an article can have one or more of the $64$ different topic labels. For
each topic label we train an independent binary classifier using logistic
regression, for which we use the publicly available implementation in Scikit-
learn (48) with the prescribed default parameters. We use $80\%$ as the
training set, $10\%$ as validation, and $10\%$ as the test set. We report
micro and macro-F1 statistics. We explored other statistics (precision and
recall) as well as the effect of hyperparameters on the resultant performance,
specifically, the regularization parameter $\alpha$ and the usage of
reciprocal class frequencies as weights in the loss computation for managing
the class imbalance. The results portrayed similar trends, and are therefore
omitted.

In Table 2c we observe that the performance for topic classification does not
vary strongly between real and synthetic datasets as features. Using
navigation embeddings generated from public clickstream data yields the lowest
scores. However, the relative difference to using real navigation sequences
remains well below $10\%$ in most cases. Surprisingly, embeddings generated
from the unweighted hyperlink graph yield a performance on par with real
navigation sequences. Overall, these results largely mirror the findings from
the downstream task on semantic similarity/relatedness in the previous section
(Sec. 6.3). The latter also used embeddings generated from navigation
sequences. Therefore, we can conclude that article embeddings generated from
synthetic navigation sequences are of comparable quality to those generated
from real navigation sequences.

##  7\. Discussion and Concluding Insights

###  7.1. Summary of results

Characterizing the flow of navigation sequences. Across all 8 considered
languages, our results show that navigation sequences passing through a given
article are strongly mixing with most pages exhibiting a mutual information
close to zero, i.e. knowing the source-article provides little information
about the target-article of the navigation sequence. However, for a small set
of articles (around $0.1-1\%$) we observed much larger values of mutual
information, which provides clear evidence for cases where the real navigation
sequences differ substantially from the synthetic navigation sequences. We
showed that, as a result, overall the diffusion in the semantic space of
articles is virtually indistinguishable when comparing real navigation
sequences with synthetic sequences from public clickstream. While differences
in the cosine-similarity between articles separated by $k$ steps are
statistically significant, the effect sizes are small (Table S2).

Performance of synthetic navigation sequences in downstream tasks. We showed
that synthetic navigation sequences from the public clickstream dataset are
effective for many practical applications for all 8 considered languages. We
compared the performance of real and synthetic navigation sequences in four
different downstream tasks involving the use of navigation sequences ( link
prediction (47), next-article prediction (13), generating representations
(61), and topic classification (36)), revealing that using clickstream data
often yields performance that are within $10\%$ (or less) in comparison to
using real navigation sequences (Table S2). Specifically, article embeddings
generated from synthetic navigation sequences are of comparable quality to
those generated from real navigation sequences. Furthermore, in the case of
next-article prediction and semantic similarity/relatedness we found evidence
that the main limitations do not originate from the restrictions to first-
order Markov processes when generating the synthetic data but from additional
filtering of the public data using $k$-anonymity necessary for ensuring
privacy.

###  7.2. Implications and Future Work

When synthetic data is enough. Our results indicate that, for many practical
cases, the synthetic navigation sequences from public clickstream data can be
used as a good approximation for real navigation sequences in Wikipedia. In
order to generate the synthetic sequences in practice, one cannot exactly
match length and starting articles of each real sequence; it is, however,
possible to match these properties on average by sampling from the
distributions of lengths (63) and overall pageview statistics (19),
respectively. Alternatively, it is possible to circumvent the requirement of
matching on length by using intrinsic stopping similar to Clickstream-Pub (I)
style sequences. For cases in which necessary privacy filters (e.g.,
$k$-anonymity) are believed to remove too many rarely-used links, one
potential solution would be to augment the public clickstream data with the
unweighted hyperlink graph.

There are several implications of this finding. First, previous research
investigating navigation on Wikipedia using the public clickstream data (e.g.
on search strategies (55)) could be generalized to describe navigation on
Wikipedia more generally; naturally, it is unlikely to capture all the nuances
of how readers browse Wikipedia (51). Second, research on navigation in
Wikipedia becomes more accessible to a wider range of researchers as the data
underlying the synthetic sequences is publicly available for 11 languages and
updated on a monthly basis. Other resources such as article representations
learned from navigation embeddings, such as the so-called navigation vectors
(76), can now be generated from publicly available datasets and thus become
much more widely available and customizable. Third, our results question the
un-scrutinized approaches to improving our understanding of user behavior
through more and more data which often comes at significant costs to user
privacy. The example of navigation in Wikipedia provides clear evidence that
for many practical downstream tasks (of which we gave four examples) the
available synthetic data can be considered “good enough”. Fourth, the
Wikipedia clickstream data provide an example case for how to approach
research on navigation of users in online platforms more generally in a
privacy-preserving way. It remains an open question whether our findings will
generalize beyond Wikipedia. However, our results highlight that publicly
sharing clickstream-like data constitutes an immensely valuable data source
and empowers others to better understand navigation on these platforms.

When synthetic data is not enough. The clickstream represents an excellent
resource to approximate the global behavior of the readers on Wikipedia, but
it cannot replace the server logs entirely. The fine-grained private
activities stored on the servers, despite the careful anonymization guidelines
of the Wikimedia Foundation, remain a valuable resource for studies that focus
on the properties of readers. Real navigation sequences could help answer
questions that rely on keeping track of the activities of the same user, such
as revisitation patterns, multi-tab behavior, and how readers interact with
additional content on a Wikipedia page (e.g., images or infoboxes (20)). At
the same time, features removed during the aggregation of the public
clickstream, such as time and geolocation, can support a more in-depth
understanding of the information consumption patterns of Wikipedia readers
(51). To this end, an interesting future direction would be to build
generative models capable of generating realistic navigation sequences in a
privacy-preserving manner.

Memory in navigation sequences. The comparison between real and synthetic data
provides insights on the degree of memory in navigation sequences; i.e., we
characterize memory not at the level of an individual sequence but as a
collective property emerging from averaging over hundreds of millions of
sequences. By construction, the synthetic sequences are generated from a
process without memory where the next step does not depend on any of the
previously visited pages, such that deviations from the real sequences
indicate importance of memory. This problem is typically approached by
estimating the order of a Markov-process fitted to the data for, e.g., Web (9)
or targeted navigation (65). While previous works have yielded inconclusive
results, our results suggest that fitting a single order constitutes an ill-
posed problem. While we find that most paths do not possess memory (cf. Fig. 1
where most pages are characterized by mutual information close to $0$), we
cannot claim that readers follow a Markovian process of order $1$. In fact, we
note that there could be a plethora of small but consequential subsets of
navigation sequences with extremely strong memory (e.g., a reporter
researching a topic for their front-page article).

Context of readers during navigation. Our findings serve as a starting point
for more in-depth studies taking into account the context of the reader by
providing ground-truth labels collected from, e.g., surveys. In fact, previous
research on why readers visit Wikipedia (66; 42) showed that motivations are
diverse (e.g. ‘intrinsic learning’, ‘bored’, etc.), or that some topics are
more viewed in some regions (e.g. STEM in countries with lower human
development index). This suggests that future work should aim at better
understanding the heterogeneity of readers and context of their visit.
Furthermore, one promising direction would be to study reading behavior on
longer timescales identifying learning pathways in order to, e.g., generate
curricula around broader topics (57).

###  7.3. Methodological limitations

Pageload as a proxy for reading. The navigation sequences only capture
pageloads from the http-request to Wikimedia’s server. Our data does not
capture actual reading behavior, such as how much time a reader was spending
on a specific page (70). Thus, the pageloads only serve as a proxy.

Wikipedia readers. The construction of the navigation sequences requires the
grouping of pageloads by users. For privacy reasons (e.g. no use of cookies),
we use an approximate unique id by concatenating client IP address and user-
agent (cf. Sec. 4.1). This can lead to aggregation of pageviews by different
readers into the same sequence (e.g. through a shared network) or separation
of pageview by the same reader into different sequences (e.g. by using several
devices). Therefore, the attribution of pageviews to readers is imperfect. For
more information on the implications of this approach, we refer to the
detailed discussion by Singer et al. (66) who use a similar methodology.

##  8\. Conclusions

In this study, we addressed the question of how much of the complexity of
reader navigation in Wikipedia can be captured by the publicly available
clickstream data. We systematically compared ensembles of real and
synthetically generated navigation sequences across 8 different languages. We
found that differences are statistically significant but absolute effect sizes
are small establishing quantitative confidence in the utility of clickstream
data to study navigation more generally. Our results empower more researchers
to study navigation in Wikipedia and further strengthen the privacy of readers
by limiting the need to share further potentially sensitive data in most
practical use-cases.

###### Acknowledgements.

We thank Leila Zia for insightful discussions. This project was partly funded
by the Swiss National Science Foundation (grant 200021_185043), the European
Union (TAILOR, grant 952215), and the Microsoft Swiss Joint Research Center.
We also gratefully acknowledge generous gifts from Facebook and Google
supporting West’s lab.

## References

  * (1)
  * wik ([n.d.]a) [n.d.]a.  The Problem with Wikipedia.  https://xkcd.com/214/.  accessed: 13 August 2021.
  * wik ([n.d.]b) [n.d.]b.  Wiki Rabbit Hole.  https://en.wikipedia.org/wiki/Wiki˙rabbit˙hole.  accessed: 13 August 2021.
  * Asthana and Halfaker (2018) Sumit Asthana and Aaron Halfaker. 2018.  With Few Eyes, All Hoaxes are Deep.  _Proceedings of the ACM on Human-Computer Interaction_ 2, CSCW (2018), 21.
  * Benson et al. (2016) Austin R. Benson, Ravi Kumar, and Andrew Tomkins. 2016\.  Modeling User Consumption Sequences. In _Proc. WWW_. 519–529.
  * Bojanowski et al. ([n.d.]) P. Bojanowski, E. Grave, A. Joulin, and T. Mikolov. [n.d.].  Word vectors for 157 languages.  https://fasttext.cc/docs/en/crawl-vectors.html.  accessed: 13 August 2021.
  * Bojanowski et al. (2017) Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017.  Enriching Word Vectors with Subword Information.  _TACL_ 5 (2017), 135–146.
  * Catledge and Pitkow (1995) Lara D Catledge and James E Pitkow. 1995.  Characterizing browsing strategies in the World-Wide web.  _Computer Networks and ISDN Systems_ 27, 6 (April 1995), 1065–1073.  https://doi.org/10.1016/0169-7552(95)00043-7
  * Chierichetti et al. (2012) Flavio Chierichetti, Ravi Kumar, Prabhakar Raghavan, and Tamas Sarlos. 2012.  Are Web Users Really Markovian?. In _Proc. WWW_. 609–618.
  * Clemesha ([n.d.]) Alex Clemesha. [n.d.].  The Wiki Game.  https://www.thewikigame.com/.  accessed: 13 August 2021.
  * Consonni et al. (2019) Cristian Consonni, David Laniado, and Alberto Montresor. 2019\.  WikiLinkGraphs: A Complete, Longitudinal and Multi-Language Dataset of the Wikipedia Link Networks.  (2019), 598–607.
  * Consonni et al. (2020) Cristian Consonni, David Laniado, and Alberto Montresor. 2020\.  CycleRank, or there and back again: personalized relevance scores from cyclic paths on directed graphs.  _Proceedings. Mathematical, physical, and engineering sciences / the Royal Society_ 476, 2241 (2020).
  * Cordonnier and Loukas (2019) Jean-Baptiste Cordonnier and Andreas Loukas. 2019.  Extrapolating paths with graph neural networks.  _arXiv preprint arXiv:1903.07518_ (2019).
  * Dallmann et al. (2016) Alexander Dallmann, Thomas Niebler, Florian Lemmerich, and Andreas Hotho. 2016.  Extracting semantics from random walks on wikipedia: Comparing learning and counting methods. In _Proc. ICWSM_.
  * Dimitrov et al. (2019) Dimitar Dimitrov, Florian Lemmerich, Fabian Flöck, and Markus Strohmaier. 2019.  Different topic, different trafic: How search and navigation interplay on wikipedia.  _The Journal of Web Science_ 1 (2019).
  * Dimitrov et al. (2016) Dimitar Dimitrov, Philipp Singer, Florian Lemmerich, and Markus Strohmaier. 2016.  Visual Positions of Links and Clicks on Wikipedia. In _Proc. WWW (Companion)_. 27–28.
  * Dimitrov et al. (2017) Dimitar Dimitrov, Philipp Singer, Florian Lemmerich, and Markus Strohmaier. 2017.  What Makes a Link Successful on Wikipedia?. In _Proc. WWW_. 917–926.
  * Foundation ([n.d.]a) Wikimedia Foundation. [n.d.]a.  Analytics Datasets: Clickstream.  https://dumps.wikimedia.org/other/clickstream/readme.html.  accessed: 13 August 2021.
  * Foundation ([n.d.]b) Wikimedia Foundation. [n.d.]b.  Analytics Datasets: Pageviews.  https://dumps.wikimedia.org/other/pageviews/readme.html.  accessed: 13 August 2021.
  * Foundation ([n.d.]c) Wikimedia Foundation. [n.d.]c.  Infobox.  https://en.wikipedia.org/wiki/Infobox.  accessed: 13 August 2021.
  * Foundation ([n.d.]d) Wikimedia Foundation. [n.d.]d.  Wikimedia Downloads.  https://dumps.wikimedia.org/backup-index.html.  accessed: 13 August 2021.
  * Foundation ([n.d.]e) Wikimedia Foundation. [n.d.]e.  Wikimedia Privacy Policy.  https://foundation.wikimedia.org/wiki/Privacy˙policy.  accessed: 13 August 2021.
  * Foundation ([n.d.]f) Wikimedia Foundation. [n.d.]f.  Wikipedia Pageviews Analysis Tool.  https://pageviews.toolforge.org.  accessed: 13 August 2021.
  * Foundation ([n.d.]g) Wikimedia Foundation. [n.d.]g.  WikiProject Council/Directory.  https://en.wikipedia.org/wiki/Wikipedia:WikiProject˙Council/Directory.  accessed: 13 August 2021.
  * Foundation ([n.d.]h) Wikimedia Foundation. [n.d.]h.  Wikistats: Pageview complete dumps.  https://dumps.wikimedia.org/other/pageview˙complete/readme.html.  accessed: 13 August 2021.
  * Foundation (2015) Wikimedia Foundation. 2015\.  Wikimedia Webrequest Server Logs.  https://wikitech.wikimedia.org/wiki/Analytics/Data˙Lake/Traffic/Webrequest.  accessed: 13 August 2021.
  * García-Gavilanes et al. (2017) Ruth García-Gavilanes, Anders Mollgaard, Milena Tsvetkova, and Taha Yasseri. 2017.  The memory remains: Understanding collective memory in the digital age.  _Science advances_ 3, 4 (2017).
  * Geigl et al. (2015) Florian Geigl, Daniel Lamprecht, Rainer Hofmann-Wellenhof, Simon Walk, Markus Strohmaier, and Denis Helic. 2015.  Random Surfers on a Web Encyclopedia. In _Proc. i-KNOW_. 8 pages.
  * Gildersleve and Yasseri (2018) Patrick Gildersleve and Taha Yasseri. 2018.  Inspiration, Captivation, and Misdirection: Emergent Properties in Networks of Online Navigation. In _Complex Networks IX_. 271–282.
  * Graells-Garrido et al. (2015) E Graells-Garrido, M Lalmas, and F Menczer. 2015.  First women, second sex: Gender bias in Wikipedia.  _Proceedings of the 26th ACM_ (2015).
  * Grave et al. (2018) Edouard Grave, Piotr Bojanowski, Prakhar Gupta, Armand Joulin, and Tomas Mikolov. 2018\.  Learning Word Vectors for 157 Languages.  _arXiv preprint arXiv:1802.06893_ (2018).
  * Halfaker and Altay ([n.d.]) Aaron Halfaker and Gabriel Altay. [n.d.].  Text processing utilities for MediaWiki.  https://github.com/mediawiki-utilities/python-mwtext.  accessed: 13 August 2021.
  * Halfaker and Johnson ([n.d.]) Aaron Halfaker and Isaac Johnson. [n.d.].  The WikiTax Taxonomy.  https://github.com/wikimedia/wikitax.  accessed: 13 August 2021.
  * Halfaker et al. (2015) Aaron Halfaker, Os Keyes, Daniel Kluver, Jacob Thebault-Spieker, Tien Nguyen, Kenneth Shores, Anuradha Uduwage, and Morten Warncke-Wang. 2015.  User Session Identification Based on Strong Regularities in Inter-Activity Time. In _Proc. WWW_. 410–418.
  * Helic et al. (2013) Denis Helic, Markus Strohmaier, Michael Granitzer, and Reinhold Scherer. 2013.  Models of human navigation in information networks based on decentralized search. In _Proc. HT_.
  * Johnson et al. (2021a) Isaac Johnson, Martin Gerlach, and Diego Sáez-Trumper. 2021a.  Language-agnostic Topic Classification for Wikipedia.  _arXiv preprint arXiv:2103.00068_ (2021).
  * Johnson et al. (2021b) Isaac Johnson, Florian Lemmerich, Diego Sáez-Trumper, Robert West, Markus Strohmaier, and Leila Zia. 2021b.  Global gender differences in Wikipedia readership. In _Proceedings of the Thirteenth International AAAI Conference on Web and Social Media (ICWSM ’21)_.
  * Kulshrestha et al. (2020) Juhi Kulshrestha, Marcos Oliveira, Orkut Karacalik, Denis Bonnay, and Claudia Wagner. 2020.  Web Routineness and Limits of Predictability: Investigating Demographic and Behavioral Differences Using Web Tracking Data.  _arXiv preprint arXiv:2012.15112_ (2020).
  * Lamprecht et al. (2017) Daniel Lamprecht, Kristina Lerman, Denis Helic, and Markus Strohmaier. 2017.  How the structure of Wikipedia articles influences user navigation.  _New Review of Hypermedia and Multimedia_ 23, 1 (2017), 29–50.
  * Langrock and González-Bailón (2020) Isabelle Langrock and Sandra González-Bailón. 2020\.  The Gender Divide in Wikipedia: A Computational Approach to Assessing the Impact of Two Feminist Interventions. (Nov. 2020).  https://doi.org/10.2139/ssrn.3739176
  * Lehmann et al. (2014) Janette Lehmann, Claudia Müller-Birn, David Laniado, Mounia Lalmas, and Andreas Kaltenbrunner. 2014\.  Reader Preferences and Behavior on Wikipedia. In _Proc. HT_. 88–97.
  * Lemmerich et al. (2019) Florian Lemmerich, Diego Sáez-Trumper, Robert West, and Leila Zia. 2019.  Why the world reads Wikipedia: Beyond English speakers. In _Proc. WSDM_.
  * Lydon-Staley et al. (2021) David M Lydon-Staley, Dale Zhou, Ann Sizemore Blevins, Perry Zurn, and Danielle S Bassett. 2021.  Hunters, busybodies and the knowledge network building associated with deprivation curiosity.  _Nature Human Behaviour_ 5, 3 (2021), 327–336.
  * Menghini et al. (2020) Cristina Menghini, Aris Anagnostopoulos, and Eli Upfal. 2020\.  Wikipedia’s Network Bias on Controversial Topics.  _arXiv preprint arXiv:2007.08197_ (2020).
  * Mitrevski et al. (2020) Blagoj Mitrevski, Tiziano Piccardi, and Robert West. 2020\.  WikiHist.html: English Wikipedia’s Full Revision History in HTML Format.  _Proc. ICWSM_ 14 (2020), 878–884.
  * Newman-Griffis et al. (2018) Denis Newman-Griffis, Albert M Lai, and Eric Fosler-Lussier. 2018\.  Jointly Embedding Entities and Text with Distant Supervision. In _Proc. of ACL RepL4NLP Workshop_. 195–206.
  * Paranjape et al. (2016) Ashwin Paranjape, Robert West, Leila Zia, and Jure Leskovec. 2016\.  Improving Website Hyperlink Structure Using Server Logs. In _Proc. WSDM_. 615–624.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011.  Scikit-learn: Machine Learning in Python.  _JMLR_ 12 (2011), 2825–2830.
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  DeepWalk: Online Learning of Social Representations. In _KDD_. 701–710.
  * Petrović and Scholtes (2020) Luka V Petrović and Ingo Scholtes. 2020.  Learning the Markov order of paths in a network.  _arXiv preprint arXiv:2007.02861_ (2020).
  * Piccardi et al. (2021) Tiziano Piccardi, Martin Gerlach, Akhil Arora, and Robert West. 2021.  A Large-Scale Characterization of How Readers Browse Wikipedia.  _arXiv preprint arXiv:2112.11848_ (2021).
  * Quadrana et al. (2018) Massimo Quadrana, Paolo Cremonesi, and Dietmar Jannach. 2018\.  Sequence-Aware Recommender Systems.  _ACM Comput. Surv._ 51, 4 (2018), 1–36.
  * Redi et al. (2020) Miriam Redi, Martin Gerlach, Isaac Johnson, Jonathan Morgan, and Leila Zia. 2020.  A Taxonomy of Knowledge Gaps for Wikimedia Projects (Second Draft).  _arXiv preprint arXiv:2008.12314_ (2020).
  * Ribeiro et al. (2020) Manoel Horta Ribeiro, Kristina Gligorić, Maxime Peyrard, Florian Lemmerich, Markus Strohmaier, and Robert West. 2020.  Sudden Attention Shifts on Wikipedia Following COVID-19 Mobility Restrictions.  _arXiv preprint arXiv:2005.08505_ (2020).
  * Rodi et al. (2017) Giovanna Chiara Rodi, Vittorio Loreto, and Francesca Tria. 2017\.  Search strategies of Wikipedia readers.  _PLOS ONE_ 12, 2 (2017), 1–15.  https://doi.org/10.1371/journal.pone.0170746
  * Rosvall et al. (2014) Martin Rosvall, Alcides V Esquivel, Andrea Lancichinetti, Jevin D West, and Renaud Lambiotte. 2014\.  Memory in network flows and its effects on spreading dynamics and community detection.  _Nature communications_ 5 (2014).
  * Sayyadiharikandeh et al. (2019) Mohsen Sayyadiharikandeh, Jonathan Gordon, Jose-Luis Ambite, and Kristina Lerman. 2019.  Finding Prerequisite Relations using the Wikipedia Clickstream. In _Proc. WWW (Companion)_. 1240–1247.
  * Scaria et al. (2014) Aju Thalappillil Scaria, Rose Marie Philip, Robert West, and Jure Leskovec. 2014.  The Last Click: Why Users Give up Information Network Navigation. In _Proc. WSDM_. 213–222.
  * Schwarzer et al. (2016) Malte Schwarzer, Moritz Schubotz, Norman Meuschke, Corinna Breitinger, Volker Markl, and Bela Gipp. 2016.  Evaluating link-based recommendations for Wikipedia. In _Proc. JCDL_.
  * Scikit-learn ([n.d.]) Scikit-learn. [n.d.].  Scikit-learn: Adjusted Mutual Information Score.  https://scikit-learn.org/stable/modules/generated/sklearn.metrics.adjusted˙mutual˙info˙score.html.  accessed: 13 August 2021.
  * Sen et al. (2019) Shilad Sen, Anja Beth Swoap, Qisheng Li, Ilse Dippenaar, Monica Ngo, Sarah Pujol, Rebecca Gold, Brooke Boatman, Brent Hecht, and Bret Jackson. 2019\.  Toward Universal Spatialization Through Wikipedia-Based Semantic Enhancement.  _ACM Trans. Interact. Intell. Syst_ 9, 2-3 (2019).
  * Shaw and Hargittai (2018) Aaron Shaw and Eszter Hargittai. 2018.  The Pipeline of Online Participation Inequalities: The Case of Wikipedia Editing.  _The Journal of communication_ 68, 1 (2018), 143–168.
  * Singer (2014) Philipp Singer. 2014\.  Understanding, Leveraging and Improving Human Navigation on the Web. In _Proc. WWW_. 27–32.
  * Singer et al. (2015) Philipp Singer, Denis Helic, Andreas Hotho, and Markus Strohmaier. 2015.  HypTrails: A Bayesian Approach for Comparing Hypotheses About Human Trails on the Web. In _Proc. WWW_. 1003–1013.
  * Singer et al. (2014) Philipp Singer, Denis Helic, Behnam Taraghi, and Markus Strohmaier. 2014.  Detecting Memory and Structure in Human Navigation Patterns Using Markov Chain Models of Varying Order.
  * Singer et al. (2017) Philipp Singer, Florian Lemmerich, Robert West, Leila Zia, Ellery Wulczyn, Markus Strohmaier, and Jure Leskovec. 2017.  Why we read Wikipedia. In _Proc. WWW_.
  * Singer et al. (2013) Philipp Singer, Thomas Niebler, Markus Strohmaier, and Andreas Hotho. 2013.  Computing Semantic Relatedness from Human Navigational Paths: A Case Study on Wikipedia.  _Int. J. Semant. Web Inf. Syst._ 9, 4 (2013), 41–70.
  * Slatelab ([n.d.]) OSU Slatelab. [n.d.].  The WikiSRS Dataset.  https://github.com/OSU-slatelab/WikiSRS.  accessed: 13 August 2021.
  * Tauscher and Greenberg (1997) Linda Tauscher and Saul Greenberg. 1997.  Revisitation Patterns in World Wide Web Navigation. In _Proc. SIGCHI_. 399–406.
  * TeBlunthuis et al. (2019) Nathan TeBlunthuis, Tilman Bayer, and Olga Vasileva. 2019\.  Dwelling on Wikipedia: Investigating Time Spent by Global Encyclopedia Readers. In _Proc. OpenSym_. 14 pages.
  * Vinh et al. (2009) Nguyen Xuan Vinh, Julien Epps, and James Bailey. 2009\.  Information theoretic measures for clusterings comparison.  _Proc. ICML_ (2009).
  * Warncke-Wang et al. (2015) Morten Warncke-Wang, Vivek Ranjan, Loren Terveen, and Brent Hecht. 2015.  Misalignment between supply and demand of quality content in peer production communities. In _Proc. ICWSM_.
  * West ([n.d.]) Robert West. [n.d.].  Wikispeedia.  https://dlab.epfl.ch/wikispeedia.  accessed: 13 August 2021.
  * West and Leskovec (2012) Robert West and Jure Leskovec. 2012.  Human Wayfinding in Information Networks. In _Proc. WWW_. 619–628.
  * West et al. (2009) Robert West, Joelle Pineau, and Doina Precup. 2009\.  Wikispeedia: An Online Game for Inferring Semantic Distances between Concepts. In _Proc. IJCAI_. 1598–1603.
  * Wulczyn ([n.d.]) Ellery Wulczyn. [n.d.].  Wikipedia Navigation Vectors.  https://meta.wikimedia.org/wiki/Research:Wikipedia˙Navigation˙Vectors.  accessed: 13 August 2021.
  * Wulczyn and Taraborelli (2015) Ellery Wulczyn and Dario Taraborelli. 2015.  Wikipedia clickstream.  https://meta.wikimedia.org/wiki/Research:Wikipedia˙clickstream.
  * Zia et al. (2019) Leila Zia, Isaac Johnson, Bahodir Mansurov, Jonathan Morgan, Miriam Redi, Diego Saez-Trumper, and Dario Taraborelli. 2019.  Knowledge Gaps – Wikimedia Research 2030.  https://doi.org/10.6084/m9.figshare.7698245.v1

Figure S1. Diffusion in semantic space: Distribution of cosine distance
between the first article of a sequence and the article after $k$-steps
($k=1,2,3$) for English Wikipedia.

##  Appendix A Implementation details

###  A.1. Constructing navigation sequences

We mimic a reader via an MD5 digest of the concatenation of the client IP
address and the user agent string, which serves as an approximate reader ID.
The user agent information is also used to discard common bots and crawlers.

###  A.2. Semantic embedding

As stated in Sec. 4.3, semantic embeddings for each Wikipedia article is
obtained by using the content in its abstract, i.e., all the content before
the first section. To this end, we used the Python package mwtext (v0.0.1)
(32) for extracting the article abstracts from its wikitext-markdown.

###  A.3. Added-links data

Given all $s$ and $t$ appearing in a link $(s,t)\in\mathcal{L}$ we consider as
negative examples all $(s,t^{\prime})$ and $(s^{\prime},t)$ for which i)
$(s,t^{\prime})$ or $(s^{\prime},t)$ is not already a link, ii)
$(s,t^{\prime}),(s^{\prime},t)\notin\mathcal{L}$, and iii) there are at least
$10$ navigation sequences with an indirect path between $s$ and $t^{\prime}$
or $s^{\prime}$ and $t$, respectively.

Table S1.  Dataset statistics.

Language | #Pages | #Links | #NavigationSequences
---|---|---|---
English (EN) | 6,279,688 | 228,874,000 | 810,994,170
Japanese (JA) | 1,261,262 | 59,872,582 | 122,157,015
German (DE) | 2,557,540 | 76,790,852 | 89,441,061
Russian (RU) | 1,711,949 | 47,989,746 | 81,877,016
French (FR) | 2,314,313 | 73,343,009 | 70,321,709
Italian (IT) | 1,683,856 | 48,708,959 | 65,974,945
Polish (PL) | 1,465,640 | 31,460,165 | 27,531,169
Persian (FA) | 778,667 | 9,660,952 | 15,845,197

###  A.4. Mixing of flows: AMI

Specifically, we get all triples of consecutively visited pages $(s,m,t)$. For
every distinct page $m^{*}$ we consider the set
$\left\\{(s,m=m^{*},t)\right\\}$ of all triples passing through $m^{*}$ and
calculate the joint distribution

(3)
$P_{m^{*}}(s=s^{*},t=t^{*})=\frac{\left|\left\\{(s=s^{*},m=m^{*},t=t^{*})\right\\}\right|}{\left|\left\\{(s,m=m^{*},t)\right\\}\right|}$

counting the fraction of triples starting in $s^{*}$ and ending in $t^{*}$
while passing through $m^{*}$. We calculate the AMI for each page $m$ to
assess the degree of mixing of the trajectories passing through. We first
calculate the MI between all sources $s\in S$ and targets $t\in T$ as

(4) $MI_{m}(S,T)=\sum_{s\in S,t\in
T}P_{m}(s,t)\log\frac{P_{m}(s,t)}{P_{m}(s)P_{m}(t)}$

from which we get the AMI as

(5)
$AMI_{m}(S,T)=\frac{MI_{m}(S,T)-\hat{MI}_{m}(S,T)}{\max{\left\\{H(S),H(T)\right\\}}-\hat{MI}_{m}(S,T)}.$

where $H(S),H(T)$ are the entropies over the marginal distributions and
$\hat{MI}_{m}(S,T)$ is the expected MI from finite-size effects when randomly
relating source and target. In practice, we use the implementation (60) from
Scikit-learn (48).

##  Appendix B Diffusion in semantic space

We observe in Fig. S1 that the distribution of distances for real and
synthetic sequences from clickstream are almost completely overlapping (even
for larger $k$) showing that differences are present but overall small. In
contrast, the distribution of distances from the synthetic sequences of the
unweighted random walk on the hyperlink graph is substantially shifted to
larger values indicating that these sequences are much less confined and, as a
result diffuse much faster. As a sanity-check, we show that the semantic
distance between two completely randomly drawn articles is much larger
corroborating that the embedding space captures the semantic similarity
between articles.

Table S2. Quantifying the effect size measured as the percentage relative
difference of the observed outcomes between real (Logs) and synthetic
(Clickstream-Pub) navigation sequences for the analyses and downstream tasks
in this study. A negative relative difference indicates that synthetic
navigation sequences (Clickstream-Pub) achieve a better outcome than real
navigation sequences (Logs).

| Language version
---|---
Task | EN | JA | DE | RU | FR | IT | PL | FA
Semantic distance ($k=1$) | -1.49 | -0.98 | -1.28 | -1.25 | -2.4 | -2.33 | -1.18 | -0.79
Semantic distance ($k=3$) | 11.1 | 2.32 | 6.43 | 6.21 | 8.17 | 12.96 | 4.09 | 5.44
Semantic distance ($k=5$) | 28.93 | 5.12 | 19.11 | 14.77 | 19.3 | 36.43 | 9.24 | 14.91
Semantic distance ($k=9$) | 68.59 | 10.11 | 47.99 | 23.72 | 29.4 | 58.57 | 24.49 | 43.6
Next-article prediction (All queries) | 14.38 | 18.01 | 13.33 | 18.51 | 15.71 | 19.92 | 18.31 | 30.56
Next-article prediction (Filtered queries) | 9.20 | 8.85 | 8.32 | 8.60 | 8.86 | 9.93 | 7.58 | 3.64
Semantic relatedness | 2.58 | 16.45 | 6.05 | 7.48 | 7.67 | 10.39 | 15.64 | 22.94
Semantic similarity | 2.61 | 12.19 | 4.38 | 10.64 | 6.86 | 7.47 | 21.30 | 17.18
Topic classification (Micro) | 6.67 | 7.47 | 7.43 | 7.35 | 10.08 | 9.78 | 7.18 | 6.78
Topic classification (Macro) | 6.68 | 9.61 | 10.24 | 10.08 | 11.32 | 12.13 | 11.56 | 10.12
Link prediction (P@10) | -25.00 | 10.00 | 0.00 | 0.00 | 0.00 | -11.11 | -11.11 | 0.00
Link prediction (P@50) | -13.64 | 17.78 | 18.75 | 13.04 | 0.00 | -4.55 | 11.11 | 2.50
Link prediction (P@100) | -2.38 | 22.47 | 20.45 | 7.41 | 8.43 | 4.88 | 12.50 | 10.26