In smaller graphs with fewer articles and links, players have fewer choices at each step, which might lead them to reach their target more quickly. Conversely, in larger graphs, the abundance of options could either provide shorter paths through well-connected hubs or lead to longer, more exploratory routes.
To test this hypothesis, we compare the path length distributions across different graph configurations: the full Wikispeedia graph versus category-stratified subgraphs (75%, 50%, 25% of articles) and restricted subgraphs (First 7 Links, Lead Section only). By analyzing these distributions, we can determine whether smaller graphs enable faster navigation or whether the additional connectivity in larger graphs provides more efficient routes.
We assume that shorter paths correspond to faster players who navigate more directly to their targets. This is what we obtained by running our models on the different subgraphs:
The plot shows that smaller graphs lead to significantly shorter navigation paths. The category-stratified subgraphs (75%, 50%, 25%) all show distributions that peak at shorter path lengths compared to the full graph. This clearly demonstrates that yes, players are faster on subsets of Wikipedia—reducing the graph size forces more direct navigation with fewer detours.
However, the restricted subgraphs reveal a nuanced picture. The First 7 Links restriction shows a significant left-shift with much shorter paths, confirming that limiting options forces efficiency. Surprisingly, the Lead Section restriction shows the opposite effect: its peak occurs at longer path lengths (~7-8 steps) compared to the full graph (~5-6 steps). This suggests that while the lead section contains many important links, it lacks some of the “shortcut” links found deeper in articles that enable the most efficient navigation routes.
While smaller graphs may lead to faster navigation, they might also reduce the number of viable paths, making it harder for players to successfully reach their target. Conversely, larger graphs offer more navigation options but could overwhelm players with choices, leading to confusion and abandoned paths.
To investigate whether there exists an optimal graph size that balances navigability with success rate, we examine the path completion rate (percentage of successfully completed paths) across different category-stratified subgraphs. This analysis helps us understand whether reducing the graph size improves or hinders players’ ability to complete their navigation tasks.
Path completion rates drop as graphs get smaller. The full graph has the highest success rate, which decreases when we remove articles down to 75%, 50%, and 25%. So there’s no optimal smaller size. Bigger graphs work better for completing paths.
Smaller graphs make paths shorter, but players are less likely to finish successfully. The tradeoff: smaller graphs = faster but less successful, larger graphs = slower but more successful. More links mean more ways to reach the target, which helps rather than confuses players.
We infered what would happen on restriction of the graph by stratyfying categories. But how would our AI perform if we try to restrict to high placed links?
To investigate whether restricting link placement affects game completion, we compare the two restricted subgraphs with the full graph:
- First 7 Links: Only the first 7 hyperlinks of each article are available
- Lead Section: Only hyperlinks in the lead section are available
These restrictions simulate scenarios where players have limited navigation options, either due to only seeing the top links or only reading the introduction of articles. By comparing their path completion rates with the full graph, we can determine whether players clicking only on first links would still have a good chance of finishing the game efficiently. These are the results we obtained:
Both restrictions severely hurt completion rates. The Full Graph achieves 45.5% completion rate, while First 7 Links drops to just 3.8% and Lead Section to 11.0%. So no, players who only click on first links would struggle to finish the game.
The First 7 Links restriction is too limiting, cutting out over 90% of successful paths. The Lead Section does better but still loses three quarters of the completion rate. This shows that players need access to links throughout the article, not just at the beginning, to find their way to the target.
We can draw here the conclusions of these experiments on the size of the graph: bigger graphs tend to give greater completion rates but slower solutions. We can expect the same effect to scale to the 2025 Wikipedia graph: a player today would have many more options to finish his game so he would achieve greater win rate, unless he gives up before finding them! It might take him much more time to find these options.
This concludes our story, let’s wrap-up!
Hint
- No hint this time ;)