cugraph/community/Spectral-Clustering.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Spectral Clustering  \n",
    "\n",
    "In this notebook, we will use cuGraph to identify the cluster in a test graph using Spectral Clustering with both the (A) Balance Cut metric, and (B) the Modularity Maximization metric\n",
    "\n",
    "\n",
    "Notebook Credits\n",
    "* Original Authors: Bradley Rees and James Wyles\n",
    "* Created:   08/01/2019\n",
    "* Last Edit: 10/16/2019\n",
    "\n",
    "RAPIDS Versions: 0.10.0\n",
    "\n",
    "Test Hardware\n",
    "* GV100 32G, CUDA 10.0\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "Spectral clustering uses the eigenvectors of a Laplacian of the input graph to find a given number of clusters which satisfy a given quality metric. Balanced Cut and Modularity Maximization are two such quality metrics. \n",
    "\n",
    "@See:  https://en.wikipedia.org/wiki/Spectral_clustering\n",
    "\n",
    "To perform spectral clustering using the balanced cut metric in cugraph use:\n",
    "\n",
    "__df = cugraph.spectralBalancedCutClustering(G, num_clusters, num_eigen_vects)__\n",
    "<br>or<br>\n",
    "__df = cugraph.spectralModularityMaximizationClustering(G, num_clusters, num_eigen_vects)__\n",
    "\n",
    "\n",
    "\n",
    "Input\n",
    "* __G__: A cugraph.Graph object\n",
    "* __num_clusters__: The number of clusters to find\n",
    "* __num_eig__: (optional) The number of eigenvectors to use\n",
    "\n",
    "Returns\n",
    "* __df__: cudf.DataFrame with two names columns:\n",
    "    * df[\"vertex\"]: The vertex id.\n",
    "    * df[\"cluster\"]: The assigned partition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 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",
    "\n",
    "Zachary used a min-cut flow model to partition the graph into two clusters, shown by the circles and squares.  Zarchary wanted just two cluster based on a conflict that caused the Karate club to break into two separate clubs.  Many social network clustering methods identify more that two social groups in the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read the CSV datafile using cuDF"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test file  \n",
    "datafile='../data/karate-data.csv'\n",
    "\n",
    "gdf = cudf.read_csv(datafile, delimiter='\\t', names=['src', 'dst'], dtype=['int32', 'int32'] )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Adjusting the vertex ID\n",
    "Let's adjust all the vertex IDs to be zero based.  We are going to do this by creating two new columns with the adjusted IDs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gdf[\"src\"] = gdf[\"src\"] - 1\n",
    "gdf[\"dst\"] = gdf[\"dst\"] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The algorithm requires that there are edge weights.  In this case all the weights are being ste to 1\n",
    "gdf[\"data\"] = cudf.Series(np.ones(len(gdf), dtype=np.float32))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Look at the first few data records - the output should be two colums src and dst\n",
    "gdf.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# verify data type\n",
    "gdf.dtypes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Everything looks good, we can now create a graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a CuGraph \n",
    "G = cugraph.Graph()\n",
    "G.add_edge_list(gdf[\"src\"], gdf[\"dst\"], gdf[\"data\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "#### Define and print function, but adjust vertex ID so that they match the illustration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_cluster(_df, id):\n",
    "    \n",
    "    _f = _df.query('cluster == @id')\n",
    "  \n",
    "    part = []\n",
    "    for i in range(len(_f)):\n",
    "        part.append(_f['vertex'][i] + 1)\n",
    "    print(part)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "#### Using Balanced Cut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call spectralBalancedCutClustering on the graph for 3 clusters\n",
    "# using 3 eigenvectors:\n",
    "bc_gdf = cugraph.spectralBalancedCutClustering(G, 3, num_eigen_vects=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check the edge cut score for the produced clustering\n",
    "score = cugraph.analyzeClustering_edge_cut(G, 3, bc_gdf['cluster'])\n",
    "score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# See which nodes are in cluster 0:\n",
    "print_cluster(bc_gdf, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# See which nodes are in cluster 1:\n",
    "print_cluster(bc_gdf, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# See which nodes are in cluster 2:\n",
    "print_cluster(bc_gdf, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "#### Modularity Maximization\n",
    "Let's now look at the clustering using the modularity maximization metric"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call spectralModularityMaximizationClustering on the graph for 3 clusters\n",
    "# using 3 eigenvectors:\n",
    "mm_gdf = cugraph.spectralModularityMaximizationClustering(G, 3, num_eigen_vects=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check the modularity score for the produced clustering\n",
    "score = cugraph.analyzeClustering_modularity(G, 3, mm_gdf['cluster'])\n",
    "score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# See which nodes are in cluster 0:\n",
    "print_cluster(mm_gdf, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_cluster(mm_gdf, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_cluster(mm_gdf, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the two metrics produce different results"
   ]
  },
  {
   "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
}