{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "741d3cc3",
   "metadata": {},
   "source": [
    "# Tutorial 2 - Page rank, plotting and more numpy gymnastics"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0b980c8",
   "metadata": {},
   "source": [
    "In this exercise, we will implement and play with the page rank algorithm.\n",
    "As seen in the lecture, the page rank algorithm allows to take a graph (e.g. the internet graph) and rank its nodes (the websites) in order of importance, or relevance, to the rest of the graph.  Of course, we can apply the page rank algorithm also to other graphs, not only to the internet.\n",
    "\n",
    "In exercise 1, we play with the novel \"Les Miserables\". We construct the graph of co-occurencies of the characters: each character of the novel is a node of the graph (a website in the internet example) and each pair of characters is linked if they appear together in at least one scene. We will use pagerank to identify the most relevant characters of the novel.\n",
    "We will then compare the pagerank algorithm with the direct computation of the leading eigenvector using numpy's eigen-decomposition utilities.\n",
    "\n",
    "In exercise 2, we implement page rank for a much larger graph, the graph of links in the wikipedia of simple english. This will require some care in the implementation to run efficiently - for this we will use the sparse matrix format and think about how to re-express a single pagerank iteration more efficiently.\n",
    "\n",
    "Exercise 3 consists in a few theoretical questions similar to those asked in the exam.\n",
    "\n",
    "The theoretical tools used in this tutorial are those of section 1 of the lecture notes (eigenvalues, the power method and the page rank algorithm)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ee5ac7b",
   "metadata": {},
   "source": [
    "# Exercise 1 : Les Miserables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "352415d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# importing libraries we need later\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf0459c1",
   "metadata": {},
   "source": [
    "## 1.a Loading the data and visualization\n",
    "For starters, we go for the dataset of co-occurences in a scene between the characters of \"Les Miserables\". This containes 77 characters and counts for every pairs if they appear together. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec6b77be",
   "metadata": {},
   "source": [
    "Note that in the beginning of this notebook, we already imported all the proprietary libraries we will need. You know `numpy` for arrays and vectors, but we added `matplotlib` we will use for plotting later. \n",
    "\n",
    "To load the data from Les Miserables, the TAs wrote some code to import it. Since it is not important that you read/understand it, we put the code in a separate file in this directory `utils.py`.\n",
    "\n",
    "To use the functions defined in there for data loading and visualization, we simply use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "28346ac6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# import from current directory, a function to visualize the toy graph\n",
    "from utils import load_les_miserables, plot_les_miserables"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8c8a288",
   "metadata": {},
   "source": [
    "It is a nice way to keep code orderly and reuse it later. For more info on this, see [this Tutorial](https://www.geeksforgeeks.org/python-modules/).\n",
    "\n",
    "You can now use these functions like any other function coming from a library like numpy. You do not need to use a prefix like `np.your_function()` though, because we imported the functions directly via the `from ... import ...` statement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "947eebe6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# This function returns\n",
    "# n: number of characters\n",
    "# names: of the characters\n",
    "# A: (n,n) matrix where A[i,j] counts common appearences\n",
    "n, names, A = load_les_miserables()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66a18c25",
   "metadata": {},
   "source": [
    "- Given the indices associated to character 0 and character 17, find their names and, check whether these two co-occur in the story. Compute the number of appearances each one of them has."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "1c4e845d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Napoleon and Tholomyes appear together: False.'"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# by putting the f in front of a string, you can evaluate expressions\n",
    "# directly in a string\n",
    "# bool(.) converts 1 to True and 0 to False\n",
    "f\"{names[0]} and {names[17]} appear together: {bool(A[0,14])}.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "a3b42b90",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Napoleon appears 1 times.'"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f\"{names[0]} appears {A[:,0].sum()} times.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "11d15cdf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Tholomyes appears 9 times.'"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f\"{names[17]} appears {A[:,17].sum()} times.\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f6e2899",
   "metadata": {},
   "source": [
    "To get a feeling for how the matrix looks like, we want to plot it using `plt.imshow` from the [matplotlib library](https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.imshow.html), probably the most basic and important library for plotting in python.\n",
    "By sending commands to the `plt` module, one procedurally builds a plot.\n",
    "- Use `plt.imshow` to display the matrix $A$ and title the plot 'The adjacency matrix A'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "5e02f919",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Text(0.5, 1.0, 'The adjacency matrix A')"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 17036 characters]",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# using the matplotlib library \n",
    "# visualize the 2D matrix A\n",
    "# set a title\n",
    "# show the plot\n",
    "plt.imshow(A)\n",
    "plt.title('The adjacency matrix A')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5aa47f9e",
   "metadata": {},
   "source": [
    "- What property can you deduce about the network from the image ? Does this make sense given the considered data ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d0082e3",
   "metadata": {},
   "source": [
    "> The graph is not directed (it is symmetric): If node A points to node B, then also B points to A. This means that every edge is bidrectional. We will come to directed examples later when we look at internet data where a link points from a site A to a site B, but not necessarily the other way around. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c780d27",
   "metadata": {},
   "source": [
    "## 1.b Creating the page rank matrix $G$\n",
    "\n",
    "We now want to find the PageRank $w_i$ of every member $i$ of the Les Miserables cast. How can we interpret such a value? \n",
    "Essentially, $w_i$ will be high for members that have many appearences with different cast members, i.e. that are 'central' in the cast graph.\n",
    "\n",
    "To find out who these members are, let's go on to define the matrix used in the algorithm using the notation from the lecture:\n",
    "\n",
    "Recall from the lecture, the definition of the pagerank matrix $G$.\n",
    "$$\n",
    "G = (1-\\epsilon)S+\\epsilon \\frac{1}{n}\\\\\n",
    "$$\n",
    "with\n",
    "$$\n",
    "S_{ij} = A_{ij}/d_j\\quad \\mathrm{if } \\,\\,\\,d_j > 0\\ ,\\quad\n",
    "S_{ij} = 1/n\\quad \\mathrm{if }\\,\\,\\,d_j = 0\n",
    "$$\n",
    "and $A$ is the adjacency matrix of the underlying graph, so $A_{ij}=1$ if there is an link from $j$ to $i$ and it is zero otherwise.\n",
    "Since every node in our current example is connected, we can brush over the case $d_j=0$ for now."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "c74ed94e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# set the dampening parameter\n",
    "eps = 0.05"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "182e5aea",
   "metadata": {},
   "source": [
    "Compute the outgoing edges that a node $i$ has by summing over the column $d_j = \\sum_i A_{ij}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "id": "2053d41b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculate the vector degrees of size (n) which contains d_j\n",
    "degrees = A.sum(axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "50d4a2a1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Woman1 has [2] pair appearences, Javert has [17] pair appearences'"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# the degree of node 'Woman1' and 'Javert'\n",
    "# here, using the double == gives a boolean mask, which subsequently only selects \n",
    "# entries that are true\n",
    "neigh_wmn = degrees[names=='Woman1']\n",
    "neigh_javert =  degrees[names=='Javert']\n",
    "f'Woman1 has {neigh_wmn} pair appearences, Javert has {neigh_javert} pair appearences'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1c836c3",
   "metadata": {},
   "source": [
    "- Now we want to compute the matrix $S$. For this, we use [broadcasting](https://numpy.org/doc/stable/user/basics.broadcasting.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "7cb93c31",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute the matrix S\n",
    "S = A / degrees # s_ij = a_ij / d_j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "71e5efae",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 1, 0, ..., 0, 0, 0],\n",
       "       [1, 0, 1, ..., 0, 0, 0],\n",
       "       [0, 1, 0, ..., 0, 0, 0],\n",
       "       ...,\n",
       "       [0, 0, 0, ..., 0, 0, 0],\n",
       "       [0, 0, 0, ..., 0, 0, 0],\n",
       "       [0, 0, 0, ..., 0, 0, 0]])"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "bebe20e1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 1, 10,  3,  3,  1,  1,  1,  1,  1,  1, 36,  1,  2,  1,  1,  1,  7,\n",
       "        9,  7,  7,  7,  7,  7, 15, 11, 16, 11, 17,  4,  8,  2,  4,  1,  2,\n",
       "        6,  6,  6,  6,  6,  3,  1, 11,  3,  3,  2,  1,  2,  1, 22,  7,  2,\n",
       "        7,  2,  1,  4, 19,  2, 11, 15, 11,  9, 11, 13, 12, 13, 12, 10,  1,\n",
       "       10, 10, 10,  9,  3,  2,  2,  7,  7])"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "degrees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "4092b123",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.        , 0.1       , 0.        , ..., 0.        , 0.        ,\n",
       "        0.        ],\n",
       "       [1.        , 0.        , 0.33333333, ..., 0.        , 0.        ,\n",
       "        0.        ],\n",
       "       [0.        , 0.1       , 0.        , ..., 0.        , 0.        ,\n",
       "        0.        ],\n",
       "       ...,\n",
       "       [0.        , 0.        , 0.        , ..., 0.        , 0.        ,\n",
       "        0.        ],\n",
       "       [0.        , 0.        , 0.        , ..., 0.        , 0.        ,\n",
       "        0.        ],\n",
       "       [0.        , 0.        , 0.        , ..., 0.        , 0.        ,\n",
       "        0.        ]])"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A/degrees"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9124a717",
   "metadata": {},
   "source": [
    "- Propose a piece of code to check that your $S$ matrix makes sense."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "7672f50f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# check e.g. that column 23 sums to 1\n",
    "S[:,23].sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "a04f34f2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute G\n",
    "G = (1-eps)*S+eps/n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a8240f4",
   "metadata": {},
   "source": [
    "## 1.c Running the power iteration\n",
    "\n",
    "We now have all the ingredients to run PageRank. We initialize the weight vector $w$ uniformly and then update it iteratively via $w = Gw$ until the changes per iteration are not too big (the iterations converge).\n",
    "\n",
    "We measure this change at every iteration, track it and plot the convergence."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2e236c1",
   "metadata": {},
   "source": [
    "- Initilize $w$ uniformly with $1/n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "bbec752d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a vector w of length n with weight uniformly distributed\n",
    "w = np.ones(n)/n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd2c9c8a",
   "metadata": {},
   "source": [
    "- Run the pagerank iteratively until w changes less than 1e-10 between two iterations. Keep track of the distance between the updated and old $w$ in a list, so that we can visualize it after."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "c7fa514e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# track distance and convergence\n",
    "dist = 1e300\n",
    "dists = []\n",
    "# a while loop is run, until the condition at the beginning is False\n",
    "while dist > 1e-10:\n",
    "    w = G @ w\n",
    "    dist = np.linalg.norm(w-G @ w)\n",
    "    dists.append(dist)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9adc3e65",
   "metadata": {},
   "source": [
    "- Plot the list of distances using `plt.plot` and label the x (time) and y (distance) axis accordingly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "e53e74bc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 28332 characters]",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# we plot the list of the distance values as a function of time\n",
    "plt.plot(dists)\n",
    "plt.axhline(np.linalg.norm(w - G @ w),color='red',linestyle='dotted')\n",
    "plt.xlabel('t')\n",
    "plt.ylabel('||w-Gw||')\n",
    "plt.title('Convergence of Power Iteration');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e177054",
   "metadata": {},
   "source": [
    "## 1.d Comparison against the `np.linalg` eigendecomposition \n",
    "\n",
    "For this we use numpy `linalg` module to compute the eigenvalues and vectors for a matrix. Since the poweriteration is computing $w$, such that $w=Gw$, we need to check for the eigenvalue $\\lambda=1$.\n",
    "\n",
    "However, $G$ may not be symmetric, so some eigenvalues may be complex. Therefore, the eigenvalue $1$ we are be looking for is the largest in complex norm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "53b0b6d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# use numpys code to do the eigenvalue decomp\n",
    "eigenvalues, eigenvectors = np.linalg.eig(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "708ee82d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((0.8064824421368109+0j),\n",
       " array([-0.03142441+0.j, -0.26677091+0.j, -0.02806124+0.j, -0.02806124+0.j,\n",
       "        -0.03142441+0.j, -0.03142441+0.j, -0.03142441+0.j, -0.03142441+0.j,\n",
       "        -0.03142441+0.j, -0.03142441+0.j,  0.43951833+0.j,  0.01438147+0.j,\n",
       "         0.01161503+0.j,  0.01438147+0.j,  0.01438147+0.j,  0.01438147+0.j,\n",
       "        -0.11162947+0.j, -0.11413478+0.j, -0.11162947+0.j, -0.11162947+0.j,\n",
       "        -0.11162947+0.j, -0.11162947+0.j, -0.11162947+0.j, -0.03522757+0.j,\n",
       "         0.06683161+0.j,  0.06816096+0.j,  0.05691123+0.j,  0.14409749+0.j,\n",
       "         0.06845822+0.j,  0.26732297+0.j,  0.00434873+0.j,  0.02416106+0.j,\n",
       "         0.01438147+0.j,  0.02436619+0.j,  0.25032184+0.j,  0.25032184+0.j,\n",
       "         0.25032184+0.j,  0.25032184+0.j,  0.25032184+0.j,  0.00524097+0.j,\n",
       "         0.00501816+0.j,  0.01766551+0.j,  0.01406669+0.j,  0.03046064+0.j,\n",
       "         0.03454164+0.j,  0.02016018+0.j, -0.02258656+0.j, -0.01330297+0.j,\n",
       "        -0.12917097+0.j,  0.03430656+0.j,  0.01292987+0.j,  0.03797686+0.j,\n",
       "         0.00844859+0.j,  0.00639072+0.j,  0.01350502+0.j, -0.07666778+0.j,\n",
       "         0.00101986+0.j, -0.11292813+0.j, -0.11604606+0.j, -0.12804889+0.j,\n",
       "        -0.11045776+0.j, -0.12804889+0.j, -0.14106048+0.j, -0.14181318+0.j,\n",
       "        -0.12960844+0.j, -0.14181318+0.j, -0.12425139+0.j, -0.01209311+0.j,\n",
       "         0.05467188+0.j,  0.05467188+0.j,  0.05270651+0.j,  0.04771064+0.j,\n",
       "         0.03046064+0.j, -0.01682695+0.j, -0.01682695+0.j,  0.02532699+0.j,\n",
       "        -0.08303306+0.j]))"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# the complex values eigenvalue and eigenvector at position 3\n",
    "# the eigenvectors are organized in a matrix, where the ith column belongs to the ith eigenvalue\n",
    "eigenvalues[3], eigenvectors[:,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "id": "10de5c6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# We sort the eigenvalues by their norm, using `np.absolute`\n",
    "sorted_idx = np.argsort(np.absolute(eigenvalues))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "id": "f6294465",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([71, 74, 75, 61, 76, 73, 72, 70, 69, 68, 67, 66, 65, 41, 42, 44, 47,\n",
       "       32, 50, 54, 51, 31, 53, 30, 49, 52, 48, 46, 45, 29, 57, 64, 63, 56,\n",
       "       58, 62, 59, 55, 60, 43, 40, 23, 39, 38, 37, 21, 20, 36, 34, 19, 33,\n",
       "       18, 35, 17, 28, 27, 26, 15, 25, 22, 12, 11, 24, 16, 10, 14, 13,  8,\n",
       "        7,  6,  9,  5,  3,  4,  2,  1,  0], dtype=int64)"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted_idx"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6322e7af",
   "metadata": {},
   "source": [
    "- Check what `np.argsort` does, and find the index from `sorted_idx` of the largest element in `eigenvalues`. Then, using this index, select the corresponding eigenvector and norm it to be a probability distribution. Then compare it to the pagerank values $w$. Do they match?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "a7e0dee8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Take the index of the largest element, now positioned a the end of the array, due to ascending order.\n",
    "idx = sorted_idx[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "id": "0740a673",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.02533913+0.j, 0.22144899+0.j, 0.0561884 +0.j, 0.0561884 +0.j,\n",
       "       0.02533913+0.j, 0.02533913+0.j, 0.02533913+0.j, 0.02533913+0.j,\n",
       "       0.02533913+0.j, 0.02533913+0.j, 0.49476412+0.j, 0.01735776+0.j,\n",
       "       0.02933894+0.j, 0.01735776+0.j, 0.01735776+0.j, 0.01735776+0.j,\n",
       "       0.08701045+0.j, 0.11069985+0.j, 0.08701045+0.j, 0.08701045+0.j,\n",
       "       0.08701045+0.j, 0.08701045+0.j, 0.08701045+0.j, 0.18917654+0.j,\n",
       "       0.13758021+0.j, 0.19837824+0.j, 0.14128606+0.j, 0.21460062+0.j,\n",
       "       0.0630046 +0.j, 0.10598098+0.j, 0.02941751+0.j, 0.05530464+0.j,\n",
       "       0.01735776+0.j, 0.02935014+0.j, 0.08166272+0.j, 0.08166272+0.j,\n",
       "       0.08166272+0.j, 0.08166272+0.j, 0.08166272+0.j, 0.0421402 +0.j,\n",
       "       0.01608019+0.j, 0.13131463+0.j, 0.03930293+0.j, 0.04155212+0.j,\n",
       "       0.03232135+0.j, 0.01926507+0.j, 0.03590874+0.j, 0.02135813+0.j,\n",
       "       0.26207873+0.j, 0.0943218 +0.j, 0.02898422+0.j, 0.0979516 +0.j,\n",
       "       0.03093931+0.j, 0.01759491+0.j, 0.05396155+0.j, 0.22727686+0.j,\n",
       "       0.02846614+0.j, 0.1276779 +0.j, 0.1706968 +0.j, 0.12343718+0.j,\n",
       "       0.10104159+0.j, 0.12343718+0.j, 0.14561649+0.j, 0.13428592+0.j,\n",
       "       0.14721514+0.j, 0.13428592+0.j, 0.11189618+0.j, 0.01532821+0.j,\n",
       "       0.12195748+0.j, 0.12195748+0.j, 0.12149516+0.j, 0.11004559+0.j,\n",
       "       0.04155212+0.j, 0.02974956+0.j, 0.02974956+0.j, 0.08506792+0.j,\n",
       "       0.07972062+0.j])"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# select the respective eigenvector from the matrix\n",
    "eigv = eigenvectors[:,idx]\n",
    "eigv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "faaf6ef7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# norm the eigenvector to be a probability distribution, so that we can directly compare to pagerank\n",
    "eigv = eigv/eigv.sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "id": "c9202366",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.4273947287048745e-09"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# compare the eigenv from the eigendecomposition with the the pagerank result\n",
    "np.abs(eigv-w).sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0fd742e",
   "metadata": {},
   "source": [
    "## 1.e Interpreting the results\n",
    "\n",
    "We are looking for central characters whose interactions are central. Are these the characters that also are the main characters in the story, such as percieved by respected scholars such as ChatGPT? \n",
    "\n",
    "> Can you give me a list of the ten main characters in Les Miserables, in the form of a python list?\n",
    "\n",
    "\n",
    "\n",
    "```\n",
    "main_characters = [\n",
    "    \"Valjean\",\n",
    "    \"Javert\",\n",
    "    \"Cosette\",\n",
    "    \"Marius\",\n",
    "    \"MmeThenardier\",\n",
    "    \"Thenardier\",\n",
    "    \"Fantine\",\n",
    "    \"Gavroche\",\n",
    "    \"Enjolras\",\n",
    "    \"Myriel\"\n",
    "]\n",
    "```\n",
    "\n",
    "- To compare to those we need to extract the names of the nodes with the highest 10 page rank weights."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "id": "ba6b5349",
   "metadata": {},
   "outputs": [],
   "source": [
    "# return a sorted index by page rank weight (ascending order)\n",
    "sorted_importance = np.argsort(w) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "id": "41e6c901",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Courfeyrac',\n",
       " 'Bossuet',\n",
       " 'Enjolras',\n",
       " 'Fantine',\n",
       " 'Thenardier',\n",
       " 'Javert',\n",
       " 'Myriel',\n",
       " 'Marius',\n",
       " 'Gavroche',\n",
       " 'Valjean']"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# the ten most central characters are those, with the highest page rank\n",
    "ten_most_central_characters = names[sorted_importance][-10:]\n",
    "list(ten_most_central_characters)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2e7cf11",
   "metadata": {},
   "source": [
    "... the central characters seem also be the main ones, they are interacting with one another a lot!\n",
    "\n",
    "We can also look at them in the graph view:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "id": "07ef4ecc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 192988 characters]",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_les_miserables(highlight_names=ten_most_central_characters,layout='spring')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b09230d",
   "metadata": {},
   "source": [
    "- It looks like the nodes with a high page rank value have also high degree. Check this by plotting the weight $w$ and the degree $d$ against one another on a scatterplot using `plt.scatter`. Don't forget to label the axes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "id": "0a3ff158",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 32276 characters]",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# also, we plot the distribution of the page rank values w\n",
    "plt.scatter(w,degrees)\n",
    "x = np.linspace(0,w.max(),30)\n",
    "y = np.linspace(0,degrees.max(),30)\n",
    "plt.plot(x,y,c='grey',linestyle='dashed')\n",
    "plt.xlabel('w')\n",
    "plt.ylabel('degree')\n",
    "plt.title('Correlation between $w$ and $d$');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "40503745",
   "metadata": {},
   "source": [
    "# Exercise 2: The simple wikipedia link database"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b37312f",
   "metadata": {},
   "source": [
    "We now want to use PageRank on the [DBpedia link dataset](https://databus.dbpedia.org/dbpedia/generic/wikilinks/). We use the collection of all links between wikipedia pages that appear in the article collection of [simple english wikipedia](https://simple.wikipedia.org/wiki/Main_Page), which aims to explain things in understandable easy terms. It has ~ 1.3 Mio articles and categories, which is big - but not too big to run on a Laptop.\n",
    "\n",
    "This will help us understand what the most central (or general) articles in this wikipedia database are.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "id": "33efdccd",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import load_simple_wikipedia\n",
    "# load the dbpedia adjacency matrix and the names of the articles\n",
    "names, A = load_simple_wikipedia()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "id": "f9e924bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Compressed Sparse Row sparse matrix of dtype 'int64'\n",
       "\twith 5343446 stored elements and shape (1349256, 1349256)>"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f863718",
   "metadata": {},
   "source": [
    "- How many entities does the simple english wikipedia have exactly?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "id": "757a4458",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1349256"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = A.shape[0]\n",
    "n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9fadcda",
   "metadata": {},
   "source": [
    "## 2.a Data Inspection: Does the loaded data 'make sense'?\n",
    "\n",
    "Page # 13997 is [Electricity](https://simple.wikipedia.org/w/index.php?title=Electricity&oldid=8522069). We can use the list of names to verify this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "id": "eb65ed47",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Electricity'"
      ]
     },
     "execution_count": 129,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "names[13997]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5feaf6d",
   "metadata": {},
   "source": [
    "The format of the array is now in [sparse row format](https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csr_array.html#scipy.sparse.csr_array), because this makes saving and computing matrix products much cheaper. You can use `type` to check the type of a variable (it is similar to a C++ class)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "id": "4b548ace",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "scipy.sparse._csr.csr_matrix"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "690a2565",
   "metadata": {},
   "source": [
    "Let's look at the pages 'Electrictiy' is linking to.\n",
    "\n",
    "The interface of the sparse matrix is slightly different than `np.array`. When we select a column, we first need to convert it back to a numpy array to use it like before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "id": "3ed847e1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "numpy.ndarray"
      ]
     },
     "execution_count": 131,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(A[:,13997].toarray())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a339e798",
   "metadata": {},
   "source": [
    "But then it has one extra dimension."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "id": "133f3dca",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1349256, 1)"
      ]
     },
     "execution_count": 132,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A[:,13997].toarray().shape"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f88d4316",
   "metadata": {},
   "source": [
    "So we squish it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "id": "e48ecdd8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1349256,)"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A[:,13997].toarray().flatten().shape"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83692d1e",
   "metadata": {},
   "source": [
    "And then we can use it to find the names of the pages that are linked from electricity (are not 0)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "id": "b35915f8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(['Electric_motor', 'Electrical_engineering', 'Universe', 'Metal',\n",
       "       'Battery', 'Nature', 'Electronics', 'Lightning', 'Atom',\n",
       "       'Molecule', 'Benjamin_Franklin', 'Water', 'Engineering',\n",
       "       'Estimate', 'Electric_power', 'Turbine', 'Steam_engine', 'Proton',\n",
       "       'Category:Basic_English_850_words', 'Electron', 'Hydropower',\n",
       "       'Renewable_energy', 'Insulator_(electricity)', 'Watt', 'Ohm',\n",
       "       'Copper', 'Volt', 'Energy', 'Magnet', 'Static_electricity',\n",
       "       'Electrons', 'Category:Electricity', 'Theophrastus', 'Movement',\n",
       "       'Magnetic_field', 'Steam', 'Electric_current', 'Salt',\n",
       "       'Non-renewable_resource', 'Wind_power', 'Thales',\n",
       "       'Electric_charge', 'Machine', 'Ammeter', 'Light_bulb', 'Wire',\n",
       "       'Power_line', 'Thunderstorm', 'Heating', 'Electrical_circuit',\n",
       "       'Electric_field', 'Joule', 'Michael_Faraday',\n",
       "       'Electromagnetic_induction', 'Neutral', 'Electrical_energy',\n",
       "       'Particles', 'Electrical_conductor', 'Joules', 'Power_station',\n",
       "       'Transmission_medium', 'Telephones', 'Photovoltaic', 'Electrician',\n",
       "       'Electrical_resistance', 'Chemicals', 'Kilowatt', 'Spark',\n",
       "       'Coulomb', 'Ampere', 'Voltmeter', 'Generator', 'Insulator',\n",
       "       'Washing_machine', 'Electric_voltage',\n",
       "       'File:Electric_wiring_near_Helsinki.JPG', 'Appliance', \"Ohm's_law\",\n",
       "       'Electric_lamp',\n",
       "       'File:Edison_Central_Station_Dynamos_and_Engine.jpg',\n",
       "       'Volt-ampere', 'File:Ampe_ke.gif'], dtype='<U266')"
      ]
     },
     "execution_count": 134,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "names[A[:,13997].toarray().flatten() != 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0386bd30",
   "metadata": {},
   "source": [
    "- Can we similarly find the pages linking to 'Electricity'? How do the list of the terms linking to and from the main page differ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "id": "59b5ae25",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(['South_Region,_Brazil', 'Color_blindness', 'Slum',\n",
       "       'Electrical_engineering', 'Human', 'City', 'Silicon',\n",
       "       'Electromagnetism', 'Morwell,_Victoria', 'Engine', 'Earth',\n",
       "       'Cable', 'October_9', 'Metal', 'Battery', 'Airbus_A330',\n",
       "       'String_theory', 'Electronics', 'Judaism', '2012', 'Natural_gas',\n",
       "       'Computer', 'Siméon_Denis_Poisson', 'Solid', 'Book',\n",
       "       'List_of_tallest_structures_in_the_world', 'Brass', 'Chris_Huhne',\n",
       "       'Lightning', 'Ground', 'June_11', 'Virginia_Beach,_Virginia',\n",
       "       'Drill', '2013', 'Lake', 'Atom', 'Physics', 'November_8',\n",
       "       'Dipole_antenna', 'Electricity_meter', 'Fire_extinguisher',\n",
       "       'Cryogenics', 'ARM_architecture', 'Diode', 'June_16',\n",
       "       'List_of_phobias', 'Demolition', 'Aluminium', 'September_20',\n",
       "       'Plasma_(physics)', 'Freelan_Oscar_Stanley', 'Diesel_locomotive',\n",
       "       'Al_Jazeera', 'Nashville,_Tennessee', 'Lawrence,_Kansas',\n",
       "       'Benjamin_Franklin', 'Electric_multiple_unit', '1820',\n",
       "       'Automobile', 'Steam_turbine', 'Neoprene', 'Polarity',\n",
       "       'Data_storage_device', 'Group_11_element', 'Iodine_trichloride',\n",
       "       'Solar_panel', 'Depression_(mental_illness)', 'June_22',\n",
       "       'Year_2000_problem', 'Laser', 'Engineer', 'December_20',\n",
       "       'Treehouse', 'List_of_words_about_computers', 'Ionizing_radiation',\n",
       "       'Semiconductor', 'Calculus', 'Engineering', 'Hydrogel',\n",
       "       'Cloud_computing', 'Electric_locomotive', 'Burrendong_Dam',\n",
       "       'Hydroelectricity', 'Platypus', 'Photovoltaics', 'Electromagnet',\n",
       "       'Magnetism', 'Windmill', 'Three_Gorges_Dam', 'March_22',\n",
       "       'Nuclear_reactor', 'Steam_engine', 'Aurora', 'Ventilator', 'Heart',\n",
       "       'Pikachu', 'Prefix', 'Billy_Bob_Thornton',\n",
       "       'Cognitive_neuropsychology', 'Electric_vehicle',\n",
       "       'Parveen_Talukder', 'Standard_Model', 'Natural_resource',\n",
       "       'List_of_accidents_and_incidents_involving_commercial_aircraft_1990_–_2021',\n",
       "       'Public_transport', 'Novachord', 'James_Prescott_Joule',\n",
       "       'November_5', 'Sony', 'Electron', 'Pablo_Escobar', 'October_22',\n",
       "       'Metre_Convention', 'Direct_current', 'Lesotho', 'Graphite',\n",
       "       'Analog_signal', 'Ironing', 'Chassis', 'Renewable_energy',\n",
       "       'Geophysics', 'RCA_connector', 'Gabriel_Lippmann',\n",
       "       'Read-only_memory', 'Shark', 'Fluorescent_lamp',\n",
       "       'Capital_punishment_in_the_United_States',\n",
       "       'Fossil-fuel_power_station', 'Mercury_(element)',\n",
       "       'Load_following_power_plant', 'Ion', 'Allspice', 'Pedal',\n",
       "       'Creutzfeldt–Jakob_disease', 'Apartment', 'Rubber',\n",
       "       'Tropical_Storm_Delta_(2005)', \"Laplace's_equation\", 'Idaho',\n",
       "       'Vehicle', 'Power_Purchasing_Agreement', 'Energy', 'Lead',\n",
       "       'Cooking', 'ʻIolani_Palace', 'Neon',\n",
       "       'International_System_of_Units', 'Cryptozoology', 'Welding',\n",
       "       'Electric_Light_Orchestra', 'London_Underground',\n",
       "       'Alternating_current', 'Coal', 'Muscle', 'Who_Shot_Mr._Burns%3F',\n",
       "       'Public_utility', 'Pipe_organ', 'Pierre_Curie',\n",
       "       'Amazon_rainforest', 'Electricity_generation',\n",
       "       'Thiruvananthapuram', 'Computer_monitor', 'Silver',\n",
       "       'Walter_Rudolf_Hess', 'Sunlight', 'Didcot', 'Internal_energy',\n",
       "       'Shabbat', 'Cermet', 'Conduction', 'Undersea_cable', 'Coal_mining',\n",
       "       'Erection', 'Infrared', 'Salvador_Allende', 'Physical_change',\n",
       "       'Rapid_transit', 'Merit_badge', 'Moscow_Metro', 'Weapon',\n",
       "       'Solar_cell', 'Filter', 'Surgut', '1909_Cherry_Mine_disaster',\n",
       "       'Transduction_(physiology)', 'Lake_Sevan', 'Candle',\n",
       "       'History_of_hearing_aids', 'Inventor', 'RAID', 'Shanty_town',\n",
       "       'Yaque_del_Norte_River', 'Fuel', 'Locomotive',\n",
       "       'Peterhouse,_Cambridge', 'Bellows', 'Lithium', 'Reservoir',\n",
       "       '2011_Christchurch_earthquake', 'Salt', 'Selenium',\n",
       "       'Unit_of_measurement', 'Physical_constant', 'Aswan_Low_Dam',\n",
       "       'Hughes_Medal', 'Metallurgy', 'Luminescence', 'Absurd_(band)',\n",
       "       'Vladimir,_Russia', 'Westinghouse_Electric_Corporation',\n",
       "       'Republic_of_Lakotah', 'Electric_power_distribution',\n",
       "       'Railway_electrification_system', 'Wind_power',\n",
       "       'Fermionic_condensate', 'Lightning_rod', 'States_of_matter',\n",
       "       'Clock', 'Strong_interaction', 'Covalent_bond', 'Watermill',\n",
       "       'Nuclear_fusion', 'Experiment', 'Solar_energy', 'Nuclear_power',\n",
       "       'Death_row', 'Hôtel_Ritz_Paris', 'Electrical_generator',\n",
       "       'Zanzibar', 'Switch', 'Giant_magnetoresistance',\n",
       "       'Institute_of_Electrical_and_Electronics_Engineers',\n",
       "       'History_of_Ireland', 'Electrical',\n",
       "       \"Faraday's_laws_of_electrolysis\", 'Circuit_breaker',\n",
       "       'Electric_charge', 'Tunnel', 'Death_penalty',\n",
       "       'Minimum_spanning_tree', 'Light_bulb', \"Ship's_cat\",\n",
       "       'Electrophysiology', 'Cash_register', 'Carom_billiards',\n",
       "       'Ghost_light', 'Hydrogen_economy', 'Fossil_fuel',\n",
       "       'André-Marie_Ampère', 'Primary_cell', 'Bradycardia', 'Wire',\n",
       "       'Power_line', 'Optical_fiber', 'Superconductor',\n",
       "       'Alexander_Graham_Bell', 'Destroy_All_Humans!_Path_of_the_Furon',\n",
       "       'Organic_light-emitting_diode', 'Standardization',\n",
       "       'Parkes,_New_South_Wales', 'Wart', 'Power_factor', 'Tungsten',\n",
       "       'Thunderstorm', 'Woodworking', 'Forestle', 'Bismuth', 'Oh_Se-hoon',\n",
       "       'Capital_Development_Authority_(Islamabad)', 'MOSFET',\n",
       "       'Mill_(grinding)', 'Electrical_conduit', 'Hydrosphere', 'Shack',\n",
       "       'Dehydration', 'Nundle,_New_South_Wales', 'W',\n",
       "       'Gameplay_of_Pokémon', 'Band_gap', 'William_Thomson',\n",
       "       'Electrocution', 'Environment_of_Florida', 'Amish', 'La_Scala',\n",
       "       'Brain_death', 'Ventricular_fibrillation', 'Commodity',\n",
       "       'Typewriter', 'Cowra', 'Slide_rule', 'Hammond_organ',\n",
       "       'Synthesizer', 'Transperth', 'Michael_Faraday', 'Potato_gun',\n",
       "       'Burn', 'Luigi_Galvani', 'Computer_data_storage', 'Nanotechnology',\n",
       "       'Pulilan', 'Cogeneration', 'Microphone', 'Cruachan_Power_Station',\n",
       "       'Electric_power_transmission', 'Chow_Yun-Fat', 'Electrical_outlet',\n",
       "       'Electrical_energy', 'Spyro_(character)', 'Yeast',\n",
       "       'Doping_(semiconductor)', 'Itaipu_Dam', 'Power_over_Ethernet',\n",
       "       'Moravia_(canton)', 'Hurricane_Lorenzo_(2007)',\n",
       "       'Renewable_energy_commercialisation_in_Australia', 'Pantograph',\n",
       "       'Wireless', 'Overclocking', 'Electrical_conductor', 'Opinion',\n",
       "       'Fuel_cell', 'Nuclear_power_plant', 'Manhole', 'Erasmus_Darwin',\n",
       "       'Electric', 'Woodford_tube_station', 'Human_Connectome_Project',\n",
       "       'Power_station', 'PS10_solar_power_plant',\n",
       "       'Programmable_logic_controller', 'Boron', 'Evergy', 'Ed_Gein',\n",
       "       'Ion_thruster', 'Transmission_medium',\n",
       "       'Washington_Dulles_International_Airport',\n",
       "       'Double-layer_capacitance', 'Monte_Alto_solar_power_plant',\n",
       "       'Molar_conductivity', 'Madam_C._J._Walker', 'Vibrator_(sensual)',\n",
       "       'Water_heating', 'Trolley',\n",
       "       'St._Croix_River_(Wisconsin–Minnesota)',\n",
       "       '2013-14_Atlantic_winter_storms_in_Europe', 'Natural_gas_vehicle',\n",
       "       'Mobile_device', 'Rechargeable_battery', 'Economic_liberalization',\n",
       "       'Quantum_electrodynamics', '1999_East_Timorese_crisis',\n",
       "       'Geothermal_energy', 'High-voltage_direct_current',\n",
       "       'Glen_Canyon_Dam', 'Copper_wire_and_cable', 'SimCity_DS',\n",
       "       'Analog_television', 'Toronto_subway', 'Eugenio_Beltrami', 'Match',\n",
       "       'Thermocouple', 'Natural_monopoly', 'Crystal_structure',\n",
       "       'Black_Hills_Corporation', 'Radiant_heating', 'Faraday_cage',\n",
       "       'Chemical_cell', 'Third_rail', 'Whaling', 'Penthouse', 'Desiro',\n",
       "       'Frozen_dinner', 'Biltmore_Estate', 'Electrical_cell',\n",
       "       'Brihanmumbai_Electric_Supply_and_Transport',\n",
       "       'Magnetic_field_line', 'Composite_Compound_4', 'Copper_(color)',\n",
       "       'Lineman_(technician)', 'Pavement_light', 'Peaking_power_plant',\n",
       "       'Point_Hicks', 'Dipole', 'Electrical_conductivity', 'Gallium',\n",
       "       'Floodlight', 'SimCity', 'Electrical_grid', 'Disconnecting_switch',\n",
       "       'Traction_motor', 'Year_100_problem', 'Nuclear_reaction',\n",
       "       'Logic_gate', 'Electrochemistry', 'Benign_neonatal_seizures',\n",
       "       'Saint_Lawrence_Seaway', 'Nuclear_proliferation', 'Electrode',\n",
       "       'Batch_processing', 'Gas_discharge_lamp', 'Online_and_offline',\n",
       "       'Classical_physics', 'Trolleybus', 'Trolley_pole',\n",
       "       'Liquid_crystal_display', 'Diesel_generator', 'Fire_triangle',\n",
       "       'Tellurium(IV)_iodide', 'Electric_chair', 'Utility_pole',\n",
       "       'Gas-fired_power_plant', 'Distributed_generation', 'Fire_ant',\n",
       "       'Tidal_stream_power', 'Solar_power_plant', 'Solar_thermal_energy',\n",
       "       'Availability_factor', 'Allotropes_of_carbon',\n",
       "       'Büsingen_am_Hochrhein', 'Railgun', 'Pot-in-pot_refrigerator',\n",
       "       'Knob_and_tube_wiring', 'Taser', 'British_Rail_Class_800',\n",
       "       'Clothes_iron', 'Navier–Stokes_equations', 'Blanket',\n",
       "       'Status_epilepticus', 'Serpa_solar_power_plant', 'Heart_block',\n",
       "       'China_Southern_Power_Grid', 'Luník_IX', 'Cuckoo_clock',\n",
       "       'Electronic_system', \"Archimedes'_screw\", 'Arcology',\n",
       "       'Incineration', 'State_Grid_Corporation_of_China', 'Wendy_Carlos',\n",
       "       '2014_North_American_polar_vortex', 'Base_load_power_plant',\n",
       "       'Félix_Soto_Toro', 'Hans_Christian_Ørsted', 'Taiwan_Power_Company',\n",
       "       '1752', 'Trams_in_Biel', 'Substitute_good', 'Patience_(operetta)',\n",
       "       'Hot_stick', 'Utility_frequency', 'Cadmium_telluride', 'Steampunk',\n",
       "       'Energoatom', 'Electric_arc', 'Creos_Luxembourg_S.A.',\n",
       "       'Electrical_substation', 'V', 'Lamp', 'Complex_plane',\n",
       "       'Lake_Berryessa', 'Earthship',\n",
       "       'Solar_power_plants_in_the_Mojave_Desert', 'Electrical_telegraph',\n",
       "       'Lighter', 'Distribution_board', 'Motor–generator',\n",
       "       'Sphygmomanometer', 'Doorbell', 'Lamp_(electrical_component)',\n",
       "       'Fryazino', 'Waveform', 'Electromagnetic_Pulse',\n",
       "       'Electric_bicycle', 'Oil_lamp', 'Nissan_Leaf',\n",
       "       'Charles-Augustin_de_Coulomb', 'Electric_match', 'Smart_grid',\n",
       "       'Fusion_power', 'Appliance', 'Bayville,_New_York', 'Data_center',\n",
       "       'Water_organ', 'Capacitance', 'Electroencephalography',\n",
       "       'Power_line_communication', 'Mill_(currency)',\n",
       "       'Electric_switchboard', 'Lead(II)_bromide', 'Electrology',\n",
       "       'Radioisotope_heater_unit', 'Buckypaper', 'Shocked',\n",
       "       'Parabolic_trough', 'Independent_Power_Producer', 'Eklutna_Lake'],\n",
       "      dtype='<U266')"
      ]
     },
     "execution_count": 135,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "names[A[13997,:].toarray().flatten() != 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6c6b1ad",
   "metadata": {},
   "source": [
    "Some extra questions:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae8fefae",
   "metadata": {},
   "source": [
    "- How many entities have no outgoing links?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "id": "631e9cc9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1038300"
      ]
     },
     "execution_count": 136,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A.sum(axis=0)==0).sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfd99f4b",
   "metadata": {},
   "source": [
    "- How many entities have no incoming links?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "id": "c33e27a6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "68083"
      ]
     },
     "execution_count": 137,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A.sum(axis=1)==0).sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b77dae34",
   "metadata": {},
   "source": [
    "## 2.b Implementing Page Rank using sparse matrix multiplication\n",
    "\n",
    "To compute anything for wikipedia, we need to use the sparse matrix format and reexpress our PageRank matrix $G$ in an efficient way. Then you can easily process the data on a laptop. Recall that a sparse matrix has only few nonzero values. \n",
    "- We can check the percentage of nonzerovalues of A to see that this is indeed just a small fraction of the whole matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "id": "ca8112ed",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.935166275607265e-06"
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A != 0).sum() / n**2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "057391d8",
   "metadata": {},
   "source": [
    "Recall that in exercise 1, we computed the matrix $G$ as follows\n",
    "$$\n",
    "G = (1-\\epsilon)S+\\epsilon \\frac{1}{n}\n",
    "$$\n",
    "$$\n",
    "S_{ij} = A_{ij}/d_j\\quad \\mathrm{if } \\,\\,\\,d_j > 0\\ ,\\quad\n",
    "S_{ij} = 1/n\\quad \\mathrm{if }\\,\\,\\,d_j = 0\n",
    "$$\n",
    "where $A$ is the adjacency matrix of the underlying graph, so $A_{ij}=1$ if there is an edge connection (link) pointing to $i$ from $j$ and it is zero if there is no link.\n",
    "Then we run the following iteration until convergence\n",
    "$$\n",
    "w_{t+1} = G w_{t}\n",
    "$$\n",
    "\n",
    "Now, since we now have ~1,000,000 nodes and a dense matrix would have 1,000,000,000,000 entries, it is not very efficient to use a dense matrix (np.array) directly. This is why we went for the CSR format for $A$ previously (and it was already in that format when we imported it because saving it is also more efficient). "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7abb13c2",
   "metadata": {},
   "source": [
    "However, in the pagerank update the matrices $S$ and $G$ are not as sparse, so it does not make sense to represent them as a sparse matrix. \n",
    "\n",
    "With a bit of thinking though, we realize that we can reformulate the computation of G at every iteration such that we only work with sparse matrices multiplcations and vector products directly.\n",
    "\n",
    "We can still rescale $\\tilde{A}=A_{ij}/d_j$ which maintains the zeros of A.\n",
    "\n",
    "\n",
    "For the iterative update $w=Gw$ instead do the following calculation, where adding scalars is adding it to every entry of the vector\n",
    "$$\n",
    "w_{t+1} = (1-\\epsilon) \\left(\\tilde{A}w_{t} + 1/n \\sum_{j | d_j = 0} w_j \\right) + \\epsilon * 1/n\n",
    "$$\n",
    "Let's construct these things step by step."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "id": "c7c5485b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# First import the datatype, so that we can create a new diagonal matrix\n",
    "# which divides the column j by the outgoing degree d_j\n",
    "from scipy.sparse import csr_matrix\n",
    "\n",
    "# calculate the row sums\n",
    "row_sums = np.array(A.sum(axis=0)).flatten()\n",
    "\n",
    "# prevent divide by zero error\n",
    "row_sums[row_sums == 0.0] = 1.0\n",
    "\n",
    "# create a diagonal matrix with the reciprocals of the row sums\n",
    "division_matrix = csr_matrix((1 / row_sums, (range(len(row_sums)), range(len(row_sums)))), shape=(len(row_sums), len(row_sums)))\n",
    "\n",
    "# apply the matrix \n",
    "A_tilde = A @ division_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8cecb15",
   "metadata": {},
   "source": [
    "- Is the 'Electricity' column in `A_tilde` properly scaled to 1?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "id": "2dc875ab",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0000000000000004"
      ]
     },
     "execution_count": 140,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_tilde[:,13997].sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e55708ca",
   "metadata": {},
   "source": [
    "We want to build a binary mask of the $j | d_j = 0$, so we can use it in the algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "id": "7a22b3ea",
   "metadata": {},
   "outputs": [],
   "source": [
    "zero_row_mask = np.array(A_tilde.sum(axis=1)).flatten() == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8a05765",
   "metadata": {},
   "source": [
    "And now this is an implementation of the sparsity adapted computation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "id": "935ef914",
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a vector w of length n with weight uniformly distributed\n",
    "w = np.ones(n)/n\n",
    "\n",
    "# track distance and convergence\n",
    "dist = np.inf\n",
    "dists = []\n",
    "# a while loop is run, until the condition at the beginning is False\n",
    "while dist > 1e-7:\n",
    "    w_new = (1-eps) * (A_tilde@w + w[zero_row_mask].sum()*1/n) + eps * 1/n\n",
    "    dist = np.linalg.norm(w-w_new)\n",
    "    w = w_new\n",
    "    dists.append(dist)\n",
    "    \n",
    "#... should be done in a few seconds."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec247a3c",
   "metadata": {},
   "source": [
    "## 2.c Interpreting the results\n",
    "- What are the ten most central articles? Use `np.argpartition` instead of `np.argsort`. Why is this the better choice?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "id": "8e5df96a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['India',\n",
       " 'U.S._state',\n",
       " 'United_Kingdom',\n",
       " 'Germany',\n",
       " 'Departments_of_France',\n",
       " 'City',\n",
       " 'Category:Living_people',\n",
       " 'France',\n",
       " 'United_States',\n",
       " 'Communes_of_France']"
      ]
     },
     "execution_count": 143,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ten_most_central_articles = names[np.argpartition(w,-10)][-10:]\n",
    "list(ten_most_central_articles)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d33b783c",
   "metadata": {},
   "source": [
    "## 2.d Bounus Question\n",
    "\n",
    "As an open bonus exercise, we want to know which of the terms 'Physics', 'Chemistry', 'Computer Science', 'Biology', 'Mathematics' is most central in simple english wikipedia. Can you extract the pagerank of these articles and compare their ranks? "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2580cf62-6ee8-4518-81a9-70a50b96cc37",
   "metadata": {},
   "source": [
    "# Exercice 3: Theoretical questions for the exam"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a41d202-07ea-49a9-afb7-7a58c68fbfee",
   "metadata": {},
   "source": [
    "1. Donnez la matrice d’adjacence $A \\in \\{0, 1\\}^{5\\times 5}$ du réseau de sites web donné ci-dessous. $A_{ij} = 1$ si le site web $j$\n",
    "a un lien vers le site web $i$, sinon $A_{ij} = 0$. Les indices $i$ et $j$ indiquent respectivement les lignes et les colonnes de $A$.\n",
    "\n",
    "![Image](data/graphe.png)\n",
    "\n",
    "Solution :\n",
    "\n",
    "$$A = \n",
    "\\begin{pmatrix}\n",
    "0 & 1 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 1 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 1 \\\\\n",
    "1 & 0 & 1 & 1 & 0\n",
    "\\end{pmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b201853-c2b9-4514-8af5-57a0f1fa6329",
   "metadata": {},
   "source": [
    "2. Quel site web a le plus grand degré sortant (out-degree) ? Quel site web a le plus grand degré entrant\n",
    "(in-degree) ?\n",
    "\n",
    "\n",
    "Solution :\n",
    "\n",
    "Plus grand degré sortant : 4 ; entrant : 5."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ac180a7-ce7e-4a38-b099-53ecfb491a40",
   "metadata": {},
   "source": [
    "3. À quelle condition une matrice est-elle stochastique par colonnes (column-stochastic) ?\n",
    "\n",
    "Solution :\n",
    "\n",
    "Tous les éléments doivent être positifs et la somme de chaque colonne vaut 1."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env",
   "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
