bschne · October 11, 2019 10:11
diff --git a/pagerank.ipynb b/pagerank.ipynb
 {
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Some setup...\n",
    "import copy\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PageRank Damping Simulator\n",
    "\n",
    "Let's look at a sample graph of 11 pages linking to eachother.\n",
    "\n",
    "This is what the graph for our pages looks like. Note how Page A does not link to any other pages, and pages B and C only have outgoing links to eachother - this is going to be important in understanding why damping is necessary.\n",
    "\n",
    "![Example page graph](https://upload.wikimedia.org/wikipedia/commons/f/fb/PageRanks-Example.svg)\n",
    "\n",
    "(Don't mind the percentages, we'll calculate our own shortly :-)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are first going to model the pages and links:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Dictionary of all pages & initial pagerank values\n",
    "page_names = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']\n",
    "initial_pr = 1j / len(page_names)\n",
    "\n",
    "pages = {}\n",
    "for p in page_names:\n",
    "    pages[p] = initial_pr\n",
    "\n",
    "# List of all links, structure: (from, to)\n",
    "links = [('G', 'B'),('G', 'E'),('H', 'B'),('H', 'E'),('I', 'B'),('I', 'E'),\n",
    "         ('J', 'E'),('K', 'E'),('B', 'C'),('C', 'B'),('D', 'A'),('D', 'B'),\n",
    "         ('E', 'B'),('E', 'D'),('E', 'F'),('F', 'B'),('F', 'E')]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calculating PageRank\n",
    "\n",
    "Now we have our network set up, let's get started with calculating PageRank. Recall that the formula to update each page's PageRank value in each iteration is given by\n",
    "\n",
    "$$\n",
    "PR(p_i) = (1-d) + d \\cdot \\sum_{p_j \\in M(p_i)} \\frac{PR(p_j)}{L(p_j)}\n",
    "$$\n",
    "\n",
    "where $p$ stands for a single page, $M(p_i)$ is the set of all pages linking to page $p_i$, $L(p_j)$ is the number of outgoing links from page $p_j$ and $d$ is the damping factor.\n",
    "\n",
    "We are going to use a slightly adapted formula here, but don't worry about that - all it does is make sure all PageRank values in the graph sum to 1 at the end. The version we're going to use is\n",
    "\n",
    "$$\n",
    "PR(p_i) = \\frac{1-d}{N} + d \\cdot \\sum_{p_j \\in M(p_i)} \\frac{PR(p_j)}{L(p_j)}\n",
    "$$\n",
    "\n",
    "where $N$ is the total number of pages.\n",
    "\n",
    "Let's define a function that does a given number of iterations of the algorithm on our pages:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "def run_pagerank(pages, links, damping_factor, iterations):\n",
    "    # Build index of outgoing links for all pages\n",
    "    outgoing_links = {}\n",
    "    for p in list(pages.keys()):\n",
    "        outgoing_links[p] = [link[1] for link in links if link[0] == p]\n",
    "\n",
    "    # Build index of incoming links for all pages\n",
    "    incoming_links = {}\n",
    "    for p in list(pages.keys()):\n",
    "        incoming_links[p] = [link[0] for link in links if link[1] == p]\n",
    "    \n",
    "    for i in range(iterations):\n",
    "        for p in list(pages.keys()):\n",
    "            # Sum across all pages that link to p\n",
    "            incoming = 0\n",
    "            for src in incoming_links[p]:\n",
    "                incoming += pages[src] / len(outgoing_links[src])\n",
    "            \n",
    "            pages[p] = (1 - damping_factor) / len(pages.keys()) + damping_factor * incoming\n",
    "            \n",
    "    return pages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### With Damping\n",
    "\n",
    "Traditionally, the damping factor is set to $d = 0.85$. Let's make a copy of our pages, run 25 iterations of the PageRank algorithm, and see what happens."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': 0.02764593471426726,\n",
       " 'B': 0.3242749719364733,\n",
       " 'C': 0.2892700897823659,\n",
       " 'D': 0.03296369665389088,\n",
       " 'E': 0.06821411653244909,\n",
       " 'F': 0.03296369665389088,\n",
       " 'G': 0.01363636363636364,\n",
       " 'H': 0.01363636363636364,\n",
       " 'I': 0.01363636363636364,\n",
       " 'J': 0.01363636363636364,\n",
       " 'K': 0.01363636363636364}"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "with_damping = copy.deepcopy(pages)\n",
    "with_damping = run_pagerank(with_damping, links, 0.85, 25)\n",
    "\n",
    "# TODO: Fix summing issue...\n",
    "with_damping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Without Damping\n",
    "\n",
    "Now let's see what happens when we do the same thing as before, but without damping. To achieve this, we can simply set $d = 1$. We're running this on another copy of our input data for 25 iterations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': 4.604564356550932e-19,\n",
       " 'B': 0.6545454545454544,\n",
       " 'C': 0.6545454545454544,\n",
       " 'D': 1.5348547855169775e-19,\n",
       " 'E': 7.674273927584887e-20,\n",
       " 'F': 2.5580913091949625e-20,\n",
       " 'G': 0.0,\n",
       " 'H': 0.0,\n",
       " 'I': 0.0,\n",
       " 'J': 0.0,\n",
       " 'K': 0.0}"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "without_damping = copy.deepcopy(pages)\n",
    "without_damping = run_pagerank(without_damping, links, 1, 25)\n",
    "\n",
    "# TODO Fix summing issue...\n",
    "without_damping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Wait, What Just Happened?!\n",
    "\n",
    "Let's compare the two graphically to see what happened with and without damping."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAEICAYAAACzliQjAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAG4lJREFUeJzt3X+cXVV97vHPY2KCCEKAkWoSSJCoBNFAh1BUEOVXAE2gFzSANeFiES+5xdLbEq0FGmoNtrfoLfHyQ1MQiwHR6txLkNICAoXQDBjQBCKTEMkYgUACgkAw4ds/9hrcczgzs8/MnJkk63m/XvPK3muvvdfa58dz1llnnxNFBGZmloc3DHcHzMxs6Dj0zcwy4tA3M8uIQ9/MLCMOfTOzjDj0zcwy4tDPnKQ1ko4agnaOkNTZ7HYGQtLNkmb1sv1qSX8zlH0aTJJekLRPk449WVJ7L9u32dtO0mhJj0h663D3ZTA49BuQAvKl9OR5UtI/SdqpyW0eIenV1ObzklZKOqOZbfbQj0ck/fc65ef29mQfLpIOlfRrSSNKZVf1UHY5QEQcFxHXpPLZku4eQPsTJEW637oeL/9f0tEDOa+BiIidImJ1kw5/MfD3TTp2jyT9qaQnJD0naaGk0b3U/bikh9PzaIWkE0vbZkvaUrq/XpB0BEBEbAIWAuc3/YSGgEO/cR+LiJ2Ag4CDgS8OQZvrUptvAf4UuErSu4ag3bJrgE/VKf+jtG1r0w6MoLifuhwGrKspOxy4s4n92DXdd+8DbgX+RdLsJrY35CS9Dfgw8IMhbvdYYC5wJDAB2Af46x7qjgW+DZxH8Tz6c+C6mtH7vemFsevvjtK264BZvb2obCsc+v0UEb8EbgbeAyDpjNIoYrWkz5TrS/oLSb+StE7Sp9MocN+0bbSkv5f0eBoRXi7pTXXajIhYDGwA3ls69tckrU2j2PslHVbadpGkGyR9K/VtuaTWeuck6d2SHpM0s87ma4EPStq7VH+/1I/vVLkNatp67fzTere3/5I+KmmZpGcl3SOpfL7nS/pl6Z3PkXVuq98CSyhCnfTkHgVcX1P2TlLoS7oj3Tf7AZcDh6YR37OlQ4+RdFNq+z5J7+jpHGv680REfA24CLhE0htSm3MlrSqNPk8qnedsSf8h6dJ0O6yW9P5UvlbSUypNR6Xb8HJJt6bj/bjm/io/5q6WtKCnc5F0TLptn5P09XSsT/dwekcDD0TEy6X9D5T0QDr29cAOVW6nBs0CvhkRyyNiI8W7jdk91B0HPBsRN6fn0U3Ab4Cq918nsBH4g4F3e3g59PtJ0njgeOAnqegp4KMUo4gzgEslHZTqTqMYYRwF7At8qOZwl1CEz5S0fSxwQZ023yBpOrAH0FHatDTtuxvFiOS7kspPsunAImBXoA24rM6xDwL+FfifEbGodnt60N9OMbLv8ilgcUQ83ddt0Ii0z0LgM8DuwBVAW3pxfBcwBzg4InYGjgXW9HCoO0kBn/69O/2Vyx5L51Y+14eBs/ndyG/X0uZTKUaTYyjugy81eHrfB94KdL1TW0XxDmSXdNxvp5Fzl0OAhyhuh+so7seDKR4nnwQuU/cpxtMpwm8PYBnwz730pe65SNoDuBH4fGp3JfD+Xo5zQKpD2n8Uxaj/WorH5HeB/9bTzpI+mF7Uevr7YA+77g88WFp/ENhT0u516rYDD0uaLmmEiqmdTRS3bZcDJT0t6eeS/krSyJpjPEzxjm3bFhH+q/hHES4vAM8CvwC+Dryph7o/AM5NywuBL5e27QtE+lekEUdp+6EUYQRwBPBqanMTsAX4XB/93Ai8Ly1fBPxbadtk4KWac/proBP4cB/H/SSwMi2/AXgcOKmX+uXb4Aigs7QtgH1L61cDf5OW/y9wcc2xVlK8WO5L8eJyFPDGPvp7BPBMuo2/BvwxsBPwZKnsn0r17wA+nZZnA3fXHO9q4Bul9eOBR3poe0I6x5E15Tuk8g/0sN8yYEapD4+Wth2Q9t2zVPYMMKXUv0WlbTulx8v42tu8t3OheDG/t7RNwNqu26ZOn68C5pfWD6eYRlOp7J6u+3cQn4+rgGml9Temc5zQQ/0zKZ6/m4EXgRNK2/YBJqbH9QHACuDzNfv/M3DBYJ7DcPx5pN+4EyNi14jYOyL+R0S8BCDpOElLJG1I0wHHU4y2AN5O8aTpUl5uAXYE7u8a2QA/SuVd1kUx2nwL8H+Aj5Q7JOnP0rTKc2n/XUptAzxRWn4R2KFmFHM2cE9E3N7HuX8feJukP6AI1B2Bm0r96O02aMTewJ+VR3vAeODtEdEBfI7ixewpSYskvb2H4yyhCL73UATRXRHxAsXt31XW6Hx+7W3Z6Af5Y9O/GwAkfao0jfVs6lf5NnuytPwSQETUlpX78NpjK53rBorHXz09nUu3x2sUidfblVcbgZ1L628Hfpn26/KLXvbvrxconhNdupafr62o4gq1r1A8bkdRDCC+IWkKQESsjojHIuLViPgpMA84ueYwO1MMvrZpDv1BoOLDne9RXL2wZwroxRQjJIBfUcwpdhlfWn6a4om7f3ox2TUidoniw79uoriK4HzggPT2FBXz9+cDHwfGpLafK7VdxdnAXpIu7a1SRLxI8bb/UxTTPIsi4pWKt0GtFyleNLr8Xml5LfCl0u2xa0TsGBHfSf24LiI+SPHiEBTTY/X6+zLF1NdHgbdFxCNp012p7L30HPrN+vnZkyjeqaxM8+1XUUxX7Z5us5/R2H1X67XHVpr22Y1i1N2Ibo9XSaL747fWQxTTk+X9x6b9uuzV086SDlP3q2Zq/w7rYdfldJ9ueR/wZEQ8U6fuFODOiGhPwb4UuI/iHWM9wevvh/3oPp20TXLoD45RwGhgPbBZ0nHAMaXtNwBnSNpP0o6U5usj4lWKJ/6lSlcSSBqr4sqE10kh+79Lx9iZ4u3qemCkpAvoPvqp4nlgGnC4pPl91L0G+ATFHG35qp2+boNay4DT0vzqNLp/znEVcLakQ1R4s6QTJO0s6V2SPpJeZF6meMHc0ks7d1K8M7inVHZ3KnsiIlb1sN+TwLg0Pz1gkvaUNAe4kGLa4FXgzRThsj7VOYN0YcAAHJ/myEdRzO3fFxFr+9qpxk2kgUV6R3gO3V+Ua90KHFT6HOleisfkn0gaKekPgak97RwRd0X3q2Zq/+7qYddvAWeq+I7AGIor6a7uoe5S4LCukb2kAyk+S3korR8nac+0/G7gr4Afdu2s4uqf3SjePW7THPqDICKeB/6EItw3AqdRfGDatf1mimmZ2yk+MLs3bdqU/j0/lS+R9Gvg3/jdB331LKQYmX8MuIXiKqKfU7yFfpnu00dVz+FZiqswjpN0cS9V76R4J/HLNFrq2r/X26COc4GPUbxdPp3S5X4R0U4x/35ZOlYHv7sqYzQwn+Id0hMUH4p+oZd2fpzqlK+5vzuV9Ta1cxvFSPIJSU/3Uq8vz0r6DfBTiumuUyJiIUBErKB4Ab+X4kXmAOA/BtAWFB/2XkgxrfP7FLdtQ6L4YP4UiumQZyg+B2rnd4/X2vpPUtxeM9L6K8AfUtxnGykGCd9vtB8V+vmj1MfbKR77v6A4dwBUXKl2eqr7Y4opwRslPU/xrvRvI+JfU/UjgYfSfbU49fdvS82dBlyT3m1v09R92s2GgopLAn8GjI6IzcPdH9s+SLqa4sPyQf3uiIrLSzuB03v63EfSZIp3flNjOwuV9K7yQeDwiHhquPszUB7pDxFJJ0kald6GXgL8Pwe+ba0kHStp1xR4X6CY3+5xaiMiVkTEwdtb4EPxWVpEvHt7CHxw6A+lz1DM3a6imIP+7PB2x6xXh1I8Vp+mmIY7setKNdu2eXrHzCwjHumbmWWk9mvGw26PPfaICRMmDHc3zMy2Kffff//TEdHSV72tLvQnTJhAe/tW90u9ZmZbNUmVvvXs6R0zs4w49M3MMuLQNzPLiEPfzCwjDn0zs4w49M3MMuLQNzPLiEPfzCwjDn0zs4xsdd/I3dZMmHtT35X6Yc38E5pyXDPLm0f6ZmYZceibmWXEoW9mlhGHvplZRhz6ZmYZceibmWXEoW9mlhGHvplZRhz6ZmYZceibmWXEoW9mlpFKoS9pmqSVkjokza2z/WxJP5W0TNLdkiaXtn0+7bdS0rGD2XkzM2tMn6EvaQSwADgOmAycWg715LqIOCAipgBfAf4h7TsZmAnsD0wDvp6OZ2Zmw6DKSH8q0BERqyPiFWARMKNcISJ+XVp9MxBpeQawKCI2RcRjQEc6npmZDYMqP608FlhbWu8EDqmtJOkc4DxgFPCR0r5LavYdW2ffs4CzAPbaa68q/TYzs36oMtJXnbJ4XUHEgoh4B3A+8MUG970yIlojorWlpaVCl8zMrD+qhH4nML60Pg5Y10v9RcCJ/dzXzMyaqEroLwUmSZooaRTFB7Nt5QqSJpVWTwAeTcttwExJoyVNBCYB/znwbpuZWX/0OacfEZslzQFuAUYACyNiuaR5QHtEtAFzJB0F/BbYCMxK+y6XdAOwAtgMnBMRW5p0LmZm1odK/0duRCwGFteUXVBaPreXfb8EfKm/HTQzs8Hjb+SamWWk0kjfth4T5t7UtGOvmX9C045tZlsHj/TNzDLi0Dczy4hD38wsIw59M7OMOPTNzDLi0Dczy4hD38wsIw59M7OMOPTNzDLi0Dczy4hD38wsIw59M7OMOPTNzDLi0Dczy4hD38wsIw59M7OMOPTNzDLi0Dczy4hD38wsIw59M7OMOPTNzDJSKfQlTZO0UlKHpLl1tp8naYWkhyT9u6S9S9u2SFqW/toGs/NmZtaYkX1VkDQCWAAcDXQCSyW1RcSKUrWfAK0R8aKkzwJfAT6Rtr0UEVMGud9mZtYPVUb6U4GOiFgdEa8Ai4AZ5QoRcXtEvJhWlwDjBrebZmY2GKqE/lhgbWm9M5X15Ezg5tL6DpLaJS2RdGK9HSSdleq0r1+/vkKXzMysP/qc3gFUpyzqVpQ+CbQCHyoV7xUR6yTtA9wm6acRsarbwSKuBK4EaG1trXtsMzMbuCoj/U5gfGl9HLCutpKko4C/BKZHxKau8ohYl/5dDdwBHDiA/pqZ2QBUCf2lwCRJEyWNAmYC3a7CkXQgcAVF4D9VKh8jaXRa3gP4AFD+ANjMzIZQn9M7EbFZ0hzgFmAEsDAilkuaB7RHRBvwd8BOwHclATweEdOB/YArJL1K8QIzv+aqHzMzG0JV5vSJiMXA4pqyC0rLR/Ww3z3AAQPpoJmZDR5/I9fMLCMOfTOzjDj0zcwy4tA3M8uIQ9/MLCMOfTOzjDj0zcwy4tA3M8uIQ9/MLCMOfTOzjDj0zcwy4tA3M8uIQ9/MLCMOfTOzjDj0zcwy4tA3M8uIQ9/MLCMOfTOzjDj0zcwy4tA3M8uIQ9/MLCMOfTOzjDj0zcwyUin0JU2TtFJSh6S5dbafJ2mFpIck/bukvUvbZkl6NP3NGszOm5lZY/oMfUkjgAXAccBk4FRJk2uq/QRojYj3AjcCX0n77gZcCBwCTAUulDRm8LpvZmaNqDLSnwp0RMTqiHgFWATMKFeIiNsj4sW0ugQYl5aPBW6NiA0RsRG4FZg2OF03M7NGVQn9scDa0npnKuvJmcDNjewr6SxJ7ZLa169fX6FLZmbWH1VCX3XKom5F6ZNAK/B3jewbEVdGRGtEtLa0tFTokpmZ9UeV0O8ExpfWxwHraitJOgr4S2B6RGxqZF8zMxsaVUJ/KTBJ0kRJo4CZQFu5gqQDgSsoAv+p0qZbgGMkjUkf4B6TyszMbBiM7KtCRGyWNIcirEcACyNiuaR5QHtEtFFM5+wEfFcSwOMRMT0iNki6mOKFA2BeRGxoypmYmVmf+gx9gIhYDCyuKbugtHxUL/suBBb2t4NmZjZ4/I1cM7OMOPTNzDLi0Dczy4hD38wsIw59M7OMOPTNzDLi0Dczy4hD38wsIw59M7OMOPTNzDLi0Dczy4hD38wsIw59M7OMOPTNzDLi0Dczy4hD38wsIw59M7OMOPTNzDLi0Dczy4hD38wsIw59M7OMOPTNzDLi0Dczy0il0Jc0TdJKSR2S5tbZfrikByRtlnRyzbYtkpalv7bB6riZmTVuZF8VJI0AFgBHA53AUkltEbGiVO1xYDbwv+oc4qWImDIIfTUzswHqM/SBqUBHRKwGkLQImAG8FvoRsSZte7UJfTQzs0FSZXpnLLC2tN6ZyqraQVK7pCWSTqxXQdJZqU77+vXrGzi0mZk1okroq05ZNNDGXhHRCpwGfFXSO153sIgrI6I1IlpbWloaOLSZmTWiSuh3AuNL6+OAdVUbiIh16d/VwB3AgQ30z8zMBlGV0F8KTJI0UdIoYCZQ6SocSWMkjU7LewAfoPRZgJmZDa0+Qz8iNgNzgFuAh4EbImK5pHmSpgNIOlhSJ3AKcIWk5Wn3/YB2SQ8CtwPza676MTOzIVTl6h0iYjGwuKbsgtLyUoppn9r97gEOGGAfzcxskPgbuWZmGXHom5llxKFvZpYRh76ZWUYc+mZmGXHom5llxKFvZpYRh76ZWUYc+mZmGXHom5llxKFvZpYRh76ZWUYc+mZmGXHom5llxKFvZpYRh76ZWUYc+mZmGXHom5llxKFvZpYRh76ZWUYc+mZmGXHom5llxKFvZpaRSqEvaZqklZI6JM2ts/1wSQ9I2izp5JptsyQ9mv5mDVbHzcyscX2GvqQRwALgOGAycKqkyTXVHgdmA9fV7LsbcCFwCDAVuFDSmIF328zM+qPKSH8q0BERqyPiFWARMKNcISLWRMRDwKs1+x4L3BoRGyJiI3ArMG0Q+m1mZv1QJfTHAmtL652prIpK+0o6S1K7pPb169dXPLSZmTWqSuirTllUPH6lfSPiyohojYjWlpaWioc2M7NGVQn9TmB8aX0csK7i8Qeyr5mZDbIqob8UmCRpoqRRwEygreLxbwGOkTQmfYB7TCozM7Nh0GfoR8RmYA5FWD8M3BARyyXNkzQdQNLBkjqBU4ArJC1P+24ALqZ44VgKzEtlZmY2DEZWqRQRi4HFNWUXlJaXUkzd1Nt3IbBwAH00M7NB4m/kmpllxKFvZpYRh76ZWUYc+mZmGXHom5llxKFvZpYRh76ZWUYc+mZmGXHom5llxKFvZpYRh76ZWUYc+mZmGXHom5llxKFvZpaRSj+tbDZUJsy9qWnHXjP/hKYd22xb4ZG+mVlGHPpmZhlx6JuZZcShb2aWEYe+mVlGHPpmZhlx6JuZZcShb2aWkUqhL2mapJWSOiTNrbN9tKTr0/b7JE1I5RMkvSRpWfq7fHC7b2ZmjejzG7mSRgALgKOBTmCppLaIWFGqdiawMSL2lTQTuAT4RNq2KiKmDHK/zcysH6qM9KcCHRGxOiJeARYBM2rqzACuScs3AkdK0uB108zMBkOV0B8LrC2td6ayunUiYjPwHLB72jZR0k8k/VjSYfUakHSWpHZJ7evXr2/oBMzMrLoqoV9vxB4V6/wK2CsiDgTOA66T9JbXVYy4MiJaI6K1paWlQpfMzKw/qoR+JzC+tD4OWNdTHUkjgV2ADRGxKSKeAYiI+4FVwDsH2mkzM+ufKqG/FJgkaaKkUcBMoK2mThswKy2fDNwWESGpJX0QjKR9gEnA6sHpupmZNarPq3ciYrOkOcAtwAhgYUQslzQPaI+INuCbwLWSOoANFC8MAIcD8yRtBrYAZ0fEhmaciJmZ9a3Sf6ISEYuBxTVlF5SWXwZOqbPf94DvDbCPZmY2SPyNXDOzjDj0zcwy4tA3M8uIQ9/MLCMOfTOzjFS6esfyNWHuTU079pr5JzTt2I1o1jluLednVuaRvplZRhz6ZmYZ2e6md/xW3cysZx7pm5llxKFvZpYRh76ZWUYc+mZmGXHom5llxKFvZpYRh76ZWUYc+mZmGdnuvpxltrUb6i8Qbi/t9dTm9t7eYPNI38wsIw59M7OMOPTNzDLi0Dczy4hD38wsI5VCX9I0SSsldUiaW2f7aEnXp+33SZpQ2vb5VL5S0rGD13UzM2tUn6EvaQSwADgOmAycKmlyTbUzgY0RsS9wKXBJ2ncyMBPYH5gGfD0dz8zMhkGVkf5UoCMiVkfEK8AiYEZNnRnANWn5RuBISUrliyJiU0Q8BnSk45mZ2TBQRPReQToZmBYRn07rfwQcEhFzSnV+lup0pvVVwCHARcCSiPh2Kv8mcHNE3FjTxlnAWWn1XcDKgZ9aJXsATw9RW25v+2jT7W3b7Q1Hm0PV3t4R0dJXpSrfyFWdstpXip7qVNmXiLgSuLJCXwaVpPaIaHV722Z7w9Gm29u22xuONofjHHtTZXqnExhfWh8HrOupjqSRwC7Ahor7mpnZEKkS+kuBSZImShpF8cFsW02dNmBWWj4ZuC2KeaM2YGa6umciMAn4z8HpupmZNarP6Z2I2CxpDnALMAJYGBHLJc0D2iOiDfgmcK2kDooR/sy073JJNwArgM3AORGxpUnn0h9DPaXk9rb9Nt3ett3ecLQ5HOfYoz4/yDUzs+2Hv5FrZpYRh76ZWUayDX1JJ0kKSe8egra2SFom6UFJD0h6f5Pb+z1JiyStkrRC0mJJ72xie13ntzyd43mSmvrYKrXZ9fe6nwdpcnsTmtzenpKuk7Ra0v2S7pV0UpPaeqFmfbaky5rRVl9tb09tltuRdLykRyXtNRRt9ybn/znrVOBuig+dL2pyWy9FxBSA9PtDXwY+1IyG0jeh/wW4JiJmprIpwJ7Az5vRJt3P763AdRSX7V7YpPa6tTlEhqy9dB/+gOI+PC2V7Q1MH4r2bXBJOhL4R+CYiHh8uPuT5Uhf0k7AByh+M2jmEDf/FmBjE4//YeC3EXF5V0FELIuIu5rY5msi4imKb1fPSeFljfsI8ErNffiLiPjHYeyT9YOkw4CrgBMiYtVw9wfyHemfCPwoIn4uaYOkgyLigSa29yZJy4AdgLdRPKmb5T3A/U08fp8iYnWa3nkr8GSTmum6Tbt8OSKub1Jbte09FhFNmWpJ9gea+XisVXtb7sbrv4tjjRsN/BA4IiIeGe7OdMk19E8FvpqWF6X1Zj7JytMfhwLfkvSe2L6vl232KH+7nd6pJWkB8EGK0f/BTWii27lJmg1sNT8bsA37LXAPxYzCucPcl9dkN70jaXeKkfY3JK0B/hz4xFBNRUTEvRQ/wNTnDyP103Lg95t07Eok7QNsAZ4azn5sw5YDB3WtRMQ5wJE07zFjzfEq8HHgYElfGO7OdMku9Cl+JuJbEbF3REyIiPHAYxQjqaZLVwuNAJ5pUhO3AaMl/XGpzYMlNeWD41qSWoDLgcu283cyzXQbsIOkz5bKdhyuzlj/RcSLwEeB0yWdOdz9gTynd04F5teUfQ84DWjWh53lOVMBs5r1cxQREenSvq+myxhfBtYAn2tGe0nX+b2R4uc2rgX+oYntldvs8qOIaOplm0Ml3YcnApdK+gtgPfAb4Pzh7dm2L/0g5KahbDMiNkiaBtwp6emI+OFQtl/LP8NgZtmQ9D7gqojI9j9zynF6x8wyJOls4DvAF4e7L8PJI30zs4x4pG9mlhGHvplZRhz6ZmYZceibmWXEoW9mlpH/AiN4cJ3dwSeQAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Plot pagerank with damping\n",
    "plt.bar(range(len(with_damping)), list(with_damping.values()), align='center')\n",
    "plt.xticks(range(len(with_damping)), list(with_damping.keys()))\n",
    "plt.title(\"PageRank Values With Damping (d = 0.85)\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEICAYAAACktLTqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAGK5JREFUeJzt3X+YXVV97/H3x8SACIrAoJAfhGqwRqWIA6IVRcGaCCbw1IsJtgWvJaVtKhauEnu91FKtaKvQlvSB0GKRigF/FKYymj5eEKQSbwaby+0Qo0MAM6bKAAmC/Ax87x97Tbtzcn7sMzl7Jln9vJ5nnpy99zr7u86vz1l77XNOFBGYmVlenjfVHTAzs95zuJuZZcjhbmaWIYe7mVmGHO5mZhlyuJuZZcjh/l+ApPsknTQJdU6QNFp3nV0h6RuSzmyz/e8lfWIy+7S7kvQ+Sf9c4/4/JelDbbaHpFfUVb9JvSMlfXey6tXN4d4gBeETkh6T9DNJn5e0b801T5D0XKr5qKSNkt5fZ80W/fiBpP/eZP25koYmuz+dSHqjpJ9LmlZad2WLdZcDRMTCiLg6rT9L0u2T1Ne5Kaymt2nzcUnPpOfAo5J+KOkySYdMRh8bRcQXI+LX6ti3pD7gt4Ar6th/m7rLJQ1JekrS35e3RcRdwDZJ757MPtXF4d7cuyNiX+Bo4BjgY5NQc0uq+SLgD4ErJb1yEuqWXU3xgmv0m2nb7mYImEbxOI07HtjSsO4twG2T2K9dcV1E7AccAJwGvAy4c6oCvkZnAYMR8cQk190CfAK4qsX2LwK/M3ndqY/DvY2I+AnwDeA1AJLeL2lDGlVtkrTDk0DSRyT9u6Qtkn67fFgpaS9JfyHpx+mI4HJJL2hSMyJiEHgYOLK077+UtDmNSu+UdHxp28clXS/pC6lvw5L6m90mSb8s6V5JS5psvgZ4s6TDSu1flfrxpSr3QUOtHQ6rG6c8JJ0iab2kbZK+K6l8ey+Q9JPSkcyJTe6rZ4C1FOGNpIOBGcB1DeuOIIW7pG+nx+ZVwOXAG9MR07bSrl8i6aZU+3uSXl7q15skrZP0SPr3TaVtO0x/pcflH9Li+JvLtlTvja3ut/HbFhHDwHuBMeD8tM+XSPq6pDFJW9PlWaWa35b0iXR/PibpnyQdKOmL6bmzTtLcUvuQ9MH0WD4o6c8lPS9t2+HIJrU9R9KPUu2VkpS2TZP02bSPe9MIud2RykLg1vIKSR8uvX52OoLshYj4WkTcADzUosm3gRMl7VVH/cnkcG9D0mzgXcC/plUPAKdQjK7fD1wi6ejUdgFwHnAS8ArgrQ27+zRFyByVts8ELmxS83mSFgEHASOlTevSdQ8ArgW+LGnv0vZFwGpgf2AAuKzJvo8G/hn4g4hY3bg9IkaBWyhG6uN+i2KE9WCn+6Ab6TpXUYySDqQ4PB9Ib4KvBJYDx6RR7DuB+1rs6jZSkKd/b09/5XX3pttWvq0bgHOAOyJi34jYv7R5KfAnwEsoHoNPpj4fANwE/FXq8+eAmyQdWOEmj/dn/1TvjgrXISKeBW6kOCKB4jX7eeAwYA7wBDs/1ksoHsOZwMuBO9J1DgA2AH/c0P40oJ/iaGcx0C5YT6E4mv0V4HSKxwbgbIrAPirt59QON+21wMbxhfT6+R/AO4B5FK+jliT9TRoUNPu7q0PtltKA7hlgso+ae87h3twNaSR3O8Xo4s8AIuKmiLgnja5vpQjK8Rfd6cDnI2I4Ih6nCAcA0ujmbOAPI+LhiHg07bM8ej401XwC+EfgvIgYf1MhIv4hIh6KiO0R8VlgL3Z8At4eEYMpDK6hePGVHU8R+mdGxNfb3ParSeGeRnDvozQl0+E+6MbZwBUR8b2IeDbNgz8FHAc8m27ffEnPj4j7IuKeFvu5leJoQ6kf36EIs+NK625tcd1WvhYR/ycitlMcph+V1p8M/CgirkmPw5eAHwB1z9FuoQhm0nPgqxHxeHoefZKdBxKfT4/RIxRHnvdExLfS7fky8LqG9p9Oz8sfA5dSvLm1cnFEbEttb+E/75vTgb+MiNGI2Apc3OE27Q88Wloef/38W0T8Avh4uytHxO9FxP4t/o5sd90KHk3926M53Js7NT1JDktPoicAJC2UtFbSwymI30UxwgY4FNhc2kf5ch+wD8Xc6bZ03W+m9eO2pNHjiyhGhm8vd0jS+Wk65JF0/ReXagP8tHT5cWDvhkPic4DvRsQtHW7714BDJB0HnJD6fVOpH+3ug24cBpxfHnEBs4FDI2IE+BDFC/wBSaslHdpiP2uBfSmmzt4CfCciHqO4/8fXdTvf3nhfjp9QPxS4v6Ht/RQj5DrNpJimQ9I+kq6QdL+kn1Pctv1VOoEM/Kx0+Ykmy40fECg/V++nuJ2ttLtvWj3/m9kK7Fdabrx+4/08mfYDtnVstZtzuFeU5uC+CvwF8NIUxIOAUpN/B2aVrjK7dPlBihfVq0ujixenE6g7iIingAuA10o6NdU+Pq07HXhJqv1IqXYV5wBzJF3SrlE66vgKxXTMbwKrI+LpivdBo8cp3hzGvax0eTPwyYYR1z5pNExEXBsRb6Z4EwiKaa1m/X2SYsrqFOCQiPhB2vSdtO5IWod7tz+JuiX1p2wO8JN0+Re0vr0T+vnVdPT0borbA8Xc+yuBN0TEi/jP6Z5unguNys/VORS3s1vtnv/N3EUxTVm+fmM/WlJxzuqxFn/DXfV8x/0eSnHeZmOntrs7h3t1MyimCsaA7ZIWAuWPiV0PvF/SqyTtQ2k+PSKeA66kmJ8+GEDSTEnvpIkUpp8t7WM/YHuqPV3ShRQj/G48CiwA3iKp0yHz1RQn8n6dHT8l0+k+aLQeOCOdbFvAjtMHVwLnSHqDCi+UdLKk/SS9UtLb05vJkxRvjM+2qXMbxUi//Bnl29O6n7aZ0vkZMEvSjDb7LhsEjpB0hqTpkt4LzAfGp7nWA0skPV/FCe33lK47BjwH/FKVQmkfr6I4kf0yivl9KJ4LT1CcmD2AnefPJ+LDKk7UzgbOpTgh3a3rgXPT83p/isFIO4Ps+Hy4HjhL0vz0+ml7uyLinHTuotnfq1tdLz1ue1N8ymqapMYj3BOAm9Mga4/mcK8ozW9+kOJJuBU4g2IOe3z7NyimU26hOAk3fsJs/ElyQVq/Nh1Of4v2J22uohhpvxtYQzF3+kOKw9Un6XzY2+w2bKM4YbVQ0p+2aXobxZHBTyJiXen6be+DJs6lGHVuo5i7v6G0ryGKeffL0r5GKD4eB8UbyMUURzw/BQ4G/qhNnVtTm/Jn1m9P69pNydwMDAM/lfRgm3bjfX6I4mjgfIpPW3wEOKV0svl/UZzA3EpxzuXa0nUfp5gf/5c0DXVcizLvlfQYxX02kOq8PiLGR9OXAi+guG/WUkzv7aobgTsp3pxuAv5uAvu4kuL8y10UH0AYpBiQtHpT/gLwLqVPjKXXz6UUj8lI+rcOH6N4c1wB/Ea6XP6o8/soPkW1x1P4P+uoRRp1/RuwVzqRZbbbkRTAvHSeo5f7XQhcHhGN01jlNn8GPBARl/ay9kRJei2wKiLafkx1T+Fw7yFJp1GMfF5IMZ3xXER0+kiY2ZTpVbinEfjbKEbvL6U4N7M2Ilr+vIDVy9MyvfU7FHOr91Acjv7u1HbHbNKIYipqK8W0zAaafI/DJo9H7mZmGfLI3cwsQy1/oa5uBx10UMydO3eqypuZ7ZHuvPPOByOir1O7KQv3uXPnMjS02/2KrJnZbk1SpW/velrGzCxDDnczsww53M3MMuRwNzPLkMPdzCxDDnczsww53M3MMuRwNzPLkMPdzCxDU/YN1T3J3BU3dW40QfddfPKk1mxVz8zy4pG7mVmGHO5mZhlyuJuZZcjhbmaWIYe7mVmGHO5mZhlyuJuZZcjhbmaWIYe7mVmGHO5mZhlyuJuZZcjhbmaWIYe7mVmGKoW7pAWSNkoakbSiRZvTJd0taVjStb3tppmZdaPjT/5KmgasBN4BjALrJA1ExN2lNvOAjwK/GhFbJR1cV4fNzKyzKiP3Y4GRiNgUEU8Dq4HFDW3OBlZGxFaAiHigt900M7NuVAn3mcDm0vJoWld2BHCEpH+RtFbSgmY7krRM0pCkobGxsYn12MzMOqoS7mqyLhqWpwPzgBOApcDfStp/pytFrIqI/ojo7+vr67avZmZWUZVwHwVml5ZnAVuatLkxIp6JiHuBjRRhb2ZmU6BKuK8D5kk6XNIMYAkw0NDmBuBtAJIOopim2dTLjpqZWXUdwz0itgPLgTXABuD6iBiWdJGkRanZGuAhSXcDtwAfjoiH6uq0mZm11/GjkAARMQgMNqy7sHQ5gPPSn5mZTTF/Q9XMLEMOdzOzDDnczcwy5HA3M8uQw93MLEMOdzOzDDnczcwy5HA3M8uQw93MLEMOdzOzDDnczcwy5HA3M8uQw93MLEMOdzOzDDnczcwy5HA3M8uQw93MLEMOdzOzDDnczcwy5HA3M8uQw93MLEMOdzOzDFUKd0kLJG2UNCJpRZPtZ0kak7Q+/f1277tqZmZVTe/UQNI0YCXwDmAUWCdpICLubmh6XUQsr6GPZmbWpSoj92OBkYjYFBFPA6uBxfV2y8zMdkWVcJ8JbC4tj6Z1jX5d0l2SviJpdk96Z2ZmE1Il3NVkXTQs/xMwNyKOBL4FXN10R9IySUOShsbGxrrrqZmZVVYl3EeB8kh8FrCl3CAiHoqIp9LilcDrm+0oIlZFRH9E9Pf19U2kv2ZmVkGVcF8HzJN0uKQZwBJgoNxA0iGlxUXAht510czMutXx0zIRsV3ScmANMA24KiKGJV0EDEXEAPBBSYuA7cDDwFk19tnMzDroGO4AETEIDDasu7B0+aPAR3vbNTMzmyh/Q9XMLEMOdzOzDDnczcwy5HA3M8uQw93MLEMOdzOzDDnczcwy5HA3M8uQw93MLEMOdzOzDDnczcwy5HA3M8uQw93MLEMOdzOzDDnczcwy5HA3M8uQw93MLEMOdzOzDDnczcwy5HA3M8uQw93MLEMOdzOzDDnczcwyVCncJS2QtFHSiKQVbdq9R1JI6u9dF83MrFsdw13SNGAlsBCYDyyVNL9Ju/2ADwLf63UnzcysO1VG7scCIxGxKSKeBlYDi5u0+1PgM8CTPeyfmZlNQJVwnwlsLi2PpnX/QdLrgNkR8fV2O5K0TNKQpKGxsbGuO2tmZtVUCXc1WRf/sVF6HnAJcH6nHUXEqojoj4j+vr6+6r00M7OuVAn3UWB2aXkWsKW0vB/wGuDbku4DjgMGfFLVzGzqVAn3dcA8SYdLmgEsAQbGN0bEIxFxUETMjYi5wFpgUUQM1dJjMzPrqGO4R8R2YDmwBtgAXB8Rw5IukrSo7g6amVn3pldpFBGDwGDDugtbtD1h17tlZma7wt9QNTPLkMPdzCxDDnczsww53M3MMuRwNzPLkMPdzCxDDnczsww53M3MMuRwNzPLkMPdzCxDDnczsww53M3MMuRwNzPLkMPdzCxDDnczsww53M3MMuRwNzPLkMPdzCxDDnczsww53M3MMuRwNzPLkMPdzCxDDnczswxVCndJCyRtlDQiaUWT7edI+n+S1ku6XdL83nfVzMyq6hjukqYBK4GFwHxgaZPwvjYiXhsRRwGfAT7X856amVllVUbuxwIjEbEpIp4GVgOLyw0i4uelxRcC0bsumplZt6ZXaDMT2FxaHgXe0NhI0u8D5wEzgLc325GkZcAygDlz5nTbVzMzq6jKyF1N1u00Mo+IlRHxcuAC4GPNdhQRqyKiPyL6+/r6uuupmZlVViXcR4HZpeVZwJY27VcDp+5Kp8zMbNdUCfd1wDxJh0uaASwBBsoNJM0rLZ4M/Kh3XTQzs251nHOPiO2SlgNrgGnAVRExLOkiYCgiBoDlkk4CngG2AmfW2WkzM2uvyglVImIQGGxYd2Hp8rk97peZme0Cf0PVzCxDDnczsww53M3MMuRwNzPLkMPdzCxDDnczsww53M3MMuRwNzPLkMPdzCxDDnczsww53M3MMuRwNzPLkMPdzCxDDnczsww53M3MMuRwNzPLkMPdzCxDDnczsww53M3MMuRwNzPLkMPdzCxDDnczswxVCndJCyRtlDQiaUWT7edJulvSXZL+t6TDet9VMzOrqmO4S5oGrAQWAvOBpZLmNzT7V6A/Io4EvgJ8ptcdNTOz6qqM3I8FRiJiU0Q8DawGFpcbRMQtEfF4WlwLzOptN83MrBtVwn0msLm0PJrWtfIB4Bu70ikzM9s10yu0UZN10bSh9BtAP/DWFtuXAcsA5syZU7GLZmbWrSoj91Fgdml5FrClsZGkk4D/CSyKiKea7SgiVkVEf0T09/X1TaS/ZmZWQZVwXwfMk3S4pBnAEmCg3EDS64ArKIL9gd5308zMutEx3CNiO7AcWANsAK6PiGFJF0lalJr9ObAv8GVJ6yUNtNidmZlNgipz7kTEIDDYsO7C0uWTetwvMzPbBf6GqplZhhzuZmYZcribmWXI4W5mliGHu5lZhhzuZmYZcribmWXI4W5mliGHu5lZhhzuZmYZcribmWXI4W5mliGHu5lZhhzuZmYZcribmWXI4W5mliGHu5lZhhzuZmYZcribmWXI4W5mliGHu5lZhhzuZmYZcribmWWoUrhLWiBpo6QRSSuabH+LpO9L2i7pPb3vppmZdaNjuEuaBqwEFgLzgaWS5jc0+zFwFnBtrztoZmbdm16hzbHASERsApC0GlgM3D3eICLuS9ueq6GPZmbWpSrTMjOBzaXl0bSua5KWSRqSNDQ2NjaRXZiZWQVVwl1N1sVEikXEqojoj4j+vr6+iezCzMwqqBLuo8Ds0vIsYEs93TEzs16oEu7rgHmSDpc0A1gCDNTbLTMz2xUdwz0itgPLgTXABuD6iBiWdJGkRQCSjpE0Cvw34ApJw3V22szM2qvyaRkiYhAYbFh3YenyOorpGjMz2w34G6pmZhlyuJuZZcjhbmaWIYe7mVmGHO5mZhlyuJuZZcjhbmaWIYe7mVmGHO5mZhlyuJuZZcjhbmaWIYe7mVmGHO5mZhlyuJuZZcjhbmaWIYe7mVmGHO5mZhlyuJuZZcjhbmaWIYe7mVmGHO5mZhlyuJuZZcjhbmaWoUrhLmmBpI2SRiStaLJ9L0nXpe3fkzS31x01M7PqOoa7pGnASmAhMB9YKml+Q7MPAFsj4hXAJcCne91RMzOrrsrI/VhgJCI2RcTTwGpgcUObxcDV6fJXgBMlqXfdNDOzbkyv0GYmsLm0PAq8oVWbiNgu6RHgQODBciNJy4BlafExSRsn0ukJOKixL7tLPfXmGGe3rdcjudebipqut+fWO6xKoyrh3mwEHhNoQ0SsAlZVqNlTkoYiot/1XG93rDcVNV1vz65XRZVpmVFgdml5FrClVRtJ04EXAw/3ooNmZta9KuG+Dpgn6XBJM4AlwEBDmwHgzHT5PcDNEbHTyN3MzCZHx2mZNIe+HFgDTAOuiohhSRcBQxExAPwdcI2kEYoR+5I6Oz0Bkz0V5Hqut7vXdL09u15H8gDbzCw//oaqmVmGHO5mZhnKOtwlnSYpJP3yJNR6VtJ6Sf9X0vclvWkSar5M0mpJ90i6W9KgpCNqqjV++4bTbTxPUq3Pn1LN8b+dfvpiEmrOrbHWSyVdK2mTpDsl3SHptBrrPdawfJaky+qq1652LvXKdSS9S9KPJM2ZjNqdVPmc+55sKXA7xQnej9dc64mIOApA0juBTwFvratY+gbwPwJXR8SStO4o4KXAD2soWb59BwPXUnzk9Y9rqLVTzUk0KTXT43cDxeN3Rlp3GLCo7trWe5JOBP4a+LWI+PFU9wcyHrlL2hf4VYrfvZnsT++8CNhac423Ac9ExOXjKyJifUR8p+a6RMQDFN80Xu6fmZiwtwNPNzx+90fEX09hn2wCJB0PXAmcHBH3THV/xuU8cj8V+GZE/FDSw5KOjojv11jvBZLWA3sDh1C8eOv0GuDOmmu0FBGb0rTMwcDPaiozfp+O+1REXFdTrWY1742IuqZJXg3U+XxspvH+PICdv7Ni3dkLuBE4ISJ+MNWdKcs53JcCl6bLq9NynS+m8rTFG4EvSHpN5l/mqnvUnu20TCNJK4E3U4zmj6mpzA63TdJZwG71lfk90DPAdylmCM6d4r7sIMtpGUkHUoyc/1bSfcCHgfdO1hRCRNxB8UNCfTWWGQZeX+P+25L0S8CzwANT1Yc93DBw9PhCRPw+cCL1Pmes954DTgeOkfRHU92ZsizDneInEL4QEYdFxNyImA3cSzEyql36dM404KEay9wM7CXp7FLdYyTVdhK3VKcPuBy4LPMjkzrdDOwt6XdL6/aZqs7YxEXE48ApwPskfWCq+zMu12mZpcDFDeu+CpwB1HXCsTyfKeDMiHi2plpERKSPzV2aPiL4JHAf8KGaSo7fvucD24FrgM/VVKux5rhvRkTtH4ecDOnxOxW4RNJHgDHgF8AFU9uzPV/68cKnJrNmRDwsaQFwm6QHI+LGyazfjH9+wMyyIulXgCsj4tip7stUynVaxsz+C5J0DvAl4GNT3Zep5pG7mVmGPHI3M8uQw93MLEMOdzOzDDnczcwy5HA3M8vQ/wdcYJiUqV33KwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Plot pagerank without damping\n",
    "plt.bar(range(len(without_damping)), list(without_damping.values()), align='center')\n",
    "plt.xticks(range(len(without_damping)), list(without_damping.keys()))\n",
    "plt.title(\"PageRank Values Without Damping (d = 1)\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What we can see is that, while $d=0.85$ gave us a result that makes intuitive sense by looking at the links in our example, $d=1$ led to the whole score being accumulated by B and C, two pages that only have outgoing links to eachother.\n",
    "\n",
    "Because a damping factor $d \\neq 1$ is added to every page's score at every iteration, it prevents this from happening by not having the whole score of a page with outgoing links only \"flow off\" over time.\n",
    "\n",
    "### Clicking Random Links\n",
    "\n",
    "PageRank can also be though of as modeling what happens when someone surfs the web by randomly clicking a link on the current page. This gives us another intuitive way of thinking about damping.\n",
    "\n",
    "A damping factor of $d$ means that at any step, such a \"random surfer\" has a probability of $d-1$ of not clicking a link, but instead jumping to any other page. Without damping, they would get stuck as soon as they reach a page without outgoing links or a cycle of pages that only link to eachother."
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
 }
No results found