notebooks/algorithms/link_prediction/Jaccard-Similarity.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Jaccard Similarity\n",
    "----\n",
    "\n",
    "In this notebook we will explore the Jaccard vertex similarity metrics available in cuGraph."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "The Jaccard similarity between two sets is defined as the ratio of the volume of their intersection divided by the volume of their union. \n",
    "\n",
    "The Jaccard Similarity can then be expressed as\n",
    "\n",
    "$\\text{Jaccard similarity} = \\frac{|A \\cap B|}{|A \\cup B|}$\n",
    "\n",
    "\n",
    "To compute the Jaccard similarity between all pairs of vertices connected by an edge in cuGraph use: <br>\n",
    "__df = cugraph.jaccard(G)__\n",
    "\n",
    "    G: A cugraph.Graph object\n",
    "\n",
    "Returns:\n",
    "\n",
    "    df: cudf.DataFrame with three columns:\n",
    "        df[\"first\"]: The first vertex id of each pair.\n",
    "        df[\"second\"]: The second vertex id of each pair.\n",
    "        df[\"jaccard_coeff\"]: The jaccard coefficient computed between the vertex pairs.\n",
    "<br>\n",
    "\n",
    "__References__ \n",
    "- https://research.nvidia.com/publication/2017-11_Parallel-Jaccard-and \n",
    "\n",
    "__Additional Reading__ \n",
    "- [Wikipedia: Jaccard](https://en.wikipedia.org/wiki/Jaccard_index)\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",
    "<img src=\"../../img/karate_similarity.png\" width=\"50%\"/>\n",
    "\n",
    "This is a small graph which allows for easy visual inspection to validate results."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Let's get started!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "\n",
    "# The cugraph.datasets package contains several common graph datasets useful\n",
    "# for testing and demonstrations.\n",
    "from cugraph.datasets import karate"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create the Graph object"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a cugraph.Graph object from the karate dataset. Download the karate\n",
    "# dataset if not already present on disk.\n",
    "G = karate.get_graph(download=True)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Run `jaccard`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute Jaccard coefficients for all pairs of vertices that are part of the\n",
    "# two-hop neighborhood for each vertex.\n",
    "jaccard_coeffs = cugraph.jaccard(G)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Analyze the results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Remove redundancies (remove (b, a) if (a, b) is present) and pairs consisting\n",
    "# of the same vertices (a, a) from the results, then sort from most similar to\n",
    "# least.\n",
    "jaccard_coeffs = jaccard_coeffs.query(\"first < second\")\n",
    "jaccard_coeffs = jaccard_coeffs.sort_values(\"jaccard_coeff\", ascending=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Show the top-20 most similar vertices.\n",
    "jaccard_coeffs.head(20)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see that several pairs have a coefficient of 1.0, meaning they have\n",
    "the same set of neighbors. This can be easily verified in the plot above."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have to specify vertices in a DataFrame to see their similarity if they\n",
    "are not part of the same two-hop neighborhood."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cugraph.jaccard(G, cudf.DataFrame([(16, 33)]))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, the coefficient is 0.0 because vertices 16 and 33 do not share any\n",
    "neighbors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Now we look at weighted Jaccard!\n",
    "\n",
    "A full explanation of the weighted jaccard is found [here](https://en.wikipedia.org/wiki/Jaccard_index#Weighted_Jaccard_similarity_and_distance).\n",
    "\n",
    "The Dining Preferences data set is a staple of smallest scale social network analysis.\n",
    "The data represents the first (weight = 1) and second (weight = 2) dining partner preference from a survey done in a small school dormitory.\n",
    "\n",
    "This data originated in social network publication by J.L. Moreno\n",
    "\n",
    "Reference: J. L. Moreno (1960). The Sociometry Reader. The Free Press, Glencoe, Illinois, pg.35\n",
    "\n",
    "\n",
    "Here is a visualization of the dataset\n",
    "<img src=\"../../img/dorm_data_diagram.png\" width=\"100%\"/>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### First pull in the dining preferences data set and load it into a cuGraph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import the dining preferences dataset from cugraph's examples\n",
    "from cugraph.datasets import dining_prefs\n",
    "# load the graph making sure to not ignore the weights\n",
    "G = dining_prefs.get_graph(download=True, store_transposed=True, ignore_weights=False)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Do the calculations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculate both the unweighted and weighted Jaccard\n",
    "jaccard_coeffs = cugraph.jaccard(G)\n",
    "jaccard_weighted = cugraph.jaccard(G, use_weight=True)\n",
    "# rename the weighted results\n",
    "jaccard_weighted = jaccard_weighted.rename(columns={'jaccard_coeff' : 'weighted_jaccard' })"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Join the results dataframes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>first</th>\n",
       "      <th>second</th>\n",
       "      <th>jaccard_coeff</th>\n",
       "      <th>weighted_jaccard</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Lena</td>\n",
       "      <td>Marion</td>\n",
       "      <td>0.125000</td>\n",
       "      <td>0.076923</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Lena</td>\n",
       "      <td>Adele</td>\n",
       "      <td>0.142857</td>\n",
       "      <td>0.090909</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Lena</td>\n",
       "      <td>Ellen</td>\n",
       "      <td>0.166667</td>\n",
       "      <td>0.100000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Lena</td>\n",
       "      <td>Louise</td>\n",
       "      <td>0.200000</td>\n",
       "      <td>0.111111</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Louise</td>\n",
       "      <td>Eva</td>\n",
       "      <td>0.111111</td>\n",
       "      <td>0.076923</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    first  second  jaccard_coeff  weighted_jaccard\n",
       "0    Lena  Marion       0.125000          0.076923\n",
       "1    Lena   Adele       0.142857          0.090909\n",
       "2    Lena   Ellen       0.166667          0.100000\n",
       "3    Lena  Louise       0.200000          0.111111\n",
       "4  Louise     Eva       0.111111          0.076923"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Merge the two results together joining on the vertices pairs\n",
    "jaccard_merged = jaccard_coeffs.merge(jaccard_weighted, on=['first','second'], how='left')\n",
    "jaccard_merged.sort_values('weighted_jaccard',ascending=False)\n",
    "jaccard_merged.head()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "### It's that easy with cuGraph\n",
    "\n",
    "Copyright (c) 2019-2024, 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.13"
  },
  "vscode": {
   "interpreter": {
    "hash": "cee8a395f2f0c5a5bcf513ae8b620111f4346eff6dc64e1ea99c951b2ec68604"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}