cugraph/link_analysis/Pagerank.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PageRank\n",
    "\n",
    "In this notebook, we will use both NetworkX and cuGraph to compute the PageRank of each vertex in our test dataset.  The NetworkX and cuGraph processes will be interleaved so that each step can be compared.\n",
    "\n",
    "Notebook Credits\n",
    "* Original Authors: Bradley Rees and James Wyles\n",
    "* Created:   08/13/2019\n",
    "* Updated:   10/28/2019\n",
    "\n",
    "RAPIDS Versions: 0.10.0    \n",
    "\n",
    "Test Hardware\n",
    "\n",
    "* GV100 32G, CUDA 10.0\n",
    "\n",
    "\n",
    "## Introduction\n",
    "Pagerank is measure of the relative importance, also called centrality, of a vertex based on the relative importance of it's neighbors.  PageRank was developed by Google and is (was) used to rank it's search results. PageRank uses the connectivity information of a graph to rank the importance of each vertex. \n",
    "\n",
    "See [Wikipedia](https://en.wikipedia.org/wiki/PageRank) for more details on the algorithm.\n",
    "\n",
    "To compute the Pagerank scores for a graph in cuGraph we use:<br>\n",
    "\n",
    "**cugraph.pagerank(G,alpha=0.85, max_iter=100, tol=1.0e-5)**\n",
    "* __G__: cugraph.Graph object\n",
    "* __alpha__: float, The damping factor represents the probability to follow an outgoing edge. default is 0.85\n",
    "* __max_iter__: int, The maximum number of iterations before an answer is returned. This can be used to limit the execution time and do an early exit before the solver reaches the convergence tolerance. If this value is lower or equal to 0 cuGraph will use the default value, which is 100\n",
    "* __tol__: float, Set the tolerance the approximation, this parameter should be a small magnitude value. The lower the tolerance the better the approximation. If this value is 0.0f, cuGraph will use the default value which is 0.00001. Setting too small a tolerance can lead to non-convergence due to numerical roundoff. Usually values between 0.01 and 0.00001 are acceptable.\n",
    "\n",
    "Returns:\n",
    "* __df__: a cudf.DataFrame object with two columns:\n",
    "    * df['vertex']: The vertex identifier for the vertex\n",
    "    * df['pagerank']: The pagerank score for the vertex\n",
    "\n",
    "\n",
    "## cuGraph Notice \n",
    "The current version of cuGraph has some limitations:\n",
    "\n",
    "* Vertex IDs need to be 32-bit integers.\n",
    "* Vertex IDs are expected to be contiguous integers starting from 0.\n",
    "\n",
    "cuGraph provides the renumber function to mitigate this problem. Input vertex IDs for the renumber function can be either 32-bit or 64-bit integers, can be non-contiguous, and can start from an arbitrary number. The renumber function maps the provided input vertex IDs to 32-bit contiguous integers starting from 0. cuGraph still requires the renumbered vertex IDs to be representable in 32-bit integers. These limitations are being addressed and will be fixed soon.    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Data\n",
    "We will be using the Zachary Karate club dataset \n",
    "*W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of\n",
    "Anthropological Research 33, 452-473 (1977).*\n",
    "\n",
    "\n",
    "![Karate Club](../img/zachary_black_lines.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The notebook compares cuGraph to NetworkX,  \n",
    "# therefore there some additional non-RAPIDS python libraries need to be installed. \n",
    "# Please run this cell if you need the additional libraries\n",
    "!pip install networkx\n",
    "!pip install scipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "from collections import OrderedDict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# NetworkX libraries\n",
    "import networkx as nx\n",
    "from scipy.io import mmread"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Some Prep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define the parameters \n",
    "max_iter = 100  # The maximum number of iterations\n",
    "tol = 0.00001   # tolerance\n",
    "alpha = 0.85    # alpha"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define the path to the test data  \n",
    "datafile='../data/karate-data.csv'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# NetworkX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read the data, this also created a NetworkX Graph \n",
    "file = open(datafile, 'rb')\n",
    "Gnx = nx.read_edgelist(file)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pr_nx = nx.pagerank(Gnx, alpha=alpha, max_iter=max_iter, tol=tol)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pr_nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Running NetworkX is that easy.  \n",
    "Let's seet how that compares to cuGraph\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# cuGraph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read in the data - GPU\n",
    "cuGraph depends on cuDF for data loading and the initial Dataframe creation\n",
    "\n",
    "The data file contains an edge list, which represents the connection of a vertex to another.  The `source` to `destination` pairs is in what is known as Coordinate Format (COO).  In this test case, the data is just two columns.  However a third, `weight`, column is also possible"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read the data  \n",
    "gdf = cudf.read_csv(datafile, names=[\"src\", \"dst\"], delimiter='\\t', dtype=[\"int32\", \"int32\"] )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Graph "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph using the source (src) and destination (dst) vertex pairs from the Dataframe \n",
    "G = cugraph.Graph()\n",
    "G.add_edge_list(gdf[\"src\"], gdf[\"dst\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Call the PageRank algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call cugraph.pagerank to get the pagerank scores\n",
    "gdf_page = cugraph.pagerank(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_It was that easy!_  \n",
    "Compared to NetworkX, the cuGraph data loading might have been more steps, but using cuDF allows for a wider range of data to be loaded. \n",
    "\n",
    "\n",
    "----\n",
    "\n",
    "Let's now look at the results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Find the most important vertex using the scores\n",
    "# This methods should only be used for small graph\n",
    "bestScore = gdf_page['pagerank'][0]\n",
    "bestVert = gdf_page['vertex'][0]\n",
    "\n",
    "for i in range(len(gdf_page)):\n",
    "    if gdf_page['pagerank'][i] > bestScore:\n",
    "        bestScore = gdf_page['pagerank'][i]\n",
    "        bestVert = gdf_page['vertex'][i]\n",
    "        \n",
    "print(\"Best vertex is \" + str(bestVert) + \" with score of \" + str(bestScore))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The top PageRank vertex and socre match what was found by NetworkX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A better way to do that would be to find the max and then use that values in a query\n",
    "pr_max = gdf_page['pagerank'].max()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_pagerank_threshold(_df, t=0) :\n",
    "    filtered = _df.query('pagerank >= @t')\n",
    "    \n",
    "    for i in range(len(filtered)):\n",
    "        print(\"Best vertex is \" + str(filtered['vertex'][i]) + \n",
    "            \" with score of \" + str(filtered['pagerank'][i]))              "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_pagerank_threshold(gdf_page, pr_max)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "a PageRank score of _0.10047_ is very low, which can be an indication that there is no more central vertex than any other.  Rather than just looking at the top score, let's look at the top three vertices and see if there are any insights that can be inferred.  \n",
    "\n",
    "Since this is a very small graph, let's just sort and get the first three records"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sort_pr = gdf_page.sort_values('pagerank', ascending=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sort_pr.head(3).to_pandas()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Going back and looking at the graph with the top three vertices highlighted (illustration below) it is easy to see that the top scoring vertices also appear to be the vertices with the most connections.   \n",
    "Let's look at sorted list of degrees (since the graph is undirected and symmetrized, the out degree is the same as the in degree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = G.degrees()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d.sort_values('out_degree', ascending=False).head(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../img/zachary_graph_pagerank.png\" width=\"600\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "Copyright (c) 2019, NVIDIA CORPORATION.\n",
    "\n",
    "Licensed under the Apache License, Version 2.0 (the \"License\");  you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
    "___"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "cugraph_dev",
   "language": "python",
   "name": "cugraph_dev"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}