Degrees of Wikipedia

Question

Here is my attempt on implementing "Degrees of Wikipedia" (much faster version can be seen at degreesofwikipedia.com.It's basically an algorithm which tries to connect two unrelated Wikipedia pages by traversing the internal wikilinks they contain. This version in order to produce faster result doesn't look for the exact match, but just for the matching substring in the url, but that can be changed by editing one line, so it's not really an issue.

import re
from collections import deque

import requests
from bs4 import BeautifulSoup


class UrlNode:
    def __init__(self, url, prev):
        self.url = url
        self.prev = prev
        self.transform_url()

    def transform_url(self):
        if self.url.startswith("/wiki"):
            self.url = "https://en.wikipedia.org" + self.url

    def get_subject(self):
        return self.url.rsplit("/", 1)[1].replace("_", " ")


def is_wiki_url(url):
    url_pattern = r"^/wiki/[a-zA-Z0-9_\,.'-]+$"
    return re.match(url_pattern, url, re.I)


def print_path(result):
    path = []
    distance = 0
    while result is not None:
        path.append(result.get_subject())
        distance += 1
        result = result.prev
    path.reverse()

    print("DISTANCE:", distance)
    print(" -> ".join(path))


def crawl(start, query):
    print(" ==== WIKI CRAWLER === ")
    print("Searching for connnection between '", start, "' and '", query, "'", sep="")
    query = query.replace(" ", "_")
    start = "/wiki/" + start.replace(" ", "_")
    session = requests.session()
    visited_urls = []
    start_url = UrlNode(start, None)
    url_queue = deque()
    url_queue.append(start_url)
    while url_queue:
        url_node = url_queue.popleft()
        if url_node.url in visited_urls:
            continue
        visited_urls.append(url_node.url)
        print(url_node.url)
        req = session.get(url_node.url)
        bs = BeautifulSoup(req.text, 'html.parser')
        for link in bs.find_all('a'):
            if not link.has_attr("href"):
                continue
            if is_wiki_url(link["href"]) and link["href"] not in visited_urls:
                # print("\tFound: ", link["href"])
                new_node = UrlNode(link["href"], url_node)
                if query in new_node.url:
                    print("Total pages visited:", str(len(visited_urls)))
                    return new_node
                url_queue.append(new_node)
    return None


start = "Stack Overflow"
query = "Banana"
result = crawl(start, query)
print_path(result)

This generates result:

Total pages visited: 1054
DISTANCE: 4
Stack Overflow -> Wiki -> University of California -> UC Santa Cruz Banana Slugs

My question is: how can I make this work faster? I welcome both algorithmic suggestions and various "hacks", e.g. requesting the mobile version of the page, which should load faster etc. Here I used breadth-first algorithm, which is very basic and I'm pretty sure better options exist.

Answer 1

• I think you can potentially remove the impact of the network altogether by using offline Wikipedia dumps. Wikipedia itself asks to not crawl them:

  Suppose you are building a piece of software that at certain points displays information that came from Wikipedia. If you want your program to display the information in a different way than can be seen in the live version, you'll probably need the wikicode that is used to enter it, instead of the finished HTML.

  Also, if you want to get all the data, you'll probably want to transfer it in the most efficient way that's possible. The wikipedia.org servers need to do quite a bit of work to convert the wikicode into HTML. That's time consuming both for you and for the wikipedia.org servers, so simply spidering all pages is not the way to go.

  Please do not use a web crawler to download large numbers of articles. Aggressive crawling of the server can cause a dramatic slow-down of Wikipedia.

• as far as improving HTML parsing, you can replace html.parser with a faster lxml:

  bs = BeautifulSoup(req.text, 'lxml')
  

  Note: this requires lxml package to be installed.

• make visited_urls a set - this would dramatically improve the lookups

• instead of locating all links and then filtering them, you can ask BeautifulSoup to locate only "wiki" links by using a a[href^="/wiki/"] CSS selector - this would also lead to removing the "href" attribute presence check:

  for link in bs.select('a[href^="/wiki/"]'):
      if link["href"] not in visited_urls:
  

• there is also this SoupStrainer class that would allow you to parse only a part of the document - see if you can apply it to skip some irrelevant parts of the pages

• I am not sure if you actually need a UrlNode class, but if you think you do, __slots__ should improve performance and memory usage:

  class UrlNode:
      __slots__ = ['url', 'prev']
  

Answer 2

DegreesOfWikipedia.com works from both sides of the graph to determine a midpoint.

Basically, it is a double-sided breath-first search.

Here is some bad psuedocode...

1. Get list of outgoing links from article A (starting article) and store in list_a
2. Get list of incoming links from article B (ending article) and store in list_b
3. Check for a common article between list_a and list_b. If one exists, you found your mid point! (1 hop chain! woohoo!)
4. If no common article exists, dive into the shorter of list_a or list_b (whichever has fewer items) and pull the list of outgoing or incoming links to articles (depending on whether you are examining an article in list_a or list_b).
5. Immediately after pulling the list of links to or from each article add the newly seen articles to list_a or list_b, and check to see if a common item exists between list_a and list_b
6. If a common article exists, you have found the midpoint!!! Backtrace your path and return the result!
7. If no common article exists, go to step 4!

Wikipedia has a backlinks API that makes perusing the route in reverse possible. I'm not sure you could obtain rapid results without it.

Hope this makes sense.

Note: By 'list' above, I mean hashtables of some sort, where you can immediately index into any article and know that you've seen it before, and quickly obtain a list of keys (article names) to cross check between both lists.

Source: I wrote degreesofwikipedia.com back in ~2010.

Update 2018-03-21: Here is a link to a github repo, containing the source. Learn from it at your own risk, it's pretty messy (hahaha!):

https://github.com/LKDev5/DegreesOfWikipedia