cugraph/Triangle-Counting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Triangle Counting\n",
    "\n",
    "In this notebook, we will count the numner of trianges 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\n",
    "* Last Edit: 08/13/2019\n",
    "\n",
    "RAPIDS Versions: 0.9.0    \n",
    "\n",
    "Test Hardware\n",
    "\n",
    "* GV100 32G, CUDA 10.0\n",
    "\n",
    "\n",
    "## Introduction\n",
    "Triancle Counting, as the name implies, finds the number of triangles in a graph.  Triangles are important in computing the clustering Coefficient and can be used for clustering.  \n",
    "\n",
    "\n",
    "To compute the Pagerank scores for a graph in cuGraph we use:<br>\n",
    "\n",
    "**cugraph.triangles(G)**\n",
    "* __G__: cugraph.Graph object\n",
    "\n",
    "\n",
    "Returns:\n",
    "* int64 count\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": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: networkx in /home/seunghwak/Program/anaconda3/envs/cuda10/lib/python3.7/site-packages (2.3)\n",
      "Requirement already satisfied: decorator>=4.3.0 in /home/seunghwak/Program/anaconda3/envs/cuda10/lib/python3.7/site-packages (from networkx) (4.4.0)\n",
      "Requirement already satisfied: scipy in /home/seunghwak/Program/anaconda3/envs/cuda10/lib/python3.7/site-packages (1.3.1)\n",
      "Requirement already satisfied: numpy>=1.13.3 in /home/seunghwak/Program/anaconda3/envs/cuda10/lib/python3.7/site-packages (from scipy) (1.17.0)\n"
     ]
    }
   ],
   "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\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "from collections import OrderedDict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "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": 4,
   "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": 5,
   "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": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx_count = nx.triangles(Gnx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': 18,\n",
       " '2': 12,\n",
       " '3': 11,\n",
       " '4': 10,\n",
       " '5': 2,\n",
       " '6': 3,\n",
       " '7': 3,\n",
       " '8': 6,\n",
       " '9': 5,\n",
       " '11': 2,\n",
       " '12': 0,\n",
       " '13': 1,\n",
       " '14': 6,\n",
       " '18': 1,\n",
       " '20': 1,\n",
       " '22': 1,\n",
       " '32': 3,\n",
       " '31': 3,\n",
       " '10': 0,\n",
       " '28': 1,\n",
       " '29': 1,\n",
       " '33': 13,\n",
       " '17': 1,\n",
       " '34': 15,\n",
       " '15': 1,\n",
       " '16': 1,\n",
       " '19': 1,\n",
       " '21': 1,\n",
       " '23': 1,\n",
       " '24': 4,\n",
       " '26': 1,\n",
       " '30': 4,\n",
       " '25': 1,\n",
       " '27': 1}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# NetworkX does not give a single count, but list how many triangles each vertex is associated with\n",
    "nx_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# To get the number of triangles, we would need to loop through the array and add up each count\n",
    "count = 0\n",
    "for key, value in nx_count.items():\n",
    "    count = count + value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "135"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test file    \n",
    "datafile='./data/karate-data.csv'\n",
    "\n",
    "# Read the data file\n",
    "cols = [\"src\", \"dst\"]\n",
    "\n",
    "dtypes = OrderedDict([\n",
    "        (\"src\", \"int32\"), \n",
    "        (\"dst\", \"int32\")\n",
    "        ])\n",
    "\n",
    "gdf = cudf.read_csv(datafile, names=cols, delimiter='\\t', dtype=list(dtypes.values()) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Graph "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "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 Triangle Counting "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call cugraph.pagerank to get the pagerank scores\n",
    "cu_count = cugraph.triangles(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "135"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cu_count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_It was that easy!_  \n",
    "\n",
    "----\n"
   ]
  },
  {
   "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": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}