notebooks/algorithms/centrality/Katz.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Katz Centrality\n",
    "\n",
    "In this notebook, we will compute the Katz centrality of each vertex in our test datase using both cuGraph and NetworkX. Additionally, NetworkX also contains a Numpy implementation that will used. 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     | 10/15/2019 | created          | 0.14            | GV100, CUDA 10.2\n",
    "| Brad Rees     | 08/16/2020 | tested / updated | 0.15.1 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",
    "Katz centrality is a measure of the relative importance of a vertex within the graph based on measuring the influence across the total number of walks between vertex pairs. \n",
    "\n",
    "$C_{katz}(i)=\\sum_{k=1}^{\\infty}\\sum_{j=1}^{n}\\alpha^k(A^k)_{ji}$\n",
    "\n",
    "See [Katz on Wikipedia](https://en.wikipedia.org/wiki/Katz_centrality) for more details on the algorithm.\n",
    "\n",
    "To compute the Katz centrality scores for a graph in cuGraph we use:<br>\n",
    "__df = cugraph.katz_centrality(G,alpha=0.1, max_iter=100, tol=1.0e-6, nstart=None, normalized=True)__\n",
    "\n",
    "    G: cugraph.Graph object\n",
    "    alpha: float, Attenuation factor. default is 0.1\n",
    "    max_iter: int, The maximum number of iterations before an answer is returned.\n",
    "            This can be used to limit the execution time and do an early exit\n",
    "            before the solver reaches the convergence tolerance. If this value\n",
    "            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\n",
    "            magnitude value. The lower the tolerance the better the approximation. If\n",
    "            this value is 0.0f, cuGraph will use the default value which is 0.00001.\n",
    "            Setting too small a tolerance can lead to non-convergence due to numerical\n",
    "            roundoff. Usually values between 0.01 and 0.00001 are acceptable.\n",
    "    nstart: cuDataFrame, GPU Dataframe containing the initial guess for katz centrality. \n",
    "            Default is None\n",
    "    normalized: bool, If True normalize the resulting katz centrality values.  \n",
    "            Default is True\n",
    "\n",
    "Returns:\n",
    "\n",
    "    df: a cudf.DataFrame object with two columns:\n",
    "        df['vertex']: The vertex identifier for the vertex\n",
    "        df['katz_centrality']: The Katz centrality score for the vertex\n",
    "\n",
    "\n",
    "\n",
    "The value of _alpha_ should be<br>\n",
    "$\\alpha < \\frac{1}{\\lambda _{max} }$\n",
    "currently the user is responsible for setting alpha appropriately.\n",
    "\n",
    "### _NOTICE_\n",
    "There is a difference between how cuGraph and how NetworkX computes the Katz centrality score.  That difference leads to the scores not matching.  cuGraph does not currently support the 'beta' and 'weight' parameters as seen in the corresponding networkX call. The cuGraph implementation is based on a relaxed version of Katz defined by Foster with a reduced computational complexity of O(n+m)\n",
    "\n",
    "    Foster, K.C., Muth, S.Q., Potterat, J.J. et al.\n",
    "    Computational & Mathematical Organization Theory (2001) 7: 275.\n",
    "    https://doi.org/10.1023/A:1013470632383\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Some notes about vertex IDs...\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": [
    "### Importing needed Libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import rapids 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": [
    "# Import NetworkX libraries\n",
    "import networkx as nx"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### parameters\n",
    "max_iter determines the number of iterations the algorithm will run to seek convergence\n",
    "tol is the maximum difference that indicates convergence.\n",
    "The algorithm will fail if it fails to converge within the tolerance (tol) after max_iter number of runs. This is often due to dataset characteristics.\n"
   ]
  },
  {
   "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"
   ]
  },
  {
   "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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute degree and get the max\n",
    "degree = G.degrees()\n",
    "lamda = degree['out_degree'].max()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"The max degree is \" + str(lamda))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Call the Katz algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "alpha = 1 / lamda"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call cugraph.katz_centrality to get the Katz scores\n",
    "gdf_katz = cugraph.katz_centrality(G, alpha=alpha)"
   ]
  },
  {
   "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",
    "gdf_katz.sort_values(by='katz_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": [
    "k_nx = nx.katz_centrality(Gnx, alpha=alpha, max_iter=max_iter, tol=tol)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k_nx_s = sorted(((value, key) for (key,value) in k_nx.items()), reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k_nx_s[:5]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As mentioned, the scores are different but the ranking is the same."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The Numpy version\n",
    "k_nx_mp = nx.katz_centrality_numpy(Gnx, alpha=alpha)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(((value, key) for (key,value) in k_nx_mp.items()), reverse=True)[:5]"
   ]
  },
  {
   "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 (ipykernel)",
   "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
}