Session 2. Tutorial on PageRank - Part 2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hands-on Tutorial for Link Analysis\n",
    "\n",
    "Welcome to hands-on tutorial for link analysis. \n",
    "In this tutorial, we will study several techniques for link analysis in graphs. \n",
    "This tutorial consists of four sessions, and each session will handle the following topic:\n",
    "\n",
    "* **Session 1**. Tutorial on PageRank - Part 1 (50 mins)\n",
    "* **Session 2**. Tutorial on PageRank - Part 2 (50 mins) <<<\n",
    "* **Session 3**. Tutorial on Topic-specific PageRank (50 mins)\n",
    "* **Session 4**. Tutorial on HITS (50 mins)\n",
    "\n",
    "We recommend fully understanding link analysis (or ranking) models such as PageRank, Topic-specific PageRank, and HITS before entering this tutorial since we will **NOT** explain the theoretical backgrounds on these techniques during the tutorial. \n",
    "We will mainly focus on how to implement the algorithms of those models and how to rank nodes in real-world graphs using those ranking models. \n",
    "\n",
    "The main contributor of this meterial is as follows:\n",
    "\n",
    "* Jinhong Jung (jinhongjung@snu.ac.kr)\n",
    "\n",
    "------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Session 2. Tutorial on PageRank - Part 2 (50 mins)\n",
    "In this session, we will explore how to implement PageRank in Python. \n",
    "The main goals of this session are summarized as follows:\n",
    "* **Goal 1.** How to implement PageRank based on sparse matrices using `numpy` and `scipy` in Python\n",
    "* **Goal 2.** How to handle the deadend issue in PageRank\n",
    "* **Goal 3.** To perform a qualitative analysis of the ranking result from PageRank in real-world networks\n",
    "\n",
    "The outline of this session is as follows:\n",
    "* **Step 1.** Introduction to sparse matrices\n",
    "* **Step 2.** Impelement PageRank - the sparse matrix version\n",
    "* **Step 3.** Running time comparison between the dense and sparse versions of PageRank\n",
    "* **Step 4.** Deadend handling and validation of the implementation of PageRank with the deadend handling\n",
    "* **Step 5.** Qualitative analysis of the ranking result from PageRank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the previous session, the problem of the dense matrix version of PageRank is to store all zero values in the adjacency matrix of the graph while most real-world networks are extremely sparse.\n",
    "Due to the problem, the time and space complexities of the previous implementation are $O(n^2)$ where $n$ is the number of nodes in the graph. \n",
    "In this session, we will build an efficient implementation of PageRank using `sparse` matrices which stores only non-zero values in the matrix. \n",
    "\n",
    "------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1. Introduction to sparse matrices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are various data structures for sparse matrices, e.g., compressed sparse column (CSC), compressed sparse row (CSR), coordinate list (COO), etc. \n",
    "Most data structures for sparse matrices aim to store only non-zero entries and their locations. \n",
    "The intuition behind this is that in fact, zero values in a matrix do not contribute to the result of an matrix operation at all. \n",
    "For example, consider the following (sparse) matrix vector multiplication: \n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0 & 2 & 0 \\\\\n",
    "2 & 0 & 0 \\\\\n",
    "0 & 0 & 2\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "2 \\\\\n",
    "3 \\\\\n",
    "4\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "0 \\times 2 + 2 \\times 2 + 0 \\times 2 \\\\\n",
    "2 \\times 3 + 0 \\times 3 + 0 \\times 3 \\\\\n",
    "0 \\times 4 + 0 \\times 4 + 2 \\times 4 \\\\\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "4 \\\\\n",
    "6 \\\\\n",
    "8\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "As you can see the example, we can ignore the zero values in the matrix vector multiplication, implying we do not need to store those zero values inside a data structure for sparse matrices. \n",
    "Also, this indicates we are able to do a matrix vector multiplication within $O(\\text{nnz}(\\mathbf{A}))$ time where $\\text{nnz}(\\mathbf{A})$ is the number of non-zeros in matrix $\\mathbf{A}$.\n",
    "\n",
    "In Python, we are able to achieve the purpose using `scipy` which provides various data structures for sparse matrices. \n",
    "We will use compressed sparse row (CSR, `csr_matrix` in `scipy`) to implement the sparse matrix version of PageRank. \n",
    "\n",
    "The details on CSR (e.g., how to store non-zero values) are out-of-scope for this tutorial. \n",
    "If you are interested in the details, you can refer to the below references:\n",
    "* Basic CSR data structure: http://netlib.org/linalg/html_templates/node91.html\n",
    "* Sparse matrix vector multiplication: https://www.it.uu.se/education/phd_studies/phd_courses/pasc/lecture-1\n",
    "\n",
    "------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 2. Implement PageRank - the sparse matrix version\n",
    "\n",
    "Let's implement the sparse matrix version of PageRank in this step. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 2-1. Set up requirements for this tutorial\n",
    "\n",
    "First of all, we will use several Python packages such as `numpy`, `scipy`, `pandas`, and `matplotlib`. \n",
    "As in the previous session, please check if those packages are installed in your local system. \n",
    "If you encounter error messages, please install required packages. \n",
    "If there is no any message, move to the next step. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "try:\n",
    "    import numpy\n",
    "except ImportError:\n",
    "    print(\"numpy is not installed, type pip install numpy\")\n",
    "\n",
    "try:\n",
    "    import scipy\n",
    "except ImportError:\n",
    "    print(\"scipy is not installed, type pip install scipy\")\n",
    "    \n",
    "try:\n",
    "    import matplotlib\n",
    "except ImportError:\n",
    "    print(\"matplotlib is not installed, type pip install matplotlib\")\n",
    "    \n",
    "try:\n",
    "    import pandas\n",
    "except ImportError:\n",
    "    print(\"pandas is not installed, type pip install pandas\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 2-2. Play with `csr_matrix` of `scipy`\n",
    "Let's construct `csr_matrix` with a simple example. Before going further, we need to import packages for this. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the below commands restrict the number of computation threads to 1\n",
    "import os\n",
    "os.environ[\"MKL_NUM_THREADS\"] = \"1\" \n",
    "os.environ[\"NUMEXPR_NUM_THREADS\"] = \"1\" \n",
    "os.environ[\"OMP_NUM_THREADS\"] = \"1\" \n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from scipy.sparse import csr_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following examples shows how to build a sparse matrix from an edge list. \n",
    "You can refer to the following link to check other examples: \n",
    "- https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csr_matrix.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Data stored in A:\n",
      "  (0, 1)\t1\n",
      "  (1, 2)\t1\n",
      "  (2, 3)\t1\n",
      "  (3, 1)\t1\n",
      "\n",
      "To dense matrix:\n",
      "[[0 1 0 0]\n",
      " [0 0 1 0]\n",
      " [0 0 0 1]\n",
      " [0 1 0 0]]\n"
     ]
    }
   ],
   "source": [
    "edges = [ [0, 1, 1],\n",
    "          [1, 2, 1],\n",
    "          [2, 3, 1],\n",
    "          [3, 1, 1] ]\n",
    "edges = np.asarray(edges)\n",
    "\n",
    "rows = edges[:, 0]\n",
    "cols = edges[:, 1]\n",
    "weights = edges[:, 2]\n",
    "\n",
    "A = csr_matrix((weights, (rows, cols)), shape=(4, 4))\n",
    "print(\"Data stored in A:\")\n",
    "print(A)\n",
    "\n",
    "print(\"\\nTo dense matrix:\")\n",
    "print(A.toarray())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 2-3. Implement the phase for loading the graph dataset\n",
    "\n",
    "In this step, we will implement the phase for loading the graph dataset of the spare matrix version of PageRank. \n",
    "First, let's import several packages used in the phase."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We briefly introduce several APIs used when implementing the below function which constructs the adjacency matrix of a graph.\n",
    "* `loadtxt`: this loads data from a text file\n",
    "    - https://docs.scipy.org/doc/numpy/reference/generated/numpy.loadtxt.html\n",
    "* `amax`: this returns the maximum of an array\n",
    "    - https://docs.scipy.org/doc/numpy/reference/generated/numpy.amax.html\n",
    "* `A.nnz`: this return the number of non-zeros of matrix `A`\n",
    "* slice: `edge[:, 0]` will return the first column of matrix `edge`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePageRank:\n",
    "    def load_graph_dataset(self, data_home, is_undirected=False):\n",
    "        '''\n",
    "        Load the graph dataset from the given directory (data_home)\n",
    "\n",
    "        inputs:\n",
    "            data_home: string\n",
    "                directory path conatining a dataset (edges.tsv, node_labels.tsv)\n",
    "            is_undirected: bool\n",
    "                if the graph is undirected\n",
    "        '''\n",
    "        # Step 1. set file paths from data_home\n",
    "        edge_path = \"{}/edges.tsv\".format(data_home)\n",
    "        \n",
    "        # Step 2. read the list of edges from edge_path\n",
    "        edges = np.loadtxt(edge_path, dtype=int)\n",
    "        n = int(np.amax(edges)) + 1\n",
    "        \n",
    "        # Step 3. convert the edge list to the adjacency matrix\n",
    "        rows = edges[:, 0]\n",
    "        cols = edges[:, 1]\n",
    "        weights = edges[:, 2]\n",
    "        self.A = csr_matrix((weights, (rows, cols)), shape=(n, n))\n",
    "        if is_undirected == True:\n",
    "            self.A = self.A + self.A.T\n",
    "        \n",
    "        # Step 5. set n (# of nodes) and m (# of edges)\n",
    "        self.n = self.A.shape[0]     # number of nodes\n",
    "        self.m = self.A.nnz          # number of edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePageRank(SparsePageRank):\n",
    "    def load_node_labels(self, data_home):\n",
    "        '''\n",
    "        Load the node labels from the given directory (data_home)\n",
    "\n",
    "        inputs:\n",
    "            data_home: string\n",
    "                directory path conatining a dataset\n",
    "        '''\n",
    "        label_path = \"{}/node_labels.tsv\".format(data_home)\n",
    "        self.node_labels = pd.read_csv(label_path, sep=\"\\t\")        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's check if the function is correctly implemented. \n",
    "We will used the same dataset at `./data/small` used in the previous session.\n",
    "Please run the below cell to check it. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The number n of nodes: 29\n",
      "The number m of edges: 376\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>node_id</th>\n",
       "      <th>label</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>male_noah</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>male_liam</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>male_william</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>male_benjamin</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>male_jacob</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   node_id            label\n",
       "0         0       male_noah\n",
       "1         1       male_liam\n",
       "2         2    male_william\n",
       "3         3   male_benjamin\n",
       "4         4      male_jacob"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "data_home = './data/small'\n",
    "spr = SparsePageRank()\n",
    "spr.load_graph_dataset(data_home, is_undirected=False)\n",
    "spr.load_node_labels(data_home)\n",
    "\n",
    "# print the number of nodes and edges\n",
    "print(\"The number n of nodes: {}\".format(spr.n))\n",
    "print(\"The number m of edges: {}\".format(spr.m))\n",
    "\n",
    "# print the heads (5) of the node labels\n",
    "display(spr.node_labels.head(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 2-4. Implement the normalization phase\n",
    "Next, we need the row-normalized adjacency matrix $\\mathbf{\\tilde{A}}$ of the adjacency matrix $\\mathbf{A}$. \n",
    "Note that we are implementing the phase based on sparse matrices. \n",
    "For the degree diagonal matrix $\\mathbf{D}$, we will use `spdiags` which is for a sparse diagonal matrix. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.sparse import spdiags"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As described in Session 1, we aim to implement the following operation in this phase: \n",
    "\n",
    "$$\\mathbf{\\tilde{A}} = \\mathbf{D}^{-1}\\mathbf{A}$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePageRank(SparsePageRank):\n",
    "    def normalize(self):\n",
    "        '''\n",
    "        Perform the row-normalization of the given adjacency matrix\n",
    "        '''\n",
    "        d = self.A.sum(axis=1) # since A is csr_matrix, the result of sum() is not a normal vector\n",
    "        d = np.asarray(d).flatten() # to make it vector\n",
    "        \n",
    "        d = np.maximum(d, np.ones(self.n))\n",
    "        invd = 1.0 / d\n",
    "        invD = spdiags(invd, 0, self.n, self.n)\n",
    "        \n",
    "        self.nA = invD.dot(self.A)\n",
    "        self.nAT = self.nA.T\n",
    "        \n",
    "        self.out_degrees = d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's check if the function is correctly implemented. \n",
    "As described in Session 1, the sum of each row of the row-normalized matrix $\\mathbf{\\tilde{A}}$ should be $1$. \n",
    "Hence, let's check if the sum of each row is $1$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "node:  0, out-degree: 14,  row_sum: 1.00\n",
      "node:  1, out-degree: 15,  row_sum: 1.00\n",
      "node:  2, out-degree: 17,  row_sum: 1.00\n",
      "node:  3, out-degree: 23,  row_sum: 1.00\n",
      "node:  4, out-degree: 27,  row_sum: 1.00\n",
      "node:  5, out-degree: 27,  row_sum: 1.00\n",
      "node:  6, out-degree: 12,  row_sum: 1.00\n",
      "node:  7, out-degree: 14,  row_sum: 1.00\n",
      "node:  8, out-degree: 16,  row_sum: 1.00\n",
      "node:  9, out-degree: 12,  row_sum: 1.00\n",
      "node: 10, out-degree: 14,  row_sum: 1.00\n",
      "node: 11, out-degree: 10,  row_sum: 1.00\n",
      "node: 12, out-degree: 13,  row_sum: 1.00\n",
      "node: 13, out-degree:  8,  row_sum: 1.00\n",
      "node: 14, out-degree:  9,  row_sum: 1.00\n",
      "node: 15, out-degree:  5,  row_sum: 1.00\n",
      "node: 16, out-degree:  6,  row_sum: 1.00\n",
      "node: 17, out-degree:  1,  row_sum: 1.00\n",
      "node: 18, out-degree:  6,  row_sum: 1.00\n",
      "node: 19, out-degree: 13,  row_sum: 1.00\n",
      "node: 20, out-degree: 15,  row_sum: 1.00\n",
      "node: 21, out-degree: 19,  row_sum: 1.00\n",
      "node: 22, out-degree: 12,  row_sum: 1.00\n",
      "node: 23, out-degree: 16,  row_sum: 1.00\n",
      "node: 24, out-degree: 11,  row_sum: 1.00\n",
      "node: 25, out-degree: 16,  row_sum: 1.00\n",
      "node: 26, out-degree: 15,  row_sum: 1.00\n",
      "node: 27, out-degree:  5,  row_sum: 1.00\n",
      "node: 28, out-degree:  5,  row_sum: 1.00\n"
     ]
    }
   ],
   "source": [
    "spr = SparsePageRank()\n",
    "spr.load_graph_dataset('./data/small', is_undirected=False)\n",
    "spr.normalize()\n",
    "\n",
    "# check the sum of each row in the row-normalized matrix nA\n",
    "row_sums = np.asarray(spr.nA.sum(axis=1)).flatten()\n",
    "for (i, degree, row_sum) in zip(range(spr.n), spr.out_degrees, row_sums):\n",
    "    print(\"node: {:2d}, out-degree: {:2d},  row_sum: {:.2f}\".format(i, int(degree), row_sum))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that `nA` is `csr_matrix`; hence, `nP.sum` returns a matrix. \n",
    "To convert it to a vector, we use `np.asarray` and `flatten` functions as above. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 2-5. Implement the iterative phase\n",
    "Now, let's implement the iterative phase of PageRank based on sparse matrices. \n",
    "After constructing the sparse matrix used in this phase, the implementation is the same with the one of the dense matrix version. \n",
    "Hence, you do not need to modify the code itself.\n",
    "\n",
    "For convenience, we provide the iterative algorithm in this cell again.\n",
    "\n",
    "<img src=\"./images/iterative-algorithm-pagerank.png\" width=\"400\">\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePageRank(SparsePageRank):\n",
    "    def iterate_PageRank(self, b=0.15, epsilon=1e-9, maxIters=100):\n",
    "        '''\n",
    "        Iterate the PageRank equation to obatin the PageRank score vector\n",
    "        \n",
    "        inputs:\n",
    "            b: float (between 0 and 1)\n",
    "                the teleport probability\n",
    "            epsilon : float\n",
    "                the error tolerance of the iteration\n",
    "            maxIters : int\n",
    "                the maximum number of iterations\n",
    "\n",
    "        outputs:\n",
    "            p: np.ndarray (n x 1 vector)\n",
    "                the final PageRank score vector\n",
    "            residuals: list\n",
    "                the list of residuals over the iteration\n",
    "\n",
    "        '''\n",
    "        q = np.ones(self.n)/self.n\n",
    "        old_p = q\n",
    "        residuals = []\n",
    "        \n",
    "        for t in range(maxIters):\n",
    "            p = (1 - b) * (self.nAT.dot(old_p)) + (b * q)\n",
    "            residual = np.linalg.norm(p - old_p, 1)\n",
    "            residuals.append(residual)\n",
    "            old_p = p\n",
    "            \n",
    "            if residual < epsilon:\n",
    "                break\n",
    "                \n",
    "        return p, residuals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's check the result of the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "node:  0, PageRank score: 0.0237\n",
      "node:  1, PageRank score: 0.0393\n",
      "node:  2, PageRank score: 0.0387\n",
      "node:  3, PageRank score: 0.0177\n",
      "node:  4, PageRank score: 0.0345\n",
      "node:  5, PageRank score: 0.0446\n",
      "node:  6, PageRank score: 0.0200\n",
      "node:  7, PageRank score: 0.0522\n",
      "node:  8, PageRank score: 0.0518\n",
      "node:  9, PageRank score: 0.0327\n",
      "node: 10, PageRank score: 0.0508\n",
      "node: 11, PageRank score: 0.0435\n",
      "node: 12, PageRank score: 0.0466\n",
      "node: 13, PageRank score: 0.0454\n",
      "node: 14, PageRank score: 0.0420\n",
      "node: 15, PageRank score: 0.0334\n",
      "node: 16, PageRank score: 0.0214\n",
      "node: 17, PageRank score: 0.0203\n",
      "node: 18, PageRank score: 0.0183\n",
      "node: 19, PageRank score: 0.0437\n",
      "node: 20, PageRank score: 0.0478\n",
      "node: 21, PageRank score: 0.0243\n",
      "node: 22, PageRank score: 0.0449\n",
      "node: 23, PageRank score: 0.0274\n",
      "node: 24, PageRank score: 0.0346\n",
      "node: 25, PageRank score: 0.0350\n",
      "node: 26, PageRank score: 0.0255\n",
      "node: 27, PageRank score: 0.0187\n",
      "node: 28, PageRank score: 0.0211\n"
     ]
    }
   ],
   "source": [
    "spr = SparsePageRank()\n",
    "spr.load_graph_dataset('./data/small', is_undirected=False)\n",
    "spr.normalize()\n",
    "\n",
    "p, residuals = spr.iterate_PageRank(b=0.15, epsilon=1e-9, maxIters=100)\n",
    "\n",
    "for (i, score) in zip(range(spr.n), p):\n",
    "    print(\"node: {:2d}, PageRank score: {:.4f}\".format(i, score))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 2-6. Comparison between the sparse and dense matrix versions. \n",
    "\n",
    "Let's compare the sparse matrix version to the dense version. \n",
    "The code for the dense matrix version are from the previous session. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !!! SHOULD NOT MODIFY THE BELOW CODES - JUST RUN !!!\n",
    "# This class is copied from the previous session\n",
    "class DensePageRank:\n",
    "    def load_graph_dataset(self, data_home, is_undirected=False):\n",
    "        '''\n",
    "        Load the graph dataset from the given directory (data_home)\n",
    "\n",
    "        inputs:\n",
    "            data_home: string\n",
    "                directory path conatining a dataset\n",
    "            is_undirected: bool\n",
    "                if the graph is undirected\n",
    "        '''\n",
    "        # Step 1. set file paths from data_home\n",
    "        edge_path = \"{}/edges.tsv\".format(data_home)\n",
    "\n",
    "        # Step 2. read the list of edges from edge_path\n",
    "        edges = np.loadtxt(edge_path, dtype=int)\n",
    "        n = int(np.amax(edges[:, 0:2])) + 1 # the current n is the maximum node id (starting from 0)\n",
    "\n",
    "        # Step 3. convert the edge list to the adjacency matrix\n",
    "        self.A = np.zeros((n, n))\n",
    "        for i in range(edges.shape[0]):\n",
    "            source, target, weight = edges[i, :]\n",
    "            self.A[(source, target)] = weight\n",
    "            if is_undirected:\n",
    "                self.A[(target, source)] = weight\n",
    "\n",
    "        # Step 4. set n (# of nodes) and m (# of edges)\n",
    "        self.n = n                         # number of nodes\n",
    "        self.m = np.count_nonzero(self.A)  # number of edges\n",
    "    \n",
    "    def normalize(self):\n",
    "        '''\n",
    "        Perform the row-normalization of the given adjacency matrix\n",
    "        '''\n",
    "        # Step 1. obatin the out-degree vector d\n",
    "        d = self.A.sum(axis = 1)           # row-wise summation\n",
    "\n",
    "        # Step 2. obtain the inverse of the out-degree matrix\n",
    "        d = np.maximum(d, np.ones(self.n)) # handles zero out-degree nodes, `maximum` perform entry-wise maximum \n",
    "        invd = 1.0 / d                # entry-wise division\n",
    "        invD = np.diag(invd)          # convert invd vector to a diagonal matrix\n",
    "\n",
    "        # Step 3. compute the row-normalized adjacency matrix\n",
    "        self.nA = invD.dot(self.A)   # nA = invD * A\n",
    "        self.nAT = self.nA.T         # nAT is the transpose of nA\n",
    "        \n",
    "        self.out_degrees = d\n",
    "    \n",
    "    def iterate_PageRank(self, b=0.15, epsilon=1e-9, maxIters=100):\n",
    "        '''\n",
    "        Iterate the PageRank equation to obatin the PageRank score vector\n",
    "\n",
    "        inputs:\n",
    "            b: float (between 0 and 1)\n",
    "                the teleport probability\n",
    "            epsilon : float\n",
    "                the error tolerance of the iteration\n",
    "            maxIters : int\n",
    "                the maximum number of iterations\n",
    "\n",
    "        outputs:\n",
    "            p: np.ndarray (n x 1 vector)\n",
    "                the final PageRank score vector\n",
    "            residuals: list\n",
    "                the list of residuals over the iteration\n",
    "        '''\n",
    "        q = np.ones(self.n)/self.n     # set the query vector q\n",
    "        old_p = q                 # set the previous PageRank score vector\n",
    "        residuals = []            # set the list for residuals over iterations\n",
    "\n",
    "        for t in range(maxIters):\n",
    "            p = (1-b)*(self.nAT.dot(old_p)) + b*q\n",
    "            residual = np.linalg.norm(p - old_p, 1)\n",
    "            residuals.append(residual)\n",
    "            old_p = p\n",
    "\n",
    "            if residual < epsilon:\n",
    "                break\n",
    "\n",
    "        return p, residuals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we are able to compare them. \n",
    "Let's compute the PageRank score vector from each version, and measure the error between them. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error between sparse and dense PageRank scores: 3.087808e-16\n"
     ]
    }
   ],
   "source": [
    "data_home = './data/small'\n",
    "\n",
    "spr = SparsePageRank()\n",
    "spr.load_graph_dataset(data_home, is_undirected=False)\n",
    "spr.normalize()\n",
    "p_spr, _ = spr.iterate_PageRank(b=0.15, epsilon=1e-9, maxIters=100)\n",
    "\n",
    "dpr = DensePageRank()\n",
    "dpr.load_graph_dataset(data_home, is_undirected=False)\n",
    "dpr.normalize()\n",
    "p_dpr, _ = dpr.iterate_PageRank(b=0.15, epsilon=1e-9, maxIters=100)\n",
    "\n",
    "error = np.linalg.norm(p_spr - p_dpr, 1)\n",
    "print(\"Error between sparse and dense PageRank scores: {:e}\".format(error))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the error between them is very small, indicating they are effectively equivalent. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 3. Running time comparison between the dense and sparse versions of PageRank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The reason why we implemented the sparse matrix version is that the dense version is not efficient. \n",
    "Let's empirically check the efficiency of the sparse matrix version. \n",
    "First, we need to import `time` package to measure wall-clock time. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The usage of `time` is simple as follows:\n",
    "\n",
    "```python\n",
    "start_time = time()\n",
    "... your codes\n",
    "run_time = time() - start_time # in seconds\n",
    "```\n",
    "\n",
    "Using `time`, let's measure the wall-clock time of the whole procedure of each version for a medium size of dataset at `./data/medium`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Running time of the sparse version: 0.1235 seconds\n",
      "Running time of the dense version : 4.6013 seconds\n"
     ]
    }
   ],
   "source": [
    "data_home = './data/medium'\n",
    "\n",
    "start_time = time()\n",
    "spr = SparsePageRank()\n",
    "spr.load_graph_dataset(data_home, is_undirected=False)\n",
    "spr.normalize()\n",
    "spr_p, _ = spr.iterate_PageRank(b=0.01, epsilon=1e-9, maxIters=1000)\n",
    "spr_run_time = time() - start_time\n",
    "print(\"Running time of the sparse version: {:.4f} seconds\".format(spr_run_time))\n",
    "\n",
    "start_time = time()\n",
    "dpr = DensePageRank()\n",
    "dpr.load_graph_dataset(data_home, is_undirected=False)\n",
    "dpr.normalize()\n",
    "dpr_p, _ = dpr.iterate_PageRank(b=0.01, epsilon=1e-9, maxIters=1000)\n",
    "dpr_run_time = time() - start_time\n",
    "\n",
    "print(\"Running time of the dense version : {:.4f} seconds\".format(dpr_run_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the running time of the dense version is much larger than that of the sparse version. \n",
    "From now on, we only use the sparse version to analyze large-scale real-world networks. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 4. Deaded handling and validation of the implementation of PageRank with the deaded handling \n",
    "\n",
    "When we compute the PageRank score vector in *directed* networks, there is one issue unresolved in the previous steps. \n",
    "The issue is called `deadend` issue where a deadend node is a node whose out-degree is zero (i.e., there are only in-coming links to the node). \n",
    "Before describing the deadend issue, let's check how many deadend nodes exist in a directed network. \n",
    "We will use `enron` dataset (at `./data/enron`) which is a directed network (we will describe the details on the dataset later). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The number n of nodes: 9958\n",
      "The number m of edges: 53116\n",
      "The number of deadend nodes: 5840\n"
     ]
    }
   ],
   "source": [
    "data_home = './data/enron'\n",
    "spr = SparsePageRank()\n",
    "spr.load_graph_dataset(data_home, is_undirected=False)\n",
    "spr.normalize()\n",
    "\n",
    "# count deadend nodes\n",
    "num_deadends = np.count_nonzero(spr.out_degrees == True)\n",
    "print(\"The number n of nodes: {}\".format(spr.n))\n",
    "print(\"The number m of edges: {}\".format(spr.m))\n",
    "print(\"The number of deadend nodes: {}\".format(num_deadends))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, nearly half of the nodes are deadend nodes ($5,840/9,958$). \n",
    "When a directed network contain deadend nodes, the problem is that PageRank scores are leaked out, i.e., the sum of the PageRank score vector will be less than $1.0$ (note that the PageRank score vector should be a probability distribution) since when a random surfer visits a deadend node, the surfer cannot escape from the node. \n",
    "The problem is called the deadend issue. \n",
    "The issue is easily checked by summing the PageRank score vector as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sum of the PageRank score vector: 0.42\n"
     ]
    }
   ],
   "source": [
    "p, _ = spr.iterate_PageRank(b=0.15, epsilon=1e-9, maxIters=300)\n",
    "\n",
    "print(\"The sum of the PageRank score vector: {:.2f}\".format(np.sum(p)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the sum of the PageRank score vector is less than $1$ indicating there is a score leak.\n",
    "For the deadend issue, you need to implement the following algorithm. \n",
    "\n",
    "<img src=\"./images/iterative-algorithm-pagerank-deadend.png\" width=\"400\">\n",
    "\n",
    "We will not explain the details on the solution, but using this, we will guarantee that the sum of the PageRank score is $1$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePageRank(SparsePageRank):\n",
    "    def iterate_PageRank(self, b=0.15, epsilon=1e-9, maxIters=100, handles_deadend=True):\n",
    "        '''\n",
    "        Iterate the PageRank equation to obatin the PageRank score vector\n",
    "        \n",
    "        inputs:\n",
    "            b: float (between 0 and 1)\n",
    "                the teleport probability\n",
    "            epsilon: float\n",
    "                the error tolerance of the iteration\n",
    "            maxIters: int\n",
    "                the maximum number of iterations\n",
    "            handles_deadend: bool\n",
    "                if it handles the deadend issue\n",
    "\n",
    "        outputs:\n",
    "            p: np.ndarray (n x 1 vector)\n",
    "                the final PageRank score vector\n",
    "            residuals: list\n",
    "                the list of residuals over the iteration\n",
    "\n",
    "        '''\n",
    "        q = np.ones(self.n)/self.n\n",
    "        old_p = q\n",
    "        residuals = []\n",
    "        \n",
    "        for t in range(maxIters):\n",
    "            if handles_deadend:\n",
    "                p = (1 - b) * (self.nAT.dot(old_p))\n",
    "                S = np.sum(p)\n",
    "                p = p + (1 - S) * q\n",
    "            else:\n",
    "                p = (1 - b) * (self.nAT.dot(old_p)) + (b * q)\n",
    "                \n",
    "            residual = np.linalg.norm(p - old_p, 1)\n",
    "            residuals.append(residual)\n",
    "            old_p = p\n",
    "            \n",
    "            if residual < epsilon:\n",
    "                break\n",
    "                \n",
    "        return p, residuals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's check the result of the modified iterative algorithm. \n",
    "Since we need to handle the deadend issues, we should set `handles_deadend` to `True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sum of the PageRank score vector: 1.00\n"
     ]
    }
   ],
   "source": [
    "data_home = './data/enron'\n",
    "spr = SparsePageRank()\n",
    "spr.load_graph_dataset(data_home, is_undirected=False)\n",
    "spr.normalize()\n",
    "p, _ = spr.iterate_PageRank(b=0.15, epsilon=1e-9, maxIters=100, handles_deadend=True)\n",
    "\n",
    "print(\"The sum of the PageRank score vector: {:.2f}\".format(np.sum(p)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 5. Qualitative analysis of the ranking result from PageRank\n",
    "\n",
    "In this step, we will perform a qualitative analysis of the ranking result from PageRank using a real-world graph. \n",
    "The dataset is `enron` dataset. \n",
    "This is a communication network of emails where nodes represent email addresses and directed edges represent email communications (e.g., for an edge $u \\rightarrow v$, $u$ sent $v$ an email).\n",
    "The statistics of the dataset is as follows:\n",
    "\n",
    "| Statistic | Value |\n",
    "| --- | --- |\n",
    "| $n$: the number of nodes | 9,958 |\n",
    "| $m$: the number of edges | 53,116|\n",
    "\n",
    "To perform the analysis, we implement a function for ranking nodes in the order of PageRank scores (in fact, we implemented this in the dense matrix version; hence, copy the codes)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePageRank(SparsePageRank):\n",
    "    def rank_nodes(self, ranking_scores, topk=-1):\n",
    "        '''\n",
    "        Rank nodes in the order of given ranking scores. \n",
    "        This function reports top-k rankings. \n",
    "\n",
    "        inputs:\n",
    "            ranking_scores: np.ndarray\n",
    "                ranking score vector\n",
    "            topk: int\n",
    "                top-k ranking parameter, default is -1 indicating report all ranks\n",
    "        '''\n",
    "        sorted_nodes = np.flipud(np.argsort(ranking_scores)) # argsort in the descending order\n",
    "        sorted_scores = ranking_scores[sorted_nodes]         # sort the ranking scores\n",
    "        ranks = range(1, self.n+1) # 0~n-1\n",
    "\n",
    "        result_labels = self.node_labels.iloc[sorted_nodes][0:topk]\n",
    "        result_labels.insert(0, \"rank\", ranks[0:topk])\n",
    "        result_labels[\"score\"] = sorted_scores[0:topk]\n",
    "        result_labels.reset_index(drop = True, inplace = True)\n",
    "        return result_labels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's rank nodes based on the PageRank score vector. Print the top-$10$ rankings since there are almost $10,000$ nodes, and thus it is hard to visually check all nodes in a cell.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>rank</th>\n",
       "      <th>node_id</th>\n",
       "      <th>address</th>\n",
       "      <th>score</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>1154</td>\n",
       "      <td>jeff.skilling@enron.com</td>\n",
       "      <td>0.008293</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>1692</td>\n",
       "      <td>kenneth.lay@enron.com</td>\n",
       "      <td>0.008103</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>156</td>\n",
       "      <td>louise.kitchen@enron.com</td>\n",
       "      <td>0.007959</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>97</td>\n",
       "      <td>sally.beck@enron.com</td>\n",
       "      <td>0.007420</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>733</td>\n",
       "      <td>tana.jones@enron.com</td>\n",
       "      <td>0.005536</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>2</td>\n",
       "      <td>john.lavorato@enron.com</td>\n",
       "      <td>0.005520</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>228</td>\n",
       "      <td>greg.whalley@enron.com</td>\n",
       "      <td>0.004613</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>259</td>\n",
       "      <td>vince.kaminski@enron.com</td>\n",
       "      <td>0.004450</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>671</td>\n",
       "      <td>sara.shackleton@enron.com</td>\n",
       "      <td>0.004368</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>1492</td>\n",
       "      <td>rod.hayslett@enron.com</td>\n",
       "      <td>0.004172</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   rank  node_id                    address     score\n",
       "0     1     1154    jeff.skilling@enron.com  0.008293\n",
       "1     2     1692      kenneth.lay@enron.com  0.008103\n",
       "2     3      156   louise.kitchen@enron.com  0.007959\n",
       "3     4       97       sally.beck@enron.com  0.007420\n",
       "4     5      733       tana.jones@enron.com  0.005536\n",
       "5     6        2    john.lavorato@enron.com  0.005520\n",
       "6     7      228     greg.whalley@enron.com  0.004613\n",
       "7     8      259   vince.kaminski@enron.com  0.004450\n",
       "8     9      671  sara.shackleton@enron.com  0.004368\n",
       "9    10     1492     rod.hayslett@enron.com  0.004172"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "data_home = './data/enron'\n",
    "spr = SparsePageRank()\n",
    "spr.load_graph_dataset(data_home, is_undirected=False)\n",
    "spr.load_node_labels(data_home)\n",
    "spr.normalize()\n",
    "p, _ = spr.iterate_PageRank(b=0.15, epsilon=1e-9, maxIters=100, handles_deadend=True)\n",
    "\n",
    "# display top-10 ranking in the order of PageRank scores\n",
    "display(spr.rank_nodes(p, topk=10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With only the ranking results, we do not know the owner and position of each e-mail address. \n",
    "In the raw data of `enron`, there is no information on the positions of employees. \n",
    "Fortunately, someones have already surveyed the positions of several custodians of the enron company. \n",
    "You can check the data at the following link:\n",
    "* https://github.com/enrondata/enrondata/blob/master/data/misc/edo_enron-custodians-data.tsv\n",
    "\n",
    "\n",
    "Based on the data, we summarize the ranking result in the following table:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| Rank | E-mail address | Name | Title |\n",
    "| --- | --- | --- | -- |\n",
    "| 1 | `jeff.skilling at enron.com` | Jeffery Skilling | Chief Executive Officer (CEO) |\n",
    "| 2 | `kenneth.lay at enron.com` | Kenneth Lay\t| Chief Executive Officer (CEO)  |\n",
    "| 3 | `louise.kitchen at enron.com` | Louise Kitchen | President, Enron Online |\n",
    "| 4 | `sally.beck at enron.com` | Sally Beck | Chief Operating Officer (COO) | \n",
    "| 5 | `tana.jones at enron.com` | Tana Jones | No Information (maybe manager) | \n",
    "| 6 | `john.lavorato at enron.com` | John Lavorato\t| Chief Executive Officer (CEO), Enron America |\n",
    "| 7 | `greg.whalley at enron.com` | Lawrence Greg Whalley | President |\n",
    "| 8 | `vince.kaminski at enron.com ` | Vince Kaminski | Manager, Risk Management Head | \n",
    "| 9 | `sara.shackleton at enron.com` | Sara Shackleton | No Information (maybe manager) |\n",
    "| 10 | `rod.hayslett at enron.com` | Rod Hayslett | Vice President, Chief Financial Officer (CFO)|\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that most nodes ranked high are senior officials such as CEO or COO at the company.\n",
    "There is no information of `Tana Jones` and `Sara Shackleton`, but there are in the custodian (manager) list, implying they are also senior officials. \n",
    "This result naturally follows our intuition since many managers frequently communicate with other employees, especially, they would received many e-mails from many other seniors as well as normal employees. \n",
    "That is why their PageRank scores are high since according to the mechanism of PageRank, more important nodes are likely to receive more links from other nodes. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Session 2. Summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this session, we implemented PageRank (the sparse matrix version) in Python. \n",
    "More specifically, we are able to answer the following goals now. \n",
    "* **Goal 1.** How to implement PageRank based on sparse matrices using `numpy` and `scipy` in Python\n",
    "    - We implemented the iterative algorithm for PageRank based on sparse matrices.\n",
    "* **Goal 2.** How to handle the deadend issue in PageRank\n",
    "    - We empirically check the deadend issue in a directed network, and implement the solution of the deadend issue.\n",
    "* **Goal 3.** To perform a qualitative analysis of the ranking result from PageRank in real-world networks\n",
    "    - We performed a qualitative analysis on the `enron` dataset which is a real-world network. \n"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}