logo Netzschleuder network catalog, repository, and centrifuge

History of wikispeedia

The changes to the source code of this entry in the repository, newest first, each with the differences it made to the entry's files. They are also listed on GitLab.

[entries] New entry: wikispeedia by Tiago de Paula Peixoto 61ea62b
diff --git a/entries/wikispeedia/__init__.py b/entries/wikispeedia/__init__.py
new file mode 100644
index 0000000..650a178
--- /dev/null
+++ b/entries/wikispeedia/__init__.py
@@ -0,0 +1,124 @@
+#! /usr/bin/env python
+# -*- coding: utf-8 -*-
+#
+# Copyright (C) 2020-2026 Tiago de Paula Peixoto <tiago@skewed.de>
+#
+# This program is free software: you can redistribute it and/or modify it under
+# the terms of the GNU Affero General Public License as published by the Free
+# Software Foundation, either version 3 of the License, or (at your option) any
+# later version.
+#
+# This program is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+# FOR A PARTICULAR PURPOSE.  See the GNU Affero General Public License for more
+# details.
+#
+# You should have received a copy of the GNU Affero General Public License along
+# with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+
+from .. import *
+
+import urllib.parse
+from collections import defaultdict
+
+title = "Wikispeedia hyperlinks and human navigation paths (2008-2014)"
+description = r"""Hyperlinks between the articles of a condensed version of the English Wikipedia (the 2007 Wikipedia for Schools, 4,604 articles), and the paths along which people navigated them in the online game Wikispeedia, collected by R. West and collaborators. In the game, a player is given a source and a target article and has to reach the target by clicking only on the links of the articles, as fast as possible. The data contain 51,318 finished and 24,875 unfinished games, played between August 2008 and January 2014.
+
+There are two networks, whose nodes are the same 4,604 articles:
+
+- `links`: the directed hyperlink network; an edge points from an article to an article it links to. 110 articles link to themselves (self-loops).
+- `navigation`: the directed network of the clicks made by the players, aggregated over all games, finished or not; an edge points from an article to an article the players went to from it by clicking a link, weighted by the number of such clicks. The players could also go back to the previous article (a "back click"); back clicks (33,468) are not edges, but they determine the article from which the next click is made. In 146 clicks, the players went along a link that is not in the hyperlink network.
+
+Left out are the individual games: their (hashed) players, start times, durations, the difficulty ratings given by the players, and the reasons why unfinished games ended. The matrix of shortest-path distances provided with the data, which can be computed from the `links` network, is also left out. The targets of 29 unfinished games are not among the articles; they are not counted in `targets`.
+
+The networks have the following properties:
+
+- `name`: the title of the article (with underscores instead of spaces, as given).
+- `categories`: the hierarchical categories of the article (e.g. "subject.Science.Biology"), as given (some articles have none).
+- `navigation`, vertex `sources` and `targets`: the number of games (finished or not) whose source and target was the article.
+- `navigation`, edge `count`: the number of clicks from one article to the other, in all games; `count_finished`, the number of those in finished games; `is_link`, whether the clicked link is in the `links` network."""
+tags = ['Informational', 'Web graph', 'Weighted', 'Metadata']
+url = ['https://snap.stanford.edu/data/wikispeedia.html',
+       'https://dlab.epfl.ch/wikispeedia/play/']
+citation = [('R. West and J. Leskovec, "Human wayfinding in information networks." Proceedings of the 21st International Conference on World Wide Web (WWW), 619-628 (2012).', 'https://doi.org/10.1145/2187836.2187920'),
+            ('R. West, J. Pineau, and D. Precup, "Wikispeedia: An Online Game for Inferring Semantic Distances between Concepts." Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), 1598-1603 (2009).', 'https://www.ijcai.org/Proceedings/09/Papers/267.pdf')]
+icon_hash = None
+upstream_license = None
+upstream_prefix = 'https://snap.stanford.edu/data/wikispeedia'
+_arch = 'wikispeedia_paths-and-graph.tar.gz:wikispeedia_paths-and-graph'
+files = [((f'{_arch}/articles.tsv', f'{_arch}/categories.tsv',
+           f'{_arch}/links.tsv'), 'links', None),
+         ((f'{_arch}/articles.tsv', f'{_arch}/categories.tsv',
+           f'{_arch}/links.tsv', f'{_arch}/paths_finished.tsv', f'{_arch}/paths_unfinished.tsv'),
+          'navigation', None)]
+
+def fetch_upstream(force=False):
+    return fetch_upstream_files(__name__.split(".")[-1], upstream_prefix, files,
+                                force)
+
+def _rows(name, fname):
+    with open_upstream_file(name, fname, "r") as f:
+        for line in f:
+            if line.startswith("#") or not line.strip():
+                continue
+            yield line.rstrip("\n").split("\t")
+
+def _clicks(path):
+    "Clicks (source, target) of a path, resolving the back clicks."
+    stack = []
+    for a in path.split(";"):
+        if a == "<":
+            stack.pop()
+            continue
+        if stack:
+            yield stack[-1], a
+        stack.append(a)
+
+@cache_network()
+@coerce_props()
+@annotate()
+def parse(alts=None):
+    name = __name__.split(".")[-1]
+    for fnames, alt, fmt in files:
+        if alts is not None and alt not in alts:
+            continue
+        arts = [r[0] for r in _rows(name, fnames[0])]
+        idx = {a: i for i, a in enumerate(arts)}
+        g = Graph(directed=True)
+        g.add_vertex(len(arts))
+        g.vp.name = g.new_vp("string", vals=[urllib.parse.unquote(a) for a in arts])
+        g.vp.categories = g.new_vp("vector<string>")
+        for a, c in _rows(name, fnames[1]):
+            g.vp.categories[idx[a]].append(c)
+
+        links = [(idx[a], idx[b]) for a, b in _rows(name, fnames[2])]
+        if alt == "links":
+            g.add_edge_list(links)
+        else:
+            lset = set(links)
+            count = defaultdict(int)
+            count_fin = defaultdict(int)
+            g.vp.sources = g.new_vp("int32_t")
+            g.vp.targets = g.new_vp("int32_t")
+            for fname in fnames[3:]:
+                finished = fname.endswith("paths_finished.tsv")
+                for r in _rows(name, fname):
+                    path = r[3]
+                    g.vp.sources[idx[path.split(";")[0]]] += 1
+                    target = path.split(";")[-1] if finished else r[4]
+                    if target in idx:
+                        g.vp.targets[idx[target]] += 1
+                    for a, b in _clicks(path):
+                        e = (idx[a], idx[b])
+                        count[e] += 1
+                        if finished:
+                            count_fin[e] += 1
+            g.ep.count = g.new_ep("int32_t")
+            g.ep.count_finished = g.new_ep("int32_t")
+            g.ep.is_link = g.new_ep("bool")
+            g.add_edge_list([(s, t, c, count_fin[(s, t)], (s, t) in lset)
+                             for (s, t), c in count.items()],
+                            eprops=[g.ep.count, g.ep.count_finished,
+                                    g.ep.is_link])
+        yield alt, g