notebooks/algorithms/centrality/Betweenness.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Betweenness Centrality\n",
    "\n",
    "In this notebook, we will compute the Betweenness centrality for both vertices and edges in our test database using cuGraph and NetworkX. The NetworkX and cuGraph processes will be interleaved so that each step can be compared.\n",
    "\n",
    "| Author Credit |    Date    |  Update          | cuGraph Version |  Test Hardware |\n",
    "| --------------|------------|------------------|-----------------|----------------|\n",
    "| Brad Rees     | 04/24/2019 | created          | 0.15            | GV100, CUDA 11.0\n",
    "| Brad Rees     | 08/16/2020 | tested / updated | 21.10 nightly   | RTX 3090 CUDA 11.4\n",
    "| Don Acosta    | 07/05/2022 | tested / updated | 22.08 nightly   | DGX Tesla V100 CUDA 11.5\n",
    "| Ralph Liu    | 07/26/2022 | updated | 22.08 nightly   | DGX Tesla V100 CUDA 11.5\n",
    "|              | 06/29/2023 | updated | 23.08 nightly   | DGX Tesla V100 CUDA 12.0"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "Betweenness centrality is a measure of the relative importance based on measuring the number of shortest paths that pass through each vertex or over each edge.  High betweenness centrality vertices have a greater number of path cross through the vertex.  Likewise, high centrality edges have more shortest paths that pass over the edge.\n",
    "\n",
    "See [Betweenness on Wikipedia](https://en.wikipedia.org/wiki/Betweenness_centrality) for more details on the algorithm.\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Betweenness centrality of a node 𝑣 is the sum of the fraction of all-pairs shortest paths that pass through 𝑣\n",
    "\n",
    "<img src=\"https://latex.codecogs.com/png.latex?c_B(v)&space;=\\sum_{s,t&space;\\in&space;V}&space;\\frac{\\sigma(s,&space;t|v)}{\\sigma(s,&space;t)}\" title=\"c_B(v) =\\sum_{s,t \\in V} \\frac{\\sigma(s, t|v)}{\\sigma(s, t)}\" />\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To compute the Betweenness centrality scores for a graph in cuGraph we use:<br>\n",
    "__df_v = cugraph.betweenness_centrality(G)__\n",
    "    G: cugraph.Graph object\n",
    "   \n",
    "\n",
    "Returns:\n",
    "\n",
    "    df: a cudf.DataFrame object with two columns:\n",
    "        df['vertex']: The vertex identifier for the vertex\n",
    "        df['betweenness_centrality']: The betweenness centrality score for the vertex\n",
    "\n",
    "\n",
    "\n",
    "__df_e = cugraph.edge_betweenness_centrality(G)__\n",
    "    G: cugraph.Graph object\n",
    "\n",
    "Returns:\n",
    "\n",
    "    df: a cudf.DataFrame object with two columns:\n",
    "        df[‘src’]cudf.Series\n",
    "            Contains the vertex identifiers of the source of each edge\n",
    "        df[‘dst’]cudf.Series\n",
    "            Contains the vertex identifiers of the destination of each edge\n",
    "        df['betweenness_centrality']: The betweenness centrality score for the vertex\n",
    "\n",
    "\n",
    "### _NOTICE_\n",
    "cuGraph does not currently support the ‘endpoints’ and ‘weight’ parameters as seen in the corresponding networkX call. "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Some notes about vertex IDs...\n",
    "\n",
    "* cuGraph will automatically renumber graphs to an internal format consisting of a contiguous series of integers starting from 0, and convert back to the original IDs when returning data to the caller. If the vertex IDs of the data are already a contiguous series of integers starting from 0, the auto-renumbering step can be skipped for faster graph creation times.\n",
    "  * To skip auto-renumbering, set the `renumber` boolean arg to `False` when calling the appropriate graph creation API (eg. `G.from_cudf_edgelist(gdf_r, source='src', destination='dst', renumber=False)`).\n",
    "  * For more advanced renumbering support, see the examples in `structure/renumber.ipynb` and `structure/renumber-2.ipynb`\n"
   ]
  },
  {
   "attachments": {},
   "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",
    "<img src=\"../../img/zachary_black_lines.png\" width=\"35%\"/>\n",
    "\n",
    "\n",
    "Because the test data has vertex IDs starting at 1, the auto-renumber feature of cuGraph (mentioned above) will be used so the starting vertex ID is zero for maximum efficiency. The resulting data will then be auto-unrenumbered, making the entire renumbering process transparent to users.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "\n",
    "# Import a built-in dataset\n",
    "from cugraph.datasets import karate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# NetworkX libraries\n",
    "import networkx as nx"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Graph "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a graph using the imported Dataset object\n",
    "G = karate.get_graph(download=True)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Call the Betweenness Centrality algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call cugraph.betweenness_centrality \n",
    "vertex_bc = cugraph.betweenness_centrality(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call cugraph.edge_betweenness_centrality \n",
    "edge_bc = cugraph.edge_betweenness_centrality(G)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_It was that easy!_  \n",
    "\n",
    "----\n",
    "\n",
    "Let's now look at the results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's sort the data and look at the top 5 vertices\n",
    "vertex_bc.sort_values(by='betweenness_centrality', ascending=False).head(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edge_bc.sort_values(by='betweenness_centrality', ascending=False).head(5)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Now compute using NetworkX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read the data, this also created a NetworkX Graph \n",
    "datafile=\"../../data/karate-data.csv\"\n",
    "file = open(datafile, 'rb')\n",
    "Gnx = nx.read_edgelist(file)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bc_nx_vert = nx.betweenness_centrality(Gnx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bc_nx_edge = nx.edge_betweenness_centrality(Gnx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bc_nx_sv = sorted(((value, key) for (key,value) in bc_nx_vert.items()), reverse=True)\n",
    "bc_nx_sv[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bc_nx_se = sorted(((value, key) for (key,value) in bc_nx_edge.items()), reverse=True)\n",
    "bc_nx_se[:5]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As mentioned, the scores are different but the ranking is the same."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "Copyright (c) 2019-2023, 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.9.7 ('base')",
   "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.10.12"
  },
  "vscode": {
   "interpreter": {
    "hash": "f708a36acfaef0acf74ccd43dfb58100269bf08fb79032a1e0a6f35bd9856f51"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}