07-Wikipedia-PageRank-TP.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# INF674 S7: Wikipedia PageRank\n",
    "\n",
    "## Céline Comte & Fabien Mathieu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "You learned the theoretical basis of PageRank in previous session and earlier today. Time to get your hands dirty."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%pylab inline\n",
    "import zipfile\n",
    "import gzip\n",
    "import codecs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Using Datasets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Wikipedia Dataset\n",
    "\n",
    "We use French and English crawls of Wikipedia made in 2013 and available on http://webgraph.di.unimi.it/. The graphs have been *cleaned*: only links from one article to another article are kept.\n",
    "\n",
    "Two main differences with the DBLP database:\n",
    "- The graphs are *oriented*: a link from $i$ to $j$ does not mean there is a link from $j$ to $i$.\n",
    "- The graphs are bigger. You need to be smart on the way you write your code, both from theoretical and practical points of view. \n",
    "\n",
    "**Important note:** as the English dataset is quite bigger than the French dataset, it is recommended to play with the French dataset first.\n",
    "\n",
    "The datasets are provided in the form of *zip* archives. Each *zip* archive contains the following files:\n",
    "- **_dataset_.ids** contains the actual names of the nodes (one per line, $ n $ lines in total). By convention, each node is associated to its line number (from $ 0 $ to $ n-1 $). Actual names may contain special characters (e.g. *ç*, *é*), so they are encoded with *utf-8*.\n",
    "- **_dataset_.adja** contains the adjacency list of the graph: line $ i $ (from $ 0 $ to $ n-1 $) contains, in plain ASCII, the numbers of the nodes that are neighbors of $ i $.\n",
    "- For oriented graphs, **_dataset_-t.adja** contains the adjacency list of the transposed graph: line $ i $ (from $ 0 $ to $ n-1 $) contains, in plain ASCII, the indices of the nodes that are linked by $ i $.\n",
    "\n",
    "\n",
    "You should have the datasets by now. If not, ask for them. This practical assumes they are stored in **../Datasets/** relatively to your working directory (change the line below to adapt if it is not the case)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "directory = \"../Datasets/\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Caching results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It can be a burden to parse again and again the same datas from ASCII files and convert them into a proper format. The following function will be used to stash your variable in a file for further use. Thanks to Pierre-Antoine (ACN 2017-2018) for pointing out the possibility."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Remark:** compared to previous versions, the code has slightly been updated to be able to pass the transposition through a ``transpose`` boolean. That been said, your old files from previous practicals should still work, so you **do not** have to recompute them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def use_cache(builder, prefix=\"frwiki-2013\", variable = \"size\", transpose=False, rebuild=False, compress=False):            \n",
    "    if transpose:\n",
    "        t = \"-t\"\n",
    "    else:\n",
    "        t = \"\"\n",
    "    try:\n",
    "        if rebuild:\n",
    "            raise ValueError('Value needs to be rebuilt')\n",
    "        if compress:\n",
    "            with gzip.GzipFile(directory+prefix+t+\"-\"+variable+\".npy.gz\", \"r\") as f:\n",
    "                return np.load(f)\n",
    "        else:\n",
    "            return np.load(directory+prefix+t+\"-\"+variable+\".npy\")\n",
    "    except:\n",
    "        data = builder(prefix, transpose=transpose)\n",
    "        if compress:\n",
    "            with gzip.GzipFile(directory+prefix+t+\"-\"+variable+\".npy.gz\", \"w\") as f:\n",
    "                np.save(f, data)\n",
    "        else:\n",
    "            np.save(directory+prefix+t+\"-\"+variable, data)\n",
    "        return data\n",
    "# Set default behavior\n",
    "compress = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most of the core functions below have the following behavior: first they try to load the results from an npy file if one exists, otherwise they parse the dataset to extract the information and save it in an npy file for the next use. This approach avoids re-doing the same work over and over again.\n",
    "\n",
    "You are strongly encouraged to use the same tactic for saving your PageRank computations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Size and degree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following function gives the number of nodes $n$ and the total number of *oriented edges* $m$ of the graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_size(prefix = \"frwiki-2013\", transpose=False):\n",
    "    n = 0\n",
    "    m = 0\n",
    "    with zipfile.ZipFile(directory+prefix+\".zip\") as myzip:\n",
    "        with myzip.open(prefix+\".adja\") as f:\n",
    "            for line in f:\n",
    "                n += 1\n",
    "                m += len([int(s) for s in line.split()])\n",
    "    size = array([n, m])\n",
    "    return size\n",
    "\n",
    "def get_size(prefix = \"frwiki-2013\", rebuild = False):\n",
    "    return use_cache(build_size, prefix, variable = \"size\", rebuild = rebuild, compress = compress)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us run it once to create the value if you didn't keep it from previous practicals."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prefix = \"frwiki-2013\"\n",
    "n, m = get_size(prefix)\n",
    "print(\"Number of nodes in %s: %s\" % (prefix, n))\n",
    "print(\"Number of edges in %s: %s\" % (prefix, m//2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, the function for extracting degree. Remind that in oriented graphs, you have to distinguish between indegree and outdegree (cf the *Power Laws* practical)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_degree(prefix = \"frwiki-2013\", transpose=False):\n",
    "    if transpose:\n",
    "        t = \"-t\"\n",
    "    else:\n",
    "        t = \"\"\n",
    "    n, m = get_size(prefix)\n",
    "    degree = zeros(n, dtype = int)\n",
    "    i = 0\n",
    "    with zipfile.ZipFile(directory+prefix+\".zip\") as myzip:\n",
    "        with myzip.open(prefix+t+\".adja\") as f:\n",
    "            for line in f:\n",
    "                degree[i] = len([int(s) for s in line.split()])\n",
    "                i += 1\n",
    "    return degree\n",
    "\n",
    "def get_degree(prefix = \"frwiki-2013\", transpose=False, rebuild = False):\n",
    "    return use_cache(build_degree, prefix, variable = \"degree\", transpose=transpose, rebuild = rebuild, compress = compress)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us parse the degrees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "out_deg = get_degree(prefix)\n",
    "in_deg = get_degree(prefix, transpose = True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "loglog(sort(out_deg), 1-linspace(0,1,len(out_deg)), 'r', label = \"Out Degree\")\n",
    "loglog(sort(in_deg), 1-linspace(0,1,len(in_deg)), 'b', label = \"In Degree\")\n",
    "xlabel(\"Degree\")\n",
    "ylabel(\"CCDF\")\n",
    "title(prefix)\n",
    "legend(loc = 3)\n",
    "show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adjacency List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to avoid crippling your RAM with a full matrix, we'll use the same format as the one introduced in previous practicals."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_adjacency(prefix=\"frwiki-2013\", transpose=False):\n",
    "    if transpose:\n",
    "        t = \"-t\"\n",
    "    else:\n",
    "        t = \"\"\n",
    "    n, m = get_size(prefix)\n",
    "    A = zeros(n + m + 1, dtype=int)\n",
    "    A[0] = n + 1  # Don't forget the +1!!!\n",
    "    with zipfile.ZipFile(directory + prefix + \".zip\") as myzip:\n",
    "        with myzip.open(prefix + t + \".adja\") as f:\n",
    "            i = 0\n",
    "            for line in f:\n",
    "                neighbors = array(line.split(), dtype=int)\n",
    "                A[i + 1] = A[i] + len(neighbors)\n",
    "                A[A[i]:A[i + 1]] = neighbors\n",
    "                i += 1\n",
    "    return A\n",
    "\n",
    "\n",
    "def get_adjacency(prefix=\"frwiki-2013\", transpose=False, rebuild=False):\n",
    "    return use_cache(\n",
    "        build_adjacency,\n",
    "        prefix,\n",
    "        variable=\"adjacency\",\n",
    "        transpose=transpose,\n",
    "        rebuild=rebuild,\n",
    "        compress=compress)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The result, *A*, is a numpy array of integers of size $n+m+1$, organized as follows:\n",
    "- The $n+1$ first values are indexes\n",
    "- The $m$ last values are destinations\n",
    "- The neighbors of a node $i$ are stored in A[A[i]:A[i+1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = get_adjacency(prefix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Index / Name conversion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following cell extracts the names."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_ids(prefix=\"dblp\", transpose=False):\n",
    "    n, m = get_size(prefix)\n",
    "    delimiter = zeros(n + 1, dtype=int)\n",
    "    text = \"\"\n",
    "    with zipfile.ZipFile(directory + prefix + \".zip\") as myzip:\n",
    "        with myzip.open(prefix + \".ids\") as f:\n",
    "            i = 0\n",
    "            for line in codecs.iterdecode(f, 'utf8'):\n",
    "                delimiter[i + 1] = delimiter[i] + len(line) - 1\n",
    "                text += line[0:-1]\n",
    "                i += 1\n",
    "    return [delimiter, text]\n",
    "\n",
    "\n",
    "def get_ids(prefix=\"dblp\", rebuild=False):\n",
    "    return use_cache(\n",
    "        build_ids, prefix, variable=\"ids\", rebuild=rebuild, compress=compress)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then the traditional **index2name** translator (remark: name2index will not be required for this practical)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def index2name(index, prefix = \"dblp\", delimiter = None, text = None):\n",
    "    if delimiter is None:\n",
    "        delimiter, text = get_ids(prefix)\n",
    "    return text[delimiter[index]:delimiter[index+1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "index2name(123456, prefix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.  Computing Rankings "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most rankings techniques give a score to each page, and then display the pages that have the best score.\n",
    "- Propose a function that takes for input a score vector $ P $ of size $ n $, an integer $ k>0 $ (default to $ k=10 $) and a prefix for a dataset of size $n$ (e.g. <tt>frwiki-2013</tt> or <tt>enwiki-2013</tt>). The function should print the titles of the $ k $ articles with highest value according to $ P $.\n",
    "- Test your function by displaying the names of the $ k $ articles with highest indegree, then the name of the $k$ articles with highest outdegree.\n",
    "- Comment the results: in terms of ranking, which seems to be the more relevant: indegree or outdegree? (remember to try and justify your answer, please)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $A$ the transition matrix seen in course, defined by\n",
    "$$A[i,j] = \\frac{1}{outdegree(i)}\\text{ if }i\\rightarrow j, 0\\text{ otherwise.}$$\n",
    "\n",
    "Compute a PageRank based on the following iteration: do $P_{n+1} = \\alpha P_n A + (1-\\alpha)Z$ until $||P_{n+1}-P_n||_1\\leq \\epsilon ||P_n||_1$.\n",
    "\n",
    "A few hints:\n",
    "- First write a function <tt>pagerank_iteration</tt> that takes as input the (transposed?) adjacency of the graph, the current score $P_{n}$, the out degree distribution, and alpha, and returns the next score $P_{n+1}$. It is recommended to use one single <tt>for</tt> loop over the $n$ nodes.\n",
    "- Then write a <tt>pagerank</tt> that will loop the <tt>pagerank_iteration</tt> function until convergence.\n",
    "- Use a $P_{old}$ vector to store previous iteration and a $P_{new}$ vector to store the new one.\n",
    "- Monitor (e.g. with the <tt>print</tt> function) the time per iteration and the total time (you can use <tt>import time</tt>, <tt>time.clock()</tt>).\n",
    "- Comment the results (top $k$).\n",
    "- Recommended values: $\\alpha = 0.7$, $Z = [1,\\ldots, 1]/n$, $\\epsilon=0.1$ (you may go down to $0.01$ or even further later)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pagerank_iteration(A, P, out, alpha):\n",
    "    # Your code here\n",
    "    # ...\n",
    "    return new_P\n",
    "    \n",
    "def pagerank(prefix = \"frwiki-2013\", alpha = 0.7, epsilon = .01):\n",
    "    # Your code here\n",
    "    # ...\n",
    "    return P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The algorithm above may be a little bit slow. Let's do some tuning. You will learn to speed up your algorithm by mixing theoretical and practical considerations, and it will allow you to play more with the last part. Don't forget to compare your results to the previous question to verify that you did not break anything.\n",
    "\n",
    "It is OK if the name of your PageRank function remains the same thorough all questions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In some corrections of previous practicals, we introduced the package ``numba`` that can be used to accelerate your code. ``numba`` is a Python package that compiles your python code on the fly instead of evaluating it. This called *Just-n-Time* (JiT) compilation.\n",
    "- Pros: a code that is processed with numba has a speed that compares to a C implementation\n",
    "- Cons: while numba understands most standard and numpy Python instructions, some instructions are not, or only partially, implemented, so you may have to modify slightly your code to make it numba-compliant.\n",
    "\n",
    "If you want to learn more about Numba, you can look at the following gist: https://gist.github.com/balouf/007f9360127da12fb6455a9bbceeca36\n",
    "\n",
    "\n",
    "While usually it is best to first optimize your code from an algorithmic perspective before using ``numba`` acceleration, for this practical, you should start with speeding up your inner function ``pagerank_iteration``.\n",
    "\n",
    "Try the following change to your code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numba import njit\n",
    "\n",
    "@njit\n",
    "def pagerank_iteration(A, P, out, alpha):\n",
    "    # Your code here, from previous question\n",
    "    # ...\n",
    "    return new_P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If it works, well done! You can probably use better precision now (recommended: $\\epsilon=0.01$).\n",
    "\n",
    "If not, try to debug to make it work."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Playing with $ \\alpha $ and with the precision may help to speed up the process. Is it a good idea?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try to downsize the time per iteration. How many divisions do you perform per iteration? If it is $m$, you should be able to cut that to $ n $ (with better memory access too). Beware of leaves! How does the time per iteration evolve?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Downsize the number of iterations. Instead of using a new vector for $PA$, try to do the update in place. How does the number of iterations evolve (note: you will probably not notice a difference if $\\epsilon$ is too large, you should try $\\epsilon=0.01$)? For the record, this is called the Gauss-Seidel method, and one can prove that it enhances convergence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For practical use, the ranking matters but not the actual importance values. Replace the stopping condition by *last iteration did not change the ranking of the top $ k $ articles* (e.g. with $ k = 20 $). If you did the previous optimization, you probably do not need to store two distinct values of $P$ anymore."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 6 (bonus)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Look at the following code. Can you tell what it does? Compare it with the previous PageRank function in terms of results and efficiency (time and memory)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@njit\n",
    "def diteration_loop(F, H, A, alpha):\n",
    "    for i in nditer(nonzero(F>alpha*mean(F))):\n",
    "        outnodes = A[A[i]:A[i+1]]\n",
    "        H[i] += F[i]\n",
    "        if outnodes.size:\n",
    "            F[outnodes] += alpha*F[i]/outnodes.size\n",
    "        F[i]=0\n",
    "\n",
    "\n",
    "def diteration(prefix = \"frwiki-2013\", alpha = 0.75, k = 20):\n",
    "    # Setup\n",
    "    n, m = get_size(prefix)\n",
    "    H = zeros(n)\n",
    "    F = ones(n)\n",
    "    A = get_adjacency(prefix)\n",
    "    total_time = time.clock()\n",
    "    ind = argsort(H)[-1:-k-1:-1]\n",
    "    stable = False\n",
    "    iter = 0\n",
    "    # Outer loop\n",
    "    while not(stable):\n",
    "        iter += 1\n",
    "        iter_time = time.clock()\n",
    "        ind_old = ind\n",
    "        # Inner loop\n",
    "        diteration_loop(F, H, A, alpha)\n",
    "        ind = argsort(H)[-1:-k-1:-1]\n",
    "        stable = (ind_old == ind).all()\n",
    "        print(\"Iteration {}: time \".format(iter)+str(time.clock()-iter_time))\n",
    "    print(\"Total time: \"+str(time.clock()-total_time)+\" ({} iterations)\".format(iter))\n",
    "    return H "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of using a uniform distribution as initial value for $P$, why not use a previously saved computation? Interest:\n",
    "- if you already computed a PageRank for a small $ k $ and want better precision (larger $ k $), you do not need to restart from scratch.\n",
    "- this approach will be re-used in the last part.\n",
    "For the record, this is how one updates PageRank of Web graphs when a fresh crawl is made: one uses the old PageRank as an educated guess for the new PageRank."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 8 (bonus)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Discuss what should be done for computing PageRank on a much larger graph (hundred of millions, or even billions of nodes)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Customization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The only semantic information you have about the datasets is the name of the articles. Is it enough to get pertinent pages relatively to a given subject?\n",
    "\n",
    "**Remark:** It is strongly recommended (but not mandatory) that you work on the Optimization questions *before* starting this part."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The algorithm uses a uniform vector $ Z = [1, \\ldots, 1] $. Modify it to take an additional argument **kw** (a string) such that  $ Z[i] $ is  1 if **kw** is in the title of $ i $, 0 otherwise. Save your $ Z $ and $ P $ in files with **kw** in the name. Test your algorithm on some values of **kw** and comment. Possible inputs (don't hesitate to propose your owns; some inputs work better than others):\n",
    "- for **frwiki-2013**: **film**, **biologie**, **physique**, **philosoph**, ... \n",
    "- for **enwiki-2013**: **movie**, **biology**, **physic**, **philosoph**, ... \n",
    "As usual, comment the results!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using a non-uniform $ Z $ will create a bias in favor of the pages that contain **kw** in the title. A simple workaround consists in ranking according to $ P-(1-\\alpha)Z $ instead of $ P $.\n",
    "\n",
    "$ P-(1-\\alpha)Z $ is called the residual PageRank.\n",
    "\n",
    "Explain what is the meaning of $P-(1-\\alpha)Z$ and modify your algorithm to output that instead of $P$.\n",
    "\n",
    "Remark: Some of you may have suppressed the $(1-\\alpha)$ factor from your update function. In that case, the residual PageRank would be just $P-Z$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3 (bonus)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Adapt the algorithm from *3. Optimization Question 6* to compute the residual PageRank. Discuss the differences.\n",
    "\n",
    "Remark: the optimization from Question 3.7 is not easy to make on the algorithm from 3.6. Don't try to implement it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 4 (bonus)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try the other dataset (English / French)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** "
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}