The Story
What even are Wikispeedia Voyages?
Let's address the elephant in the room: what exactly are Wikispeedia Voyages? In short, they are defined as a game path where neither the source nor the target is in World Regions, but the path includes at least one article from this category. But that raises another question: how do we identify all the articles that qualify as "World Regions"? The dataset attributes a category to each article in the network - we found out that by combining all the articles with main category "Countries" and a subset of "Geography" subcategories, we obtain an exhaustive set of articles that refer to places, cities, regions or countries. The Treemap below shows what articles the new category "World Regions" comprises, as well as its size and sub-structure comparing to all the other categories.
To visualise the changes of this new category assignment, this Sankey flow chart shows how the initial categories are regrouped into "World Regions" and "Others" categories, displaying their final distribution in the articles dataset.
About a third of all the paths are Voyages, which is a sizable portion of the user paths. It seems that we are not the only ones to use the Wikispeedia Voyage strategy, as more than \( 40\% \) of the users that started in "Others", deviated through "World Regions" to rejoin "Others". Now that we have established that there seems to be some interesting behavioural phenomenon, let's have a closer look at what could explain it.
Impact of the Page Structure
First, as a prerequisite for the main analysis, let's have a look at where users click on pages during their games and whether they are particularly attracted by special elements in the articles such as the abstract, info-boxes or tables.
To achieve this, we parsed and extracted all links along with other useful information from the HTML file of the articles. The first step is to identify the position of links to a particular category within the article (in purple in the following plot). "Position" refers to the rank of a link, such as whether it is the first, last, or somewhere in between. By computing the distribution of these category-specific links across all articles, we can assess whether users' link choices are influenced by the position of the links on the page. The next step is to analyze where users are clicking on an article page. We calculate the typical position of the clicked link for each article in each user path (in blue).
Our analysis reveals that the median and mean positions of category-specific links are both around \( 0.5 \). This suggests that the links are fairly evenly distributed across the page. Furthermore, the difference in link positions between the category "World Regions" and other categories does not show a statistically significant difference based on a \( t \)-test.
This indicates that there is no bias toward the "World Regions" category. However, we also observe that, while links are distributed randomly, users tend to click on the first links more often than those later in the article (with a median click position of \( 0.43 \)). The position of links seems to influence user behaviour, as users are slightly more likely to engage with links that appear earlier on the page.
Now, let's investigate in which section of the page the links are located and on which section users click the most. As before, we identify the section of the clicked links for each article in each path. We then compare this distribution with the section distribution of all links across all articles and paths.
We see here that users click significantly more on links in the Abstract section (\( 30\% \) of clicks, compared to only \( 8\% \) of links). They also engage with the Info-boxes (\( 12\% \) of clicks, though they represent only \( 5\% \) of links) !
Mr. Markov vs. Users
Before diving into detailed comparisons between user behaviour and random network transitions, it is important to first explore the general structure of transitions between categories. This helps us establish a baseline understanding of both the users' navigation patterns and the inherent structure of the Wikispeedia network.
We create a network (directed graph) to represent transitions between different categories of articles:
Nodes: Each node represents a category of articles, where individual articles are grouped under their primary category.- The node size reflects the number of articles within a category.
- The edge width represents the frequency of transitions between categories. Self-loops (transitions within the same category) are excluded to focus on inter-category transitions.
There seems to be some inherent bias of the categories just by the structure of the Wikispeedia network. Indeed, it seems much more likely to end up in World Regions or Science just because the categories are much bigger and more links lead to it. This is a first hint that World Regions are intertwined with the human mind, as humans wrote the articles in questions and made them particularly rich and link-dense.
We also see that World Regions are central for users, but maybe there is a way of disentangling the user behaviour from the network structure? If we consider that users only click on links randomly (i.e. a random walk in the Wikispeedia Network), we can capture the effect of the network structure. Indeed, if taking a random walk always leads you to World Regions, then maybe the users do not actually choose to go there but the network structure just makes it very likely that they end there anyway.
To model this, let's introduce our friend Andrey Andreyevich Markov, who is known for his work on Markov Chains. Using these chains, we can model the transition probabilities from one article A to an article B just by counting the number of links to article B in article A, and dividing by the number of links there are on the page in total. We found in the section about page structure that links further up in the page may be clicked more, but the deviation (only \( 7\% \) above the middle) is small enough. Therefore, we consider the homogenous click probability hypothesis sufficient for the Markov chain to give valuable insight about the network structure.
To get an equivalent transition matrix for users, we can simply count the transitions users actually made at each step. To compare the two obtained probability distributions, we will use the Kullback-Leibler divergence (\( KL \) divergence), a type of statistical distance measuring how much a model probability distribution \( Q \) (the random probabilities) differ from a probability distribution \( P \) (our users' transitions).
Each entry \( P_{ij} \) and \( Q_{ij} \) corresponds to the transition probability from article \( i \) to article \( j \). The \( KL \) divergence is \( 0 \) when \( P_{ij} \) and \( Q_{ij} \) are exactly the same or when the user transition probability is \( 0 \). This means that paths that perfectly aligns with the random transitions should have a baseline divergence of \( 0 \).
A higher value indicates a stronger divergence: if the divergence is high, users choose a certain transition more than the random transitions in the network would suggest. That is, the users actually choose this transition and it is not only due to the network structure. To get an aggregated effect for a certain target article \( j \), we then simply take the mean divergences corresponding to the transition leading to this article (the mean of all divergences in article \( j \)'s column).
It seems that even when comparing the random transitions (that already favour World Region articles) with the user transitions, there is a consistent bias in the first steps towards World Region articles. This shows that users use certain articles more than the already favourable random transitions would suggest. This could have multiple reasons: it could be because users are more comfortable with the articles' topic, but it could also be part of the users' strategy if they noticed that these articles had promising connectivity.
The main takeaway is that in the first few steps, World Region articles seem to be chosen by users much more than random. The Divergence Value is statistically significantly higher (no overlap of the confidence intervals) for World Regions than it is for all the other categories.
User Behaviour in Voyages
As we analyze the impact of user strategies, including their tendency to favor World Region articles, it's important to explore whether this preference for World Regions correlates with ease of gameplay. This section will explore how difficulty metrics differ between Wikispeedia Voyage and non-Voyage paths, as well as between World Regions and non-World Regions categories, to better understand the user experience.
Wikispeedia Voyage paths are significantly longer in time than other paths, with more back-clicks (mean backclicks number of \( 0.54 \) compared to \( 0.31 \)). There is a slightly lower number of ratings of 1 (on a scale from 1 to 5, where 1 indicates ease and 5 indicates difficulty), suggesting that the task is perceived as a bit more difficult. Contrary to what might be expected, the size of the paths (number of steps) remains the same between Voyage and Non-Voyage paths. Moreover, the completion rate for Voyage paths is higher, indicating a level of comfort or strategic advantage.
To delve further into our finding that Voyage paths are longer and have more back-clicks, we can look into how similar the names of articles along the path are. For this, we use both BERT and BGEM3 embeddings of article names (to validate our results with at least two different models) and compute their similarity as the cosine similarity. While this is not a precise method (for individual paths, the similarity may or may not make intuitive sense), it seems that the aggregated similarity over all paths does give significant results.
The similarities are computed for all paths and all steps along each path. We focus here on the first 10 steps of all paths and take the mean over each step in all paths. Because the paths have different lenghts, the mean of e.g. a position \( L \) is taken over all paths that have at least \( L \) steps. Furthermore, we compute the \( 95\% \) confidence interval as \( 1.96 \) times the standard error, which we compute in the same fashion as the mean for each path position. We also min-max normalise the scale to \( [0, 1] \), as the similarity scores for the two models are in a different, somewhat arbitrary range.
There is a clear trend for both types of embeddings: in the first few clicks, the articles chosen have a low similarity to the previous one. This can be interpreted as leaving the original category, because article names in different categories are likely to be less similar. After this, the similarity for the next clicks stabilises, with relatively small fluctuations.
There is also a statistically significant difference between Voyages and Other paths. Generally, both embeddings agree that the similarity along paths is generally lower for Voyages. This could indeed show that there is a stronger detour and zoom-out behaviour from users in Voyages, as the articles visited are on average less similar to one-another. This could also explain the longer paths and more back-clicks: if users more often radically change to less similar articles, they might make more mistakes and end up taking longer.
Are Voyages a Good Strategy?
Since we learned that users pass through World Regions more often than they would during random exploration, we can evaluate whether this is an effective strategy or if there might be a better approach. One way to address this question is to compare user paths with optimal paths.
Let's define the optimal path as the algorithmic shortest path that can be taken. This assumption aligns with the game's goal: to reach the target while minimizing the number of clicks. To analyze the effectiveness of the World Regions strategy, we can examine whether users' choice of categories aligns with the categories in the optimal paths. This involves computing the optimal path by constructing a directed graph where edges represent connections between articles. Using this graph, we calculate all the shortest paths for each source-target pair present in users' games. Interestingly, some pairs have a surprisingly large number of possible optimal paths, up to 599!
The figure below shows the normalized percentage of times each category is visited at each step. For simplicity, only the first 10 steps of user paths are displayed, while optimal paths are shown in full. Note that for optimal paths there is a steep increase for certain categories at the 5th or 6th step, reflecting the fact that fewer paths of this length exist, thus representing a larger percentage over all categories.
We clearly see that in the early steps, World Regions appears most frequently, with its presence steadily decreasing over subsequent steps, aligning with other categories. This trend holds for both user and optimal paths, suggesting that using World Regions early in the path is generally a good strategy.
The plot on the right compares the percentage differences, averaged across all steps. Surprisingly, users pass through World Regions less frequently than optimal paths suggest. This finding is surprising, as we intuitively expected humans to rely more on Wikispeedia Voyages than necessary. However, the opposite is true. Users might benefit from using this category more, maybe because, as shown earlier, it is highly interconnected with other categories.
But Wait?
Our initial hypothesis naively generalises that any article related to countries, places or cities can make Voyages. We then validated our assumption by observing that there were indeed significant changes between Voyages and other paths. But Wait? What if only a subset of well known large countries really contribute to the observations made about Voyages?
We can ask our friend Andrey Andreyevich Markov for advice again. He informed us that the normalised left eigenvector of the transition matrix \( Q \) with eigenvalue \( 1 \) is called the steady-state (SS) of the system. This steady-state gives the probability distribution of which article you end up in when taking infinitely many steps in the random network. For the 8 first values we get:
| Metric | United States | France | United Kingdom | Europe | Germany | English language | European Union | World War II |
|---|---|---|---|---|---|---|---|---|
| SS Proportion | 1.35% | 1.01% | 0.99% | 0.75% | 0.74% | 0.69% | 0.61% | 0.58% |
Indeed, the most likely article to randomly arrive at in the network is United States (with \( 1.35\% \) probability), followed mainly by other World Regions. However, most of the World Region articles in fact have a steady state probability that is almost \( 0 \). That means that only a subset of the World Region articles actually contribute to the effect of Wikispeedia Voyages that we observed. Indeed, while places such as "Suburbs of Johannesburg" do respect our definition of Voyages and World Regions, they are not really what we pictured and observed in the first place. Looking at the user click divergence for single articles and not entire categories (see the first plot about \( KL \) divergence) gives the following figure.
Certain articles in the World Region category have a much higher impact than others. Looking at the scales of mean divergence (\( 10^{-1} \) for United States vs. \( 10^{-4} \) for aggregated World Regions), it seems that a few articles contribute much more than others to World Regions being so popular.
While all our previous conclusions remain valid, it is important to note that the conclusions would probably be more extreme when focusing only on a subset of hubs within World Regions. There are a lot of articles in World Regions that are hubs that are central and used often, but certainly not all of the articles such as hypothesised initially.