cugraph/Vertex-Similarity.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Vertex Similarity\n",
    "----\n",
    "\n",
    "In this notebook, we will use cuGraph to compute vertex similarity using both the Jaccard Similarity and the Overlap Coefficient.  \n",
    "\n",
    "\n",
    "Notebook Credits\n",
    "\n",
    "    Original Authors: Bradley Rees\n",
    "    Last Edit: 08/13/2019\n",
    "\n",
    "RAPIDS Versions: 0.9.0\n",
    "\n",
    "Test Hardware\n",
    "* GV100 32G, CUDA 10.0\n",
    "\n",
    "\n",
    "\n",
    "## Introduction\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Defining a Set\n",
    "Both Jaccard and the Overlap Coefficient operate on sets, and in a graph setting, those sets are the list of neighbor vertices. <br>\n",
    "For those that like math:  The neighbors of a vertex, _v_, is defined as the set, _U_, of vertices connected by way of an edge to vertex v, or _N(v) = {U} where v ∈ V and ∀ u ∈ U ∃ edge(v,u)∈ E_.\n",
    "\n",
    "For the rest of this introduction, set A will equate to A = N(i) and set B will quate to B = N(j).  That just make the rest of the text more readable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Jaccard Similarity\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 defined as\n",
    "\n",
    "<a href=\"https://www.codecogs.com/eqnedit.php?latex=js(A,B)&space;=&space;\\frac{|A&space;\\cap&space;B|}{|A&space;\\cup&space;B&space;|&space;}&space;=&space;\\frac{|A&space;\\cap&space;B|}{&space;|A|&space;&plus;&space;|B|&space;-&space;|A&space;\\cup&space;B&space;|&space;}\" target=\"_blank\"><img src=\"https://latex.codecogs.com/gif.latex?js(A,B)&space;=&space;\\frac{|A&space;\\cap&space;B|}{|A&space;\\cup&space;B&space;|&space;}&space;=&space;\\frac{|A&space;\\cap&space;B|}{&space;|A|&space;&plus;&space;|B|&space;-&space;|A&space;\\cup&space;B&space;|&space;}\" title=\"js(A,B) = \\frac{|A \\cap B|}{|A \\cup B | } = \\frac{|A \\cap B|}{ |A| + |B| - |A \\cup B | }\" /></a>\n",
    "\n",
    "\n",
    "\n",
    "For further detail see Wikipedia - https://en.wikipedia.org/wiki/Jaccard_index\n",
    "\n",
    "To compute the Jaccard similarity between all pairs of vertices connected by an edge in cuGraph use: <br>\n",
    "__jaccard(G)__\n",
    "\n",
    "    G: A cugraph.Graph object\n",
    "\n",
    "Returns:\n",
    "\n",
    "    df: cudf.DataFrame with three names columns:\n",
    "        df[\"source\"]: The source vertex id.\n",
    "        df[\"destination\"]: The destination vertex id.\n",
    "        df[\"jaccard_coeff\"]: The jaccard coefficient computed between the source and destination vertex.\n",
    "\n",
    "<br>\n",
    "\n",
    "\n",
    "__References__\n",
    "\n",
    "    https://research.nvidia.com/publication/2017-11_Parallel-Jaccard-and"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Overlap Coefficient\n",
    "\n",
    "The Overlap Coefficient between two sets is defined as the ratio of the volume of their intersection divided by the volume of the smaller set.\n",
    "The Overlap Coefficient can be defined as\n",
    "\n",
    "<a href=\"https://www.codecogs.com/eqnedit.php?latex=oc(A,B)&space;=&space;\\frac{|A|&space;\\cap&space;|B|}{min(|A|,&space;|B|)&space;}\" target=\"_blank\"><img src=\"https://latex.codecogs.com/gif.latex?oc(A,B)&space;=&space;\\frac{|A&space;\\cap&space;B|}{min(|A|,&space;|B|)&space;}\" title=\"oc(A,B) = \\frac{|A \\cap B|}{min(|A|, |B|) }\" /></a>\n",
    "\n",
    "For further detail see Wikipedia - https://en.wikipedia.org/wiki/Overlap_coefficient\n",
    "\n",
    "To compute the Overlap Coefficient between all pairs of vertices connected by an edge in cuGraph use: <br>\n",
    "\n",
    "__overlap(G)__\n",
    "\n",
    "    G: A cugraph.Graph object\n",
    "\n",
    "Returns:\n",
    "\n",
    "    df: cudf.DataFrame with three names columns:\n",
    "        df[\"source\"]: The source vertex id.\n",
    "        df[\"destination\"]: The destination vertex id.\n",
    "        df[\"overlap_coeff\"]: The overlap coefficient computed between the source and destination vertex.\n",
    "\n"
   ]
  },
  {
   "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",
    "This is a small graph which allows for easy visual inspection to validate results.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "from collections import OrderedDict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Define some Print functions\n",
    "(the `del` are not needed since going out of scope should free memory)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing the top most similar vertices\n",
    "def print_most_similar_jaccard(df):\n",
    "    \n",
    "    jmax = df['jaccard_coeff'].max()\n",
    "    dm = df.query('jaccard_coeff >= @jmax')    \n",
    "    \n",
    "    #find the best\n",
    "    for i in range(len(dm)):    \n",
    "        print(\"Vertices \" + str(dm['source'][i]) + \" and \" + \n",
    "              str(dm['destination'][i]) + \" are most similar with score: \" \n",
    "              + str(dm['jaccard_coeff'][i]))\n",
    "    del jmax\n",
    "    del dm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing the top most similar vertices\n",
    "def print_most_similar_overlap(df):\n",
    "    \n",
    "    smax = df['overlap_coeff'].max()\n",
    "    dm = df.query('overlap_coeff >= @smax')      \n",
    "    \n",
    "    for i in range(len(dm)):\n",
    "        print(\"Vertices \" + str(dm['source'][i]) + \" and \" + \n",
    "          str(dm['destination'][i]) + \" are most similar with score: \" \n",
    "          + str(dm['overlap_coeff'][i]))\n",
    "        \n",
    "    del smax\n",
    "    del dm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing jaccard similar vertices based on a threshold\n",
    "def print_jaccard_threshold(_d, limit):\n",
    "    \n",
    "    filtered = _d.query('jaccard_coeff > @limit')\n",
    "    \n",
    "    for i in range(len(filtered)):\n",
    "        print(\"Vertices \" + str(filtered['source'][i]) + \" and \" + \n",
    "            str(filtered['destination'][i]) + \" are similar with score: \" + \n",
    "            str(filtered['jaccard_coeff'][i]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing similar vertices based on a threshold\n",
    "def print_overlap_threshold(_d, limit):\n",
    "    \n",
    "    filtered = _d.query('overlap_coeff > @limit')\n",
    "    \n",
    "    for i in range(len(filtered)):\n",
    "        if filtered['source'][i] != filtered['destination'][i] :\n",
    "            print(\"Vertices \" + str(filtered['source'][i]) + \" and \" + \n",
    "                str(filtered['destination'][i]) + \" are similar with score: \" + \n",
    "                str(filtered['overlap_coeff'][i]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read the CSV datafile using cuDF\n",
    "data file is actually _tab_ separated, so we need to set the delimiter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test file  \n",
    "datafile='./data/karate-data.csv'\n",
    "\n",
    "# define the column names\n",
    "cols = [\"src\", \"dst\"]\n",
    "\n",
    "# define the column data types\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": "code",
   "execution_count": 7,
   "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>src</th>\n",
       "      <th>dst</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>1</td>\n",
       "      <td>7</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>1</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>1</td>\n",
       "      <td>9</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>1</td>\n",
       "      <td>11</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>1</td>\n",
       "      <td>12</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>1</td>\n",
       "      <td>13</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>1</td>\n",
       "      <td>14</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>1</td>\n",
       "      <td>18</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>1</td>\n",
       "      <td>20</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>1</td>\n",
       "      <td>22</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>1</td>\n",
       "      <td>32</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>17</th>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>18</th>\n",
       "      <td>2</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>19</th>\n",
       "      <td>2</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>20</th>\n",
       "      <td>2</td>\n",
       "      <td>14</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>21</th>\n",
       "      <td>2</td>\n",
       "      <td>18</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>22</th>\n",
       "      <td>2</td>\n",
       "      <td>20</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>23</th>\n",
       "      <td>2</td>\n",
       "      <td>22</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>24</th>\n",
       "      <td>2</td>\n",
       "      <td>31</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>25</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>26</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>27</th>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>28</th>\n",
       "      <td>3</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>29</th>\n",
       "      <td>3</td>\n",
       "      <td>9</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>126</th>\n",
       "      <td>32</td>\n",
       "      <td>34</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>127</th>\n",
       "      <td>33</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>128</th>\n",
       "      <td>33</td>\n",
       "      <td>9</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>129</th>\n",
       "      <td>33</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>130</th>\n",
       "      <td>33</td>\n",
       "      <td>16</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>131</th>\n",
       "      <td>33</td>\n",
       "      <td>19</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>132</th>\n",
       "      <td>33</td>\n",
       "      <td>21</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>133</th>\n",
       "      <td>33</td>\n",
       "      <td>23</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>134</th>\n",
       "      <td>33</td>\n",
       "      <td>24</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>135</th>\n",
       "      <td>33</td>\n",
       "      <td>30</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>136</th>\n",
       "      <td>33</td>\n",
       "      <td>31</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>137</th>\n",
       "      <td>33</td>\n",
       "      <td>32</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>138</th>\n",
       "      <td>33</td>\n",
       "      <td>34</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>139</th>\n",
       "      <td>34</td>\n",
       "      <td>9</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>140</th>\n",
       "      <td>34</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>141</th>\n",
       "      <td>34</td>\n",
       "      <td>14</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>142</th>\n",
       "      <td>34</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>143</th>\n",
       "      <td>34</td>\n",
       "      <td>16</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>144</th>\n",
       "      <td>34</td>\n",
       "      <td>19</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>145</th>\n",
       "      <td>34</td>\n",
       "      <td>20</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>146</th>\n",
       "      <td>34</td>\n",
       "      <td>21</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>147</th>\n",
       "      <td>34</td>\n",
       "      <td>23</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>148</th>\n",
       "      <td>34</td>\n",
       "      <td>24</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>149</th>\n",
       "      <td>34</td>\n",
       "      <td>27</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>150</th>\n",
       "      <td>34</td>\n",
       "      <td>28</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>151</th>\n",
       "      <td>34</td>\n",
       "      <td>29</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>152</th>\n",
       "      <td>34</td>\n",
       "      <td>30</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>153</th>\n",
       "      <td>34</td>\n",
       "      <td>31</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>154</th>\n",
       "      <td>34</td>\n",
       "      <td>32</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>155</th>\n",
       "      <td>34</td>\n",
       "      <td>33</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>156 rows × 2 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "     src  dst\n",
       "0      1    2\n",
       "1      1    3\n",
       "2      1    4\n",
       "3      1    5\n",
       "4      1    6\n",
       "5      1    7\n",
       "6      1    8\n",
       "7      1    9\n",
       "8      1   11\n",
       "9      1   12\n",
       "10     1   13\n",
       "11     1   14\n",
       "12     1   18\n",
       "13     1   20\n",
       "14     1   22\n",
       "15     1   32\n",
       "16     2    1\n",
       "17     2    3\n",
       "18     2    4\n",
       "19     2    8\n",
       "20     2   14\n",
       "21     2   18\n",
       "22     2   20\n",
       "23     2   22\n",
       "24     2   31\n",
       "25     3    1\n",
       "26     3    2\n",
       "27     3    4\n",
       "28     3    8\n",
       "29     3    9\n",
       "..   ...  ...\n",
       "126   32   34\n",
       "127   33    3\n",
       "128   33    9\n",
       "129   33   15\n",
       "130   33   16\n",
       "131   33   19\n",
       "132   33   21\n",
       "133   33   23\n",
       "134   33   24\n",
       "135   33   30\n",
       "136   33   31\n",
       "137   33   32\n",
       "138   33   34\n",
       "139   34    9\n",
       "140   34   10\n",
       "141   34   14\n",
       "142   34   15\n",
       "143   34   16\n",
       "144   34   19\n",
       "145   34   20\n",
       "146   34   21\n",
       "147   34   23\n",
       "148   34   24\n",
       "149   34   27\n",
       "150   34   28\n",
       "151   34   29\n",
       "152   34   30\n",
       "153   34   31\n",
       "154   34   32\n",
       "155   34   33\n",
       "\n",
       "[156 rows x 2 columns]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Let's look at the DataFrame. There should be two columns and 156 records\n",
    "gdf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "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>src</th>\n",
       "      <th>dst</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   src  dst\n",
       "0    1    2\n",
       "1    1    3\n",
       "2    1    4\n",
       "3    1    5\n",
       "4    1    6"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Look at the first few data records - the output should be two colums src and dst\n",
    "gdf.head().to_pandas()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph \n",
    "G = cugraph.Graph()\n",
    "G.add_edge_list(gdf[\"src\"], gdf[\"dst\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "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>vertex</th>\n",
       "      <th>degree</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>32</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>18</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>20</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>12</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>5</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>6</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>7</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>8</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>9</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>10</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>11</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>12</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>13</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>14</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>15</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>16</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>17</th>\n",
       "      <td>17</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>18</th>\n",
       "      <td>18</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>19</th>\n",
       "      <td>19</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>20</th>\n",
       "      <td>20</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>21</th>\n",
       "      <td>21</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>22</th>\n",
       "      <td>22</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>23</th>\n",
       "      <td>23</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>24</th>\n",
       "      <td>24</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>25</th>\n",
       "      <td>25</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>26</th>\n",
       "      <td>26</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>27</th>\n",
       "      <td>27</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>28</th>\n",
       "      <td>28</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>29</th>\n",
       "      <td>29</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>30</th>\n",
       "      <td>30</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>31</th>\n",
       "      <td>31</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>32</th>\n",
       "      <td>32</td>\n",
       "      <td>12</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>33</th>\n",
       "      <td>33</td>\n",
       "      <td>24</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>34</th>\n",
       "      <td>34</td>\n",
       "      <td>34</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    vertex  degree\n",
       "0        0       0\n",
       "1        1      32\n",
       "2        2      18\n",
       "3        3      20\n",
       "4        4      12\n",
       "5        5       6\n",
       "6        6       8\n",
       "7        7       8\n",
       "8        8       8\n",
       "9        9      10\n",
       "10      10       4\n",
       "11      11       6\n",
       "12      12       2\n",
       "13      13       4\n",
       "14      14      10\n",
       "15      15       4\n",
       "16      16       4\n",
       "17      17       4\n",
       "18      18       4\n",
       "19      19       4\n",
       "20      20       6\n",
       "21      21       4\n",
       "22      22       4\n",
       "23      23       4\n",
       "24      24      10\n",
       "25      25       6\n",
       "26      26       6\n",
       "27      27       4\n",
       "28      28       8\n",
       "29      29       6\n",
       "30      30       8\n",
       "31      31       8\n",
       "32      32      12\n",
       "33      33      24\n",
       "34      34      34"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G.degree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "35"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# How many vertices are in the graph?  Remember that Graph is zero based\n",
    "G.number_of_vertices()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_The test graph has only 34 vertices, so why is the Graph listing 35?_\n",
    "\n",
    "As mentioned above, cuGraph vertex numbering is zero-based, meaning that the first vertex ID starts at zero.  The test dataset is 1-based.  Because of that, the Graph object adds an extra isolated vertex with an ID of zero.  Hence the difference in vertex count.  \n",
    "We are working on a renumbering feature to address this issue.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Jaccard "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.82 ms, sys: 0 ns, total: 1.82 ms\n",
      "Wall time: 1.56 ms\n"
     ]
    }
   ],
   "source": [
    "# Call cugraph.nvJaccard \n",
    "%time df = cugraph.jaccard(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Most similar shoul be 33 and 34.\n",
    "Vertex 33 has 12 neighbors, vertex 34 has 17 neighbors.  They share 10 neighbors in common:\n",
    "$jaccard = 10 / (10 + (12 -10) + (17-10)) = 10 / 19 = 0.526$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 33 and 34 are most similar with score: 0.5263158\n",
      "Vertices 34 and 33 are most similar with score: 0.5263158\n"
     ]
    }
   ],
   "source": [
    "print_most_similar_jaccard(df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 4 and 8 are similar with score: 0.42857143\n",
      "Vertices 8 and 4 are similar with score: 0.42857143\n",
      "Vertices 33 and 34 are similar with score: 0.5263158\n",
      "Vertices 34 and 33 are similar with score: 0.5263158\n"
     ]
    }
   ],
   "source": [
    "### let's look at all similarities over a threshold\n",
    "print_jaccard_threshold(df, 0.4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Since it is a small graph we can print all scores.\n",
    "# Notice that only connected vertices are computed\n",
    "\n",
    "# let's sort the data first.  Please note that you may get a warning.  Just ignore it.  \n",
    "## It is just converted into a dataframe so that we could do this function call.  \n",
    "## If we were going to actually do further work on it, we would leave it as it was :)\n",
    "\n",
    "g = df.groupby(['jaccard_coeff'], method='cudf', as_index=False)\n",
    "df_s = g.as_df()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 3 and 33 are similar with score: 0.04761905\n",
      "Vertices 33 and 3 are similar with score: 0.04761905\n",
      "Vertices 1 and 9 are similar with score: 0.05\n",
      "Vertices 9 and 1 are similar with score: 0.05\n",
      "Vertices 28 and 34 are similar with score: 0.05\n",
      "Vertices 34 and 28 are similar with score: 0.05\n",
      "Vertices 29 and 34 are similar with score: 0.05263158\n",
      "Vertices 34 and 29 are similar with score: 0.05263158\n",
      "Vertices 1 and 20 are similar with score: 0.055555556\n",
      "Vertices 15 and 34 are similar with score: 0.055555556\n",
      "Vertices 16 and 34 are similar with score: 0.055555556\n",
      "Vertices 19 and 34 are similar with score: 0.055555556\n",
      "Vertices 20 and 1 are similar with score: 0.055555556\n",
      "Vertices 21 and 34 are similar with score: 0.055555556\n",
      "Vertices 23 and 34 are similar with score: 0.055555556\n",
      "Vertices 27 and 34 are similar with score: 0.055555556\n",
      "Vertices 34 and 15 are similar with score: 0.055555556\n",
      "Vertices 34 and 16 are similar with score: 0.055555556\n",
      "Vertices 34 and 19 are similar with score: 0.055555556\n",
      "Vertices 34 and 21 are similar with score: 0.055555556\n",
      "Vertices 34 and 23 are similar with score: 0.055555556\n",
      "Vertices 34 and 27 are similar with score: 0.055555556\n",
      "Vertices 1 and 13 are similar with score: 0.05882353\n",
      "Vertices 1 and 18 are similar with score: 0.05882353\n",
      "Vertices 1 and 22 are similar with score: 0.05882353\n",
      "Vertices 13 and 1 are similar with score: 0.05882353\n",
      "Vertices 18 and 1 are similar with score: 0.05882353\n",
      "Vertices 22 and 1 are similar with score: 0.05882353\n",
      "Vertices 32 and 33 are similar with score: 0.05882353\n",
      "Vertices 33 and 32 are similar with score: 0.05882353\n",
      "Vertices 15 and 33 are similar with score: 0.07692308\n",
      "Vertices 16 and 33 are similar with score: 0.07692308\n",
      "Vertices 19 and 33 are similar with score: 0.07692308\n",
      "Vertices 21 and 33 are similar with score: 0.07692308\n",
      "Vertices 23 and 33 are similar with score: 0.07692308\n",
      "Vertices 33 and 15 are similar with score: 0.07692308\n",
      "Vertices 33 and 16 are similar with score: 0.07692308\n",
      "Vertices 33 and 19 are similar with score: 0.07692308\n",
      "Vertices 33 and 21 are similar with score: 0.07692308\n",
      "Vertices 33 and 23 are similar with score: 0.07692308\n",
      "Vertices 2 and 20 are similar with score: 0.09090909\n",
      "Vertices 20 and 2 are similar with score: 0.09090909\n",
      "Vertices 32 and 34 are similar with score: 0.0952381\n",
      "Vertices 34 and 32 are similar with score: 0.0952381\n",
      "Vertices 2 and 18 are similar with score: 0.1\n",
      "Vertices 2 and 22 are similar with score: 0.1\n",
      "Vertices 9 and 34 are similar with score: 0.1\n",
      "Vertices 18 and 2 are similar with score: 0.1\n",
      "Vertices 22 and 2 are similar with score: 0.1\n",
      "Vertices 34 and 9 are similar with score: 0.1\n",
      "Vertices 31 and 34 are similar with score: 0.10526316\n",
      "Vertices 34 and 31 are similar with score: 0.10526316\n",
      "Vertices 1 and 6 are similar with score: 0.11111111\n",
      "Vertices 1 and 7 are similar with score: 0.11111111\n",
      "Vertices 6 and 1 are similar with score: 0.11111111\n",
      "Vertices 7 and 1 are similar with score: 0.11111111\n",
      "Vertices 1 and 5 are similar with score: 0.11764706\n",
      "Vertices 1 and 11 are similar with score: 0.11764706\n",
      "Vertices 5 and 1 are similar with score: 0.11764706\n",
      "Vertices 11 and 1 are similar with score: 0.11764706\n",
      "Vertices 24 and 28 are similar with score: 0.125\n",
      "Vertices 25 and 32 are similar with score: 0.125\n",
      "Vertices 26 and 32 are similar with score: 0.125\n",
      "Vertices 28 and 24 are similar with score: 0.125\n",
      "Vertices 29 and 32 are similar with score: 0.125\n",
      "Vertices 32 and 25 are similar with score: 0.125\n",
      "Vertices 32 and 26 are similar with score: 0.125\n",
      "Vertices 32 and 29 are similar with score: 0.125\n",
      "Vertices 24 and 33 are similar with score: 0.13333334\n",
      "Vertices 33 and 24 are similar with score: 0.13333334\n",
      "Vertices 4 and 13 are similar with score: 0.14285715\n",
      "Vertices 13 and 4 are similar with score: 0.14285715\n",
      "Vertices 30 and 33 are similar with score: 0.14285715\n",
      "Vertices 31 and 33 are similar with score: 0.14285715\n",
      "Vertices 33 and 30 are similar with score: 0.14285715\n",
      "Vertices 33 and 31 are similar with score: 0.14285715\n",
      "Vertices 3 and 9 are similar with score: 0.15384616\n",
      "Vertices 9 and 3 are similar with score: 0.15384616\n",
      "Vertices 24 and 34 are similar with score: 0.15789473\n",
      "Vertices 34 and 24 are similar with score: 0.15789473\n",
      "Vertices 1 and 14 are similar with score: 0.16666667\n",
      "Vertices 5 and 7 are similar with score: 0.16666667\n",
      "Vertices 6 and 11 are similar with score: 0.16666667\n",
      "Vertices 7 and 5 are similar with score: 0.16666667\n",
      "Vertices 11 and 6 are similar with score: 0.16666667\n",
      "Vertices 14 and 1 are similar with score: 0.16666667\n",
      "Vertices 30 and 34 are similar with score: 0.16666667\n",
      "Vertices 34 and 30 are similar with score: 0.16666667\n",
      "Vertices 1 and 8 are similar with score: 0.1764706\n",
      "Vertices 8 and 1 are similar with score: 0.1764706\n",
      "Vertices 5 and 11 are similar with score: 0.2\n",
      "Vertices 6 and 17 are similar with score: 0.2\n",
      "Vertices 7 and 17 are similar with score: 0.2\n",
      "Vertices 11 and 5 are similar with score: 0.2\n",
      "Vertices 17 and 6 are similar with score: 0.2\n",
      "Vertices 17 and 7 are similar with score: 0.2\n",
      "Vertices 25 and 26 are similar with score: 0.2\n",
      "Vertices 26 and 25 are similar with score: 0.2\n",
      "Vertices 27 and 30 are similar with score: 0.2\n",
      "Vertices 30 and 27 are similar with score: 0.2\n",
      "Vertices 9 and 33 are similar with score: 0.21428572\n",
      "Vertices 33 and 9 are similar with score: 0.21428572\n",
      "Vertices 1 and 3 are similar with score: 0.23809524\n",
      "Vertices 3 and 1 are similar with score: 0.23809524\n",
      "Vertices 3 and 14 are similar with score: 0.25\n",
      "Vertices 14 and 3 are similar with score: 0.25\n",
      "Vertices 2 and 3 are similar with score: 0.26666668\n",
      "Vertices 3 and 2 are similar with score: 0.26666668\n",
      "Vertices 2 and 14 are similar with score: 0.27272728\n",
      "Vertices 3 and 8 are similar with score: 0.27272728\n",
      "Vertices 8 and 3 are similar with score: 0.27272728\n",
      "Vertices 14 and 2 are similar with score: 0.27272728\n",
      "Vertices 9 and 31 are similar with score: 0.2857143\n",
      "Vertices 24 and 30 are similar with score: 0.2857143\n",
      "Vertices 30 and 24 are similar with score: 0.2857143\n",
      "Vertices 31 and 9 are similar with score: 0.2857143\n",
      "Vertices 1 and 4 are similar with score: 0.29411766\n",
      "Vertices 4 and 1 are similar with score: 0.29411766\n",
      "Vertices 2 and 8 are similar with score: 0.3\n",
      "Vertices 8 and 2 are similar with score: 0.3\n",
      "Vertices 3 and 4 are similar with score: 0.33333334\n",
      "Vertices 4 and 3 are similar with score: 0.33333334\n",
      "Vertices 6 and 7 are similar with score: 0.33333334\n",
      "Vertices 7 and 6 are similar with score: 0.33333334\n",
      "Vertices 2 and 4 are similar with score: 0.36363637\n",
      "Vertices 4 and 2 are similar with score: 0.36363637\n",
      "Vertices 4 and 14 are similar with score: 0.375\n",
      "Vertices 14 and 4 are similar with score: 0.375\n",
      "Vertices 1 and 2 are similar with score: 0.3888889\n",
      "Vertices 2 and 1 are similar with score: 0.3888889\n",
      "Vertices 4 and 8 are similar with score: 0.42857143\n",
      "Vertices 8 and 4 are similar with score: 0.42857143\n",
      "Vertices 33 and 34 are similar with score: 0.5263158\n",
      "Vertices 34 and 33 are similar with score: 0.5263158\n"
     ]
    }
   ],
   "source": [
    "# The groupby as_df function returns a tuple where the first item is the dataframe\n",
    "print_jaccard_threshold(df_s[0], 0.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Overlap Coefficient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call cugraph.nvJaccard \n",
    "do = cugraph.overlap(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 1 and 4 are most similar with score: 0.8333333\n",
      "Vertices 4 and 1 are most similar with score: 0.8333333\n",
      "Vertices 33 and 34 are most similar with score: 0.8333333\n",
      "Vertices 34 and 33 are most similar with score: 0.8333333\n"
     ]
    }
   ],
   "source": [
    "print_most_similar_overlap(do)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Expanding vertex pairs for similarity scoring"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get all two-hop vertex pairs\n",
    "p = G.get_two_hop_neighbors()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's look at the Jaccard score\n",
    "j2 = cugraph.jaccard(G, first=p['first'], second=p['second'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 15 and 16 are most similar with score: 1.0\n",
      "Vertices 15 and 19 are most similar with score: 1.0\n",
      "Vertices 15 and 21 are most similar with score: 1.0\n",
      "Vertices 15 and 23 are most similar with score: 1.0\n",
      "Vertices 16 and 15 are most similar with score: 1.0\n",
      "Vertices 16 and 19 are most similar with score: 1.0\n",
      "Vertices 16 and 21 are most similar with score: 1.0\n",
      "Vertices 16 and 23 are most similar with score: 1.0\n",
      "Vertices 18 and 22 are most similar with score: 1.0\n",
      "Vertices 19 and 15 are most similar with score: 1.0\n",
      "Vertices 19 and 16 are most similar with score: 1.0\n",
      "Vertices 19 and 21 are most similar with score: 1.0\n",
      "Vertices 19 and 23 are most similar with score: 1.0\n",
      "Vertices 21 and 15 are most similar with score: 1.0\n",
      "Vertices 21 and 16 are most similar with score: 1.0\n",
      "Vertices 21 and 19 are most similar with score: 1.0\n",
      "Vertices 21 and 23 are most similar with score: 1.0\n",
      "Vertices 22 and 18 are most similar with score: 1.0\n",
      "Vertices 23 and 15 are most similar with score: 1.0\n",
      "Vertices 23 and 16 are most similar with score: 1.0\n",
      "Vertices 23 and 19 are most similar with score: 1.0\n",
      "Vertices 23 and 21 are most similar with score: 1.0\n"
     ]
    }
   ],
   "source": [
    "print_most_similar_jaccard(j2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "notice that there are a lot of very similar vertices.  For example vertices 15 and 16 share their only two neighbors in common.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "j2o = cugraph.overlap(G, first=p['first'], second=p['second'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 1 and 17 are most similar with score: 1.0\n",
      "Vertices 2 and 12 are most similar with score: 1.0\n",
      "Vertices 2 and 13 are most similar with score: 1.0\n",
      "Vertices 3 and 12 are most similar with score: 1.0\n",
      "Vertices 3 and 13 are most similar with score: 1.0\n",
      "Vertices 3 and 18 are most similar with score: 1.0\n",
      "Vertices 3 and 22 are most similar with score: 1.0\n",
      "Vertices 4 and 12 are most similar with score: 1.0\n",
      "Vertices 4 and 18 are most similar with score: 1.0\n",
      "Vertices 4 and 22 are most similar with score: 1.0\n",
      "Vertices 5 and 6 are most similar with score: 1.0\n",
      "Vertices 5 and 12 are most similar with score: 1.0\n",
      "Vertices 6 and 5 are most similar with score: 1.0\n",
      "Vertices 6 and 12 are most similar with score: 1.0\n",
      "Vertices 7 and 11 are most similar with score: 1.0\n",
      "Vertices 7 and 12 are most similar with score: 1.0\n",
      "Vertices 8 and 12 are most similar with score: 1.0\n",
      "Vertices 8 and 13 are most similar with score: 1.0\n",
      "Vertices 8 and 14 are most similar with score: 1.0\n",
      "Vertices 8 and 18 are most similar with score: 1.0\n",
      "Vertices 8 and 22 are most similar with score: 1.0\n",
      "Vertices 9 and 10 are most similar with score: 1.0\n",
      "Vertices 9 and 12 are most similar with score: 1.0\n",
      "Vertices 9 and 15 are most similar with score: 1.0\n",
      "Vertices 9 and 16 are most similar with score: 1.0\n",
      "Vertices 9 and 19 are most similar with score: 1.0\n",
      "Vertices 9 and 21 are most similar with score: 1.0\n",
      "Vertices 9 and 23 are most similar with score: 1.0\n",
      "Vertices 10 and 9 are most similar with score: 1.0\n",
      "Vertices 10 and 14 are most similar with score: 1.0\n",
      "Vertices 10 and 28 are most similar with score: 1.0\n",
      "Vertices 10 and 29 are most similar with score: 1.0\n",
      "Vertices 10 and 33 are most similar with score: 1.0\n",
      "Vertices 11 and 7 are most similar with score: 1.0\n",
      "Vertices 11 and 12 are most similar with score: 1.0\n",
      "Vertices 12 and 2 are most similar with score: 1.0\n",
      "Vertices 12 and 3 are most similar with score: 1.0\n",
      "Vertices 12 and 4 are most similar with score: 1.0\n",
      "Vertices 12 and 5 are most similar with score: 1.0\n",
      "Vertices 12 and 6 are most similar with score: 1.0\n",
      "Vertices 12 and 7 are most similar with score: 1.0\n",
      "Vertices 12 and 8 are most similar with score: 1.0\n",
      "Vertices 12 and 9 are most similar with score: 1.0\n",
      "Vertices 12 and 11 are most similar with score: 1.0\n",
      "Vertices 12 and 13 are most similar with score: 1.0\n",
      "Vertices 12 and 14 are most similar with score: 1.0\n",
      "Vertices 12 and 18 are most similar with score: 1.0\n",
      "Vertices 12 and 20 are most similar with score: 1.0\n",
      "Vertices 12 and 22 are most similar with score: 1.0\n",
      "Vertices 12 and 32 are most similar with score: 1.0\n",
      "Vertices 13 and 2 are most similar with score: 1.0\n",
      "Vertices 13 and 3 are most similar with score: 1.0\n",
      "Vertices 13 and 8 are most similar with score: 1.0\n",
      "Vertices 13 and 12 are most similar with score: 1.0\n",
      "Vertices 13 and 14 are most similar with score: 1.0\n",
      "Vertices 14 and 8 are most similar with score: 1.0\n",
      "Vertices 14 and 10 are most similar with score: 1.0\n",
      "Vertices 14 and 12 are most similar with score: 1.0\n",
      "Vertices 14 and 13 are most similar with score: 1.0\n",
      "Vertices 14 and 18 are most similar with score: 1.0\n",
      "Vertices 14 and 20 are most similar with score: 1.0\n",
      "Vertices 14 and 22 are most similar with score: 1.0\n",
      "Vertices 15 and 9 are most similar with score: 1.0\n",
      "Vertices 15 and 16 are most similar with score: 1.0\n",
      "Vertices 15 and 19 are most similar with score: 1.0\n",
      "Vertices 15 and 21 are most similar with score: 1.0\n",
      "Vertices 15 and 23 are most similar with score: 1.0\n",
      "Vertices 15 and 24 are most similar with score: 1.0\n",
      "Vertices 15 and 30 are most similar with score: 1.0\n",
      "Vertices 15 and 31 are most similar with score: 1.0\n",
      "Vertices 15 and 32 are most similar with score: 1.0\n",
      "Vertices 16 and 9 are most similar with score: 1.0\n",
      "Vertices 16 and 15 are most similar with score: 1.0\n",
      "Vertices 16 and 19 are most similar with score: 1.0\n",
      "Vertices 16 and 21 are most similar with score: 1.0\n",
      "Vertices 16 and 23 are most similar with score: 1.0\n",
      "Vertices 16 and 24 are most similar with score: 1.0\n",
      "Vertices 16 and 30 are most similar with score: 1.0\n",
      "Vertices 16 and 31 are most similar with score: 1.0\n",
      "Vertices 16 and 32 are most similar with score: 1.0\n",
      "Vertices 17 and 1 are most similar with score: 1.0\n",
      "Vertices 18 and 3 are most similar with score: 1.0\n",
      "Vertices 18 and 4 are most similar with score: 1.0\n",
      "Vertices 18 and 8 are most similar with score: 1.0\n",
      "Vertices 18 and 12 are most similar with score: 1.0\n",
      "Vertices 18 and 14 are most similar with score: 1.0\n",
      "Vertices 18 and 20 are most similar with score: 1.0\n",
      "Vertices 18 and 22 are most similar with score: 1.0\n",
      "Vertices 19 and 9 are most similar with score: 1.0\n",
      "Vertices 19 and 15 are most similar with score: 1.0\n",
      "Vertices 19 and 16 are most similar with score: 1.0\n",
      "Vertices 19 and 21 are most similar with score: 1.0\n",
      "Vertices 19 and 23 are most similar with score: 1.0\n",
      "Vertices 19 and 24 are most similar with score: 1.0\n",
      "Vertices 19 and 30 are most similar with score: 1.0\n",
      "Vertices 19 and 31 are most similar with score: 1.0\n",
      "Vertices 19 and 32 are most similar with score: 1.0\n",
      "Vertices 20 and 12 are most similar with score: 1.0\n",
      "Vertices 20 and 14 are most similar with score: 1.0\n",
      "Vertices 20 and 18 are most similar with score: 1.0\n",
      "Vertices 20 and 22 are most similar with score: 1.0\n",
      "Vertices 21 and 9 are most similar with score: 1.0\n",
      "Vertices 21 and 15 are most similar with score: 1.0\n",
      "Vertices 21 and 16 are most similar with score: 1.0\n",
      "Vertices 21 and 19 are most similar with score: 1.0\n",
      "Vertices 21 and 23 are most similar with score: 1.0\n",
      "Vertices 21 and 24 are most similar with score: 1.0\n",
      "Vertices 21 and 30 are most similar with score: 1.0\n",
      "Vertices 21 and 31 are most similar with score: 1.0\n",
      "Vertices 21 and 32 are most similar with score: 1.0\n",
      "Vertices 22 and 3 are most similar with score: 1.0\n",
      "Vertices 22 and 4 are most similar with score: 1.0\n",
      "Vertices 22 and 8 are most similar with score: 1.0\n",
      "Vertices 22 and 12 are most similar with score: 1.0\n",
      "Vertices 22 and 14 are most similar with score: 1.0\n",
      "Vertices 22 and 18 are most similar with score: 1.0\n",
      "Vertices 22 and 20 are most similar with score: 1.0\n",
      "Vertices 23 and 9 are most similar with score: 1.0\n",
      "Vertices 23 and 15 are most similar with score: 1.0\n",
      "Vertices 23 and 16 are most similar with score: 1.0\n",
      "Vertices 23 and 19 are most similar with score: 1.0\n",
      "Vertices 23 and 21 are most similar with score: 1.0\n",
      "Vertices 23 and 24 are most similar with score: 1.0\n",
      "Vertices 23 and 30 are most similar with score: 1.0\n",
      "Vertices 23 and 31 are most similar with score: 1.0\n",
      "Vertices 23 and 32 are most similar with score: 1.0\n",
      "Vertices 24 and 15 are most similar with score: 1.0\n",
      "Vertices 24 and 16 are most similar with score: 1.0\n",
      "Vertices 24 and 19 are most similar with score: 1.0\n",
      "Vertices 24 and 21 are most similar with score: 1.0\n",
      "Vertices 24 and 23 are most similar with score: 1.0\n",
      "Vertices 24 and 27 are most similar with score: 1.0\n",
      "Vertices 27 and 24 are most similar with score: 1.0\n",
      "Vertices 27 and 33 are most similar with score: 1.0\n",
      "Vertices 28 and 10 are most similar with score: 1.0\n",
      "Vertices 29 and 10 are most similar with score: 1.0\n",
      "Vertices 29 and 33 are most similar with score: 1.0\n",
      "Vertices 30 and 15 are most similar with score: 1.0\n",
      "Vertices 30 and 16 are most similar with score: 1.0\n",
      "Vertices 30 and 19 are most similar with score: 1.0\n",
      "Vertices 30 and 21 are most similar with score: 1.0\n",
      "Vertices 30 and 23 are most similar with score: 1.0\n",
      "Vertices 31 and 15 are most similar with score: 1.0\n",
      "Vertices 31 and 16 are most similar with score: 1.0\n",
      "Vertices 31 and 19 are most similar with score: 1.0\n",
      "Vertices 31 and 21 are most similar with score: 1.0\n",
      "Vertices 31 and 23 are most similar with score: 1.0\n",
      "Vertices 32 and 12 are most similar with score: 1.0\n",
      "Vertices 32 and 15 are most similar with score: 1.0\n",
      "Vertices 32 and 16 are most similar with score: 1.0\n",
      "Vertices 32 and 19 are most similar with score: 1.0\n",
      "Vertices 32 and 21 are most similar with score: 1.0\n",
      "Vertices 32 and 23 are most similar with score: 1.0\n",
      "Vertices 33 and 10 are most similar with score: 1.0\n",
      "Vertices 33 and 27 are most similar with score: 1.0\n",
      "Vertices 33 and 29 are most similar with score: 1.0\n"
     ]
    }
   ],
   "source": [
    "print_most_similar_overlap(j2o)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "the overlap score captures all the same matches that Jaccrd did, but also includes those sets that are exact subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Adjusting the vertex ID\n",
    "Let's adjust all the vertex IDs to be zero based.  We are going to do this by adding two new columns with the adjusted IDs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "gdf[\"src_0\"] = gdf[\"src\"] - 1\n",
    "gdf[\"dst_0\"] = gdf[\"dst\"] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a new Graph \n",
    "G2 = cugraph.Graph()\n",
    "G2.add_edge_list(gdf[\"src_0\"], gdf[\"dst_0\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "34"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# How many vertices are in the graph?  Remember that Graph is zero based while teh data start at vertex 1\n",
    "G2.number_of_vertices()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The number of vertices now matches what is in the test graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call cugraph.nvJaccard \n",
    "df2 = cugraph.jaccard(G2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 32 and 33 are most similar with score: 0.5263158\n",
      "Vertices 33 and 32 are most similar with score: 0.5263158\n"
     ]
    }
   ],
   "source": [
    "print_most_similar_jaccard(df2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Adjusting the vertices back (e.g adding +1 to vertex IDs) yields 33 and 34 which matches the orginal results.\n",
    "For Jaccard, the fact that vertex IDs do not start of 0 is not an issue"
   ]
  },
  {
   "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
}