{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Wikipedia principal eigenvector\n\nA classical way to assert the relative importance of vertices in a\ngraph is to compute the principal eigenvector of the adjacency matrix\nso as to assign to each vertex the values of the components of the first\neigenvector as a centrality score: https://en.wikipedia.org/wiki/Eigenvector_centrality.\nOn the graph of webpages and links those values are called the PageRank\nscores by Google.\n\nThe goal of this example is to analyze the graph of links inside\nwikipedia articles to rank articles by relative importance according to\nthis eigenvector centrality.\n\nThe traditional way to compute the principal eigenvector is to use the\n[power iteration method](https://en.wikipedia.org/wiki/Power_iteration).\nHere the computation is achieved thanks to Martinsson's Randomized SVD\nalgorithm implemented in scikit-learn.\n\nThe graph data is fetched from the DBpedia dumps. DBpedia is an extraction\nof the latent structured data of the Wikipedia content.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "# Authors: The scikit-learn developers\n# SPDX-License-Identifier: BSD-3-Clause\n\nimport os\nfrom bz2 import BZ2File\nfrom datetime import datetime\nfrom pprint import pprint\nfrom time import time\nfrom urllib.request import urlopen\n\nimport numpy as np\nfrom scipy import sparse\n\nfrom sklearn.decomposition import randomized_svd"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Download data, if not already on disk\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "redirects_url = \"http://downloads.dbpedia.org/3.5.1/en/redirects_en.nt.bz2\"\nredirects_filename = redirects_url.rsplit(\"/\", 1)[1]\n\npage_links_url = \"http://downloads.dbpedia.org/3.5.1/en/page_links_en.nt.bz2\"\npage_links_filename = page_links_url.rsplit(\"/\", 1)[1]\n\nresources = [\n    (redirects_url, redirects_filename),\n    (page_links_url, page_links_filename),\n]\n\nfor url, filename in resources:\n    if not os.path.exists(filename):\n        print(\"Downloading data from '%s', please wait...\" % url)\n        opener = urlopen(url)\n        with open(filename, \"wb\") as f:\n            f.write(opener.read())\n        print()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Loading the redirect files\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "def index(redirects, index_map, k):\n    \"\"\"Find the index of an article name after redirect resolution\"\"\"\n    k = redirects.get(k, k)\n    return index_map.setdefault(k, len(index_map))\n\n\nDBPEDIA_RESOURCE_PREFIX_LEN = len(\"http://dbpedia.org/resource/\")\nSHORTNAME_SLICE = slice(DBPEDIA_RESOURCE_PREFIX_LEN + 1, -1)\n\n\ndef short_name(nt_uri):\n    \"\"\"Remove the < and > URI markers and the common URI prefix\"\"\"\n    return nt_uri[SHORTNAME_SLICE]\n\n\ndef get_redirects(redirects_filename):\n    \"\"\"Parse the redirections and build a transitively closed map out of it\"\"\"\n    redirects = {}\n    print(\"Parsing the NT redirect file\")\n    for l, line in enumerate(BZ2File(redirects_filename)):\n        split = line.split()\n        if len(split) != 4:\n            print(\"ignoring malformed line: \" + line)\n            continue\n        redirects[short_name(split[0])] = short_name(split[2])\n        if l % 1000000 == 0:\n            print(\"[%s] line: %08d\" % (datetime.now().isoformat(), l))\n\n    # compute the transitive closure\n    print(\"Computing the transitive closure of the redirect relation\")\n    for l, source in enumerate(redirects.keys()):\n        transitive_target = None\n        target = redirects[source]\n        seen = {source}\n        while True:\n            transitive_target = target\n            target = redirects.get(target)\n            if target is None or target in seen:\n                break\n            seen.add(target)\n        redirects[source] = transitive_target\n        if l % 1000000 == 0:\n            print(\"[%s] line: %08d\" % (datetime.now().isoformat(), l))\n\n    return redirects"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Computing the Adjacency matrix\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "def get_adjacency_matrix(redirects_filename, page_links_filename, limit=None):\n    \"\"\"Extract the adjacency graph as a scipy sparse matrix\n\n    Redirects are resolved first.\n\n    Returns X, the scipy sparse adjacency matrix, redirects as python\n    dict from article names to article names and index_map a python dict\n    from article names to python int (article indexes).\n    \"\"\"\n\n    print(\"Computing the redirect map\")\n    redirects = get_redirects(redirects_filename)\n\n    print(\"Computing the integer index map\")\n    index_map = dict()\n    links = list()\n    for l, line in enumerate(BZ2File(page_links_filename)):\n        split = line.split()\n        if len(split) != 4:\n            print(\"ignoring malformed line: \" + line)\n            continue\n        i = index(redirects, index_map, short_name(split[0]))\n        j = index(redirects, index_map, short_name(split[2]))\n        links.append((i, j))\n        if l % 1000000 == 0:\n            print(\"[%s] line: %08d\" % (datetime.now().isoformat(), l))\n\n        if limit is not None and l >= limit - 1:\n            break\n\n    print(\"Computing the adjacency matrix\")\n    X = sparse.lil_matrix((len(index_map), len(index_map)), dtype=np.float32)\n    for i, j in links:\n        X[i, j] = 1.0\n    del links\n    print(\"Converting to CSR representation\")\n    X = X.tocsr()\n    print(\"CSR conversion done\")\n    return X, redirects, index_map\n\n\n# stop after 5M links to make it possible to work in RAM\nX, redirects, index_map = get_adjacency_matrix(\n    redirects_filename, page_links_filename, limit=5000000\n)\nnames = {i: name for name, i in index_map.items()}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Computing Principal Singular Vector using Randomized SVD\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "print(\"Computing the principal singular vectors using randomized_svd\")\nt0 = time()\nU, s, V = randomized_svd(X, 5, n_iter=3)\nprint(\"done in %0.3fs\" % (time() - t0))\n\n# print the names of the wikipedia related strongest components of the\n# principal singular vector which should be similar to the highest eigenvector\nprint(\"Top wikipedia pages according to principal singular vectors\")\npprint([names[i] for i in np.abs(U.T[0]).argsort()[-10:]])\npprint([names[i] for i in np.abs(V[0]).argsort()[-10:]])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Computing Centrality scores\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "def centrality_scores(X, alpha=0.85, max_iter=100, tol=1e-10):\n    \"\"\"Power iteration computation of the principal eigenvector\n\n    This method is also known as Google PageRank and the implementation\n    is based on the one from the NetworkX project (BSD licensed too)\n    with copyrights by:\n\n      Aric Hagberg <hagberg@lanl.gov>\n      Dan Schult <dschult@colgate.edu>\n      Pieter Swart <swart@lanl.gov>\n    \"\"\"\n    n = X.shape[0]\n    X = X.copy()\n    incoming_counts = np.asarray(X.sum(axis=1)).ravel()\n\n    print(\"Normalizing the graph\")\n    for i in incoming_counts.nonzero()[0]:\n        X.data[X.indptr[i] : X.indptr[i + 1]] *= 1.0 / incoming_counts[i]\n    dangle = np.asarray(np.where(np.isclose(X.sum(axis=1), 0), 1.0 / n, 0)).ravel()\n\n    scores = np.full(n, 1.0 / n, dtype=np.float32)  # initial guess\n    for i in range(max_iter):\n        print(\"power iteration #%d\" % i)\n        prev_scores = scores\n        scores = (\n            alpha * (scores * X + np.dot(dangle, prev_scores))\n            + (1 - alpha) * prev_scores.sum() / n\n        )\n        # check convergence: normalized l_inf norm\n        scores_max = np.abs(scores).max()\n        if scores_max == 0.0:\n            scores_max = 1.0\n        err = np.abs(scores - prev_scores).max() / scores_max\n        print(\"error: %0.6f\" % err)\n        if err < n * tol:\n            return scores\n\n    return scores\n\n\nprint(\"Computing principal eigenvector score using a power iteration method\")\nt0 = time()\nscores = centrality_scores(X, max_iter=100)\nprint(\"done in %0.3fs\" % (time() - t0))\npprint([names[i] for i in np.abs(scores).argsort()[-10:]])"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.9.21"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}