Session 3. Tutorial on Topic-specific PageRank.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 3. Tutorial on Topic-specific PageRank (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 Topic-specific PageRank based on sparse matrices using `numpy` and `scipy` in Python\n",
    "* **Goal 2.** To perform a qualitative analysis of the ranking result from Topic-specific PageRank in real-world networks\n",
    "\n",
    "The outline of this session is as follows:\n",
    "* **Step 1.** Review Topic-specific PageRank\n",
    "* **Step 2.** Implement Topic-specific PageRank - the sparse matrix version\n",
    "* **Step 3.** Validate your Topic-specific PageRank implementation\n",
    "* **Step 4.** Qualitative analysis of the ranking result from Topic-specific PageRank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1. Review Topic-specific PageRank (a.k.a. Personalized PageRank)\n",
    "\n",
    "In this step, we will review Topic-specific PageRank. \n",
    "Note that Topic-specific PageRank is also known as Personalized PageRank (PPR) or Random Walk with Restart (RWR). \n",
    "The main purpose of Topic-specific PageRank is to obtain a ranking w.r.t. given topics (or seed nodes). \n",
    "Since the ranking result is bias to the given seed nodes, that's why it is called Personalized PageRank. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 1-1. Mathematical definition of Topic-specific PageRank\n",
    "The mathematical definition of Topic-specific PageRank is very similar to that of PageRank. \n",
    "\n",
    "##### Problem definition of Topic-specific PageRank (Personalized PageRank)\n",
    "* **Input**: adjacency matrix $\\mathbf{A} \\in \\mathbb{R}^{n \\times n}$ of a graph $G=(V, E)$, teleport probability $\\beta$, and set of seeds $S$\n",
    "* **Output**: the Personalized PageRank (PPR) score vector $\\mathbf{r} \\in \\mathbb{R}^{n}$ such that\n",
    "\n",
    "$$\\mathbf{r} = (1-\\beta)\\mathbf{\\tilde{A}}^{\\top}\\mathbf{r} + \\beta\\mathbf{q}$$\n",
    "\n",
    "- Note that the equation of PPR is the same with that of PageRank except for the query vector $\\mathbf{q}$\n",
    "    - $\\mathbf{q}$ is a query vector where $q_{s}=\\frac{1}{|S|}$ for $s \\in S$. For other node $u$, $q_{u} = 0$.\n",
    "    \n",
    "The definitions of adjacency matrix $\\mathbf{A}$ and row-normalized adjacency matrix $\\mathbf{\\tilde{A}}$ are the same (please see Session 1 if you want to check)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 2. Implement Topic-specific PageRank - the sparse matrix version\n",
    "\n",
    "We are going to implement the sparse matrix version of Topic-specific PageRank in Python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 2-1. Set up requirements for this tutorial\n",
    "\n",
    "As in the previous sessions, we first import required packages as follows:"
   ]
  },
  {
   "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. Implement the phase for loading the graph dataset\n",
    "In this step, we will implement the phase for loading the graph dataset of the sparse matrix version of Personalized PageRank. \n",
    "We first need to import the following 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",
    "from scipy.sparse import csr_matrix, find\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As in Session 2, we implement the following function.\n",
    "Note that we do not need to modify the function since the functionality in the version is the same with that of Session 2. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePPR:\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. self file paths from data_home\n",
    "        edge_path = \"{}/edges.tsv\".format(data_home)\n",
    "\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\n",
    "        \n",
    "        # Step 3. convert the edge list to the weighted 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 4. 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": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePPR(SparsePPR):\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 use the small dataset at `./data/small` as before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The number n of nodes: 29\n",
      "The number m of edges: 376\n"
     ]
    }
   ],
   "source": [
    "sppr = SparsePPR()\n",
    "sppr.load_graph_dataset('./data/small', is_undirected=False)\n",
    "print(\"The number n of nodes: {}\".format(sppr.n))\n",
    "print(\"The number m of edges: {}\".format(sppr.m))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 2-3. Implement the normalization phase"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "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",
    "\n",
    "Note that the function `normalize` of `SparsePPR` is also the same with that of `SparsePageRank` (Session 2).\n",
    "Hence, we use the same code from `SparsePageRank` as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePPR(SparsePPR):\n",
    "    def normalize(self):\n",
    "        '''\n",
    "        Perform the row-normalization of the given adjacency matrix\n",
    "\n",
    "        outputs:\n",
    "            nA: np.ndarray (n x n matrix) \n",
    "                the row-normalized adjacency matrix of the given graph\n",
    "            d: np.ndarray (n x 1 vector)\n",
    "                the out-degree vector\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": [
    "The debugging of the above function can be performed by using the following codes used in the previous sessions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "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": [
    "sppr = SparsePPR()\n",
    "sppr.load_graph_dataset('./data/small', is_undirected=False)\n",
    "sppr.normalize()\n",
    "\n",
    "# check the sum of each row in the row-normalized matrix nA\n",
    "row_sums = np.asarray(sppr.nA.sum(axis=1)).flatten()\n",
    "for (i, degree, row_sum) in zip(range(sppr.n), sppr.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": [
    "#### Step 2-4. Implement the iterative phase"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The implementation of the iterative phase of `SparsePPR` is almost the same of that of `SparsePageRank` except for how to treat a given seed nodes. \n",
    "For brevity, we assume the index of a seed is the range of node index. \n",
    "Also, we will consider the deadend issue as in Session 2. \n",
    "Based on those considerations, let's implement the iterative phase of `SparsePPR` using the following algorithm. \n",
    "\n",
    "<img src=\"./images/iterative-algorithm-ppr.png\" width=\"400\">\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePPR(SparsePPR):\n",
    "    def iterate_PPR(self, seeds, b=0.15, epsilon=1e-9, maxIters=100, handles_deadend=True):\n",
    "        '''\n",
    "        Iterate the Personalized PageRank equation to obatin the PageRank score vector\n",
    "        \n",
    "        inputs:\n",
    "            seeds: list\n",
    "                the set of seed nodes\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.zeros(self.n)\n",
    "        q[seeds] = 1.0/len(seeds)\n",
    "        old_r = q\n",
    "        residuals = []\n",
    "        \n",
    "        for t in range(maxIters):\n",
    "            if handles_deadend:\n",
    "                r = (1 - b) * (self.nAT.dot(old_r))\n",
    "                T = np.sum(r)\n",
    "                r = r + (1 - T) * q\n",
    "            else:\n",
    "                r = (1 - b) * (self.nAT.dot(old_r)) + (b * q)\n",
    "            \n",
    "            residual = np.linalg.norm(r - old_r, 1)\n",
    "            residuals.append(residual)\n",
    "            old_r = r\n",
    "            \n",
    "            if residual < epsilon:\n",
    "                break\n",
    "        \n",
    "        return r, residuals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's check the implementation is correctly performed. \n",
    "We will briefly check each personalized ranking result using `pandas`. \n",
    "See the following code where a seed node is given. \n",
    "Note that the given seed node should have a high ranking score. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "\n",
    "def rank_nodes(ranking_scores, topk=-1):\n",
    "    sorted_nodes = np.flipud(np.argsort(ranking_scores))\n",
    "    sorted_scores = ranking_scores[sorted_nodes]\n",
    "    ranking_results = pd.DataFrame()\n",
    "    ranking_results[\"node_id\"] = sorted_nodes\n",
    "    ranking_results[\"score\"] = sorted_scores\n",
    "    \n",
    "    return ranking_results[0:topk]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sum of the PageRank score vector: 1.00\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>score</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>0.167803</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>7</td>\n",
       "      <td>0.052067</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>10</td>\n",
       "      <td>0.050641</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>8</td>\n",
       "      <td>0.050335</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>12</td>\n",
       "      <td>0.047118</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>13</td>\n",
       "      <td>0.044279</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>11</td>\n",
       "      <td>0.043499</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>5</td>\n",
       "      <td>0.041696</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>14</td>\n",
       "      <td>0.041451</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>20</td>\n",
       "      <td>0.039476</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   node_id     score\n",
       "0        0  0.167803\n",
       "1        7  0.052067\n",
       "2       10  0.050641\n",
       "3        8  0.050335\n",
       "4       12  0.047118\n",
       "5       13  0.044279\n",
       "6       11  0.043499\n",
       "7        5  0.041696\n",
       "8       14  0.041451\n",
       "9       20  0.039476"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sppr = SparsePPR()\n",
    "sppr.load_graph_dataset('./data/small', is_undirected=False)\n",
    "sppr.normalize()\n",
    "\n",
    "seeds = [0]\n",
    "r, _ = sppr.iterate_PPR(seeds, b=0.15, epsilon=1e-9, maxIters=100)\n",
    "print(\"The sum of the PageRank score vector: {:.2f}\".format(np.sum(r)))\n",
    "display(rank_nodes(r, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's provide a set of seeds to compute the personalized ranking w.r.t. the seed set. \n",
    "In this case, each seed node in the set should have a high score compared to other nodes. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sum of the PageRank score vector: 1.00\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>score</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>2</td>\n",
       "      <td>0.084563</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>0.070871</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>0.066105</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>7</td>\n",
       "      <td>0.049072</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>10</td>\n",
       "      <td>0.047907</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>8</td>\n",
       "      <td>0.047486</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>12</td>\n",
       "      <td>0.044424</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>20</td>\n",
       "      <td>0.042643</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>11</td>\n",
       "      <td>0.041562</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>13</td>\n",
       "      <td>0.040164</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   node_id     score\n",
       "0        2  0.084563\n",
       "1        0  0.070871\n",
       "2        3  0.066105\n",
       "3        7  0.049072\n",
       "4       10  0.047907\n",
       "5        8  0.047486\n",
       "6       12  0.044424\n",
       "7       20  0.042643\n",
       "8       11  0.041562\n",
       "9       13  0.040164"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "seeds = [0, 2, 3]\n",
    "r, _ = sppr.iterate_PPR(seeds, b=0.15, epsilon=1e-9, maxIters=100)\n",
    "print(\"The sum of the PageRank score vector: {:.2f}\".format(np.sum(r)))\n",
    "display(rank_nodes(r, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 3. Validate your Topic-specific PageRank implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will validate the implementation of Topic-specific PageRank. \n",
    "Since the validation and implementation ways are the same, we do not repeat describing the details on this step (also, you do not need to fill the below cells).\n",
    "Let's run each cell and check the results."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 3-1. Check if the residual monotonically decrease"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "plt.rcParams.update({'font.size': 13}) # set the font-size in the figure\n",
    "\n",
    "def plot_residuals(residuals, title):\n",
    "    plt.semilogy(residuals, marker='o', markersize=5)\n",
    "    plt.title(title)\n",
    "    plt.ylim(bottom=1e-10, top=1e-0)\n",
    "    plt.ylabel('Residual')\n",
    "    plt.xlabel('# of iterations')\n",
    "    plt.grid(True)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZIAAAEWCAYAAABMoxE0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvqOYd8AAAIABJREFUeJzt3Xd8VfX9x/HXJyFhhT3C3ogMAQFFLWoQZ9WKrQttFcVRq9UObW1//Vn6a63WVffAhRut1dbVoqARFURAQBllygjIFGQFsj6/P86JvYTcDJLce5P7fj4eeeTeMz/fe07yuef7/Z7vMXdHRETkYKXEOwAREandlEhERKRKlEhERKRKlEhERKRKlEhERKRKlEhERKRKlEiqmZmNN7Pn4h1HVZhZQzN7w8y+MbO/xXC/vzWzx8uYv8rMTqyG/Yw1s48OYr1MM5tmZjvN7K6qxpFsSn7uZrbLzHpU8z6yzezy6txmIkuU/zdKJAfBzC40s9nhH8JXZvYvMxsR77iq0TlAJtDK3c8tOTM8efPD8m83s+lmdnRVd+ruf3b3RP4ncCWwBWjq7r+M9c7NbKKZ5YWf+9dm9q6ZHRrrOKqLu2e4+8pY7a+mztsK7HeVmeWG+90QHseMmt5vLCmRVJKZ/QK4B/gzwT/bLsBDwFnxjKuadQWWuntBGcu85O4ZQGvgfSBmVy5x1BVY5FHu4jWzejGI4fbwc+8EbAImVnYDMYozURWft22Aj4BXzcxisN8zw/0OBg4HfhODfcaMEkklmFkz4P+Aa9z9VXff7e757v6Gu98YsWi6mT0TVoEsNLNhEdu4ycxWhPMWmdnZEfPGmtlHZnanmW0zsy/N7LSI+d0jqlammNmDkZe1ZnZU+C1ru5nNN7OsMsrSN6wG2B7G+L1w+h+Am4Hzw29Q48r6TMJk8zzQ0czaRGz/DDObF/HNb2DEvF+b2bqwHEvMbFQ4fXyJ8vzIzFab2VYz+58S8U80sz9FvM8ys5yKfM4ltmNm9lcz22RmO8zsCzMbUMpyE4FLgF+Fn8uJYbyvmNlzZrYDGGtm9c3sHjNbH/7cY2b1I2M0s1+F+/vKzEab2XfNbGl4lfHbsj7viM99D/ACMCDcdkpEmbea2ctm1jKc183M3MzGmdka4D0zaxDGvTU8RrPMLDNcvoOZvR7Gs9zMroj4HMaH2670+V3KZ+pm1ivc366Inz1m5hHLXWZmi8O/iclm1jVi3klm9h8LqmEfACqUFNw9H3gaaAe0MrOeZvZe+HlsMbPnzax5xH6GmNncsFx/M7OXSpx/Uc/3EvvdAEwmSCjF654ebnuHma01s/ER84qP3SVmtiaM7X9K2TRmlmZmL5rZ380svSKfQ7Vxd/1U8Ac4FSgA6pWxzHhgL/BdIBW4FfgkYv65QAeCJH4+sBtoH84bC+QDV4TrXg2sByycPwO4E0gHRgA7gOfCeR2BreF+U4CTwvdtSokxDVgO/Dbc1gnATqBPRBmeK6eMxftNB24jqPKpF047nODb8vCwHJcAq4D6QB9gLdAhXLYb0LOU7fYDdgHHhevdHX72J4bzJwJ/iogpC8ipxOf8Ufj6FGAO0Jzgn1Df4uVKKXfJfY4Pj9focD8NCb5ofAK0JfjWOx34Y0SMBQSJOi08zpsJEkIToD+QC3Qvb/9ARrjeh+H768P9dgo/r0eBFyM+YweeARqHcV4FvAE0Co/RUIIqO4BpBFfZDQj+4W0GTqim8/ujiGUd6FVKOZ+PiP0sgnO1L1AP+B0wPZzXmuC8PSf8PH8efr6XV+C8rQ/cAawJ3/ci+JupHx63acA9Eef46vAzTgO+D+RFHIuo53s4fxX/PW87AV8A95Y4dw8LP7OBwEZgdIlj91h43AYB+4C+kWUK571FcI6kxvx/Y6x3WJt/gIuADeUsMx6YEvG+H5BbxvLzgLPC12OB5RHzGoUnUTuCKrQCoFHE/Oci/jB+DTxbYtuTgUtK2eexwAYgJWLai8D4iDKUl0jygO1AIUHCyoqY/zDhP8+IaUuA48M/2E3AiUBaKdstLs/NwKSIeY3DfVYokVTgcy5OJCcAS4GjIj+PKNsouc/xwLQSy6wAvhvx/hRgVUSMucV/6ATJw4HhEcvPIfwnEmX/e8PPfQPwOv9NwouBURHLtidIcvX47z+jHhHzLyNIcgNL7KNzeEybREy7FZhYTed3mYmE4DyeAzQM3/8LGBcxPwXYQ1DNeDH7JzEDcig7kRSft5uA94ChUZYdDcwNXx8HrCP8QhdO+4j/JpKo53v4ehXBl6KdYZmnAs3L+MzuAf4avi4+dp0i5n8KXBBRpteBD4D7ImOM5Y+qtipnK9Dayq9j3hDxeg/QoHgdM7s44hJ4O0HVROvS1vWg+gKCb58dgK8jpkHwzb5YV+Dc4u2G2x5B8A+lpA7AWncvipi2muCqpqJedvfmBO1ECwi+0UbG8ssSsXQmuApZDvyM4A9gk5lNMrMO0WIsfuPuuwk+/wqpwOdcvN33gAeAB8N4JphZ04ruh/2PQXHcqyPerw6nFdvq7oXh69zw98aI+bkExzuaO929ubu3c/fvufuKcHpX4LWI8i4mSAiZUWJ9luCLxqSwCu52M0vjv+fZzhJliDw3qnJ+R2VBNe71BIm0+LPpCtwbsb2vCRJGRw48R5wDj0dJL4efX1t3P8Hd54T7zgzPxXUWVFM+FxF3B2BduP1iJf/2Sj3fI5YZ7e5NCL5MHBr5mZjZcDN738w2m9k3wI858DMr+ZlHniNHEVzJ3FYixphRIqmcGQSXlaMPZuWwbvcx4FqCHlHNCf4JV6Re9yugpZk1ipjWOeL1WoIrkuYRP43d/bZStrUe6Gxmkce/C8G3rkpx9y0EvZnGm1lx0loL3FIilkbu/mK4zgvuPoLgD9CBv0Qp77flC8vdKmL+boIrtmLtIpat1Ofs7ve5+1CCb9eHADeWtlwUJf9w1xOUq1iXcFpNWwucVuIzb+Dukcf021g9aNv7g7v3A44BziD4hr+e4DxrUqIM5Z4bVTm/zawPQZvFee4e+U96LXBViXI1dPfpHHiOGPv/TVTGnwk+n8PcvSnww4i4vyJoA4wsR8m/vajneyR3/4DgyvLOiMkvEFxVdHb3ZsAjVLCtJ/QOwVXj1OJ2rlhTIqkEd/+GoMrlQQsaSRuFDVynmdntFdhEY4KTdTOAmV1K2FhagX2vBmYT/MNOt6Db4pkRizwHnGlmp5hZqgWNqVlm1qmUzc0k+FbzqzD+rHBbkyoSSymxLSH4dvurcNJjwI/Db1pmZo3DBsUmZtbHzE6woAF6L8E38KJSNvsKcIaZjQgbDv+P/c/XecB3zaylmbUjuMopVuHP2cyOCONMI0hOe6PEU1EvAr8zszZm1prgfIlFP/9HgFvCf+aE+4/ak9DMRprZYWaWStDWlg8Uhf/EpwO3hufQQGAcFSvDQZ3f4RXgP4H/cfeS9/c8AvzGzPqHyzYzs+Iu6W8B/c3s++EV0XVEfKGopCYE1U/fmFlH9v8yMYPg6u5aM6sXfq5HRsyPer5H2dc9wElmNihi31+7+14zOxK4sLLBu/vtBAlpanjexZQSSSW5+13ALwga/TYTfBu5FvhHBdZdBNxFcGJuJGhg+7gSu78IOJqgiudPwEsEV0iE/wDOImhAL47rRko5xu6eR5A4TiNoJH8IuNjd/1OJWEq6A7jSzNq6+2yChuQHgG0EjaVjw+Xq89/G+Q0EjdIHdIV094XANQR/HF+F28mJWORZYD5B/fM7BJ9F8bqV+ZybEvwj2EZQhbM1LMvB+hNBwv+coFH1s3BaTbuX4FvtO2a2k6DhfXgZy7cjSNY7CKrBPiD4TAHGENTNrwdeA37v7lPKC6AK5/cQgk4Yf7WI3lvhNl8juGKdFFY5LSA4b4uvhs8lOJ+2Ar0ruL/S/CGM4xuCBPVqRLnyCBrYxxG0r/wQeJP//u2Vdb4fwN03E3R8uDmc9BPg/8LjdjPw8sEUwN3/SPB/aIqFPfZipbg3kNRCZvYS8B93/328YxFJJmY2E3jE3Z+KdyyJQFcktUhYDdPTgnsGTiW4Ain3SkhEqsbMjjezdmHV1iUEjdv/jndciaJW3uFqZo0JqmPygGx3fz7OIcVKO4JL7lYE1TxXu/vc+IYkkhT6EFQ5NQZWAue4+1fxDSlxJEzVlpk9SdBzZJO7D4iYfipB/W8q8Li732ZmPwK2u/sbZvaSu58fn6hFRCSRqrYmEtw5/q2wR8mDBI1r/YAxZtaP4O7Q4i6ChYiISNwkTNWWu08zs24lJh9JcKf3SgAzm0TQLpBDkEzmESUZmtmVBPc30LBhw6GdOx9c9/I9Bc6+Aie3APKLoGNGCvUSKf1Wo6KiIlJS6mjhSkiWsiZLOSF5yhrLci5dunSLu7cpb7mESSRRdGT/O0hzCLo03gc8YGanE4wXdAB3nwBMABg2bJjPnj37oIPIzs6m16AjOeWv0xjStQXPXHYkFpMBQ2MrOzubrKyseIcRE8lS1mQpJyRPWWNZTjNbXf5SiVW1VWEejLp7qbtfHauG9k4tGnHTaYfy4bIt/G12TvkriIgkiURPJOvYfyiCThzEMB7V5aLhXTmye0v++NYiNu7YG68wREQSSqInkllAbwuew5EOXEBw925cpKQYf/nBQPIKivif1xaQKD3eRETiKWESiZm9SDC0Qh8LHv4zzoOHJl1LMI7TYoKROxfGM87urRtzw8l9mLJ4I298rm7kIiIJ09ju7mOiTH8beDvG4ZTpshHdefOLrxj/+kK+07MVrTLqxzskEZG4SZgrktokNcW445yB7Nybz/g3FsU7HBGRuFIiOUiHZDbhpyf05o3563ln4YbyVxARqaOUSKrg6qye9G3flN/9YwHf7MmPdzgiInGhRFIFaakp3HHOQLbuzuNPb6mKS0SSU8I0ttdWAzo246rjevBQ9go6tWiImdG/Q1Oy+rQlNaXu3f0uIlKSEkk1uGZkL576+EvumbIMgIbpqQzu3Jxnxw1XMhGROk9VW9Xgk5VbcQ8eVu3AnrxC5q3dTvaSTfEOTUSkximRVIOF63ewr6Bov2m5eYUsWr8jThGJiMSOEkk16N+hKQ3TU/eb1iAthX4dmsYpIhGR2FEiqQZZfdoyuHNzGqWnUtwiYmYM794qrnGJiMSCGturQWqK8ey44WQv2cSi9TsodOeeKcv4/esLufPcgXXy2SUiIsWUSKpJaooxqm8mo/pmAuAO905dxtCuLbhweJc4RyciUnNUtVVDrhvVm+MOacP41xfyec72eIcjIlJjlEhqSGqKce/5g2nTpD5XP/cZ23bnxTskEZEaoURSg1o0Tuehi4aweec+rn9pHoVFehCWiNQ9SiQ1bFDn5oz/Xn+mLd3M/e8ti3c4IiLVTokkBsYc2ZkfDOnEvVOX6W53EalzlEhiwMz40+gB9Mlsws9emsfar/fEOyQRkWqjRBIjDdNTeeSHQykscn7y/GfszS+Md0giItVCiSSGurVuzF3nDuKLdd/wBz2iV0TqCN2QGGMn92/H1Vk9eTh7BQ3qpdCicbqeXyIitZoSSRz8bFRvXpi5mqemr8LQ80tEpHZT1VYcfLR8C3kFwT0len6JiNR2SiRxsHD9jgMa2/X8EhGprZRI4qC055eYwSHtmsQpIhGRg6dEEgcln1+SnppCkcO7CzfgrmFURKR2UWN7HJR8fkm/Dk2Zt3Y797+3nI4tGvHzkw6Jd4giIhWmRBInJZ9fcsKhbdnwzV7unbqMDs0bcP4ReoaJiNQOSiQJwsz48/cPY+POffz2tQW0bdqAkX3axjssEZFyqY0kgaSlpvDQRUM4tF0Trnn+M77I+SbeIYmIlEuJJMFk1K/HU2OPoEWjdC6dOEsDPIpIwlMiSUBtmzbg6cuOIL+wiEue+pTte/R0RRFJXEokCapX2yY8dvEwcr7O5fKnZ2u0YBFJWEokCezI7i356/mDmb16Gz+bNJd3F23gvqnLmLp4ox7bKyIJo1b22jKz0cDpQFPgCXd/J84h1ZjTB7Zn3fZD+fPb/2HK4k0UFrkGeRSRhBLzKxIze9LMNpnZghLTTzWzJWa23MxuKmsb7v4Pd78C+DFwfk3Gmwh6tsmgXopRUOQa5FFEEk48qrYmAqdGTjCzVOBB4DSgHzDGzPqZ2WFm9maJn8ibK34XrlenLVy/44CqLA3yKCKJwuIxtpOZdQPedPcB4fujgfHufkr4/jcA7n5rlPUNuA14192nRFnmSuBKgMzMzKGTJk066Hh37dpFRkbGQa9fVfM2FfDw/H3si2hvTzG4dnB9hmRWX+1kvMsZS8lS1mQpJyRPWWNZzpEjR85x92HlLZcobSQdgbUR73OA4WUs/1PgRKCZmfVy90dKLuDuE4AJAMOGDfOsrKyDDi47O5uqrF9VxxY5n34zk3lrt5ObV0i9VCO/0FmY24yffGcIDdJSy99IBcS7nLGULGVNlnJC8pQ1EcuZKImkUtz9PuC+eMcRK6UN8pizbQ/j31jE2Kc+5bGLh9GkQVq8wxSRJJUoiWQd0DnifadwmoRKDvII0LxROr98eT4XPjaTiZceQauM+nGMUESSVaLcRzIL6G1m3c0sHbgAeD3OMSW8swZ3ZMLFQ1m6cSfnPTqD9dtz4x2SiCSheHT/fRGYAfQxsxwzG+fuBcC1wGRgMfCyuy+MdWy10QmHZvLsuOFs2rGPcx6ezorNu+IdkogkmZgnEncf4+7t3T3N3Tu5+xPh9Lfd/RB37+nut8Q6rtrsyO4tefHKo9hXUMR5j8xgwTqNGiwisZMoVVtSRQM6NuNvPz6aBmmpXPDoDB56f7mGUxGRmEiUxnapBj3aZPDSVUdx0t0fcPvkJRhoOBURqXG6IqljlmzYCQQJQ8OpiEgsKJHUMQvX7zhgyPk9Gk5FRGqQEkkd079DUxqmH3in+77CojhEIyLJQImkjsnq05bBnZvTKD312zaSjPqpPJK9nKmLN8Y7PBGpg9TYXseUNpzK4V1aMPapT7n6uc949EdDGXlo2/I3JCJSQboiqYOKh1P56ajejOqbScvG6Tx72XAOaZfBVc/OUcO7iFQrJZIk0axRGs+NG06vthlc+ewcpi3dHO+QRKSOUCJJIs0bpfP85cPp2SaDK56ZzUfLtsQ7JBGpA5RIkkyLxkEy6d66MeOensX05UomIlI1SiRJqGWYTLq1asxlT8/i42VbmLp4I/9cnqchVUSk0tRrK0m1yqjP81cM54JHZ/CjJ2eSnprCvoIiJq+ZqyFVRKRSdEWSxFpn1OcnI3vhDnsLijSkiogcFCWSJJez7cCHYeVqSBURqQQlkiRX2pAqKQZdWzeOU0QiUtsokSS5kkOqpKUahQ5/+ddi5q3dHu/wRKQWUCJJcsVDqtw/5nDO7p3GIz8cystXHQ0Y5z4yncc/XIm7enGJSHRKJPLtkCrf65nOqL6ZHNm9JW9dN4KsPm3501uLueKZ2WzfkxfvMEUkQSmRSKmaN0pnwo+GcvMZ/fhg6Wa+e++HzFn9dbzDEpEEpEQiUZkZl43ozt+vPoZ6qSmc9+gnPJy9gvyCIqYu3qhnwosIoBsSpQIGdmrOm9eN4Ka/f85f/v0fHv1gBfsKitibX6hnwouIrkikYpo2SOPBC4fww6O6sD03n9z8Qt3AKCKAEolUgpnRtkkDSl536AZGkeSmRCKVUtoNjA7MXr2NzTv3xScoEYkrJRKplAOeCZ+WSvtmDfho2WZG3pnNQ9nL2ZtfGO8wRSSG1NgulVLaM+Gz+rRl1dbd3Pr2f7j930t4/pM1/Pq0QzlzYHvM1AAvUtcpkUilFd/AOKpv5rfTerbJ4PFLhjF9+Rb++NZirntxLk99/CX/e0Y/BnVqTvaSTSxcv4P+YeJRDy+RukOJRKrVMb1a8+ZPR/D3OTnc8c4Svv/QdFpnpLN7XwF784vUXVikDlIbiVS71BTjvCM6k31DFmcObM+WXXnk5ut5JyJ1lRKJ1JjG9evRO7OJuguL1HFKJFKjonUX/mDpZjZ8szc+QYlItVIikRpVsrtwo/RUurRoyOc52xl1VzaPf7iSgsKieIcpIlVQaxvbzawx8AEw3t3fjHc8Urpo3YXXbcvl5tcX8Ke3FvPKnBxuOXsAQ7u2jHe4InIQYn5FYmZPmtkmM1tQYvqpZrbEzJab2U0V2NSvgZdrJkqpTsXdhX86qjej+maSmmJ0adWIp8YewSM/HMI3ufn84OEZ/PqVz9myc59GFhapZeJxRTIReAB4pniCmaUCDwInATnALDN7HUgFbi2x/mXAIGAR0CAG8UoNMTNOHdCeY3u34b6py3j8w5X8/bMcUszIL1RXYZHawuLxGFUz6wa86e4DwvdHE1RRnRK+/w2Au5dMIsXr3wI0BvoBucDZ7l5UYpkrgSsBMjMzh06aNOmg4921axcZGRkHvX5tEe9yTlmdz/OL84g8I+unwtWD6jO4bfV+54l3WWMlWcoJyVPWWJZz5MiRc9x9WHnLJUobSUdgbcT7HGB4tIXd/X8AzGwssKVkEgmXmQBMABg2bJhnZWUddHDZ2dlUZf3aIt7l/HzqMli8dL9p+wphDa25/vhB1TrcSrzLGivJUk5InrImYjkTJZEcFHefGO8YpPoUdxXek/ffQR8NePWzdazcvJvrT+xN1iFtNH6XSIJJlO6/64DOEe87hdMkiZTWVfioHq340+gBbN65j0ufmsXoBz/mvf9sJB5VsiJSujKvSMxsJ1DaX6wB7u5NqymOWUBvM+tOkEAuAC6spm1LLRGtq3BqinHesM68+lkOD7y/nMsmzmZgp2Zcd0Jvsvq04YOlmzUgpEgclZlI3L1Jde/QzF4EsoDWZpYD/N7dnzCza4HJBD21nnT3hdW9b0l8pY0sDJBeL4ULjuzCD4Z24rXP1vHA+8u5/JnZNE5PpaDIyStQLy+ReKlUG4mZtSWiy627r6nsDt19TJTpbwNvV3Z7klzSUlM474jOnD2kI39+azETp6/69pI5ckDIkolIRGpOhdpIzOx7ZrYM+JLgbvJVwL9qMC6RMqWlptCicfoB0/fkFfK+RhYWiamKNrb/ETgKWOru3YFRwCc1FpVIBZQ2ICTAc5+s4acvzmX11t1xiEok+VQ0keS7+1YgxcxS3P19oNybVERqUmm9vIZ3b8lPsnry7qINjLrrA37/zwVs2bUv3qGK1GkVbSPZbmYZwDTgeTPbBOjrnsRVWb28xh7TjXunLuO5mWt4ZU4Olx/bgyuO60HDtFSyl2zizeV5FGZuVC8vkWpQ0URyFrAX+DlwEdAM+L+aCkqkoqL18mrbtAG3nH0Y40Z05653lnLv1GU8O2MVzRqls3HHXnLzCpm8Zq56eYlUgwpVbbn7bncvdPcCd3/a3e8Lq7pEElqPNhk8eNEQ/nHNd2jbpAFfbtnNnrxCPfZXpBpVtNfWTjPbEf7sNbNCM9OzUqXWGNy5Oacd1u6Ax/7uyStk4TqdyiJVUdErkibu3jS8k70h8APgoRqNTKSaDejYrNReXn+bs5apizXsisjBqvRYWx74B3BKDcQjUmNK6+XVu20GZjDu6dmc/dB0Ply2WQlFpJIq1NhuZt+PeJtC0PV3b41EJFJDInt5vTV9PqcfM4isPm0pcufVz3K4b+pyfvTEpxzZvSU3nNyHoV1bkL1kk8bxEilHRXttnRnxuoDgzvazqj0akRpW3MsrdWM6WWFPr1SM84/owujDO/LSrLXc/95yznt0Bs0aprGvoJB9+RrHS6QsFUok7n5pTQciEm/166Vy8dHdOHdoZ37/zwW8PCfn23kax0skuvKGkb+f0oeRB8Ddr6v2iETirGF6Kp1aNgqelRAxfU9eIR8v36JEIlJCeY3ts4E5BCP+DgGWhT+DgQNHzBOpI6KN4zVx+ipu+vvnrN+eG4eoRBJTec8jeRrAzK4GRrh7Qfj+EeDDmg9PJD6Ke3jNW7ud3LxCGqan0r9DU/q2b8qkT9fy6mfruOioLlwzshetM+rHO1yRuKpoY3sLoCnwdfg+I5wmUieVNY7XVcf35L4py3hmxmpemrWWS7/TjSuP7UlGg3rq5SVJqaKJ5DZgrpm9T/CY3eOA8TUVlEgiiDaOV8fmDfnLOQO56vge/HXKMh58fwXPTF9Fi8b12bJr37dXMOrlJcmione2PwUMB14DXgWOLq72EklWPdpkcP+Yw3nruhH0aJPBmq/3aBwvSUplJhIzOzT8PQToAKwNfzqE00SSXv8OzRjVN7PUcby+WPdNXGISiaXyqrZ+AVwJ3FXKPAdOqPaIRGqh4l5ee/IK95v+wsw1dGvVmDMHdVAVl9RZ5fXaujL8PTI24YjUTqX18urashFF7vzspXk8lL2cX5zUh1P6Z2KmhCJ1S0XH2joX+Le77zSz3xHcU/JHd59bo9GJ1BLRenkZ8NYXX/HXd5fy4+fmcFjHZvzy5EM4/pA2FDnq5SV1QkV7bf2vu//NzEYAJwJ3AI8QNMCLCNF7eZ05qAOnDWjHq3PXce+UZYx9ahZHdG1Bbn4hK7fsVi8vqfUqOox8ccXv6cAEd38L3dkuUmH1UlM4b1hn3r8hiz+e1Z+lm3ayYP0O9fKSOqGiiWSdmT0KnA+8bWb1K7GuiITS66Xwo6O7cfHR3Q6Yl5tXyKL1elqj1D4VTQbnAZOBU9x9O9ASuLHGohKp44ofsBXJgY+Wb+HLLbvjE5TIQaroDYl7gE3AiHBSAcHgjSJyEEo+rbFhWiodmzdk3tptnHj3B/z6lc9Zp4EhpZaoaK+t3xM8FbEP8BSQBjwHfKfmQhOpu6L18tq6ex8Pvb+CF2au4bW567hweBd+MrInrRrXVw8vSVgV7bV1NnA48BmAu683syY1FpVIEiitl1fbJg0Y/73+XHFcD+6fuoxnP1nNpE/X0CqjPtt255Gbrx5ekngq2kaS5+5O+JwfM2tccyGJSMfmDbntBwOZ8ovjGdS5Oeu257InXz28JDFVNJG8HPbaam5mVwBTgMdrLiwRAejeujHf6dW61HG8Ps/ROF6SGCr6zPY7zewkYAdBO8nN7v5ujUYmIkD0cbwmTv+S1hnpnH9EF9LrqTe+xE+Fzz53f9fdb3T3G4CpZnZRDcYpu5PyAAAUE0lEQVQlIqGSPbwapacyoENTDmnbhP/950JOuCubv81eS0FhUbxDlSRV5hWJmTUFrgE6Aq8D74bvbwDmA8/XdIAiyS5aD68Ug2nLtnDn5CXc+MrnPPzBCn5x0iF8d0B7nGAcrzeX51GYuVG9vKRGlVe19SywDZgBXA78luAJiaPdfV4NxxaVmaUAfyR4/O9sPWRL6rpo43gdf0gbjuvdmskLN3L3u0u49oW5HNpuOQas/noPuXmFTF4zV728pEaVV7XVw93HuvujwBigH8Hd7QedRMzsSTPbZGYLSkw/1cyWmNlyM7upnM2cBXQC8oGcg41FpC4wM04d0I5/XX8c95w/mK2781i8YafG8ZKYKS+R5Be/cPdCIMfd91ZxnxOBUyMnmFkq8CBwGkGyGmNm/czsMDN7s8RPW4IG/+nu/gvg6irGI1InpKYYow/vyIVHdjlgnsbxkppUXtXWIDMrPvsMaBi+N8DdvWlld+ju08ysW4nJRwLL3X0lgJlNAs5y91uBM0puw8xygLzwbWHJ+eEyVxI83ZHMzEyys7MrG+q3du3aVaX1a4tkKSfU7bLatgLqp8K+iL8MB16duZymu9fQtWlq1HVrs7p8TCMlYjnLe0JirM64jgTPgi+WQ9nPOnkVuN/MjgWmlbaAu08AJgAMGzbMs7KyDjq47OxsqrJ+bZEs5YS6XdZji5xPv5m539MaW2fUZ8vuffx++l5OP6w9Pz/pEHq1zYh3qNWqLh/TSIlYzooOkZJQwkEkx8U7DpFEFNnL663p8zn9mEFk9WnLrn0FPP7hSp786Ev+teArzj68Ez87sTedWzaisMg1lpcctERJJOuAzhHvO4XTROQgFPfySt2YTlbY06tZwzR+eXIfxh7TjYezV/DMJ6t5ff46zh3WiaUbdrHoqx16WqMclES5HXYW0NvMuptZOnABwX0rIlLNWmXU53dn9GPajSM5b1hnJn26ltmrt6mXlxy0mCcSM3uR4L6UPmaWY2bj3L0AuJbg4VmLgZfdfWGsYxNJJu2aNeCWsw/j0u90P2CeenlJZcS8asvdx0SZ/jbwdozDEUl6x/RsxYufrtlvLC8Hvty6mz15BTRKT5QacElUiVK1JSJxUnIsrwZpKbRolMarn63juNuzeerjL9lXUGovexEgcRrbRSROoo3lNW/tNu6YvIQ/vLGIx6at5LpRvTlnaCfqper7p+xPiURESh3La2jXlrx4xVF8vHwrd7yzhJte/YJHPljBz8OBIact26zuwgIokYhIGcyMEb1b851erZiyeBN3vbOE6yfN4zfpX1BY5OQVFKm7sKiNRETKZ2ac1C+Tt687liuP60FuXiH7CorUXVgAJRIRqYSUFCOj/oEVGXvyCnl30cY4RCSJQIlERCql+NG/JU2atZaxT33KgnV6lnyyUSIRkUop7dG/R/Voya9O7cO8tds54/6PuPq5OSzbuDPeoUqMqLFdRColWnfh1BTjh0d15YkPv+SJj77k3ws3cPbgjlx7Qi++3LJbPbzqMCUSEam0aI/+bdogjZ+fdAiXHNONRz9YwcTpX/Lq3HXUSzEKi1w9vOooVW2JSLVr2Tid33y3L38+eyD1UoyCIv+2h9fcNerhVdcokYhIjVm3PZfCIt9vWm5+IROmreSb3Pwoa0lto0QiIjWmtB5eqSnGzC+/5ti/vMeD7y9n976COEUn1UWJRERqTGk9vIZ3b8kb147gyO4tuWPyEo67/X2e+OhL9uZrYMjaSo3tIlJjyurh9fglR/DZmm3c9c4S/vjmIh7/cCU/PaE33x/SkY+Xb1Evr1pEiUREalS0Hl4AQ7q04PnLj2L6ii3cOXkJv33tC/7wxkIcyNc4XrWGqrZEJO6O6dmav199DNeN6kVeYRF5GserVlEiEZGEYGbUS0kJHs8YYU9eIW99/hXuXvqKEndKJCKSMErr5WXAq3PXcd6jM5i5cmt8ApMyKZGISMIofRyvVvzhrP6s3rqH8yd8wo+emMn8tdvjHapEUGO7iCSMsnp5nT+sM8/OWM1D2cs568GPOblfJr84+RB6t21C9pJNvLk8j8LMjerlFQdKJCKSUKL18mqQlsoVx/XggiM78+RHq3j8w5Wces+HtM5IZ/e+AvbmFzF5zVz18ooDVW2JSK3SpEEa15/Ymw9/PZLTBrRjy648cvPVyyuelEhEpFZq3iidvu2bUvK6Y09eIbNWfR2XmJKVqrZEpNYq7uW1J2//4VWe/GgVZsZVx/WgeaP0OEWXPHRFIiK1Vmm9vIZ0ac4p/TN55IMVHPuX97lv6jJ2aWDIGqUrEhGptSJ7eb01fT6nHzPo215b12zYwd3vLOXud5cycfoqrj6+JxcO78InK7dqHK9qpkQiIrVacS+v1I3pZEX09Dq0XVMmXDyM+Wu3c+c7S7jl7cXcPvk/GJBfqKc1VidVbYlInTYoTBY3ntKHwiInr9DVw6uaKZGISFIoLHJKDte1J6+Qf8xdR1GRxvGqCiUSEUkK0cbxeuPzrzjzgY94/z+bNDDkQVIiEZGkUFoPr6N7tuLOcwayc28Bl06cxTmPzGDGCg0MWVlqbBeRpFDWOF5nHd6Rl2ev5f6pyxnz2CeM6NWaG07pw2Edm5G9ZJN6eZWjViYSM+sC3Ad8DSx199viHJKI1ALRxvFKS03houFd+cGQTjz3yWoeyl7B6Ac/pkWjNHLzC9mXr6c1liXmVVtm9qSZbTKzBSWmn2pmS8xsuZndVM5mDgNecffLgMNrLFgRSSoN0lK5/NgeTPvVSEYP7sC2Pfns1The5YpHG8lE4NTICWaWCjwInAb0A8aYWT8zO8zM3izx0xb4BBhnZu8B/45x/CJSx2XUr0ePNhmljuM1Qw/XOoDFo5eCmXUD3nT3AeH7o4Hx7n5K+P43AO5+a5T1bwA+dfdpZvaKu59TyjJXAlcCZGZmDp00adJBx7tr1y4yMjIOev3aIlnKCclT1mQpJ1R/WedtKuDh+fvYt/8wXqQAI7vU48yeaTSvH/vv4rE8piNHjpzj7sPKWy5R2kg6Amsj3ucAw8tY/t/AeDO7EFhV2gLuPgGYADBs2DDPyso66OCys7Opyvq1RbKUE5KnrMlSTqj+sh5b5Hz6zUzmrd1Obl4hDdNT6du+Kb3aNuaVOev4+KsiLjmmGz8+rictGsduYMhEPKaJkkgqxd0XAAdchYiIVJeyenldfXwv7pmylAnTVvLCJ2sYd2x3xo3oTqP0eknZyytREsk6oHPE+07hNBGRuInWy6tb68bcc8HhXJ3Vi7vfXcI9U5Yx8eMvadYonc079317BZMsvbwS5YbEWUBvM+tuZunABcDrcY5JRKRMfdo14dEfDeP1a79DxxaNWL11D3vyCpOul1c8uv++CMwA+phZjpmNc/cC4FpgMrAYeNndF8Y6NhGRgzGwU3NO6d+u1F5eC9Z9E5eYYinmVVvuPibK9LeBt2McjohItYj2tMYXPl1DjzYZnH5Ye1LqaBVXolRtiYjUaqWN5dWnXROaNqjHT1+cy+n3f8TUxRvr5MCQidLYLiJSq0Xr5QXwxvz1/HXKUsY9PZvDuzTnxpP7cEyv1hQWeZ3o5aVEIiJSTaL18hp9eEdOH9ieV+bkcN/UZVz4+EyO7tGSXfsKWbF5V63v5aWqLRGRGEhLTWHMkV14/4Ysbj6jHwvX7+CLdd/UiV5eSiQiIjHUIC2Vy0Z05+Kjux0wLzevkEXrd8Q+qCpSIhERiYPDuwQN85EcmLFyK2u/3hOfoA6SEomISByU7OXVMC2VDs0aMGvV15xwVzb/+48FbNyxN95hVoga20VE4iBaL6/NO/dx/3vLePHTNbw8e20wMOTxPWnWMI3sJZt4c3kehZkbE6qHlxKJiEiclNbLq12zBtxy9mFcdVxP7pm6lMc/XMnzn6ymReN0vt6dR25eIZPXzE2oHl6q2hIRSUBdWjXi7vMGM/lnx3FouybkbMtN2B5eSiQiIgmsd2YTju/TttRxvD7PSYxxvJRIREQSXPE4XiU9+8lqXpq1hoLCojhE9V9KJCIiCa60cbz6tW9Cp+YN+PXfv+Ckv07jn/PWUVQUn3G81NguIpLgInt4vTV9PqcfM4isPm1JMXh30Ubufncp10+ax8PZK/jlyX04sW9bipyYjeOlRCIiUgsU9/BK3ZhOVkQvr5P7t+PEvpm88fl67pmyjCuemc3ATs0oLHS+3Lo7JuN4qWpLRKSWS0kxzhrckXd/fhx/+cFh5GzLZeFXO2LWy0uJRESkjqiXmsL5R3Thh0d1OWBeTY7jpUQiIlLHDOp04DheDdNT6dehaY3sT4lERKSOKa2X1+DOzb990FZ1U2O7iEgdE20cL/XaEhGRCov2tMaaoKotERGpEiUSERGpEiUSERGpEiUSERGpEiUSERGpEiUSERGpEiUSERGpEiUSERGpEiUSERGpEiUSERGpEiUSERGpEiUSERGpEiUSERGpkoRPJGbWw8yeMLNXIqY1NrOnzewxM7sonvGJiCS7Gk0kZvakmW0yswUlpp9qZkvMbLmZ3VTWNtx9pbuPKzH5+8Ar7n4F8L1qDltERCqhpp9HMhF4AHimeIKZpQIPAicBOcAsM3sdSAVuLbH+Ze5e2tPqOwFfhK8LqzlmERGphBpNJO4+zcy6lZh8JLDc3VcCmNkk4Cx3vxU4o4KbziFIJvOIclVlZlcCV4Zvd5nZkspFv5/WwJYqrF9bJEs5IXnKmizlhOQpayzL2bUiC8XjCYkdgbUR73OA4dEWNrNWwC3A4Wb2mzDhvAo8YGanA2+Utp67TwAmVEfAZjbb3YdVx7YSWbKUE5KnrMlSTkiesiZiORP+UbvuvhX4cYlpu4FL4xORiIhEikevrXVA54j3ncJpIiJSC8UjkcwCeptZdzNLBy4AXo9DHJVRLVVktUCylBOSp6zJUk5InrImXDnN3Wtu42YvAlkEjUMbgd+7+xNm9l3gHoKeWk+6+y01FoSIiNSoGk0kIiJS9yX8ne0iIpLYlEjKUJk78Gs7M1tlZl+Y2Twzmx3veKpLaaMrmFlLM3vXzJaFv1vEM8bqEqWs481sXXhc54XVyrWamXU2s/fNbJGZLTSz68Ppde64llHWhDquqtqKIrwDfykRd+ADY9x9UVwDqyFmtgoY5u516oYuMzsO2AU84+4Dwmm3A1+7+23hF4QW7v7reMZZHaKUdTywy93vjGds1cnM2gPt3f0zM2sCzAFGA2OpY8e1jLKeRwIdV12RRPftHfjungdMAs6Kc0xSSe4+Dfi6xOSzgKfD108T/GHWelHKWue4+1fu/ln4eiewmOBG5zp3XMsoa0JRIomutDvwE+4AViMH3jGzOeHwMnVZprt/Fb7eAGTGM5gYuNbMPg+rvmp9dU+kcAimw4GZ1PHjWqKskEDHVYlEio1w9yHAacA1YTVJnedB3W5drt99GOgJDAa+Au6KbzjVx8wygL8DP3P3HZHz6tpxLaWsCXVclUiiS6o78N19Xfh7E/AaQdVeXbUxrHsuroMubYTpOsHdN7p7obsXAY9RR46rmaUR/GN93t1fDSfXyeNaWlkT7bgqkURXG+/APyjhg8KaFL8GTgYWlL1WrfY6cEn4+hLgn3GMpUYV/2MNnU0dOK5mZsATwGJ3vztiVp07rtHKmmjHVb22ypAsd+CbWQ+CqxAIBvJ8oa6UtbTRFYB/AC8DXYDVwHnuXusbqaOUNYug+sOBVcBVEe0ItZKZjQA+JHgmUVE4+bcEbQd16riWUdYxJNBxVSIREZEqUdWWiIhUiRKJiIhUiRKJiIhUiRKJiIhUiRKJiIhUiRKJJDUzu9XMRprZaDP7TSXXbWNmM81srpkdW2Le42bWL3z922qOeayZdShtXyLxoO6/ktTM7D3gdODPwCvu/nEl1r0AONHdLy9nuV3unlHJuFLdvTDKvGzgBnevM8P9S+2mKxJJSmZ2h5l9DhwBzAAuBx42s5tLWbabmb0XDpA31cy6mNlg4HbgrPB5EA1LrJNtZsPM7DagYbjM8+G8H5rZp+G0R8NHFmBmu8zsLjObDxxtZjeb2SwzW2BmEyxwDjAMeL54v8X7CrcxxoLnyiwws79ExLPLzG4xs/lm9omZZYbTzw2XnW9m06r/k5ak4O760U9S/hAkkfuBNODjMpZ7A7gkfH0Z8I/w9VjggSjrZBM83wWC50YUT+8bbi8tfP8QcHH42gnuxi5etmXE62eBM0tuO/I90AFYA7QhGKHgPWB0xLaL178d+F34+gugY/i6ebyPiX5q54+uSCSZDQHmA4cSPOchmqOBF8LXzwIjqrDPUcBQYJaZzQvf9wjnFRIMzldsZNgG8wVwAtC/nG0fAWS7+2Z3LwCeB4pHcc4D3gxfzwG6ha8/Biaa2RUEQwGJVFq9eAcgEmthtdREghGdtwCNgsk2Dzja3XNrcvfA0+5eWsP+Xg/bRcysAcHVyjB3Xxs+6bBBFfab7+7FDaKFhH/77v5jMxtO0E40x8yGuvvWKuxHkpCuSCTpuPs8dx9M8CjlfgRVQKe4++AoSWQ6wejPABcRDKJXGfnhUOAAU4FzzKwtfPuc8a6lrFOcNLaEz6I4J2LeTqBJKet8ChxvZq3DdpcxwAdlBWZmPd19prvfDGxm/0cniFSIrkgkKZlZG2CbuxeZ2aHuvqiMxX8KPGVmNxL8s720krubAHxuZp+5+0Vm9juCp1GmAPnANQSj1X7L3beb2WMEw4NvIHisQbGJwCNmlktQ7Va8zlcWPKv8fYIrn7fcvbyh1O8ws97h8lMJqvpEKkXdf0VEpEpUtSUiIlWiRCIiIlWiRCIiIlWiRCIiIlWiRCIiIlWiRCIiIlWiRCIiIlXy/+gk0BzXykyYAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "seeds = [0, 2, 3]\n",
    "r, residuals = sppr.iterate_PPR(seeds, b=0.15, epsilon=1e-9, maxIters=100)\n",
    "\n",
    "plot_residuals(residuals, 'Change of Residuals from Personalized PageRank')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 3-2. Check if the iterative solution is equal to the exact solution of Personalized PageRank\n",
    "\n",
    "The closed form of the equation of PPR is the same with that of PageRank. \n",
    "Let's see the final closed equation of PPR. \n",
    "\n",
    "$$\n",
    "\\mathbf{r} = \\beta\\left(\\mathbf{I} - (1-\\beta)\\mathbf{\\tilde{A}}^{\\top}\\right)^{-1}\\mathbf{q} \\\\\n",
    "$$\n",
    "\n",
    "To implement the function for the exact solution, we just need to handle the query vector $\\mathbf{q}$ in the previous code. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePPR(SparsePPR):\n",
    "    def compute_exact_PPR(self, seeds, b=0.15):\n",
    "        '''\n",
    "        Compute the exact PageRank score vector from the closed form\n",
    "\n",
    "        inputs:\n",
    "            b: float (between 0 and 1)\n",
    "                the teleport probability\n",
    "        outputs:\n",
    "            p: np.ndarray (n x 1 vector)\n",
    "                the final PageRank score vector\n",
    "        '''\n",
    "        q = np.zeros(self.n)\n",
    "        q[seeds] = 1.0/len(seeds)\n",
    "\n",
    "        H = np.eye(self.n) - (1.0 - b)*self.nAT\n",
    "        invH = np.linalg.inv(H)\n",
    "\n",
    "        r = b*(invH.dot(q))\n",
    "\n",
    "        return np.asarray(r).flatten()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's check the error between the exact and iterative solutions of Personalized PageRank. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error between exact and iterative PPR scores: 9.668796e-10\n"
     ]
    }
   ],
   "source": [
    "sppr = SparsePPR()\n",
    "sppr.load_graph_dataset('./data/small', is_undirected=False)\n",
    "sppr.normalize()\n",
    "\n",
    "seeds = [0, 2, 3]\n",
    "r_exact = sppr.compute_exact_PPR(seeds, b=0.15)\n",
    "r_iter, _ = sppr.iterate_PPR(seeds, b=0.15, epsilon=1e-9, maxIters=100)\n",
    "\n",
    "error = np.linalg.norm(r_exact - r_iter, 1)\n",
    "print(\"Error between exact and iterative PPR scores: {:e}\".format(error))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 4. Qualitative analysis of the ranking result from Topic-specific PageRank\n",
    "\n",
    "In this step, we will explore a user-item network based on the ranking results of Topic-specific PageRank. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 4-0.  Description of a dataset used in this analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We briefly describe the dataset used in this analysis.\n",
    "The name of the dataset is *movielens-100k* which is an undirected network of movie rating data. \n",
    "Each node represents a *user* or *movie*, and an weighted edge between user $u$ and movie $i$ indicates a rating (the weighted of the edge) that the user rates the movie, which is ranged between $1$ and $5$. \n",
    "The dataset is located at `./data/movielens-100k`. \n",
    "The statistics of the dataset is as follows:\n",
    "\n",
    "| Statistic | Value |\n",
    "| --- | --- |\n",
    "| $n$: the number of nodes | 2,625 |\n",
    "| $m$: the number of edges | 100,000 |\n",
    "| the range of ratings | 1 ~ 5 |\n",
    "| the number of users | 943 |\n",
    "| the number of movies | 1,682 |\n",
    "\n",
    "Also, each user or movie has its attributes. \n",
    "A user has `name`, `gender`, `age` and `job`. \n",
    "A movie has `name` and `genres`. \n",
    "Those attributes are aggregated at one file called `node_labels.tsv` for brevity. \n",
    "Let's load and check the dataset. \n",
    "Note that the graph is undirected "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The number n of nodes: 2625\n",
      "The number m of edges: 200000\n",
      "\n",
      "The top-5 heads of the node labels:\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>type</th>\n",
       "      <th>name</th>\n",
       "      <th>gender/genres</th>\n",
       "      <th>age</th>\n",
       "      <th>job</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>user</td>\n",
       "      <td>james</td>\n",
       "      <td>M</td>\n",
       "      <td>24.0</td>\n",
       "      <td>technician</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>user</td>\n",
       "      <td>patricia</td>\n",
       "      <td>F</td>\n",
       "      <td>53.0</td>\n",
       "      <td>other</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>user</td>\n",
       "      <td>robert</td>\n",
       "      <td>M</td>\n",
       "      <td>23.0</td>\n",
       "      <td>writer</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>user</td>\n",
       "      <td>michael</td>\n",
       "      <td>M</td>\n",
       "      <td>24.0</td>\n",
       "      <td>technician</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>user</td>\n",
       "      <td>elizabeth</td>\n",
       "      <td>F</td>\n",
       "      <td>33.0</td>\n",
       "      <td>other</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   node_id  type       name gender/genres   age         job\n",
       "0        0  user      james             M  24.0  technician\n",
       "1        1  user   patricia             F  53.0       other\n",
       "2        2  user     robert             M  23.0      writer\n",
       "3        3  user    michael             M  24.0  technician\n",
       "4        4  user  elizabeth             F  33.0       other"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "The bottom-5 tails of the node labels:\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>type</th>\n",
       "      <th>name</th>\n",
       "      <th>gender/genres</th>\n",
       "      <th>age</th>\n",
       "      <th>job</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>2620</th>\n",
       "      <td>2620</td>\n",
       "      <td>movie</td>\n",
       "      <td>Mat' i syn (1997)</td>\n",
       "      <td>drama</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2621</th>\n",
       "      <td>2621</td>\n",
       "      <td>movie</td>\n",
       "      <td>B. Monkey (1998)</td>\n",
       "      <td>romance;thriller</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2622</th>\n",
       "      <td>2622</td>\n",
       "      <td>movie</td>\n",
       "      <td>Sliding Doors (1998)</td>\n",
       "      <td>drama;romance</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2623</th>\n",
       "      <td>2623</td>\n",
       "      <td>movie</td>\n",
       "      <td>You So Crazy (1994)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2624</th>\n",
       "      <td>2624</td>\n",
       "      <td>movie</td>\n",
       "      <td>Scream of Stone (Schrei aus Stein) (1991)</td>\n",
       "      <td>drama</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      node_id   type                                       name  \\\n",
       "2620     2620  movie                          Mat' i syn (1997)   \n",
       "2621     2621  movie                           B. Monkey (1998)   \n",
       "2622     2622  movie                       Sliding Doors (1998)   \n",
       "2623     2623  movie                        You So Crazy (1994)   \n",
       "2624     2624  movie  Scream of Stone (Schrei aus Stein) (1991)   \n",
       "\n",
       "         gender/genres  age  job  \n",
       "2620             drama  NaN  NaN  \n",
       "2621  romance;thriller  NaN  NaN  \n",
       "2622     drama;romance  NaN  NaN  \n",
       "2623            comedy  NaN  NaN  \n",
       "2624             drama  NaN  NaN  "
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "data_home = './data/movielens-100k'\n",
    "sppr = SparsePPR()\n",
    "sppr.load_graph_dataset(data_home, is_undirected=True)\n",
    "sppr.load_node_labels(data_home)\n",
    "\n",
    "print(\"The number n of nodes: {}\".format(sppr.n))\n",
    "print(\"The number m of edges: {}\".format(sppr.m))\n",
    "\n",
    "# print the heads (5) of the node labels\n",
    "print('\\nThe top-5 heads of the node labels:')\n",
    "display(sppr.node_labels.head(5))\n",
    "\n",
    "# print the tails (5) of the node labels\n",
    "print('\\nThe bottom-5 tails of the node labels:')\n",
    "display(sppr.node_labels.tail(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 4-1.  Qualitative analysis on a personalized ranking w.r.t. a specific user. \n",
    "\n",
    "Now, we will do a qualitative analysis on a personalized ranking w.r.t. a specific user. \n",
    "Before looking into the personalized ranking, we need to check the user's watch history to figure out characteristics of the user. \n",
    "The following code reports the user's demography information ans watch history. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePPR(SparsePPR):\n",
    "    def show_user_history(self, user_id):\n",
    "        print(\"user_id: {}, demographic infomration:\".format(user_id))\n",
    "        display(self.node_labels.iloc[[user_id]])\n",
    "        _, movie_ids, ratings = find(self.A[user_id, :])\n",
    "        movie_labels = self.node_labels.iloc[movie_ids]\n",
    "        movie_labels.insert(0, \"rating\", ratings)\n",
    "        print(\"user_id: {}, watch history:\".format(user_id))\n",
    "        movie_labels = movie_labels[[\"node_id\", \"type\", \"name\", \"gender/genres\", \"rating\"]]\n",
    "        display(movie_labels.sort_values(by=[\"rating\"], ascending=False))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our target user's node id is `500`, and his watch history is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "user_id: 500, demographic infomration:\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>type</th>\n",
       "      <th>name</th>\n",
       "      <th>gender/genres</th>\n",
       "      <th>age</th>\n",
       "      <th>job</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>500</th>\n",
       "      <td>500</td>\n",
       "      <td>user</td>\n",
       "      <td>emil</td>\n",
       "      <td>M</td>\n",
       "      <td>22.0</td>\n",
       "      <td>student</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     node_id  type  name gender/genres   age      job\n",
       "500      500  user  emil             M  22.0  student"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "user_id: 500, watch history:\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>type</th>\n",
       "      <th>name</th>\n",
       "      <th>gender/genres</th>\n",
       "      <th>rating</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1092</th>\n",
       "      <td>1092</td>\n",
       "      <td>movie</td>\n",
       "      <td>Swingers (1996)</td>\n",
       "      <td>comedy;drama</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2039</th>\n",
       "      <td>2039</td>\n",
       "      <td>movie</td>\n",
       "      <td>Hate (Haine, La) (1995)</td>\n",
       "      <td>drama</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2009</th>\n",
       "      <td>2009</td>\n",
       "      <td>movie</td>\n",
       "      <td>Bottle Rocket (1996)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1069</th>\n",
       "      <td>1069</td>\n",
       "      <td>movie</td>\n",
       "      <td>Godfather, The (1972)</td>\n",
       "      <td>action;crime;drama</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1417</th>\n",
       "      <td>1417</td>\n",
       "      <td>movie</td>\n",
       "      <td>Trainspotting (1996)</td>\n",
       "      <td>drama</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1683</th>\n",
       "      <td>1683</td>\n",
       "      <td>movie</td>\n",
       "      <td>Last Supper, The (1995)</td>\n",
       "      <td>drama;thriller</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1352</th>\n",
       "      <td>1352</td>\n",
       "      <td>movie</td>\n",
       "      <td>Kingpin (1996)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1486</th>\n",
       "      <td>1486</td>\n",
       "      <td>movie</td>\n",
       "      <td>Things to Do in Denver when You're Dead (1995)</td>\n",
       "      <td>crime;drama;romance</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1450</th>\n",
       "      <td>1450</td>\n",
       "      <td>movie</td>\n",
       "      <td>People vs. Larry Flynt, The (1996)</td>\n",
       "      <td>drama</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1353</th>\n",
       "      <td>1353</td>\n",
       "      <td>movie</td>\n",
       "      <td>Nutty Professor, The (1996)</td>\n",
       "      <td>comedy;fantasy;romance;sci-fi</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>949</th>\n",
       "      <td>949</td>\n",
       "      <td>movie</td>\n",
       "      <td>Twelve Monkeys (1995)</td>\n",
       "      <td>drama;sci-fi</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1488</th>\n",
       "      <td>1488</td>\n",
       "      <td>movie</td>\n",
       "      <td>Broken Arrow (1996)</td>\n",
       "      <td>action;thriller</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1311</th>\n",
       "      <td>1311</td>\n",
       "      <td>movie</td>\n",
       "      <td>Black Sheep (1996)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1284</th>\n",
       "      <td>1284</td>\n",
       "      <td>movie</td>\n",
       "      <td>Man Who Knew Too Little, The (1997)</td>\n",
       "      <td>comedy;mystery</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1266</th>\n",
       "      <td>1266</td>\n",
       "      <td>movie</td>\n",
       "      <td>Lost Highway (1997)</td>\n",
       "      <td>mystery</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>955</th>\n",
       "      <td>955</td>\n",
       "      <td>movie</td>\n",
       "      <td>Mighty Aphrodite (1995)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1249</th>\n",
       "      <td>1249</td>\n",
       "      <td>movie</td>\n",
       "      <td>Devil's Advocate, The (1997)</td>\n",
       "      <td>crime;horror;mystery;thriller</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1347</th>\n",
       "      <td>1347</td>\n",
       "      <td>movie</td>\n",
       "      <td>Mission: Impossible (1996)</td>\n",
       "      <td>action;adventure;mystery</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1570</th>\n",
       "      <td>1570</td>\n",
       "      <td>movie</td>\n",
       "      <td>Sleepers (1996)</td>\n",
       "      <td>crime;drama</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1533</th>\n",
       "      <td>1533</td>\n",
       "      <td>movie</td>\n",
       "      <td>Primal Fear (1996)</td>\n",
       "      <td>drama;thriller</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1235</th>\n",
       "      <td>1235</td>\n",
       "      <td>movie</td>\n",
       "      <td>Donnie Brasco (1997)</td>\n",
       "      <td>crime;drama</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1638</th>\n",
       "      <td>1638</td>\n",
       "      <td>movie</td>\n",
       "      <td>City Hall (1996)</td>\n",
       "      <td>drama;thriller</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1782</th>\n",
       "      <td>1782</td>\n",
       "      <td>movie</td>\n",
       "      <td>Last Man Standing (1996)</td>\n",
       "      <td>action;drama;western</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1786</th>\n",
       "      <td>1786</td>\n",
       "      <td>movie</td>\n",
       "      <td>Freeway (1996)</td>\n",
       "      <td>crime</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1864</th>\n",
       "      <td>1864</td>\n",
       "      <td>movie</td>\n",
       "      <td>Dead Man (1995)</td>\n",
       "      <td>western</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1894</th>\n",
       "      <td>1894</td>\n",
       "      <td>movie</td>\n",
       "      <td>Blue in the Face (1995)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1949</th>\n",
       "      <td>1949</td>\n",
       "      <td>movie</td>\n",
       "      <td>Waiting for Guffman (1996)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1952</th>\n",
       "      <td>1952</td>\n",
       "      <td>movie</td>\n",
       "      <td>Basquiat (1996)</td>\n",
       "      <td>drama</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1953</th>\n",
       "      <td>1953</td>\n",
       "      <td>movie</td>\n",
       "      <td>2 Days in the Valley (1996)</td>\n",
       "      <td>crime</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1956</th>\n",
       "      <td>1956</td>\n",
       "      <td>movie</td>\n",
       "      <td>Romy and Michele's High School Reunion (1997)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1164</th>\n",
       "      <td>1164</td>\n",
       "      <td>movie</td>\n",
       "      <td>Star Trek: First Contact (1996)</td>\n",
       "      <td>action;adventure;sci-fi</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1190</th>\n",
       "      <td>1190</td>\n",
       "      <td>movie</td>\n",
       "      <td>Grosse Pointe Blank (1997)</td>\n",
       "      <td>comedy;crime</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1199</th>\n",
       "      <td>1199</td>\n",
       "      <td>movie</td>\n",
       "      <td>Men in Black (1997)</td>\n",
       "      <td>action;adventure;comedy;sci-fi</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1215</th>\n",
       "      <td>1215</td>\n",
       "      <td>movie</td>\n",
       "      <td>Heat (1995)</td>\n",
       "      <td>action;crime;thriller</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1218</th>\n",
       "      <td>1218</td>\n",
       "      <td>movie</td>\n",
       "      <td>Leaving Las Vegas (1995)</td>\n",
       "      <td>drama;romance</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1224</th>\n",
       "      <td>1224</td>\n",
       "      <td>movie</td>\n",
       "      <td>Time to Kill, A (1996)</td>\n",
       "      <td>drama</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1063</th>\n",
       "      <td>1063</td>\n",
       "      <td>movie</td>\n",
       "      <td>Independence Day (ID4) (1996)</td>\n",
       "      <td>action;sci-fi;war</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>967</th>\n",
       "      <td>967</td>\n",
       "      <td>movie</td>\n",
       "      <td>Birdcage, The (1996)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1787</th>\n",
       "      <td>1787</td>\n",
       "      <td>movie</td>\n",
       "      <td>That Thing You Do! (1996)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2023</th>\n",
       "      <td>2023</td>\n",
       "      <td>movie</td>\n",
       "      <td>Curdled (1996)</td>\n",
       "      <td>crime</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>966</th>\n",
       "      <td>966</td>\n",
       "      <td>movie</td>\n",
       "      <td>Rumble in the Bronx (1995)</td>\n",
       "      <td>action;adventure;crime</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1053</th>\n",
       "      <td>1053</td>\n",
       "      <td>movie</td>\n",
       "      <td>Truth About Cats &amp; Dogs, The (1996)</td>\n",
       "      <td>comedy;romance</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1921</th>\n",
       "      <td>1921</td>\n",
       "      <td>movie</td>\n",
       "      <td>Trigger Effect, The (1996)</td>\n",
       "      <td>drama;thriller</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2220</th>\n",
       "      <td>2220</td>\n",
       "      <td>movie</td>\n",
       "      <td>Selena (1997)</td>\n",
       "      <td>drama;musical</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1870</th>\n",
       "      <td>1870</td>\n",
       "      <td>movie</td>\n",
       "      <td>Craft, The (1996)</td>\n",
       "      <td>drama;horror</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1060</th>\n",
       "      <td>1060</td>\n",
       "      <td>movie</td>\n",
       "      <td>Twister (1996)</td>\n",
       "      <td>action;adventure;thriller</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1620</th>\n",
       "      <td>1620</td>\n",
       "      <td>movie</td>\n",
       "      <td>Volcano (1997)</td>\n",
       "      <td>drama;thriller</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1771</th>\n",
       "      <td>1771</td>\n",
       "      <td>movie</td>\n",
       "      <td>Fled (1996)</td>\n",
       "      <td>action;adventure</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1067</th>\n",
       "      <td>1067</td>\n",
       "      <td>movie</td>\n",
       "      <td>Phenomenon (1996)</td>\n",
       "      <td>drama;romance</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1627</th>\n",
       "      <td>1627</td>\n",
       "      <td>movie</td>\n",
       "      <td>Executive Decision (1996)</td>\n",
       "      <td>action;thriller</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1236</th>\n",
       "      <td>1236</td>\n",
       "      <td>movie</td>\n",
       "      <td>Liar Liar (1997)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1539</th>\n",
       "      <td>1539</td>\n",
       "      <td>movie</td>\n",
       "      <td>Eraser (1996)</td>\n",
       "      <td>action;thriller</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1089</th>\n",
       "      <td>1089</td>\n",
       "      <td>movie</td>\n",
       "      <td>Long Kiss Goodnight, The (1996)</td>\n",
       "      <td>action;thriller</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1163</th>\n",
       "      <td>1163</td>\n",
       "      <td>movie</td>\n",
       "      <td>Breaking the Waves (1996)</td>\n",
       "      <td>drama</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1398</th>\n",
       "      <td>1398</td>\n",
       "      <td>movie</td>\n",
       "      <td>Beverly Hills Ninja (1997)</td>\n",
       "      <td>action;comedy</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1187</th>\n",
       "      <td>1187</td>\n",
       "      <td>movie</td>\n",
       "      <td>Devil's Own, The (1997)</td>\n",
       "      <td>action;drama;thriller;war</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1348</th>\n",
       "      <td>1348</td>\n",
       "      <td>movie</td>\n",
       "      <td>Thinner (1996)</td>\n",
       "      <td>horror;thriller</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1191</th>\n",
       "      <td>1191</td>\n",
       "      <td>movie</td>\n",
       "      <td>Austin Powers: International Man of Mystery (1...</td>\n",
       "      <td>comedy</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1216</th>\n",
       "      <td>1216</td>\n",
       "      <td>movie</td>\n",
       "      <td>Sabrina (1995)</td>\n",
       "      <td>comedy;romance</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1255</th>\n",
       "      <td>1255</td>\n",
       "      <td>movie</td>\n",
       "      <td>Titanic (1997)</td>\n",
       "      <td>action;drama;romance</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>73 rows × 5 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "      node_id   type                                               name  \\\n",
       "1092     1092  movie                                    Swingers (1996)   \n",
       "2039     2039  movie                            Hate (Haine, La) (1995)   \n",
       "2009     2009  movie                               Bottle Rocket (1996)   \n",
       "1069     1069  movie                              Godfather, The (1972)   \n",
       "1417     1417  movie                               Trainspotting (1996)   \n",
       "1683     1683  movie                            Last Supper, The (1995)   \n",
       "1352     1352  movie                                     Kingpin (1996)   \n",
       "1486     1486  movie     Things to Do in Denver when You're Dead (1995)   \n",
       "1450     1450  movie                 People vs. Larry Flynt, The (1996)   \n",
       "1353     1353  movie                        Nutty Professor, The (1996)   \n",
       "949       949  movie                              Twelve Monkeys (1995)   \n",
       "1488     1488  movie                                Broken Arrow (1996)   \n",
       "1311     1311  movie                                 Black Sheep (1996)   \n",
       "1284     1284  movie                Man Who Knew Too Little, The (1997)   \n",
       "1266     1266  movie                                Lost Highway (1997)   \n",
       "955       955  movie                            Mighty Aphrodite (1995)   \n",
       "1249     1249  movie                       Devil's Advocate, The (1997)   \n",
       "1347     1347  movie                         Mission: Impossible (1996)   \n",
       "1570     1570  movie                                    Sleepers (1996)   \n",
       "1533     1533  movie                                 Primal Fear (1996)   \n",
       "1235     1235  movie                               Donnie Brasco (1997)   \n",
       "1638     1638  movie                                   City Hall (1996)   \n",
       "1782     1782  movie                           Last Man Standing (1996)   \n",
       "1786     1786  movie                                     Freeway (1996)   \n",
       "1864     1864  movie                                    Dead Man (1995)   \n",
       "1894     1894  movie                            Blue in the Face (1995)   \n",
       "1949     1949  movie                         Waiting for Guffman (1996)   \n",
       "1952     1952  movie                                    Basquiat (1996)   \n",
       "1953     1953  movie                        2 Days in the Valley (1996)   \n",
       "1956     1956  movie      Romy and Michele's High School Reunion (1997)   \n",
       "...       ...    ...                                                ...   \n",
       "1164     1164  movie                    Star Trek: First Contact (1996)   \n",
       "1190     1190  movie                         Grosse Pointe Blank (1997)   \n",
       "1199     1199  movie                                Men in Black (1997)   \n",
       "1215     1215  movie                                        Heat (1995)   \n",
       "1218     1218  movie                           Leaving Las Vegas (1995)   \n",
       "1224     1224  movie                             Time to Kill, A (1996)   \n",
       "1063     1063  movie                      Independence Day (ID4) (1996)   \n",
       "967       967  movie                               Birdcage, The (1996)   \n",
       "1787     1787  movie                          That Thing You Do! (1996)   \n",
       "2023     2023  movie                                     Curdled (1996)   \n",
       "966       966  movie                         Rumble in the Bronx (1995)   \n",
       "1053     1053  movie                Truth About Cats & Dogs, The (1996)   \n",
       "1921     1921  movie                         Trigger Effect, The (1996)   \n",
       "2220     2220  movie                                      Selena (1997)   \n",
       "1870     1870  movie                                  Craft, The (1996)   \n",
       "1060     1060  movie                                     Twister (1996)   \n",
       "1620     1620  movie                                     Volcano (1997)   \n",
       "1771     1771  movie                                        Fled (1996)   \n",
       "1067     1067  movie                                  Phenomenon (1996)   \n",
       "1627     1627  movie                          Executive Decision (1996)   \n",
       "1236     1236  movie                                   Liar Liar (1997)   \n",
       "1539     1539  movie                                      Eraser (1996)   \n",
       "1089     1089  movie                    Long Kiss Goodnight, The (1996)   \n",
       "1163     1163  movie                          Breaking the Waves (1996)   \n",
       "1398     1398  movie                         Beverly Hills Ninja (1997)   \n",
       "1187     1187  movie                            Devil's Own, The (1997)   \n",
       "1348     1348  movie                                     Thinner (1996)   \n",
       "1191     1191  movie  Austin Powers: International Man of Mystery (1...   \n",
       "1216     1216  movie                                     Sabrina (1995)   \n",
       "1255     1255  movie                                     Titanic (1997)   \n",
       "\n",
       "                       gender/genres  rating  \n",
       "1092                    comedy;drama       5  \n",
       "2039                           drama       5  \n",
       "2009                          comedy       5  \n",
       "1069              action;crime;drama       5  \n",
       "1417                           drama       5  \n",
       "1683                  drama;thriller       5  \n",
       "1352                          comedy       4  \n",
       "1486             crime;drama;romance       4  \n",
       "1450                           drama       4  \n",
       "1353   comedy;fantasy;romance;sci-fi       4  \n",
       "949                     drama;sci-fi       4  \n",
       "1488                 action;thriller       4  \n",
       "1311                          comedy       4  \n",
       "1284                  comedy;mystery       4  \n",
       "1266                         mystery       4  \n",
       "955                           comedy       4  \n",
       "1249   crime;horror;mystery;thriller       4  \n",
       "1347        action;adventure;mystery       4  \n",
       "1570                     crime;drama       4  \n",
       "1533                  drama;thriller       4  \n",
       "1235                     crime;drama       4  \n",
       "1638                  drama;thriller       4  \n",
       "1782            action;drama;western       4  \n",
       "1786                           crime       4  \n",
       "1864                         western       4  \n",
       "1894                          comedy       4  \n",
       "1949                          comedy       4  \n",
       "1952                           drama       4  \n",
       "1953                           crime       4  \n",
       "1956                          comedy       4  \n",
       "...                              ...     ...  \n",
       "1164         action;adventure;sci-fi       4  \n",
       "1190                    comedy;crime       4  \n",
       "1199  action;adventure;comedy;sci-fi       4  \n",
       "1215           action;crime;thriller       4  \n",
       "1218                   drama;romance       4  \n",
       "1224                           drama       4  \n",
       "1063               action;sci-fi;war       4  \n",
       "967                           comedy       3  \n",
       "1787                          comedy       3  \n",
       "2023                           crime       3  \n",
       "966           action;adventure;crime       3  \n",
       "1053                  comedy;romance       3  \n",
       "1921                  drama;thriller       3  \n",
       "2220                   drama;musical       3  \n",
       "1870                    drama;horror       3  \n",
       "1060       action;adventure;thriller       3  \n",
       "1620                  drama;thriller       3  \n",
       "1771                action;adventure       3  \n",
       "1067                   drama;romance       3  \n",
       "1627                 action;thriller       3  \n",
       "1236                          comedy       3  \n",
       "1539                 action;thriller       3  \n",
       "1089                 action;thriller       3  \n",
       "1163                           drama       3  \n",
       "1398                   action;comedy       3  \n",
       "1187       action;drama;thriller;war       3  \n",
       "1348                 horror;thriller       3  \n",
       "1191                          comedy       3  \n",
       "1216                  comedy;romance       3  \n",
       "1255            action;drama;romance       3  \n",
       "\n",
       "[73 rows x 5 columns]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "data_home = \"./data/movielens-100k\"\n",
    "sppr = SparsePPR()\n",
    "sppr.load_graph_dataset(data_home, is_undirected=True)\n",
    "sppr.load_node_labels(data_home);\n",
    "sppr.normalize()\n",
    "\n",
    "sppr.show_user_history(user_id=500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Seemingly, the user frequently watched (and prefer) `drama`, `comedy`, `romance`, and `thriller` movies. \n",
    "\n",
    "We use the following code to rank nodes regardless of node type (the below codes are from the previous session). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePPR(SparsePPR):\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 test the function on a personalized ranking. "
   ]
  },
  {
   "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>type</th>\n",
       "      <th>name</th>\n",
       "      <th>gender/genres</th>\n",
       "      <th>age</th>\n",
       "      <th>job</th>\n",
       "      <th>score</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>500</td>\n",
       "      <td>user</td>\n",
       "      <td>emil</td>\n",
       "      <td>M</td>\n",
       "      <td>22.0</td>\n",
       "      <td>student</td>\n",
       "      <td>0.152269</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>1069</td>\n",
       "      <td>movie</td>\n",
       "      <td>Godfather, The (1972)</td>\n",
       "      <td>action;crime;drama</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>0.004156</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>1042</td>\n",
       "      <td>movie</td>\n",
       "      <td>Fargo (1996)</td>\n",
       "      <td>crime;drama;thriller</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>0.004118</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>1123</td>\n",
       "      <td>movie</td>\n",
       "      <td>Return of the Jedi (1983)</td>\n",
       "      <td>action;adventure;romance;sci-fi;war</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>0.003928</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>1230</td>\n",
       "      <td>movie</td>\n",
       "      <td>Scream (1996)</td>\n",
       "      <td>horror;thriller</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>0.003622</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>95</th>\n",
       "      <td>96</td>\n",
       "      <td>91</td>\n",
       "      <td>user</td>\n",
       "      <td>shawn</td>\n",
       "      <td>M</td>\n",
       "      <td>32.0</td>\n",
       "      <td>entertainment</td>\n",
       "      <td>0.001443</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>96</th>\n",
       "      <td>97</td>\n",
       "      <td>2023</td>\n",
       "      <td>movie</td>\n",
       "      <td>Curdled (1996)</td>\n",
       "      <td>crime</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>0.001440</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>97</th>\n",
       "      <td>98</td>\n",
       "      <td>536</td>\n",
       "      <td>user</td>\n",
       "      <td>robbie</td>\n",
       "      <td>M</td>\n",
       "      <td>36.0</td>\n",
       "      <td>engineer</td>\n",
       "      <td>0.001416</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>98</th>\n",
       "      <td>99</td>\n",
       "      <td>307</td>\n",
       "      <td>user</td>\n",
       "      <td>nick</td>\n",
       "      <td>M</td>\n",
       "      <td>60.0</td>\n",
       "      <td>retired</td>\n",
       "      <td>0.001415</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>99</th>\n",
       "      <td>100</td>\n",
       "      <td>290</td>\n",
       "      <td>user</td>\n",
       "      <td>tracy</td>\n",
       "      <td>M</td>\n",
       "      <td>19.0</td>\n",
       "      <td>student</td>\n",
       "      <td>0.001404</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>100 rows × 8 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "    rank  node_id   type                       name  \\\n",
       "0      1      500   user                       emil   \n",
       "1      2     1069  movie      Godfather, The (1972)   \n",
       "2      3     1042  movie               Fargo (1996)   \n",
       "3      4     1123  movie  Return of the Jedi (1983)   \n",
       "4      5     1230  movie              Scream (1996)   \n",
       "..   ...      ...    ...                        ...   \n",
       "95    96       91   user                      shawn   \n",
       "96    97     2023  movie             Curdled (1996)   \n",
       "97    98      536   user                     robbie   \n",
       "98    99      307   user                       nick   \n",
       "99   100      290   user                      tracy   \n",
       "\n",
       "                          gender/genres   age            job     score  \n",
       "0                                     M  22.0        student  0.152269  \n",
       "1                    action;crime;drama   NaN            NaN  0.004156  \n",
       "2                  crime;drama;thriller   NaN            NaN  0.004118  \n",
       "3   action;adventure;romance;sci-fi;war   NaN            NaN  0.003928  \n",
       "4                       horror;thriller   NaN            NaN  0.003622  \n",
       "..                                  ...   ...            ...       ...  \n",
       "95                                    M  32.0  entertainment  0.001443  \n",
       "96                                crime   NaN            NaN  0.001440  \n",
       "97                                    M  36.0       engineer  0.001416  \n",
       "98                                    M  60.0        retired  0.001415  \n",
       "99                                    M  19.0        student  0.001404  \n",
       "\n",
       "[100 rows x 8 columns]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "data_home = \"./data/movielens-100k\"\n",
    "sppr = SparsePPR()\n",
    "sppr.load_graph_dataset(data_home, is_undirected=True)\n",
    "sppr.load_node_labels(data_home);\n",
    "sppr.normalize()\n",
    "\n",
    "seeds = [500]\n",
    "r, _ = sppr.iterate_PPR(seeds, b=0.15, epsilon=1e-9, maxIters=1000)\n",
    "pd.set_option('display.max_rows', 10)\n",
    "display(sppr.rank_nodes(r, topk=100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see in the table, this ranking result contains nodes of movies as well as those of users. \n",
    "For better analysis, we need to implement such reporting functions according to node type. \n",
    "First, we implement `rank_users` which reports ranking results for only users. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SparsePPR(SparsePPR):\n",
    "    def rank_users(self, ranking_scores, topk=-1):\n",
    "        user_labels = self.node_labels[self.node_labels.type == \"user\"]\n",
    "        user_node_ids = user_labels[\"node_id\"].values\n",
    "        user_ranking_scores = ranking_scores[user_node_ids]\n",
    "\n",
    "        sorted_indices = np.flipud(np.argsort(user_ranking_scores))\n",
    "        sorted_users = user_node_ids[sorted_indices]\n",
    "        sorted_scores = user_ranking_scores[sorted_indices]\n",
    "        ranks = range(1, len(user_node_ids)+1)\n",
    "\n",
    "        result_labels = self.node_labels.iloc[sorted_users][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 see the example of the result from the function. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "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>type</th>\n",
       "      <th>name</th>\n",
       "      <th>gender/genres</th>\n",
       "      <th>age</th>\n",
       "      <th>job</th>\n",
       "      <th>score</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>500</td>\n",
       "      <td>user</td>\n",
       "      <td>emil</td>\n",
       "      <td>M</td>\n",
       "      <td>22.0</td>\n",
       "      <td>student</td>\n",
       "      <td>0.152269</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>275</td>\n",
       "      <td>user</td>\n",
       "      <td>julian</td>\n",
       "      <td>M</td>\n",
       "      <td>21.0</td>\n",
       "      <td>student</td>\n",
       "      <td>0.002223</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>654</td>\n",
       "      <td>user</td>\n",
       "      <td>millie</td>\n",
       "      <td>F</td>\n",
       "      <td>50.0</td>\n",
       "      <td>healthcare</td>\n",
       "      <td>0.002210</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>302</td>\n",
       "      <td>user</td>\n",
       "      <td>fredrick</td>\n",
       "      <td>M</td>\n",
       "      <td>19.0</td>\n",
       "      <td>student</td>\n",
       "      <td>0.002071</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>415</td>\n",
       "      <td>user</td>\n",
       "      <td>kari</td>\n",
       "      <td>F</td>\n",
       "      <td>20.0</td>\n",
       "      <td>student</td>\n",
       "      <td>0.002019</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>591</td>\n",
       "      <td>user</td>\n",
       "      <td>solomon</td>\n",
       "      <td>M</td>\n",
       "      <td>18.0</td>\n",
       "      <td>student</td>\n",
       "      <td>0.002016</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>449</td>\n",
       "      <td>user</td>\n",
       "      <td>kelley</td>\n",
       "      <td>F</td>\n",
       "      <td>35.0</td>\n",
       "      <td>educator</td>\n",
       "      <td>0.001836</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>12</td>\n",
       "      <td>user</td>\n",
       "      <td>paul</td>\n",
       "      <td>M</td>\n",
       "      <td>47.0</td>\n",
       "      <td>educator</td>\n",
       "      <td>0.001829</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>392</td>\n",
       "      <td>user</td>\n",
       "      <td>sherman</td>\n",
       "      <td>M</td>\n",
       "      <td>19.0</td>\n",
       "      <td>student</td>\n",
       "      <td>0.001686</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>757</td>\n",
       "      <td>user</td>\n",
       "      <td>wilmer</td>\n",
       "      <td>M</td>\n",
       "      <td>27.0</td>\n",
       "      <td>student</td>\n",
       "      <td>0.001641</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   rank  node_id  type      name gender/genres   age         job     score\n",
       "0     1      500  user      emil             M  22.0     student  0.152269\n",
       "1     2      275  user    julian             M  21.0     student  0.002223\n",
       "2     3      654  user    millie             F  50.0  healthcare  0.002210\n",
       "3     4      302  user  fredrick             M  19.0     student  0.002071\n",
       "4     5      415  user      kari             F  20.0     student  0.002019\n",
       "5     6      591  user   solomon             M  18.0     student  0.002016\n",
       "6     7      449  user    kelley             F  35.0    educator  0.001836\n",
       "7     8       12  user      paul             M  47.0    educator  0.001829\n",
       "8     9      392  user   sherman             M  19.0     student  0.001686\n",
       "9    10      757  user    wilmer             M  27.0     student  0.001641"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "data_home = \"./data/movielens-100k\"\n",
    "sppr = SparsePPR()\n",
    "sppr.load_graph_dataset(data_home, is_undirected=True)\n",
    "sppr.load_node_labels(data_home);\n",
    "sppr.normalize()\n",
    "\n",
    "seeds = [500]\n",
    "r, _ = sppr.iterate_PPR(seeds, b=0.15, epsilon=1e-9, maxIters=100)\n",
    "display(sppr.rank_users(r, topk=10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As seen in the table, there are many students in the top-$10$ ranking list. \n",
    "Note that the querying user ($500$, emil) is also a student. \n",
    "These results imply that the personalized ranking on the user is able to capture other users having the similar preference to the querying user. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we see `rank_movies` function which reports ranking results for only movies. \n",
    "Since the implementation is a little complex, we provide the full implementation of the function. \n",
    "This function additionally considers `seeds` and `shows_unseen` arguments since we sometimes want to recommend movies unseen by a user or users. \n",
    "Suppose `seeds` indicate user node ids.\n",
    "If `shows_unseen` is `True`, then the function reports the ranking result for only unseen movies. \n",
    "Otherwise, it will consider all movies to rank. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import reduce\n",
    "\n",
    "class SparsePPR(SparsePPR):\n",
    "    def rank_movies(self, seeds, ranking_scores, topk=-1, shows_unseen=True):\n",
    "        movie_labels = self.node_labels.loc[self.node_labels[\"type\"] == \"movie\"]\n",
    "        movie_node_ids = movie_labels[\"node_id\"].values\n",
    "        movie_ranking_scores = ranking_scores[movie_node_ids]\n",
    "        \n",
    "        _, seen_movie_ids, _ = find(self.A[seeds, :])\n",
    "        seen_movie_ids = np.unique(seen_movie_ids)\n",
    "        masks = [movie_node_ids == seen_movie for seen_movie in seen_movie_ids]\n",
    "        seen_mask = reduce(np.logical_or, masks)\n",
    "\n",
    "        sorted_indices = np.flipud(np.argsort(movie_ranking_scores))\n",
    "        sorted_movies = movie_node_ids[sorted_indices]\n",
    "        sorted_scores = movie_ranking_scores[sorted_indices]\n",
    "        sorted_seen_mask = seen_mask[sorted_indices]\n",
    "        ranks = range(1, len(movie_node_ids)+1)\n",
    "\n",
    "        result_labels = self.node_labels.iloc[sorted_movies]\n",
    "        result_labels.insert(0, \"rank\", ranks)\n",
    "        result_labels.insert(0, \"score\", sorted_scores)\n",
    "        result_labels.insert(0, \"seen\", sorted_seen_mask)\n",
    "        \n",
    "        if shows_unseen:\n",
    "            result_labels = result_labels.loc[result_labels[\"seen\"] == False]\n",
    "            result_labels[\"rank\"] = range(1, result_labels.shape[0]+1)\n",
    "                \n",
    "        result_labels = result_labels[0:topk]\n",
    "        result_labels.reset_index(drop = True, inplace = True)\n",
    "        return result_labels[[\"rank\", \"node_id\", \"type\", \"name\", \"gender/genres\", \"seen\", \"score\"]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see the example of the result from the function. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "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>type</th>\n",
       "      <th>name</th>\n",
       "      <th>gender/genres</th>\n",
       "      <th>seen</th>\n",
       "      <th>score</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>992</td>\n",
       "      <td>movie</td>\n",
       "      <td>Star Wars (1977)</td>\n",
       "      <td>action;adventure;romance;sci-fi;war</td>\n",
       "      <td>False</td>\n",
       "      <td>0.002541</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>1200</td>\n",
       "      <td>movie</td>\n",
       "      <td>Contact (1997)</td>\n",
       "      <td>drama;sci-fi</td>\n",
       "      <td>False</td>\n",
       "      <td>0.001946</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>943</td>\n",
       "      <td>movie</td>\n",
       "      <td>Toy Story (1995)</td>\n",
       "      <td>animation;children's;comedy</td>\n",
       "      <td>False</td>\n",
       "      <td>0.001828</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>1228</td>\n",
       "      <td>movie</td>\n",
       "      <td>English Patient, The (1996)</td>\n",
       "      <td>drama;romance;war</td>\n",
       "      <td>False</td>\n",
       "      <td>0.001738</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>1242</td>\n",
       "      <td>movie</td>\n",
       "      <td>Air Force One (1997)</td>\n",
       "      <td>action;thriller</td>\n",
       "      <td>False</td>\n",
       "      <td>0.001587</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>16</td>\n",
       "      <td>1146</td>\n",
       "      <td>movie</td>\n",
       "      <td>Back to the Future (1985)</td>\n",
       "      <td>comedy;sci-fi</td>\n",
       "      <td>False</td>\n",
       "      <td>0.001153</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>17</td>\n",
       "      <td>1260</td>\n",
       "      <td>movie</td>\n",
       "      <td>Schindler's List (1993)</td>\n",
       "      <td>drama;war</td>\n",
       "      <td>False</td>\n",
       "      <td>0.001148</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>17</th>\n",
       "      <td>18</td>\n",
       "      <td>1152</td>\n",
       "      <td>movie</td>\n",
       "      <td>Indiana Jones and the Last Crusade (1989)</td>\n",
       "      <td>action;adventure</td>\n",
       "      <td>False</td>\n",
       "      <td>0.001126</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>18</th>\n",
       "      <td>19</td>\n",
       "      <td>1110</td>\n",
       "      <td>movie</td>\n",
       "      <td>Monty Python and the Holy Grail (1974)</td>\n",
       "      <td>comedy</td>\n",
       "      <td>False</td>\n",
       "      <td>0.001121</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>19</th>\n",
       "      <td>20</td>\n",
       "      <td>1006</td>\n",
       "      <td>movie</td>\n",
       "      <td>Shawshank Redemption, The (1994)</td>\n",
       "      <td>drama</td>\n",
       "      <td>False</td>\n",
       "      <td>0.001103</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>20 rows × 7 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "    rank  node_id   type                                       name  \\\n",
       "0      1      992  movie                           Star Wars (1977)   \n",
       "1      2     1200  movie                             Contact (1997)   \n",
       "2      3      943  movie                           Toy Story (1995)   \n",
       "3      4     1228  movie                English Patient, The (1996)   \n",
       "4      5     1242  movie                       Air Force One (1997)   \n",
       "..   ...      ...    ...                                        ...   \n",
       "15    16     1146  movie                  Back to the Future (1985)   \n",
       "16    17     1260  movie                    Schindler's List (1993)   \n",
       "17    18     1152  movie  Indiana Jones and the Last Crusade (1989)   \n",
       "18    19     1110  movie     Monty Python and the Holy Grail (1974)   \n",
       "19    20     1006  movie           Shawshank Redemption, The (1994)   \n",
       "\n",
       "                          gender/genres   seen     score  \n",
       "0   action;adventure;romance;sci-fi;war  False  0.002541  \n",
       "1                          drama;sci-fi  False  0.001946  \n",
       "2           animation;children's;comedy  False  0.001828  \n",
       "3                     drama;romance;war  False  0.001738  \n",
       "4                       action;thriller  False  0.001587  \n",
       "..                                  ...    ...       ...  \n",
       "15                        comedy;sci-fi  False  0.001153  \n",
       "16                            drama;war  False  0.001148  \n",
       "17                     action;adventure  False  0.001126  \n",
       "18                               comedy  False  0.001121  \n",
       "19                                drama  False  0.001103  \n",
       "\n",
       "[20 rows x 7 columns]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "data_home = \"./data/movielens-100k\"\n",
    "sppr = SparsePPR()\n",
    "sppr.load_graph_dataset(data_home, is_undirected=True)\n",
    "sppr.load_node_labels(data_home);\n",
    "sppr.normalize()\n",
    "\n",
    "seeds = [500]\n",
    "r, _ = sppr.iterate_PPR(seeds, b=0.15, epsilon=1e-9, maxIters=100)\n",
    "display(sppr.rank_movies(seeds, r, topk=20, shows_unseen=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the querying user frequently watched `drama`, `comedy`, `romance`, and `thriller` movies. \n",
    "Also, there are many such kinds of movies in the recommendation list. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Session 3. Summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this session, we implemented Topic-specific PageRank (the sparse matrix version) in Python. \n",
    "More specifically, we are able to answer the following goals now. \n",
    "\n",
    "* **Goal 1.** How to implement Topic-specific PageRank based on sparse matrices using `numpy` and `scipy` in Python\n",
    "    - We implemented the iterative algorithm for Topic-specific PageRank based on sparse matrices.\n",
    "* **Goal 2.** To perform a qualitative analysis of the ranking result from Topic-specific PageRank in real-world networks\n",
    "    - We performed a qualitative analysis on the `movielens-100k` dataset which is a real-world network. \n"
   ]
  }
 ],
 "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}