tutorials/HyperBall-based approximated Harmonic and Closeness with GRAPE.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7673742f",
   "metadata": {},
   "source": [
    "# HyperBall-based approximated Harmonic and Closeness with GRAPE\n",
    "Graphs are an important tool in many areas of computer science, such as social networks, transportation networks, and recommendation systems. One of the key challenges when dealing with large graphs is computing various graph metrics, such as harmonic centrality and closeness centrality, in a reasonable amount of time.\n",
    "\n",
    "HyperBall is an algorithm for computing approximate graph metrics, such as centrality, on large graphs. The GRAPE library contains many features, including a Rust work-stealing implementation of HyperBall that provides a simple and efficient way to compute centrality metrics on large graphs.\n",
    "\n",
    "In this tutorial, we will use GRAPE to compute approximate harmonic and closeness centrality metrics on a decently large graph. We will begin by providing an overview of the GRAPE library and its usage. Then, we will describe the HyperBall algorithm and how it can be used to compute centrality metrics. Finally, we will walk through an example of using GRAPE to compute centrality metrics on a large graph and discuss best practices for performance optimization. By the end of this tutorial, you will have a good understanding of how to use GRAPE to compute centrality metrics on large graphs efficiently.\n",
    "\n",
    "\n",
    "## What is GRAPE\n",
    "[🍇🍇 GRAPE 🍇🍇](https://github.com/AnacletoLAB/grape) is a graph processing and embedding library that enables users to easily manipulate and analyze graphs. With [GRAPE](https://github.com/AnacletoLAB/grape), users can efficiently load and preprocess graphs, generate random walks, and apply various node and edge embedding models. Additionally, [GRAPE](https://github.com/AnacletoLAB/grape) provides a fair and reproducible evaluation pipeline for comparing different graph embedding and graph-based prediction methods.\n",
    "\n",
    "![features in GRAPE](https://github.com/AnacletoLAB/grape/raw/main/images/sequence_diagram.png?raw=true)\n",
    "\n",
    "## Closeness centrality\n",
    "Closeness centrality is a measure of the degree to which a node is close to all other nodes in a network. The intuition behind this measure is that a node that is located close to other nodes is more likely to be important in terms of transmitting information or influence through the network.\n",
    "\n",
    "Formally, the closeness centrality of a node $v$ in a connected graph $G$ is defined as the reciprocal of the sum of the shortest path distances between $v$ and all other nodes in the graph:\n",
    "$$C_c(v) = \\frac{1}{\\sum_{u \\in V} d(u, v)}$$\n",
    "\n",
    "where $d(u,v)$ is the shortest path distance between nodes $u$ and $v$, and $V$ is the set of all nodes in the graph.\n",
    "\n",
    "Note that the closeness centrality of a node is high if it is close to many other nodes in the network. Conversely, a node with low closeness centrality is located far away from other nodes in the network.\n",
    "\n",
    "[We have covered how to compute Closeness centrality with GRAPE in this past tutorial](https://github.com/AnacletoLAB/grape/blob/main/tutorials/Efficient%20Weighted%20and%20Unweighted%20Closeness%20Centrality%20with%20GRAPE.ipynb)\n",
    "\n",
    "## Harmonic centrality\n",
    "Harmonic centrality is another measure of centrality in a network that takes into account the inverse of the distances between a node and all other nodes in the network. Formally, the harmonic centrality $C_H(v)$ of a node $v$ is defined as:\n",
    "\n",
    "$$C_h(v) = \\sum_{u \\in V\\; u \\neq v} \\frac{1}{d(u, v)}$$\n",
    "\n",
    "where $d(u,v)$ is the shortest path distance between nodes $u$ and $v$. The harmonic centrality measures the extent to which a node can reach other nodes in the network and be reached by them. Nodes with higher harmonic centrality are those that are closer to many other nodes in the network.\n",
    "\n",
    "Like the closeness centrality, the harmonic centrality is oftencase normalized to be in the range $[0,1]$, where a value of 1 represents a node that is maximally central in the network. However, it is less sensitive to outliers and is generally better suited for measuring centrality in networks that are not strongly connected.\n",
    "\n",
    "We will cover extensively Harmonic Centrality in a future tutorial.\n",
    "\n",
    "## What is HyperBall\n",
    "[HyperBall](https://vigna.di.unimi.it/ftp/papers/HyperBall.pdf) is an algorithm for, among other things, approximating the closeness and harmonic centrality of nodes in large graphs. The algorithm is based on a probabilistic data structure called [HyperLogLog](https://github.com/LucaCappelletti94/hyperloglog-rs) and works by estimating the number of neighbours at different \"balls\" of neighbours.\n",
    "\n",
    "The basic idea behind HyperBall is to use HyperLogLog counters to estimate the number of distinct neighbours at distance $k$. Specifically, the algorithm maintains a set of HyperLogLog counters, one for each node in the graph.\n",
    "\n",
    "HyperBall initializes the HyperLogLog counters by inserting the associated nodes (insert the first node in the first counter etc etc). After initialization, the algorithm iteratively computes the union of the counter of a node with the counters of its neighbors. Specifically, the algorithm computes the maximum register across all of the HyperLogLog counters registers involved in the union, and then updates the counter of the node with the maximum registers. This process continues until the counters converge, i.e. all counters reachable have the same register values.\n",
    "\n",
    "The deltas between the counters at step $t$ and $t+1$ is the difference in number of neighbours between two \"neighbours balls\", and that gives us an estimate of the number of nodes at depth $t$. From there, computing the harmonic and closeness centralities becomes a trivial affair.\n",
    "\n",
    "### Work stealing\n",
    "Work stealing is a popular scheduling strategy used in parallel computing. The goal of work stealing is to balance the workload among multiple threads to improve the overall performance of the system. In a work-stealing algorithm, each thread has its own local queue of tasks to perform. When a thread completes its local tasks, it can steal tasks from the queue of another thread that has more work than it can handle.\n",
    "\n",
    "In the case of the HyperBall algorithm, work stealing is used to balance the computation of high-degree nodes across multiple threads. Since high-degree nodes can have a significant impact on the overall computation time, it is important to distribute the work of computing these nodes evenly across all threads. Work stealing allows threads to dynamically adjust their workload based on the current state of the system, ensuring that no single thread is overloaded while other threads remain idle.\n",
    "\n",
    "In this particular implementation of HyperBall, each thread is assigned a subset of nodes to process. Once a thread has completed its allotted local work, it will check the queues of other threads that have fallen behind schedule because they are dealing with some particularly high degre nodes. This allows the thread to take on additional work and balance the workload across all threads.\n",
    "\n",
    "[Find the Rust implementation of HyperBall here](https://github.com/AnacletoLAB/ensmallen/blob/fa8225614008508ac9b806d884dfc58b79d19d6f/graph/src/hyperball.rs#L63)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f15ee6fe",
   "metadata": {},
   "source": [
    "## Some pratical experiments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "0a6b4098",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "2023-05-14 18:37:48.092708: W tensorflow/stream_executor/platform/default/dso_loader.cc:64] Could not load dynamic library 'libcudart.so.11.0'; dlerror: libcudart.so.11.0: cannot open shared object file: No such file or directory\n",
      "2023-05-14 18:37:48.092727: I tensorflow/stream_executor/cuda/cudart_stub.cc:29] Ignore above cudart dlerror if you do not have a GPU set up on your machine.\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3.88 s, sys: 2.94 s, total: 6.82 s\n",
      "Wall time: 5.29 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "from grape.datasets.kgobo import HP\n",
    "from grape.datasets.string import HomoSapiens\n",
    "from grape.datasets.kghub import KGCOVID19"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5403652a",
   "metadata": {},
   "source": [
    "We start by trying it out on a small graph. We observe that here the improvements is not too significant, and to get to a low error we need to use rather high precision HyperLogLog counters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e90968b2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 157 ms, sys: 25.2 ms, total: 182 ms\n",
      "Wall time: 42 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "hp = HP()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "27f1aa23",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 148 ms, sys: 48.6 ms, total: 197 ms\n",
      "Wall time: 9.23 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(31668, 29.0, 135633)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "(hp.get_number_of_nodes(), hp.get_diameter(), hp.get_number_of_directed_edges())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "b3e973a3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 13.7 s, sys: 14.4 ms, total: 13.7 s\n",
      "Wall time: 588 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([5.6500367e-06, 5.6499730e-06, 7.5825933e-06, ..., 1.3628805e-05,\n",
       "       1.4220705e-05, 1.8399602e-05], dtype=float32)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "hp.get_closeness_centrality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "e740d9f7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 5.44 s, sys: 25.6 ms, total: 5.46 s\n",
      "Wall time: 241 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([5.49620381e-06, 5.49614288e-06, 7.35795084e-06, ...,\n",
       "       1.41679775e-05, 1.47832434e-05, 1.89927359e-05], dtype=float32)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "hp.get_approximated_closeness_centrality(precision=9, bits=6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7dacc033",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 17.7 s, sys: 37.2 ms, total: 17.8 s\n",
      "Wall time: 768 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([1618.525 , 1618.2749, 2242.5837, ..., 2752.841 , 2937.7966,\n",
       "       3908.6458], dtype=float32)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "hp.get_harmonic_centrality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "4596c8ba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 6.18 s, sys: 23.2 ms, total: 6.2 s\n",
      "Wall time: 289 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([1662.215 , 1661.9622, 2299.9229, ..., 2597.7651, 2773.5237,\n",
       "       3692.4763], dtype=float32)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "hp.get_approximated_harmonic_centrality(precision=9, bits=6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14f7c42a",
   "metadata": {},
   "source": [
    "Let's bump it up a notch, and we move to STRING Homo Sapiens:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "d19c6077",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 14.7 s, sys: 638 ms, total: 15.3 s\n",
      "Wall time: 8.98 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "string = HomoSapiens()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a553f5f0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 35.8 s, sys: 1.12 s, total: 36.9 s\n",
      "Wall time: 1.85 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(19566, 5.0, 11938498)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "(string.get_number_of_nodes(), string.get_diameter(), string.get_number_of_directed_edges())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "d545db5b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 10min 36s, sys: 1 s, total: 10min 37s\n",
      "Wall time: 27.6 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([2.6706548e-05, 2.5682513e-05, 2.6850683e-05, ..., 0.0000000e+00,\n",
       "       0.0000000e+00, 1.9996800e-05], dtype=float32)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "string.get_closeness_centrality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "ffa3c6cd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 52.8 s, sys: 53.7 ms, total: 52.9 s\n",
      "Wall time: 2.28 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([2.5858175e-05, 2.4865947e-05, 2.5768313e-05, ..., 0.0000000e+00,\n",
       "       0.0000000e+00, 1.9493376e-05], dtype=float32)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "string.get_approximated_closeness_centrality(precision=8, bits=6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "d20c84e9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 8min 12s, sys: 1.32 s, total: 8min 13s\n",
      "Wall time: 21.6 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([10392.652,  9823.812, 10512.813, ...,     0.   ,     0.   ,\n",
       "        7848.315], dtype=float32)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "string.get_harmonic_centrality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "c81a4772",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 33.2 s, sys: 29.5 ms, total: 33.2 s\n",
      "Wall time: 1.42 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([10728.257 , 10162.341 , 10726.847 , ...,     0.    ,     0.    ,\n",
       "        8176.8022], dtype=float32)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "string.get_approximated_harmonic_centrality(precision=8, bits=6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a77e198",
   "metadata": {},
   "source": [
    "We can spend a bit of time to see how the error and time requirements change with the resolution.\n",
    "\n",
    "The run at highest resolution are exponentially slower, as HyperLogLog counters have $2^{\\text{precision}}$ registers. While the HyperLogLog implementation we are using supports from resolution $4$ to resolution $16$ included, we are going to cut it short at $12$ for time sakes. Feel free to bench it extensively on your own time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "768e714a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "  0%|          | 0/8 [00:00<?, ?it/s]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 28min 56s, sys: 2.61 s, total: 28min 59s\n",
      "Wall time: 1min 15s\n"
     ]
    },
    {
     "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>mse</th>\n",
       "      <th>precision</th>\n",
       "      <th>bits</th>\n",
       "      <th>time</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>3.156656e-06</td>\n",
       "      <td>4</td>\n",
       "      <td>5</td>\n",
       "      <td>0.062338</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>3.150493e-06</td>\n",
       "      <td>4</td>\n",
       "      <td>6</td>\n",
       "      <td>0.074883</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2.285012e-07</td>\n",
       "      <td>5</td>\n",
       "      <td>5</td>\n",
       "      <td>0.209248</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>2.234365e-07</td>\n",
       "      <td>5</td>\n",
       "      <td>6</td>\n",
       "      <td>0.219988</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>2.469377e-07</td>\n",
       "      <td>6</td>\n",
       "      <td>5</td>\n",
       "      <td>0.388623</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>2.515463e-07</td>\n",
       "      <td>6</td>\n",
       "      <td>6</td>\n",
       "      <td>0.388130</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>1.346935e-07</td>\n",
       "      <td>7</td>\n",
       "      <td>5</td>\n",
       "      <td>0.892079</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>1.330898e-07</td>\n",
       "      <td>7</td>\n",
       "      <td>6</td>\n",
       "      <td>1.442079</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>1.282743e-08</td>\n",
       "      <td>8</td>\n",
       "      <td>5</td>\n",
       "      <td>1.410394</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>1.302366e-08</td>\n",
       "      <td>8</td>\n",
       "      <td>6</td>\n",
       "      <td>1.433877</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>2.301957e-08</td>\n",
       "      <td>9</td>\n",
       "      <td>5</td>\n",
       "      <td>2.873781</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>2.131471e-08</td>\n",
       "      <td>9</td>\n",
       "      <td>6</td>\n",
       "      <td>2.907431</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>1.792716e-09</td>\n",
       "      <td>10</td>\n",
       "      <td>5</td>\n",
       "      <td>5.688271</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>2.487489e-09</td>\n",
       "      <td>10</td>\n",
       "      <td>6</td>\n",
       "      <td>6.824558</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>6.013908e-09</td>\n",
       "      <td>11</td>\n",
       "      <td>5</td>\n",
       "      <td>11.194051</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>3.116792e-09</td>\n",
       "      <td>11</td>\n",
       "      <td>6</td>\n",
       "      <td>11.341292</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             mse  precision  bits       time\n",
       "0   3.156656e-06          4     5   0.062338\n",
       "1   3.150493e-06          4     6   0.074883\n",
       "2   2.285012e-07          5     5   0.209248\n",
       "3   2.234365e-07          5     6   0.219988\n",
       "4   2.469377e-07          6     5   0.388623\n",
       "5   2.515463e-07          6     6   0.388130\n",
       "6   1.346935e-07          7     5   0.892079\n",
       "7   1.330898e-07          7     6   1.442079\n",
       "8   1.282743e-08          8     5   1.410394\n",
       "9   1.302366e-08          8     6   1.433877\n",
       "10  2.301957e-08          9     5   2.873781\n",
       "11  2.131471e-08          9     6   2.907431\n",
       "12  1.792716e-09         10     5   5.688271\n",
       "13  2.487489e-09         10     6   6.824558\n",
       "14  6.013908e-09         11     5  11.194051\n",
       "15  3.116792e-09         11     6  11.341292"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from time import time\n",
    "from tqdm.auto import trange\n",
    "\n",
    "actual_values = string.get_closeness_centrality()\n",
    "\n",
    "closeness_performance = []\n",
    "\n",
    "for precision in trange(4, 11 + 1, leave=False):\n",
    "    for bits in (5, 6):\n",
    "        start = time()\n",
    "        approximated = string.get_approximated_closeness_centrality(\n",
    "            precision=precision,\n",
    "            bits=bits\n",
    "        )\n",
    "        end = time()\n",
    "        mse = np.sum((approximated - actual_values)**2)\n",
    "        closeness_performance.append(dict(\n",
    "            mse=mse,\n",
    "            precision=precision,\n",
    "            bits=bits,\n",
    "            time=end - start\n",
    "        ))\n",
    "closeness_performance = pd.DataFrame(closeness_performance)\n",
    "closeness_performance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "63defc32",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "  0%|          | 0/8 [00:00<?, ?it/s]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 26min 49s, sys: 2.87 s, total: 26min 52s\n",
      "Wall time: 1min 9s\n"
     ]
    },
    {
     "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>mse</th>\n",
       "      <th>precision</th>\n",
       "      <th>bits</th>\n",
       "      <th>time</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1.619476e+11</td>\n",
       "      <td>4</td>\n",
       "      <td>5</td>\n",
       "      <td>0.064384</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1.619132e+11</td>\n",
       "      <td>4</td>\n",
       "      <td>6</td>\n",
       "      <td>0.119695</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1.513956e+10</td>\n",
       "      <td>5</td>\n",
       "      <td>5</td>\n",
       "      <td>0.212849</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1.522282e+10</td>\n",
       "      <td>5</td>\n",
       "      <td>6</td>\n",
       "      <td>0.220850</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5.829897e+10</td>\n",
       "      <td>6</td>\n",
       "      <td>5</td>\n",
       "      <td>0.387177</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>5.690582e+10</td>\n",
       "      <td>6</td>\n",
       "      <td>6</td>\n",
       "      <td>0.380660</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>2.819333e+10</td>\n",
       "      <td>7</td>\n",
       "      <td>5</td>\n",
       "      <td>0.734679</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>2.777833e+10</td>\n",
       "      <td>7</td>\n",
       "      <td>6</td>\n",
       "      <td>0.719611</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>2.655626e+09</td>\n",
       "      <td>8</td>\n",
       "      <td>5</td>\n",
       "      <td>1.419431</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>2.265788e+09</td>\n",
       "      <td>8</td>\n",
       "      <td>6</td>\n",
       "      <td>1.435327</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>2.072834e+09</td>\n",
       "      <td>9</td>\n",
       "      <td>5</td>\n",
       "      <td>3.470075</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>2.092905e+09</td>\n",
       "      <td>9</td>\n",
       "      <td>6</td>\n",
       "      <td>2.874595</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>2.423001e+08</td>\n",
       "      <td>10</td>\n",
       "      <td>5</td>\n",
       "      <td>5.695091</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>1.730037e+07</td>\n",
       "      <td>10</td>\n",
       "      <td>6</td>\n",
       "      <td>5.707893</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>2.254612e+08</td>\n",
       "      <td>11</td>\n",
       "      <td>5</td>\n",
       "      <td>11.199482</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>3.505099e+08</td>\n",
       "      <td>11</td>\n",
       "      <td>6</td>\n",
       "      <td>13.587008</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             mse  precision  bits       time\n",
       "0   1.619476e+11          4     5   0.064384\n",
       "1   1.619132e+11          4     6   0.119695\n",
       "2   1.513956e+10          5     5   0.212849\n",
       "3   1.522282e+10          5     6   0.220850\n",
       "4   5.829897e+10          6     5   0.387177\n",
       "5   5.690582e+10          6     6   0.380660\n",
       "6   2.819333e+10          7     5   0.734679\n",
       "7   2.777833e+10          7     6   0.719611\n",
       "8   2.655626e+09          8     5   1.419431\n",
       "9   2.265788e+09          8     6   1.435327\n",
       "10  2.072834e+09          9     5   3.470075\n",
       "11  2.092905e+09          9     6   2.874595\n",
       "12  2.423001e+08         10     5   5.695091\n",
       "13  1.730037e+07         10     6   5.707893\n",
       "14  2.254612e+08         11     5  11.199482\n",
       "15  3.505099e+08         11     6  13.587008"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from time import time\n",
    "from tqdm.auto import trange\n",
    "\n",
    "actual_values = string.get_harmonic_centrality()\n",
    "\n",
    "harmonic_performance = []\n",
    "\n",
    "for precision in trange(4, 11 + 1, leave=False):\n",
    "    for bits in (5, 6):\n",
    "        start = time()\n",
    "        approximated = string.get_approximated_harmonic_centrality(\n",
    "            precision=precision,\n",
    "            bits=bits\n",
    "        )\n",
    "        end = time()\n",
    "        mse = np.sum((approximated - actual_values)**2)\n",
    "        harmonic_performance.append(dict(\n",
    "            mse=mse,\n",
    "            precision=precision,\n",
    "            bits=bits,\n",
    "            time=end - start\n",
    "        ))\n",
    "harmonic_performance = pd.DataFrame(harmonic_performance)\n",
    "harmonic_performance"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b870dd90",
   "metadata": {},
   "source": [
    "Let's move up anothe notch. From KGCOVID19 onwards, the graph is too large to finish the computation within seconds (it takes hours on this computer), so we need to use only the approximation. And that is what HyperBall is for!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "d3220ae6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 23 s, sys: 273 ms, total: 23.3 s\n",
      "Wall time: 1.79 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "kgcovid = KGCOVID19()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "b242503d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.31 s, sys: 43.3 ms, total: 1.35 s\n",
      "Wall time: 64.8 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(574232, 38.0, 36501154)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "(kgcovid.get_number_of_nodes(), kgcovid.get_diameter(), kgcovid.get_number_of_directed_edges())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "227b1d9e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 6min 25s, sys: 609 ms, total: 6min 26s\n",
      "Wall time: 16.7 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([1.8629692e-07, 2.0928746e-07, 1.6905928e-07, ..., 2.8484943e-04,\n",
       "       2.8118393e-07, 9.8631144e-02], dtype=float32)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "kgcovid.get_approximated_closeness_centrality(precision=8, bits=6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "47a919ba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 5min 42s, sys: 654 ms, total: 5min 43s\n",
      "Wall time: 14.8 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([7.07870938e+04, 8.37640078e+04, 6.51354531e+04, ...,\n",
       "       2.68150444e+01, 1.01187445e+05, 2.10325456e+00], dtype=float32)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "kgcovid.get_approximated_harmonic_centrality(precision=8, bits=6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82e0c7aa",
   "metadata": {},
   "source": [
    "## Conclusive notes\n",
    "In this tutorial, we have discussed how HyperBall, a state-of-the-art algorithm for approximating closeness and harmonic centrality in large graphs, can be easily used with GRAPE. We have introduced HyperBall and HyperLogLog counters, and explained how they work together to compute centrality measures efficiently. We have also described the work-stealing strategy implemented in the GRAPE version of HyperBall, which allows for better load balancing among threads. Overall, HyperBall provides a powerful tool for analyzing large graphs and can be easily integrated into existing workflows.\n",
    "\n",
    "[You can learn more about HyperLogLog here](https://github.com/LucaCappelletti94/hyperloglog-rs).\n",
    "\n",
    "Don't forget to ⭐ GRAPE!"
   ]
  }
 ],
 "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}