tutorials/Efficient Betweenness Centrality with GRAPE.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "dcd995f4",
   "metadata": {},
   "source": [
    "# Efficient [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) with [GRAPE](https://github.com/AnacletoLAB/grape)\n",
    "In this tutorial, we will explore the concept of [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) and its importance in network analysis. We will start by discussing the [Brandes algorithm](http://snap.stanford.edu/class/cs224w-readings/brandes01centrality.pdf), a well-known method for computing [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) in Python pseudocode. From there, we will move on to the parallel Rust implementation of the algorithm in the [GRAPE](https://github.com/AnacletoLAB/grape) library. We will use citation and protein-protein interaction graphs to demonstrate the algorithm, and briefly describe how it can be distributed over a computing cluster. By the end of this tutorial, you will have a good understanding of how to compute [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) and apply it to your own network analysis projects using [GRAPE](https://github.com/AnacletoLAB/grape).\n",
    "\n",
    "## A brief premise on graphs\n",
    "[Graphs](https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)) are a fundamental data structure used in a wide range of scientific and engineering fields. They are used to represent relationships between objects, such as social networks, transportation systems, and biological pathways. One important measure of the importance of a node in a graph is its [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality). This measure quantifies the number of shortest paths that go through a given node, indicating its importance as a connector between different parts of the graph.\n",
    "\n",
    "Computing [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) can be a challenging problem, particularly for large-scale graphs. The naive approach of computing all shortest paths between all pairs of nodes is computationally expensive and not practical for graphs with millions or billions of nodes. Several algorithms have been developed to efficiently compute betweenness centrality, and one of the most widely used algorithms is the [Brandes algorithm](http://snap.stanford.edu/class/cs224w-readings/brandes01centrality.pdf).\n",
    "\n",
    "The [Brandes algorithm](http://snap.stanford.edu/class/cs224w-readings/brandes01centrality.pdf) is an exact algorithm that computes the [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) of all nodes in a graph. It is based on a dynamic programming approach that iteratively computes the contribution of each node to the [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) of all pairs of nodes. Despite its effectiveness, the [Brandes algorithm](http://snap.stanford.edu/class/cs224w-readings/brandes01centrality.pdf) can be slow for large graphs.\n",
    "\n",
    "To address this issue, researchers have tried to develop faster algorithms for computing [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality). One such algorithm is the lock-free parallel algorithm for computing [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) [developed by Kamesh Madduri and David Bader](https://pennstate.pure.elsevier.com/en/publications/a-faster-parallel-algorithm-and-efficient-multithreaded-implement). This algorithm is optimized for high-performance computing and takes advantage of modern hardware features, such as spatial cache locality and lock-free parallelization.\n",
    "\n",
    "We will then demonstrate how to use the [GRAPE](https://github.com/AnacletoLAB/grape) library to compute [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) on three citation graphs and three protein-protein interaction graphs.\n",
    "\n",
    "## What is [GRAPE](https://github.com/AnacletoLAB/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",
    "![[GRAPE](https://github.com/AnacletoLAB/grape) illustration](https://github.com/AnacletoLAB/grape/raw/main/images/sequence_diagram.png?raw=true)\n",
    "\n",
    "## What is Betweenness Centrality?\n",
    "Betweenness centrality is a measure of the importance of a node (or sometimes an edge) in a network. It quantifies the extent to which a particular node lies on the shortest paths between all pairs of other nodes in the network. In other words, nodes with high [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) act as \"bridges\" or \"hubs\" that connect different parts of the network together.\n",
    "\n",
    "## Why is [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) Important?\n",
    "\n",
    "Betweenness centrality is important because it can help us identify key nodes that are critical to the overall functioning of a network. For example, in a social network, nodes with high [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) may be important \"brokers\" who connect different groups of people together. In a transportation network, nodes with high [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) may be important junctions or intersections that connect different routes together.\n",
    "\n",
    "## How is [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) Calculated?\n",
    "\n",
    "There are several algorithms for calculating betweenness centrality, but one of the most common is the [Brandes algorithm](http://snap.stanford.edu/class/cs224w-readings/brandes01centrality.pdf). The algorithm works by computing the shortest paths between all pairs of nodes in the network, and then counting the number of times each node lies on a shortest path. Nodes with high [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) will appear on a large number of shortest paths.\n",
    "\n",
    "Here is the pseudocode for the [Brandes algorithm](http://snap.stanford.edu/class/cs224w-readings/brandes01centrality.pdf):\n",
    "\n",
    "```python\n",
    "def betweenness_centrality(G):\n",
    "    betweenness = dict.fromkeys(G, 0.0)\n",
    "    for s in G:\n",
    "        stack = []\n",
    "        P = dict.fromkeys(G, [])\n",
    "        sigma = dict.fromkeys(G, 0.0)\n",
    "        sigma[s] = 1.0\n",
    "        d = dict.fromkeys(G, -1)\n",
    "        d[s] = 0\n",
    "        Q = [s]\n",
    "        while Q:\n",
    "            v = Q.pop(0)\n",
    "            stack.append(v)\n",
    "            for w in G[v]:\n",
    "                if d[w] < 0:\n",
    "                    Q.append(w)\n",
    "                    d[w] = d[v] + 1\n",
    "                if d[w] == d[v] + 1:\n",
    "                    sigma[w] += sigma[v]\n",
    "                    P[w].append(v)\n",
    "        delta = dict.fromkeys(G, 0.0)\n",
    "        while stack:\n",
    "            w = stack.pop()\n",
    "            for v in P[w]:\n",
    "                delta[v] += (sigma[v] / sigma[w]) * (1.0 + delta[w])\n",
    "            if w != s:\n",
    "                betweenness[w] += delta[w]\n",
    "    return betweenness\n",
    "```\n",
    "\n",
    "In this pseudocode, `G` represents the network, and betweenness is a dictionary that will eventually contain the [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) for each node in the network. The algorithm iterates over each node in the network (for `s` in `G`), and for each node, it computes the shortest paths between all pairs of nodes using a modified breadth-first search. It then uses these shortest paths to compute the [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) for each node.\n",
    "\n",
    "\n",
    "## Madduri's algorithm\n",
    "The [Madduri algorithm](https://pennstate.pure.elsevier.com/en/publications/a-faster-parallel-algorithm-and-efficient-multithreaded-implement) is a lock-free parallel algorithm designed for computing [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) in small-world networks. This algorithm achieves better spatial cache locality compared to previous approaches and is optimized for high-performance computing architectures. Let's break down its key ingredients.\n",
    "\n",
    "### What are atomic instructions?\n",
    "An [atomic instruction](https://www.ibm.com/docs/en/aix/7.2?topic=services-atomic-operations) is an operation that is executed as a single, indivisible unit of work. This means that the operation cannot be interrupted or modified by any other process or thread while it is being executed. Atomic instructions are often used in concurrent programming to implement synchronization mechanisms that ensure that shared resources are accessed and updated correctly by multiple threads. For example, in a multi-threaded environment, if two threads simultaneously try to increment the same variable, an atomic instruction can ensure that the variable is incremented exactly once, and that the final value is correct. Without atomic instructions, concurrent programs could suffer from race conditions, data races, and other synchronization-related bugs.\n",
    "\n",
    "#### Fetch add\n",
    "[Fetch add](https://www.ibm.com/docs/en/aix/7.2?topic=f-fetch-add-kernel-services) is an atomic instruction that is used to atomically increment a value by a specified amount and return the original value. The operation is typically implemented at the hardware level and provides a way to update a shared resource without the need for locks or other synchronization mechanisms. In a multi-threaded environment, if multiple threads attempt to update the same variable concurrently, fetch add can ensure that each thread gets the correct original value, increments it by the specified amount, and writes the new value back to the variable atomically, without interference from other threads. This can help prevent race conditions and other synchronization-related bugs in concurrent programs. Fetch add is commonly used in algorithms that require shared counters or accumulators, such as in parallel graph processing, where it is used to compute betweenness centrality, PageRank, and other metrics.\n",
    "\n",
    "#### Compare and swap\n",
    "[Compare-and-swap (CAS)](https://en.wikipedia.org/wiki/Compare-and-swap), is an atomic instruction that is used to perform an update to a shared variable in a multi-threaded environment. It is typically used to implement mutual exclusion, synchronization, and other concurrency control mechanisms in parallel algorithms. The operation takes three operands: a memory location, an expected value, and a new value. It compares the value in the memory location with the expected value. If they match, the operation stores the new value into the memory location. If they do not match, the operation does nothing.\n",
    "\n",
    "Compare exchange provides a way to ensure that updates to shared variables are performed atomically, without interference from other threads. It helps prevent race conditions and other synchronization-related bugs that can arise in concurrent programs. It is commonly used in algorithms that require mutual exclusion, such as locks, semaphores, and barriers, as well as in data structures that support concurrent access, such as concurrent hash tables and concurrent linked lists.\n",
    "\n",
    "While CAS can introduce a significant overhead when the graph topology has nodes with many predecessors, one solution is to replace CAS entirely with a second iteration on the visited vector. This approach eliminates the need for CAS operations altogether and can be a more efficient solution in certain scenarios. However, it is important to note that this method may not always be the most efficient and should be considered on a case-by-case basis.\n",
    "\n",
    "### Non-temporal store\n",
    "[Non-temporal stores (NT stores)](https://lwn.net/Articles/255364/) are a type of store operation that bypass the cache hierarchy and write data directly to the main memory, without trying to store it in any cache levels. This is useful when writing to large memory regions that are not going to be used in the near future or when the data written is going to be processed sequentially, as it can reduce cache pollution and cache misses.\n",
    "\n",
    "The `sfence` instruction is a memory barrier instruction that ensures that all preceding writes have been committed to memory before any subsequent writes are executed. It's used in conjunction with NT stores to make sure that all data is written to main memory before continuing with the execution of the program, ensuring consistency and preventing race conditions.\n",
    "\n",
    "We will employ non-temporal stores to let the compiler know that values such as the `i`-th successor or the status of a node does not need to be updated immediately.\n",
    "\n",
    "### Pseudocode\n",
    "In this section, we will present the pseudocode of the [Madduri algorithm](https://pennstate.pure.elsevier.com/en/publications/a-faster-parallel-algorithm-and-efficient-multithreaded-implement) for computing [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) in parallel. The algorithm has been implemented in the [GRAPE](https://github.com/AnacletoLAB/grape) library, and we will use this pseudocode to explain the implementation details.\n",
    "\n",
    "[Find the actual Rust implementation here](https://github.com/AnacletoLAB/ensmallen/blob/e96242d1f6a7f7bfbc5eb6908f0899b527eade98/graph/src/centrality.rs#L517)\n",
    "\n",
    "```python\n",
    "import numpy as np\n",
    "\n",
    "def get_betweenness_centrality(graph):\n",
    "    # First, we init the centralities\n",
    "    centralities = np.zeros(shape=graph.get_number_of_nodes())\n",
    "    # Next, a vector LARGE AS THE NUMBER OF EDGES! - THIS IS A BIG ONE!\n",
    "    successors = np.zeros(shape=graph.get_number_of_directed_edges(), dtype=np.uint32)\n",
    "    # The counter for the successors of each node.\n",
    "    successor_counts = np.zeros(shape=graph.get_number_of_nodes(), dtype=np.uint32)\n",
    "    # The number of shortest paths passing through a node.\n",
    "    # Note that these values are ATOMIC!\n",
    "    shortest_path_counts = [AtomicU32(0) for _ in range(graph.get_number_of_nodes())]\n",
    "    # Then, we fill a vector with the visited status of the nodes\n",
    "    # - UNVISITED for the nodes yet to be visited\n",
    "    # - JUST_VISITED for the nodes we have just visited, and...\n",
    "    # - VISITED for the nodes we have visited last iteration\n",
    "    # Clear, right?\n",
    "    # Since we only need 3 values, we can use an `u8` with space to spare.\n",
    "    # Note that we could also use just 2 bits instead of wasting 8 of them per node.\n",
    "    # This may be a good idea for large graphs, but the vector of successors dwarfs\n",
    "    # these other ones that scale with the number of nodes as the successors vector\n",
    "    # scales with the number of edges.\n",
    "    visited_status = np.full(graph.get_number_of_nodes(), UNVISITED, dtype=np.uint8)\n",
    "    # We init similarly the dependencies vector.\n",
    "    dependencies = np.zeros(shape=graph.get_number_of_nodes())\n",
    "    # And we init the frontiers. \n",
    "    # Frontiers are unordered vectors (read more here: https://github.com/zommiommy/parallel_frontier)\n",
    "    # that allow for parallel push and balanced parallel iteration.\n",
    "    frontiers = [Frontier(graph.get_number_of_nodes()) for _ in range(2)]\n",
    "    \n",
    "    # We start to iterate on each node.\n",
    "    # This iteration can be easily distributed on a cluster, just\n",
    "    # divide the nodes into chunks balanced by node degree and execute\n",
    "    # the task for each node. Then, simply sum the resulting betweenness\n",
    "    # centrality vectors.\n",
    "    for root in range(graph.get_number_of_nodes()):\n",
    "        \n",
    "        # First, we reset the shortest path counts.\n",
    "        shortest_path_counts[:] = 0\n",
    "        \n",
    "        # We set the number of shortest paths in the root equal\n",
    "        # to one:\n",
    "        shortest_path_counts[root] = 1\n",
    "        # And we set its status as visited\n",
    "        visited_status[root] = VISITED\n",
    "        # We clean up the first frontier, without freeing\n",
    "        # the associated memory\n",
    "        frontiers[0].clear()\n",
    "        # And initialize it with the root node.\n",
    "        frontiers[0].push(root)\n",
    "        # We initialize the current depth\n",
    "        current_depth = 0\n",
    "        # And start BFS-ing our way through the graph\n",
    "        while True:\n",
    "            # First, we increase the current depth\n",
    "            current_depth += 1\n",
    "            # If we are going at a deeper depth than what was\n",
    "            # done until now, we create a new frontier object\n",
    "            if len(frontiers) < 1 + current_depth:\n",
    "                # And push it onto the frontiers vector.\n",
    "                frontiers.append(Frontier())\n",
    "            \n",
    "            # We iterate IN PARALLEL on the last frontier we have\n",
    "            # expanded, which at the first iteration only contains\n",
    "            # the root node:\n",
    "            for src in frontiers[current_depth - 1]:\n",
    "                # We retrieve the number of paths for the current node in the frontier\n",
    "                # and we do so ATOMICALLY using relaxed ordering.\n",
    "                # Learn more about the type of orderings here: https://doc.rust-lang.org/std/sync/atomic/enum.Ordering.html\n",
    "                source_paths = shortest_path_counts[src].load(Ordering::Relaxed)\n",
    "                # We retrieve its number of successors\n",
    "                number_of_successors = successor_counts[src]\n",
    "                # And we compute its current offset, as the sum of the comulative\n",
    "                # node degree and the current number of successors, using a data-structure\n",
    "                # similar to a CSR (learn more about CSR matrices here: https://scipy-lectures.org/advanced/scipy_sparse/csr_matrix.html)\n",
    "                offset = graph.comulative_degree(src) + number_of_successors\n",
    "                # We iterate on the neighbours of `src`\n",
    "                for dst in graph.neighbours(src):\n",
    "                    # If the node was not yet visited\n",
    "                    if visited_status[dst] == UNVISITED:\n",
    "                        # We set it as visited using a non-temporal store,\n",
    "                        # as we do not care about updating immediately the\n",
    "                        # value of the node and force a cache refresh.\n",
    "                        non_temporal_store(\n",
    "                            visited_status[dst],\n",
    "                            JUST_VISITED\n",
    "                        )\n",
    "                    # NOTE THAT THE FOLLOWING IS NOT AN ELSE-IF!\n",
    "                    # If the status of the node is either just visited\n",
    "                    # or still to be visited, i.e. the value has to be\n",
    "                    # locally updated, then...\n",
    "                    if visited_status[dst] == JUST_VISITED or visited_status[dst] == UNVISITED:\n",
    "                        # We update the number of shortest paths passing through\n",
    "                        # `dst` using a FETCH ADD operation.\n",
    "                        shortest_path_counts[dst].fetch_add(source_paths, Ordering::Relaxed)\n",
    "                        # We set the `dst` node as one of the successors of `src`.\n",
    "                        successors[offset] = dst\n",
    "                        # Increase the current offset and number of successors\n",
    "                        offset += 1\n",
    "                        number_of_successors += 1\n",
    "                # and then, we can update the successors count of the\n",
    "                # node only once.\n",
    "                successor_counts[src] = number_of_successors\n",
    "            # We make sure our non-temporal writes have happened by now:\n",
    "            sfence()\n",
    "            # Next, we populate the new frontier.\n",
    "            # Do note that we choose to not do it in the \n",
    "            # previous loop as the CAS operation on some graph\n",
    "            # topology can cause severe over-head, and the following\n",
    "            # loop if quite clean to parallelize.\n",
    "            # We clear the next frontier that we are about to populate.\n",
    "            frontiers[current_depth].clear()\n",
    "            # We iterate IN PARALLEL on the status of the nodes.\n",
    "            for node_id, status in enumerate(visited_status):\n",
    "                if status == JUST_VISITED:\n",
    "                    visited_status[node_id] = VISITED\n",
    "                    frontiers[current_depth].push(node_id)\n",
    "            # If the new frontier is empty, we have finished\n",
    "            # the BFS.\n",
    "            if len(frontiers[current_depth]) == 0:\n",
    "                break\n",
    "        # We iterate SEQUENTIALLY on the frontier in REVERSED ORDER\n",
    "        # Note that we are skipping the first frontier, the one that\n",
    "        # solely contains the current root node.\n",
    "        for depth in reversed(range(1, current_depth+1)):\n",
    "            # We get the depth-th frontier\n",
    "            frontier = frontiers[depth]\n",
    "            # and we start to iterate IN PARALLEL across\n",
    "            # the nodes of the frontier\n",
    "            for src in frontier:\n",
    "                # We reset the status of the nodes\n",
    "                visited_status[src] = UNVISITED\n",
    "                # We retrieve the offset of the current node\n",
    "                offset = graph.comulative_degree(src)\n",
    "                # We need to access the dependencies.\n",
    "                # Note that all dependencies are weighted by their own shortest path counts.\n",
    "                dependencies[src] = shortest_path_counts[src] * sum([\n",
    "                    (1.0 + shared_dependencies.get()[dst]) / shortest_path_counts[dst]\n",
    "                    for dst in successors[offset:offset+successor_counts[src]]\n",
    "                ])\n",
    "                # We reset the successor counts\n",
    "                successor_counts[src] = 0\n",
    "                # And finally, we sum the centralized\n",
    "                centralities[src] += dependencies[src]\n",
    "    \n",
    "    return centralities\n",
    "```\n",
    "\n",
    "### Parallelizing the algorithm on a computing cluster\n",
    "The algorithm can be parallelized across multiple compute nodes of a cluster in a very simple way. The parallelization can be achieved by distributing the partial computation of the BC of each graph node across multiple compute nodes, and then computing the total BC by summing the partials.\n",
    "\n",
    "Each compute node can independently compute the BC values for a subset of the graph nodes, and then communicate the partial results to a designated master node. The master node can then aggregate the partial BC values for each node and compute the final BC values for the entire graph by summing up the partial values.\n",
    "\n",
    "Since the computations for each node are independent of each other, and since the partial BC values can be easily combined to obtain the total BC value, this approach scales well with the number of compute nodes. Furthermore, the parallelism can be easily adjusted to accommodate different cluster sizes or computational resources, making the algorithm highly flexible and efficient."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec983a0b",
   "metadata": {},
   "source": [
    "## Experiments\n",
    "In this section, we will present the results of our experiments using the parallel betweenness centrality algorithm described in Madduri's paper and implemented in GRAPE. We loaded three citation graphs, Cora, CiteSeer, and PubmedDiabetes, and three protein-protein interaction graphs, Homo Sapiens, Canis Lupus, and Mus Musculus. We will show the BC scores of each graph as histograms, which will give us an insight into the centrality of nodes in the network. By comparing the results of these experiments, we will be able to understand the performance of the algorithm on different types of graphs and the distribution of BC scores in each graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f1aed6bc",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "2023-04-26 17:16:45.050312: 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-04-26 17:16:45.050329: 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"
     ]
    }
   ],
   "source": [
    "from grape.datasets.linqs import Cora, CiteSeer, PubMedDiabetes, get_words_data\n",
    "\n",
    "cora = Cora()\n",
    "citeseer = CiteSeer()\n",
    "pubmed = PubMedDiabetes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d8e8f6a3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4141, 108988, 6.0)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(cora.get_number_of_nodes(), cora.get_number_of_directed_edges(), cora.get_diameter())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "8d91b404",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1min 20s, sys: 9.19 s, total: 1min 29s\n",
      "Wall time: 5.08 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "cora_bc = cora.get_betweenness_centrality(edges_normalization=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6984d7c6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAD4CAYAAAAAczaOAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/NK7nSAAAACXBIWXMAAAsTAAALEwEAmpwYAAAN1ElEQVR4nO3df6zd9V3H8edrrbDJAmOjGtdSW3IZsRjc9K6L0Rjjr7U2FxZGHJ1mbBIanDXZH9MV2R/oX2yZMS5DlyZDplE6bNTQtMo2EoIxqBTckK7p1pVOykzKD1MzloyBb/+4X+Fw6S3fe8+555zyeT6Spud8zvf7Pa8e7nnxvZ/v95xvqgpJUhteN+kAkqTxsfQlqSGWviQ1xNKXpIZY+pLUkNWTDgBw0UUX1YYNGyYdQ5LOKg899NBTVbVmKetMtPSTzAFzMzMzHDx4cJJRJOmsk+RbS11notM7VbWvqnZccMEFk4whSc1wTl+SGmLpS1JDJlr6SeaS7D516tQkY0hSM5zTl6SGOL0jSQ2x9CWpIZa+JDVkKj6RO4wNu/afdvz4rdvGnESSpp9n70hSQzx7R5Ia4py+JDXE0pekhlj6ktQQS1+SGmLpS1JDPGVTkhriKZuS1BCndySpIZa+JDXE0pekhlj6ktQQS1+SGmLpS1JDLH1JaogfzpKkhvjhLElqiNM7ktQQS1+SGmLpS1JDLH1JaoilL0kNsfQlqSGWviQ1xNKXpIZY+pLUEEtfkhpi6UtSQ0Ze+kl+LMlnk+xN8luj3r4kafl6lX6S25OcTPLogvEtSY4kOZpkF0BVHa6qG4FfA35m9JElScvVd0//DmDL4ECSVcBtwFZgE7A9yabusSuB/cCBkSWVJA2tV+lX1f3AMwuGNwNHq+pYVT0H7AGu6pa/u6q2Ar8+yrCSpOGsHmLdtcDjA/dPAO9K8vPA1cC5nGFPP8kOYAfA+vXrh4ghSeprmNI/raq6D7ivx3K7gd0As7OzNeockqRXGubsnSeAiwfur+vGevNyiZI0XsOU/oPApUk2JjkHuBa4eykb8HKJkjRefU/ZvBN4ALgsyYkk11fV88BO4B7gMHBXVR1auaiSpGH1mtOvqu2LjB9giNMyk8wBczMzM8vdhCRpCSb6NQxO70jSePndO5LUkImWvmfvSNJ4Ob0jSQ1xekeSGmLpS1JDnNOXpIY4py9JDXF6R5IaYulLUkOc05ekhjinL0kNcXpHkhpi6UtSQyx9SWqIB3IlqSEeyJWkhji9I0kNsfQlqSGWviQ1xNKXpIZY+pLUEE/ZlKSGeMqmJDXE6R1JaoilL0kNsfQlqSGWviQ1xNKXpIZY+pLUEEtfkhpi6UtSQ/xEriQ1xE/kSlJDnN6RpIZY+pLUEEtfkhpi6UtSQyx9SWqIpS9JDbH0Jakhlr4kNcTSl6SGWPqS1BBLX5IasnolNprkPcA24Hzgc1X1xZV4HknS0vTe009ye5KTSR5dML4lyZEkR5PsAqiqv6+qG4AbgfeNNrIkabmWMr1zB7BlcCDJKuA2YCuwCdieZNPAIh/vHpckTYHepV9V9wPPLBjeDBytqmNV9RywB7gq8z4B/ENVPXy67SXZkeRgkoNPPvnkcvNLkpZg2AO5a4HHB+6f6MZ+B/gl4JokN55uxaraXVWzVTW7Zs2aIWNIkvpYkQO5VfVp4NMrsW1J0vINu6f/BHDxwP113VgvXi5RksZr2NJ/ELg0ycYk5wDXAnf3XdnLJUrSeC3llM07gQeAy5KcSHJ9VT0P7ATuAQ4Dd1XVoZWJKkkaVu85/aravsj4AeDAcp48yRwwNzMzs5zVJUlLNNGvYXB6R5LGy+/ekaSGTLT0PXtHksbL6R1JaojTO5LUEEtfkhrinL4kNcQ5fUlqiNM7ktQQS1+SGuKcviQ1xDl9SWqI0zuS1BBLX5IaYulLUkM8kCtJDfFAriQ1xOkdSWqIpS9JDbH0Jakhlr4kNWT1pAOslA279p92/Pit28acRJKmh6dsSlJDPGVTkhrinL4kNcTSl6SGWPqS1BBLX5IaYulLUkMsfUlqiKUvSQ2x9CWpIX4iV5Ia4idyJakhTu9IUkMsfUlqiKUvSQ2x9CWpIZa+JDXE0pekhlj6ktQQS1+SGmLpS1JDLH1JaoilL0kNGXnpJ7kkyeeS7B31tiVJw+lV+kluT3IyyaMLxrckOZLkaJJdAFV1rKquX4mwkqTh9N3TvwPYMjiQZBVwG7AV2ARsT7JppOkkSSO1us9CVXV/kg0LhjcDR6vqGECSPcBVwNf6bDPJDmAHwPr16/vmHdqGXfsXfez4rdvGlkOSJmGYOf21wOMD908Aa5O8JclngXckuWmxlatqd1XNVtXsmjVrhoghSeqr157+UlTV08CNo96uJGl4w+zpPwFcPHB/XTfWm5dLlKTxGqb0HwQuTbIxyTnAtcDdS9mAl0uUpPHqe8rmncADwGVJTiS5vqqeB3YC9wCHgbuq6tBSntw9fUkar75n72xfZPwAcGC5T15V+4B9s7OzNyx3G5Kk/vwaBklqiKUvSQ2ZaOk7py9J4zXR0vfsHUkaL6d3JKkhI/9E7lIkmQPmZmZmJhnjRYt9L4/fySPptcLpHUlqiNM7ktQQS1+SGmLpS1JDPE9fkhrigVxJaojTO5LUEEtfkhpi6UtSQzyQK0kN8UCuJDXE6R1JaoilL0kNsfQlqSGWviQ1xNKXpIZ4yqYkNcRTNiWpIU7vSFJDLH1JaoilL0kNsfQlqSGWviQ1xNKXpIZY+pLUED+cJUkN8cNZktQQp3ckqSGWviQ1xNKXpIZY+pLUEEtfkhpi6UtSQyx9SWqIpS9JDbH0Jakhlr4kNcTSl6SGWPqS1JDVo95gkvOAPwWeA+6rqr8a9XNIkpan155+ktuTnEzy6ILxLUmOJDmaZFc3fDWwt6puAK4ccV5J0hD6Tu/cAWwZHEiyCrgN2ApsArYn2QSsAx7vFnthNDElSaPQa3qnqu5PsmHB8GbgaFUdA0iyB7gKOMF88X+FM/xPJckOYAfA+vXrl5p7rDbs2j+S7Ry/dduStj+p5UfpbMqq5TnT+8P/bi+Zlp/tYQ7kruWlPXqYL/u1wN8C703yZ8C+xVauqt1VNVtVs2vWrBkihiSpr5EfyK2qZ4EP9Vk2yRwwNzMzM+oYkqTTGGZP/wng4oH767qx3rxcoiSN1zCl/yBwaZKNSc4BrgXuHk0sSdJK6HvK5p3AA8BlSU4kub6qngd2AvcAh4G7qurQUp48yVyS3adOnVpqbknSMvQ9e2f7IuMHgAPLffKq2gfsm52dvWG525Ak9efXMEhSQyZa+k7vSNJ4TbT0PXtHksYrVTXpDCR5EvjWMle/CHhqhHHGwczjYebxMPN4nC7zj1bVkj7dOhWlP4wkB6tqdtI5lsLM42Hm8TDzeIwqswdyJakhlr4kNeS1UPq7Jx1gGcw8HmYeDzOPx0gyn/Vz+pKk/l4Le/qSpJ4sfUlqyFSX/iLX4B18/NwkX+ge/9fBq3sluakbP5Lk3dOeOckvJ3koyX90f//CtGceeHx9ku8k+ejZkDnJFUkeSHKoe71fP82Zk/xAks93WQ8nuWkceXtm/rkkDyd5Psk1Cx67Lsk3uj/XTXvmJG8f+Ll4JMn7pj3zwOPnd1+G+ZlXfbKqmso/wCrgm8AlwDnAV4FNC5b5MPDZ7va1wBe625u65c8FNnbbWTXlmd8BvLW7/ePAE9P+Og88vhf4G+Cj056Z+S8ZfAT4ie7+W86Cn433A3u62z8IHAc2TEnmDcAVwF8A1wyMvxk41v19YXf7winP/Dbg0u72W4H/At40zZkHHv8T4K+Bz7za803znv6L1+CtqueA/78G76CrgM93t/cCv5gk3fieqvpeVT0GHO22N7WZq+rfq+rb3fgh4A1Jzp3mzABJ3gM81mUel2Ey/wrwSFV9FaCqnq6qF6Y8cwHnJVkNvAF4DvifachcVcer6hHgfxes+27gS1X1TFX9N/AlYMs0Z66qr1fVN7rb3wZOAuO4luswrzNJfgr4YeCLfZ5smkt/sWvwnnaZmv9+/1PM77n1WXclDJN50HuBh6vqeyuU87R5Or0zJ3kj8DHgD8aQ87R5Okt5nd8GVJJ7ul+Xf28MeV+Wp7OUzHuBZ5nf8/xP4FNV9cxKB2a499E0vwdfVZLNzO91f3NEuc5k2ZmTvA74I6D31OrIr5Gr4SS5HPgE83uk0+4W4I+r6jvdjv/ZYDXws8A7ge8C9yZ5qKrunWysM9oMvMD8lMOFwD8l+XJVHZtsrNemJD8C/CVwXVW9Ys96ynwYOFBVJ/q+B6d5T7/PNXhfXKb71fcC4Ome666EYTKTZB3wd8AHqmocexgvy9NZSuZ3AZ9Mchz4CPD7SXaucN6X5eksJfMJ4P6qeqqqvsv8RYB+csUTD5f5/cA/VtX3q+ok8M/AOL43Zpj30TS/BxeV5HxgP3BzVf3LiLMtZpjMPw3s7N6DnwI+kOTWM66x0gcphji4sZr5gz8beengxuULlvltXn7g667u9uW8/EDuMcZzsG6YzG/qlr/6bHmdFyxzC+M7kDvM63wh8DDzB0RXA18Gtk155o8Bf97dPg/4GnDFNGQeWPYOXnkg97Hu9b6wu/3mKc98DnAv8JFx/ByPIvOCxz5IjwO5Y/uHLfPF+FXg68zPq93cjf0hcGV3+/XMnzVyFPg34JKBdW/u1jsCbJ32zMDHmZ+3/crAnx+a5swLtnELYyr9Efxs/AbzB54fBT457ZmBN3bjh5gv/N+doszvZP63p2eZ/63k0MC6v9n9W44CH5r2zN3PxfcXvAffPs2ZF2zjg/Qofb+GQZIaMs1z+pKkEbP0Jakhlr4kNcTSl6SGWPqS1BBLX5IaYulLUkP+D05FeaRe8kr8AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.hist(cora_bc, bins=50, log=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "501ca536",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7030, 219558, 6.0)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(citeseer.get_number_of_nodes(), citeseer.get_number_of_directed_edges(), citeseer.get_diameter())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e21b4afb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3min 2s, sys: 15.1 s, total: 3min 17s\n",
      "Wall time: 10.9 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "citeseer_bc = citeseer.get_betweenness_centrality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "75eb01a5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD+CAYAAADBCEVaAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/NK7nSAAAACXBIWXMAAAsTAAALEwEAmpwYAAAQAElEQVR4nO3df4wc5X3H8fe3dgytSQ0BFCH/iI3OcmtVVaAnA0qEorakdoihilDra6SkqYtFWleN+kdrRFWp/5H+UbUIWjgVl0ZK7bi0TQw4ctKkCKlCxDZJiB3HcLiOfFaIDShGjSpRkm//mDHebHbXc7e73r3H75d0ut1nZ57ne97x5+aemZ2JzESSVJafGXUBkqTBM9wlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSrQUMI9IpZGxMGI+PAw+pck9dYo3CNiZ0ScjojDbe0bI+JYRMxExI6Wl/4M2DPIQiVJzUWTyw9ExK3A/wCfycxfqtsWAS8CtwGzwAFgClgOXA1cDryamU8Op3RJUjeLmyyUmc9ExOq25g3ATGYeB4iI3cCdwBXAUmA98L8RsS8zf9yr/2uuuSZXr27vXpLUy6FDh17NzGs7vdYo3LtYDpxseT4L3JSZ2wEi4nep9tw7BntEbAO2AaxatYqDBw/2UYokXXoi4rvdXhva2TKZ+VivKZnMnM7MycycvPbajr94JEnz1E+4nwJWtjxfUbc1FhGbI2L67NmzfZQhSWrXT7gfANZGxJqIWAJsAfbOpYPMfCIzty1btqyPMiRJ7ZqeCrkLeBZYFxGzEbE1M98CtgP7gaPAnsw8MrxSJUlNNT1bZqpL+z5g33wHj4jNwOaJiYn5diFJ6mCklx9wWkaShsNry0hSgUYa7p4tI0nD0c+HmPqWmU8AT0xOTt493z5W73iqY/uJ+2+fb5eStOA5LSNJBXJaRpIK5NkyklQgp2UkqUCGuyQVyHCXpAJ5QFWSCuQBVUkqkNMyklQgw12SCmS4S1KBPKAqSQXygKokFchpGUkqkOEuSQUy3CWpQIa7JBXIs2UkqUCeLSNJBXJaRpIKZLhLUoEMd0kqkOEuSQUy3CWpQIa7JBXIcJekAvkhJkkqkB9ikqQCOS0jSQUy3CWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKpDhLkkFMtwlqUADD/eI+MWIeDgiHo+ITw66f0nShTUK94jYGRGnI+JwW/vGiDgWETMRsQMgM49m5j3AbwHvG3zJkqQLabrn/hiwsbUhIhYBDwGbgPXAVESsr1+7A3gK2DewSiVJjTUK98x8Bni9rXkDMJOZxzPzTWA3cGe9/N7M3AR8dJDFSpKaWdzHusuBky3PZ4GbIuIDwEeAy+ix5x4R24BtAKtWreqjDElSu37CvaPMfBp4usFy08A0wOTkZA66Dkm6lPVztswpYGXL8xV1W2PeiUmShqOfcD8ArI2INRGxBNgC7J1LB96JSZKGo+mpkLuAZ4F1ETEbEVsz8y1gO7AfOArsycwjwytVktRUozn3zJzq0r6PPk53jIjNwOaJiYn5diFJ6sAbZEtSgby2jCQVaKTh7tkykjQcTstIUoGclpGkAjktI0kFclpGkgrktIwkFchwl6QCOecuSQVyzl2SCuS0jCQVyHCXpAIZ7pJUIA+oSlKBPKAqSQVyWkaSCmS4S1KBDHdJKpDhLkkFMtwlqUCeCilJBfJUSEkq0OJRFzAsq3c81bH9xP23X+RKJOnic85dkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFcgPMUlSgfwQkyQVyGkZSSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLhLUoEMd0kq0FDuxBQRvwncDvw88GhmfmkY40iSOmu85x4ROyPidEQcbmvfGBHHImImInYAZObnM/Nu4B7gtwdbsiTpQuYyLfMYsLG1ISIWAQ8Bm4D1wFRErG9Z5M/r1yVJF1HjcM/MZ4DX25o3ADOZeTwz3wR2A3dG5dPAFzPz+cGVK0lqot8DqsuBky3PZ+u2PwJ+HbgrIu7ptGJEbIuIgxFx8MyZM32WIUlqNZQDqpn5APDABZaZBqYBJicncxh1SNKlqt8991PAypbnK+o2SdII9RvuB4C1EbEmIpYAW4C9TVf2TkySNBxzORVyF/AssC4iZiNia2a+BWwH9gNHgT2ZeaRpn96JSZKGo/Gce2ZOdWnfB+ybz+ARsRnYPDExMZ/VJUldeA9VSSqQ15aRpAKNNNw9oCpJw+G0jCQVyGkZSSqQ4S5JBXLOXZIK5Jy7JBXIaRlJKpDhLkkFcs5dkgrknLskFchpGUkq0FDuxDTOVu94qutrJ+6//SJWIknD4567JBXIA6qSVCAPqEpSgZyWkaQCGe6SVCDDXZIKZLhLUoE8W0aSCuTZMpJUIKdlJKlAhrskFchwl6QCXXIXDuul20XFvKCYpIXGPXdJKpDhLkkFMtwlqUCGuyQVyE+oSlKB/ISqJBXIaRlJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgrkVSEb8GqRkhYa99wlqUADD/eIuD4iHo2IxwfdtySpmUbhHhE7I+J0RBxua98YEcciYiYidgBk5vHM3DqMYiVJzTSdc38MeBD4zLmGiFgEPATcBswCByJib2Z+e9BFLjTO0UsatUZ77pn5DPB6W/MGYKbeU38T2A3cOeD6JEnz0M+c+3LgZMvzWWB5RFwdEQ8DN0TEvd1WjohtEXEwIg6eOXOmjzIkSe0GfipkZr4G3NNguWlgGmBycjIHXYckXcr62XM/Baxseb6ibpMkjVg/e+4HgLURsYYq1LcAvzOXDiJiM7B5YmKijzIWDg+0SrpYmp4KuQt4FlgXEbMRsTUz3wK2A/uBo8CezDwyl8G9E5MkDUejPffMnOrSvg/YN9/BL7U9d0m6WLyHqiQVyGvLSFKBRhruEbE5IqbPnj07yjIkqThOy0hSgZyWkaQCGe6SVCDn3CWpQM65S1KBnJaRpAIZ7pJUoIFf8ncuFvrlB7pdCGzY/XihMUkX4py7JBXIaRlJKpDhLkkFMtwlqUB+iEmSCuQBVUkqkNMyklQgw12SCmS4S1KBDHdJKpCXH7gEdLu8wcW4jMEox5YuZZ4tI0kFclpGkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCRWaObvDzH2K6+6WXXppXH4O6j6nO6/UBo1H9e5fwoSc/0HVh/hvNTUQcyszJTq/5ISZJKpDTMpJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKNPAbZEfEUuDvgDeBpzPzs4MeQ5LUW6M994jYGRGnI+JwW/vGiDgWETMRsaNu/gjweGbeDdwx4HolSQ00nZZ5DNjY2hARi4CHgE3AemAqItYDK4CT9WI/GkyZkqS5aBTumfkM8Hpb8wZgJjOPZ+abwG7gTmCWKuAb9y9JGqx+5tyXc34PHapQvwl4AHgwIm4Hnui2ckRsA7YBrFq1qo8yNGgL6Rr5g7r+93x+5m5jzLWvuf4Mc+1/2P8W87nW+kLaxgblYl+rfuAHVDPzh8AnGiw3DUwDTE5Oju6OIZJUoH6mTU4BK1uer6jbGouIzRExffbs2T7KkCS16yfcDwBrI2JNRCwBtgB759KBd2KSpOFoeirkLuBZYF1EzEbE1sx8C9gO7AeOAnsy88jwSpUkNdVozj0zp7q07wP2zXfwlhtkz7cLSVIH3iBbkgrkeeiSVKCRhrtny0jScDgtI0kFiszRf34oIs4A353n6tcArw6wnGGy1uGw1uFYSLXCwqp3ULW+JzOv7fTCWIR7PyLiYGZOjrqOJqx1OKx1OBZSrbCw6r0YtXpAVZIKZLhLUoFKCPfpURcwB9Y6HNY6HAupVlhY9Q691gU/5y5J+mkl7LlLktpl5oL9orr13zFgBtgx5LF2AqeBwy1t7wK+DLxUf7+qbg+qm5bMAC8AN7as8/F6+ZeAj7e0/wrwrXqdBzj/V1XHMXrUuRL4T+DbwBHgj8e41suBrwHfrGv9y7p9DfBc3f/ngCV1+2X185n69dUtfd1btx8DfuNC20i3MRpsB4uArwNPjnOtwIn6PfoGcHBct4F6nSuBx4HvUF2E8JYxrnVd/W967usN4FPjWO/IA3q+X1T/yV4GrgeWUAXE+iGOdytwIz8Z7n9F/Z8Q2AF8un78IeCL9Rt7M/Bcy5tzvP5+Vf343EbwtXrZqNfd1GuMHnVed24DAt4JvEh1j9txrDWAK+rH76AKsJuBPcCWuv1h4JP14z8AHq4fbwE+Vz9eX7//l1EF4cv19tF1G+k2RoPt4E+Af+Z8uI9lrVThfk1b29htA/Vy/wT8fv14CVXYj2WtHTLoFeA941jvyEN6vl9Uv933tzy/F7h3yGOu5ifD/RhwXf34OuBY/fgRYKp9OWAKeKSl/ZG67TrgOy3tby/XbYw51PwF4LZxrxX4OeB5qls1vgosbn+fqS4vfUv9eHG9XLS/9+eW67aN1Ot0HOMCNa4AvgL8KvBkr37GoNYT/HS4j902ACwD/pt673Sca+1Q+weB/xrXehfynHune7guv8g1vDszv1c/fgV4d/24W2292mc7tPca44IiYjVwA9Ue8VjWGhGLIuIbVFNeX6bae/1BVvcLaO//7Zrq188CV8/jZ7i6xxi9/A3wp8CP6+e9+hl1rQl8KSIO1fcrhvHcBtYAZ4B/jIivR8Q/RMTSMa213RZg1wX6Glm9Czncx0pWv05zXMaIiCuAfwU+lZlvzLef+Wo6Rmb+KDPfS7VXvAH4hWHWNV8R8WHgdGYeGnUtDb0/M28ENgF/GBG3tr44RtvAYqrpzr/PzBuAH1JNOcy1n77MdYz67nN3AP/Sb1/z0WSMhRzufd/DdQC+HxHXAdTfT1+gtl7tKzq09xqjq4h4B1WwfzYz/22caz0nM39AdSD4FuDKiDh3I5nW/t+uqX59GfDaPH6G13qM0c37gDsi4gSwm2pq5m/HtFYy81T9/TTw71S/OMdxG5gFZjPzufr541RhP461ttoEPJ+Z379AXyOrdyGHe9/3cB2AvVRHvKm/f6Gl/WNRuRk4W/85tR/4YERcFRFXUc3Z7a9feyMibo6IAD7W1lenMTqq138UOJqZfz3mtV4bEVfWj3+W6tjAUaqQv6tLref6vwv4ar0HsxfYEhGXRcQaYC3VQamO20i9TrcxOsrMezNzRWaurvv5amZ+dBxrjYilEfHOc4+p3rvDjOE2kJmvACcjYl3d9GtUZ3qNXa1tpjg/JdOrr9HVO5cDCOP2RXUk+kWqedr7hjzWLuB7wP9R7W1spZoP/QrVqUn/AbyrXjaAh+q6vgVMtvTze1SnOM0An2hpn6T6D/gy8CDnT3/qOEaPOt9P9efaC5w/XetDY1rrL1OdVvhC3d9f1O3XUwXeDNWfvZfV7ZfXz2fq169v6eu+up5j1GcX9NpGuo3RcFv4AOfPlhm7Wuvlv8n5U0zv6/X+jHIbqNd5L3Cw3g4+T3X2yFjWWq+3lOovqmUtbWNXr59QlaQCLeRpGUlSF4a7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKpDhLkkF+n+8pIOoU3wzCgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.hist(citeseer_bc, bins=50, log=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "1a23756e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(20217, 2064713, 4.0)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(pubmed.get_number_of_nodes(), pubmed.get_number_of_directed_edges(), pubmed.get_diameter())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "623d1785",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 28min 19s, sys: 1min 24s, total: 29min 43s\n",
      "Wall time: 1min 39s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "pubmed_bc = pubmed.get_betweenness_centrality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "53de329f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEFCAYAAAAYKqc0AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/NK7nSAAAACXBIWXMAAAsTAAALEwEAmpwYAAAOLklEQVR4nO3d749c113H8fenNik0FQER8wD/YA3ruligElilpZGqqi2SrdQJakuJKUhUlq0gHAril4v4A4qEEFRyW60aYyGCI+NGVUxM3Qc0MkImspMWYccEWU5arymyk7QGKqRg+uXBTOTVZtee3ZnZ6z37fj2x58zMvV9feT++/s6Zc1JVSJLa8qauC5AkjZ7hLkkNMtwlqUGGuyQ1yHCXpAat7boAgLvvvrsmJia6LkOSVpRnn3325apaN99zt0W4T0xMcObMma7LkKQVJcnXF3qu07ZMkp1Jpq9du9ZlGZLUnE7DvaqOVdXeu+66q8syJKk5fqAqSQ0y3CWpQYa7JDXIcJekBhnuktQgw12SGtTpl5iS7AR2Tk5OLvkYE/ufmnf8pU/dv+RjStJK5zx3SWqQbRlJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWrQWMI9yZ1JziT54DiOL0m6uYHCPcnBJFeSnJ0zvj3JC0kuJNk/66k/AI6MslBJ0uAGvXM/BGyfPZBkDXAA2AFsA3Yl2Zbk54HngSsjrFOStAgDrQpZVSeTTMwZvhe4UFUXAZI8DjwIvBW4k17g/0+S41X13bnHTLIX2AuwadOmJf8BJElvNMySv+uBS7MezwDvrKp9AEl+DXh5vmAHqKppYBpgamqqhqhDkjTH2NZzr6pDt3rNKNZzlyS90TCzZS4DG2c93tAfG5jruUvSeAwT7qeBLUk2J7kDeAh4cjRlSZKGMehUyMPAKWBrkpkku6vqOrAPOAGcB45U1bnFnDzJziTT165dW2zdkqSbGHS2zK4Fxo8Dx5d68qo6Bhybmpras9RjSJLeqNPlB7xzl6TxcINsSWqQC4dJUoNsy0hSg2zLSFKDbMtIUoMMd0lqkD13SWqQPXdJapBtGUlqkOEuSQ2y5y5JDbLnLkkNsi0jSQ0y3CWpQYa7JDXIcJekBjlbRpIa5GwZSWqQbRlJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIOe5S1KDnOcuSQ2yLSNJDTLcJalBhrskNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0aebgn+Ykkn0tyNMmvj/r4kqRbGyjckxxMciXJ2Tnj25O8kORCkv0AVXW+qh4GPgrcN/qSJUm3Muid+yFg++yBJGuAA8AOYBuwK8m2/nMPAE8Bx0dWqSRpYAOFe1WdBF6dM3wvcKGqLlbVa8DjwIP91z9ZVTuAjy10zCR7k5xJcubq1atLq16SNK+1Q7x3PXBp1uMZ4J1J3gt8CHgzN7lzr6ppYBpgamqqhqhDkjTHMOE+r6p6Gnh6kNcm2QnsnJycHHUZkrSqDTNb5jKwcdbjDf2xgbmeuySNxzDhfhrYkmRzkjuAh4AnR1OWJGkYg06FPAycArYmmUmyu6quA/uAE8B54EhVnVvMyd1mT5LGY6Cee1XtWmD8OENMd6yqY8CxqampPUs9hiTpjdwgW5Ia5AbZktQgFw6TpAbZlpGkBtmWkaQG2ZaRpAYZ7pLUIHvuktQge+6S1CDbMpLUIMNdkhpkz12SGmTPXZIaZFtGkhpkuEtSgwx3SWqQ4S5JDXK2jCQ1yNkyktQg2zKS1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQc5zl6QGOc9dkhpkW0aSGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhq0dhwHTfILwP3A9wOPVtWXx3EeSdL8Br5zT3IwyZUkZ+eMb0/yQpILSfYDVNUXq2oP8DDwS6MtWZJ0K4tpyxwCts8eSLIGOADsALYBu5Jsm/WSP+o/L0laRgOHe1WdBF6dM3wvcKGqLlbVa8DjwIPp+WPg76rqufmOl2RvkjNJzly9enWp9UuS5jHsB6rrgUuzHs/0xx4BPgB8JMnD872xqqaraqqqptatWzdkGZKk2cbygWpVfRr49K1el2QnsHNycnIcZUjSqjXsnftlYOOsxxv6YwNxPXdJGo9hw/00sCXJ5iR3AA8BTw76ZndikqTxWMxUyMPAKWBrkpkku6vqOrAPOAGcB45U1blBj+mduySNx8A996ratcD4ceD4yCqSJA1tLB+oDmqcH6hO7H9q3vGXPnX/yM8lSbcbN8iWpAa5cJgkNajTcHe2jCSNh20ZSWqQbRlJapDhLkkNsucuSQ2y5y5JDbItI0kNMtwlqUH23CWpQfbcJalBtmUkqUGGuyQ1yHCXpAYZ7pLUIGfLSFKDOt2JqaqOAcempqb2LNc5F9qhCdylSVI7bMtIUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBjnPXZIa5KqQktSgTr/EdLtZ6AtOfrlJ0kpjz12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUoJGHe5IfS/JokqOjPrYkaTADhXuSg0muJDk7Z3x7kheSXEiyH6CqLlbV7nEUK0kazKB37oeA7bMHkqwBDgA7gG3AriTbRlqdJGlJBlpbpqpOJpmYM3wvcKGqLgIkeRx4EHh+kGMm2QvsBdi0adOg9XZisWvOuEaNpK4N03NfD1ya9XgGWJ/kh5J8DrgnyScXenNVTVfVVFVNrVu3bogyJElzjXxVyKp6BXh4kNcm2QnsnJycHHUZkrSqDXPnfhnYOOvxhv7YwFzPXZLGY5g799PAliSb6YX6Q8AvL+YAK/3OfaHeuiR1bdCpkIeBU8DWJDNJdlfVdWAfcAI4DxypqnOLObl37pI0HoPOltm1wPhx4PhIK5IkDc0NsiWpQW6QLUkNcuEwSWqQbRlJapBtGUlqkG0ZSWqQ4S5JDbLnLkkNsucuSQ2yLSNJDTLcJalBI1/PfTFW+qqQozKqnZvcAUrS6+y5S1KDbMtIUoMMd0lqkOEuSQ0y3CWpQc6WuY05+0XSUjlbRpIaZFtGkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNch57stooXnrXZ13ofnyS6nTufft8PsVbXCeuyQ1yLaMJDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1aOTLDyS5E/gM8BrwdFU9NupzSJJubqA79yQHk1xJcnbO+PYkLyS5kGR/f/hDwNGq2gM8MOJ6JUkDGLQtcwjYPnsgyRrgALAD2AbsSrIN2ABc6r/s/0ZTpiRpMQZqy1TVySQTc4bvBS5U1UWAJI8DDwIz9AL+a9zkH48ke4G9AJs2bVps3ataV6tL3syoalrsSpWjWqmwy5UwR/VnW47VPxd7HFeSvGG5V9sc5gPV9dy4Q4deqK8HngA+nOSzwLGF3lxV01U1VVVT69atG6IMSdJcI/9Ataq+A3x8kNeutvXcJWm5DHPnfhnYOOvxhv7YwFzPXZLGY5hwPw1sSbI5yR3AQ8CTizlAkp1Jpq9duzZEGZKkuQadCnkYOAVsTTKTZHdVXQf2ASeA88CRqjq3mJN75y5J4zHobJldC4wfB46PtCJJ0tA6XX7AtowkjYcbZEtSg1w4TJIalKrqugaSXAW+vsS33w28PMJyVjKvRY/X4QavRU+r1+FHq2reb4HeFuE+jCRnqmqq6zpuB16LHq/DDV6LntV4HWzLSFKDDHdJalAL4T7ddQG3Ea9Fj9fhBq9Fz6q7Diu+5y5JeqMW7twlSXMY7pLUoBUd7gvs4bqqJNmY5CtJnk9yLsknuq6pS0nWJPlqkr/tupYuJfmBJEeT/GuS80l+ruuaupDkt/s/F2eTHE7yvV3XtFxWbLjfZA/X1eY68DtVtQ14F/Abq/Q6vO4T9FYpXe3+HPhSVb0deAer8JokWQ/8JjBVVT8JrKG3NPmqsGLDnVl7uFbVa8Dre7iuKlX1zap6rv/7/6L3Q7y+26q6kWQDcD/w+a5r6VKSu4D3AI8CVNVrVfXtTovqzlrg+5KsBd4C/HvH9SyblRzuC+3humr1NzG/B3im41K68mfA7wPf7biOrm0GrgJ/0W9RfT7JnV0Xtdyq6jLwJ8A3gG8C16rqy91WtXxWcrhrliRvBb4A/FZV/WfX9Sy3JB8ErlTVs13XchtYC/wM8Nmqugf4DrDqPpNK8oP0/je/GfgR4M4kv9JtVctnJYf70Hu4tiLJ99AL9seq6omu6+nIfcADSV6i16J7X5K/6rakzswAM1X1+v/gjtIL+9XmA8CLVXW1qv4XeAJ4d8c1LZuVHO5D7+HagiSh11s9X1V/2nU9XamqT1bVhqqaoPd34e+ratXcpc1WVf8BXEqytT/0fuD5DkvqyjeAdyV5S//n5P2sog+WB9pm73ZUVdeTvL6H6xrg4GL3cG3EfcCvAv+S5Gv9sT/sb4Go1esR4LH+jc9F4OMd17PsquqZJEeB5+jNKvsqq2gZApcfkKQGreS2jCRpAYa7JDXIcJekBhnuktQgw12SllmSg0muJDk74Os/OmtxwL8e6D3OlpGk5ZXkPcB/A3/ZX9TsZq/dAhwB3ldV30ryw1V15Vbn8M5dkpZZVZ0EXp09luTHk3wpybNJ/iHJ2/tP7QEOVNW3+u+9ZbCD4S5Jt4tp4JGq+lngd4HP9MffBrwtyT8m+ack2wc52Ir9hqoktaK/8N+7gb/prZQAwJv7v64FtgDvpbeG1skkP3WrZZwNd0nq3puAb1fVT8/z3AzwTH/xsxeT/Bu9sD99qwNKkjrUX6b7xSS/CL0FAZO8o//0F+ndtZPkbnptmou3OqbhLknLLMlh4BSwNclMkt3Ax4DdSf4ZOMeNneVOAK8keR74CvB7VfXKLc/hVEhJao937pLUIMNdkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNej/AbefiN5WkUT0AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.hist(pubmed_bc, bins=50, log=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "acc859d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "from grape.datasets.string import HomoSapiens, CanisLupusFamiliaris, MusMusculus\n",
    "\n",
    "homo_sapiens = HomoSapiens()\n",
    "doggo = CanisLupusFamiliaris()\n",
    "mouse = MusMusculus()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "656509e4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(19566, 11938498, 5.0)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(homo_sapiens.get_number_of_nodes(), homo_sapiens.get_number_of_directed_edges(), homo_sapiens.get_diameter())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "7b219c19",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 28min 58s, sys: 1min 20s, total: 30min 19s\n",
      "Wall time: 1min 42s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "homo_sapiens_bc = homo_sapiens.get_betweenness_centrality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "0a1fe347",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEFCAYAAAAYKqc0AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/NK7nSAAAACXBIWXMAAAsTAAALEwEAmpwYAAAPAElEQVR4nO3dX4xc51nH8e8viRJE2gbUuBJy4m5C3NBVELSM0gJSKbQgp8Exakux1QqKLFsJcm4QCKNygeAmXMBFJJewUiMDAqduVEW24mIEJDKqnGKHpm0cK8hNU7Khwk7SGvE3CX24mGm6bHa9Z3f+eV9/P1KUnTNnzzyvZ/3z2ee8855UFZKktlw27QIkSaNnuEtSgwx3SWqQ4S5JDTLcJalBV0y7AIBrr722ZmZmpl2GJK0rjz/++AtVtWGp5y6KcJ+ZmeHkyZPTLkOS1pUkX1/uOdsyktQgw12SGmS4S1KDDHdJapDhLkkNmmq4J9maZO78+fPTLEOSmjPVcK+qw1W1+5prrplmGZLUHNsyktSgi+JDTMOY2fvwktufvef2CVciSRcPz9wlqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWrQWMI9ydVJTib5+XEcX5J0YZ3CPcn9Sc4meXLR9i1Jnk5yJsneBU/9FnBwlIVKkrrreua+H9iycEOSy4F9wG3ALLAjyWySnwWeAs6OsE5J0ip0Wn6gqo4lmVm0+VbgTFU9A5DkAWAb8AbgavqB/19JjlTVtxcfM8luYDfApk2b1jwASdLrDbO2zEbguQWP54F3VdUegCQfB15YKtgBqmoOmAPo9Xo1RB2SpEXGtnBYVe0f17ElSRc2zGyZ54HrFzy+brCtM2/WIUnjMUy4nwA2J7khyZXAduDQag7gzTokaTy6ToU8ABwHbk4yn2RnVb0K7AGOAqeBg1V1ajUv7pm7JI1H19kyO5bZfgQ4stYXr6rDwOFer7drrceQJL2eyw9IUoOmGu62ZSRpPKYa7l5QlaTxsC0jSQ2yLSNJDbItI0kNsi0jSQ2yLSNJDbItI0kNsi0jSQ0y3CWpQYa7JDXIC6qS1CAvqEpSg2zLSFKDDHdJapDhLkkNMtwlqUHOlpGkBjlbRpIaZFtGkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNch57pLUIOe5S1KDbMtIUoMMd0lq0BXTLmBcZvY+vOT2Z++5fcKVSNLkeeYuSQ0y3CWpQYa7JDXIcJekBhnuktQgw12SGjTycE/y9iT3JXkwyV2jPr4kaWWdwj3J/UnOJnly0fYtSZ5OcibJXoCqOl1VdwIfAX5y9CVLklbS9cx9P7Bl4YYklwP7gNuAWWBHktnBc3cADwNHRlapJKmzTuFeVceAlxZtvhU4U1XPVNXLwAPAtsH+h6rqNuCjyx0zye4kJ5OcPHfu3NqqlyQtaZjlBzYCzy14PA+8K8l7gQ8CV3GBM/eqmgPmAHq9Xg1RhyRpkZGvLVNVjwKPdtk3yVZg60033TTqMiTpkjbMbJnngesXPL5usK0z13OXpPEYJtxPAJuT3JDkSmA7cGg0ZUmShtF1KuQB4Dhwc5L5JDur6lVgD3AUOA0crKpTq3lxb7MnSePRqedeVTuW2X6EIaY7VtVh4HCv19u11mNIkl7PG2RLUoO8QbYkNciFwySpQbZlJKlBtmUkqUG2ZSSpQYa7JDXInrskNcieuyQ1yLaMJDXIcJekBhnuktQgL6hKUoO8oCpJDbItI0kNGvk9VC92M3sfXva5Z++5fYKVSNL4eOYuSQ3ygqokNcgLqpLUINsyktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yA8xSVKD/BCTJDXItowkNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQWO5QXaSXwBuB94EfKqq/nocryNJWlrnM/ck9yc5m+TJRdu3JHk6yZkkewGq6qGq2gXcCfzSaEuWJK1kNW2Z/cCWhRuSXA7sA24DZoEdSWYX7PI7g+clSRPUuS1TVceSzCzafCtwpqqeAUjyALAtyWngHuBzVfWPoyp23Gb2Przk9mfvuX3ClUjScIa9oLoReG7B4/nBtruB9wMfTnLnUt+YZHeSk0lOnjt3bsgyJEkLjeWCalXdC9y7wj5zwBxAr9ercdQhSZeqYc/cnweuX/D4usG2TlzPXZLGY9hwPwFsTnJDkiuB7cChrt/seu6SNB6rmQp5ADgO3JxkPsnOqnoV2AMcBU4DB6vq1CqO6Zm7JI3BambL7Fhm+xHgyFpevKoOA4d7vd6utXy/JGlpLj8gSQ3yBtmS1CBvkC1JDbItI0kNsi0jSQ2yLSNJDbItI0kNGsvaMq1xtUhJ6409d0lqkD13SWqQPXdJapDhLkkNsucuSQ2y5y5JDbItI0kNMtwlqUGGuyQ1yHCXpAY5W0aSGuRsGUlqkG0ZSWqQ4S5JDXLJ3yG4FLCki5Vn7pLUIMNdkhpkuEtSg6bac0+yFdh60003TbOMkbMXL2nanOcuSQ2yLSNJDTLcJalBhrskNchwl6QGGe6S1CDDXZIaZLhLUoNcOGyC/HCTpEnxzF2SGjTycE9yY5JPJXlw1MeWJHXTKdyT3J/kbJInF23fkuTpJGeS7AWoqmeqauc4ipUkddP1zH0/sGXhhiSXA/uA24BZYEeS2ZFWJ0lak07hXlXHgJcWbb4VODM4U38ZeADY1vWFk+xOcjLJyXPnznUuWJK0smF67huB5xY8ngc2JnlzkvuAdyT57eW+uarmqqpXVb0NGzYMUYYkabGRT4WsqheBO7vs2+p67pI0bcOcuT8PXL/g8XWDbZ25nrskjccw4X4C2JzkhiRXAtuBQ6MpS5I0jK5TIQ8Ax4Gbk8wn2VlVrwJ7gKPAaeBgVZ1azYsn2Zpk7vz586utW5J0AZ167lW1Y5ntR4Aja33xqjoMHO71ervWegxJ0uu5/IAkNWiq4W5bRpLGY6rh7mwZSRoP2zKS1KCprufuh5jWxnXhJa3EtowkNci2jCQ1yNkyktQg2zKS1CDbMpLUIMNdkhpkuEtSg5znfhEY1bz15Y6zHOfFS+3ygqokNci2jCQ1yHCXpAYZ7pLUIMNdkhrkbJmL2Gpnv0yCK1JK64OzZSSpQbZlJKlBhrskNchwl6QGGe6S1CDDXZIaZLhLUoOc534Jm+ac9Zbny7c8Nq0fznOXpAbZlpGkBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAaNfPmBJFcDnwReBh6tqr8Y9WtIki6s05l7kvuTnE3y5KLtW5I8neRMkr2DzR8EHqyqXcAdI65XktRB17bMfmDLwg1JLgf2AbcBs8COJLPAdcBzg93+dzRlSpJWo1NbpqqOJZlZtPlW4ExVPQOQ5AFgGzBPP+Cf4AL/eCTZDewG2LRp02rr1hgtt6rhNE2rplGu5LjeV4ucRP3r/c/oQiY9tmEuqG7ku2fo0A/1jcBngQ8l+WPg8HLfXFVzVdWrqt6GDRuGKEOStNjIL6hW1X8Av9plX9dzl6TxGObM/Xng+gWPrxts68z13CVpPIYJ9xPA5iQ3JLkS2A4cWs0BkmxNMnf+/PkhypAkLdZ1KuQB4Dhwc5L5JDur6lVgD3AUOA0crKpTq3lxz9wlaTy6zpbZscz2I8CRkVYkSRraVJcfsC0jSePhDbIlqUEuHCZJDUpVTbsGkpwDvr7Gb78WeGGE5awXjvvS4rgvLV3H/daqWvJToBdFuA8jycmq6k27jklz3JcWx31pGcW4bctIUoMMd0lqUAvhPjftAqbEcV9aHPelZehxr/ueuyTp9Vo4c5ckLWK4S1KD1k24L3O/1oXPX5Xk04Pnv7DEnaPWpQ7j/vUkTyX5cpK/TfLWadQ5aiuNe8F+H0pSSZqYLtdl3Ek+MnjPTyX5y0nXOA4dfs43JXkkyRcHP+sfmEado7TcvakXPJ8k9w7+TL6c5J2reoGquuj/Ay4HvgrcCFwJfAmYXbTPrwH3Db7eDnx62nVPaNw/DXzv4Ou7LpVxD/Z7I3AMeAzoTbvuCb3fm4EvAt8/ePyWadc9oXHPAXcNvp4Fnp123SMY93uAdwJPLvP8B4DPAQHeDXxhNcdfL2fur92vtapeBr5zv9aFtgF/Ovj6QeB9STLBGsdhxXFX1SNV9Z+Dh4/Rv2nKetfl/Qb4feAPgP+eZHFj1GXcu4B9VfVNgKo6O+Eax6HLuAt40+Dra4B/mWB9Y1FVx4CXLrDLNuDPqu8x4PuS/EDX46+XcF/ufq1L7lP9tebPA2+eSHXj02XcC+2k/y/9erfiuAe/ol5fVRff3bzXrsv7/TbgbUk+n+SxJFsmVt34dBn37wIfSzJPf5nxuydT2lSt9u///zPye6hqOpJ8DOgBPzXtWsYtyWXAHwEfn3Ip03AF/dbMe+n/lnYsyQ9X1bemWdQE7AD2V9UfJvlx4M+T3FJV3552YRer9XLm3uV+ra/tk+QK+r+6vTiR6san031qk7wf+ARwR1X9z4RqG6eVxv1G4Bbg0STP0u9HHmrgomqX93seOFRVr1TV14B/oh/261mXce8EDgJU1XHge+gvrtWyoe5TvV7Cvcv9Wg8BvzL4+sPA39XgqsQ6tuK4k7wD+BP6wd5C/xVWGHdVna+qa6tqpqpm6F9ruKOqTk6n3JHp8nP+EP2zdpJcS79N88wEaxyHLuP+Z+B9AEneTj/cz020ysk7BPzyYNbMu4HzVfWNzt897SvGq7iy/AH6ZylfBT4x2PZ79P9SQ//N/gxwBvgH4MZp1zyhcf8N8K/AE4P/Dk275kmMe9G+j9LAbJmO73fot6SeAr4CbJ92zRMa9yzwefozaZ4Afm7aNY9gzAeAbwCv0P+NbCdwJ3Dngvd63+DP5Cur/Rl3+QFJatB6actIklbBcJekBhnuktQgw12SGmS4S9KErbRo2BL7r3qxOGfLSNKEJXkP8O/01465ZYV9N9P/ANfPVNU3k7ylOnymxTN3SZqwWmLRsCQ/mOSvkjye5O+T/NDgqTUtFme4S9LFYQ64u6p+DPgN4JOD7WtaLM6FwyRpypK8AfgJ4DMLViq/avD/NS0WZ7hL0vRdBnyrqn50iefm6d+o4xXga0m+s1jciZUOKEmaoqr6N/rB/Yvw2i32fmTw9EOsYbE4w12SJizJAeA4cHOS+SQ7gY8CO5N8CTjFd+9GdRR4MclTwCPAb1bVisuZOxVSkhrkmbskNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ36PzdeW0njiCoqAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.hist(homo_sapiens_bc, bins=50, log=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bd7d012",
   "metadata": {},
   "source": [
    "Let's see which of the proteins in Homo Sapiens have the highest BC:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "ba99d009",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('9606.ENSP00000479618', 418310.1),\n",
       " ('9606.ENSP00000295897', 440084.25),\n",
       " ('9606.ENSP00000366488', 470096.22),\n",
       " ('9606.ENSP00000359719', 530835.1),\n",
       " ('9606.ENSP00000298910', 793801.9),\n",
       " ('9606.ENSP00000309591', 539960.0),\n",
       " ('9606.ENSP00000349960', 722263.7),\n",
       " ('9606.ENSP00000229239', 982701.5),\n",
       " ('9606.ENSP00000451828', 489310.28),\n",
       " ('9606.ENSP00000269305', 550784.4)]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "k = 10\n",
    "\n",
    "highest_BC_indices = np.argpartition(homo_sapiens_bc, -k)[-k:]\n",
    "\n",
    "[\n",
    "    (\n",
    "        homo_sapiens.get_node_name_from_node_id(node_id),\n",
    "        homo_sapiens_bc[node_id]\n",
    "    )\n",
    "    for node_id in highest_BC_indices\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "7aedf47e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(20199, 8591130, 5.0)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(doggo.get_number_of_nodes(), doggo.get_number_of_directed_edges(), doggo.get_diameter())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "4d70000a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 26min 17s, sys: 1min 20s, total: 27min 37s\n",
      "Wall time: 1min 33s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "doggo_bc = doggo.get_betweenness_centrality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "ce5385b7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEFCAYAAAAYKqc0AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/NK7nSAAAACXBIWXMAAAsTAAALEwEAmpwYAAAQbklEQVR4nO3df6zdd13H8eeLzo0wtG50RLKttLNlWPAHcDMUCQJiaBmlCIptMGFYV4eWf4zEkhlj/Mf5l5FYJA0sw0Q7ylTSuuJAYamBDXZHBluZg1KGa2Ns2aBkahjDt3+cb+Fwubf93p5z7rn97PlIbnrO5/vrfT89efXbz/d7Pt9UFZKktjxt2gVIksbPcJekBhnuktQgw12SGmS4S1KDLph2AQCrVq2qNWvWTLsMSTqv3HvvvV+vqsvmWzbVcE+yGdi8bt06Zmdnp1mKJJ13knxtoWVTHZapqgNVtWPlypXTLEOSmuOYuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWrQVMM9yeYke06dOjXNMiSpOVP9ElNVHQAOzMzMXH+u+1iz6/Z52x++6dpz3aUknfcclpGkBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAZNJNyTXJxkNsnrJ7F/SdKZ9Qr3JDcnOZHkgTntG5M8lORIkl1Di/4Q2DfOQiVJ/fU9c78F2DjckGQFsBvYBGwAtiXZkORXgC8CJ8ZYpyRpEXpNHFZVh5KsmdN8DXCkqo4CJLkV2AI8E7iYQeD/b5KDVfV/c/eZZAewA2D16tXn/AtIkn7YKLNCXg48MvT+GPDSqtoJkOQ64OvzBTtAVe0B9gDMzMzUCHVIkuaY2JS/VXXL2dZJshnYvG7dukmVIUlPSaPcLXMcuHLo/RVdW29VdaCqdqxcuXKEMiRJc40S7vcA65OsTXIhsBXYP56yJEmj6Hsr5F7gLuDqJMeSbK+qJ4GdwB3Ag8C+qjq8mIP7mD1Jmoy+d8tsW6D9IHDwXA8+jsfsSZJ+mA/IlqQGTTXcvaAqSZPhxGGS1CDDXZIa5Ji7JDXIMXdJapDDMpLUIIdlJKlBDstIUoMclpGkBhnuktQgw12SGuQFVUlqkBdUJalBDstIUoMMd0lqkOEuSQ3ygqokNcgLqpLUIIdlJKlBhrskNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkF9ikqQG+SUmSWqQwzKS1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBo093JP8VJL3JbktyTvGvX9J0tn1CvckNyc5keSBOe0bkzyU5EiSXQBV9WBV3QC8BfjF8ZcsSTqbvmfutwAbhxuSrAB2A5uADcC2JBu6ZW8AbgcOjq1SSVJvvcK9qg4Bj81pvgY4UlVHq+oJ4FZgS7f+/qraBLx1oX0m2ZFkNsnsyZMnz616SdK8Lhhh28uBR4beHwNemuSVwJuAizjDmXtV7QH2AMzMzNQIdUiS5hgl3OdVVXcCd457v5Kk/ka5W+Y4cOXQ+yu6tt6cz12SJmOUcL8HWJ9kbZILga3A/sXswPncJWky+t4KuRe4C7g6ybEk26vqSWAncAfwILCvqg4v5uCeuUvSZKRq+tcyZ2ZmanZ29py2XbPr9kWt//BN157TcSRpuUlyb1XNzLfM6QckqUE+IFuSGuQDsiWpQQ7LSFKDHJaRpAY5LCNJDXJYRpIa5LCMJDXIYRlJapDDMpLUIMNdkhpkuEtSg7ygKkkN8oKqJDXIYRlJapDhLkkNMtwlqUGGuyQ1yLtlJKlB3i0jSQ1yWEaSGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yPvcJalB3ucuSQ1yWEaSGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAZdMO0CltqaXbcvuOzhm65dwkokaXImEu5J3ghcC/wY8IGq+tgkjiNJml/vYZkkNyc5keSBOe0bkzyU5EiSXQBV9ZGquh64AfiN8ZYsSTqbxYy53wJsHG5IsgLYDWwCNgDbkmwYWuWPuuWSpCXUO9yr6hDw2Jzma4AjVXW0qp4AbgW2ZODPgY9W1efGV64kqY9R75a5HHhk6P2xru2dwGuAX0tyw3wbJtmRZDbJ7MmTJ0csQ5I0bCIXVKvqPcB7zrLOHmAPwMzMTE2iDkl6qhr1zP04cOXQ+yu6tl6cz12SJmPUcL8HWJ9kbZILga3A/r4bO5+7JE3GYm6F3AvcBVyd5FiS7VX1JLATuAN4ENhXVYcXsU/P3CVpAnqPuVfVtgXaDwIHz+XgVXUAODAzM3P9uWwvSZqfc8tIUoN8QLYkNcgHZEtSgxyWkaQGOSwjSQ1yWEaSGuSwjCQ1yHCXpAY55i5JDZrqM1SX2zdUF3q+qs9WlXS+cVhGkhpkuEtSgxxzl6QGeZ+7JDXIYRlJapDhLkkNMtwlqUGGuyQ1yLtlJKlB3i0jSQ1yWEaSGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yPvcJalB3ucuSQ1yWEaSGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUoAumXcD5YM2u2+dtf/ima5e4EknqZ+xn7kmuSvKBJLeNe9+SpH56nbknuRl4PXCiql441L4R+EtgBfD+qrqpqo4C258K4e4ZvaTlqu+Z+y3AxuGGJCuA3cAmYAOwLcmGsVYnSTonvcK9qg4Bj81pvgY4UlVHq+oJ4FZgS98DJ9mRZDbJ7MmTJ3sXLEk6u1HG3C8HHhl6fwy4PMmzkrwPeFGSdy+0cVXtqaqZqpq57LLLRihDkjTX2O+WqapHgRv6rJtkM7B53bp14y5Dkp7SRjlzPw5cOfT+iq6tN+dzl6TJGCXc7wHWJ1mb5EJgK7B/MTvwSUySNBm9wj3JXuAu4Ookx5Jsr6ongZ3AHcCDwL6qOryYg3vmLkmT0WvMvaq2LdB+EDg41ookSSPzAdmS1CAfkC1JDXJWSElqkMMyktQgh2UkqUEOy0hSgwx3SWqQY+6S1CDH3CWpQQ7LSFKDDHdJatDY53NfjFbnc/fZqpKmzTF3SWqQwzKS1CDDXZIaZLhLUoMMd0lqkHfLLGOLvevGu3QknebdMpLUIIdlJKlBhrskNchwl6QGGe6S1CDDXZIaZLhLUoO8z30JLXQfuqT2LfX3ULzPXZIa5LCMJDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1aOzTDyS5GHgv8ARwZ1X97biPIUk6s15n7kluTnIiyQNz2jcmeSjJkSS7uuY3AbdV1fXAG8ZcrySph77DMrcAG4cbkqwAdgObgA3AtiQbgCuAR7rVvjueMiVJi9FrWKaqDiVZM6f5GuBIVR0FSHIrsAU4xiDg7+MM/3gk2QHsAFi9evVi69YijHM2uknPbLfY/Y+rnqWesW8U1rp0+z+fjXJB9XK+f4YOg1C/HPgH4M1J/ho4sNDGVbWnqmaqauayyy4boQxJ0lxjv6BaVf8NvL3Puk+1+dwlaamMcuZ+HLhy6P0VXVtvzucuSZMxSrjfA6xPsjbJhcBWYP9idpBkc5I9p06dGqEMSdJcfW+F3AvcBVyd5FiS7VX1JLATuAN4ENhXVYcXc3DP3CVpMvreLbNtgfaDwMGxViRJGtlUpx9wWEaSJsMHZEtSg5w4TJIalKqadg0kOQl87Rw3XwV8fYzlTNL5VCucX/Va62RY62SMq9bnVtW83wJdFuE+iiSzVTUz7Tr6OJ9qhfOrXmudDGudjKWo1WEZSWqQ4S5JDWoh3PdMu4BFOJ9qhfOrXmudDGudjInXet6PuUuSflgLZ+6SpDkMd0lq0LIO9wWe0Tq8/KIkH+qWf2b4aVFJ3t21P5Tktcug1t9P8sUkX0jyr0meO7Tsu0nu634WNbPmhGq9LsnJoZp+e2jZ25J8uft52zKo9S+G6vxSkm8OLVvqfp33WcNDy5PkPd3v8oUkLx5attT9erZa39rVeH+STyf52aFlD3ft9yWZXQa1vjLJqaG/6z8eWnbGz88Uan3XUJ0PdJ/RS7tl4+3XqlqWP8AK4CvAVcCFwOeBDXPW+V3gfd3rrcCHutcbuvUvAtZ2+1kx5VpfBTyje/2O07V27x9fZv16HfBX82x7KXC0+/OS7vUl06x1zvrvBG6eRr92x3sF8GLggQWWvw74KBDg54HPTKNfe9b6stM1MHhO8meGlj0MrFpG/fpK4J9G/fwsRa1z1t0MfGJS/bqcz9y/94zWqnoCOP2M1mFbgA92r28DfjlJuvZbq+rbVfVV4Ei3v6nVWlWfrKr/6d7ezeDhJtPQp18X8lrg41X1WFV9A/g4cx6cPmaLrXUbsHeC9ZxRVR0CHjvDKluAv6mBu4EfT/Iclr5fz1prVX26qwWm+3nt068LGeWzfk4WWetEP6/LOdwXekbrvOvUYH75U8Czem47Tos93nYGZ3CnPT3JbJK7k7xxAvUN61vrm7v/lt+W5PQTt5Ztv3bDXGuBTww1L2W/9rHQ77PU/bpYcz+vBXwsyb0ZPOh+OfiFJJ9P8tEkL+jalm2/JnkGg3/A/36oeaz9OvZnqOrMkvwmMAP80lDzc6vqeJKrgE8kub+qvjKdCoHBg833VtW3k/wOg/8dvXqK9fSxFbitqr471Lbc+vW8k+RVDML95UPNL+/69dnAx5P8e3fGOi2fY/B3/XiS1wEfAdZPsZ4+NgOfqqrhs/yx9utyPnPv84zW762T5AJgJfBoz23HqdfxkrwGuBF4Q1V9+3R7VR3v/jwK3Am8aJq1VtWjQ/W9H3hJ323HbDHH28qc/+Iucb/2sdDvs9T92kuSn2Hw97+lqh493T7UryeAf2SyQ55nVVXfqqrHu9cHgR9Jsopl2q+dM31ex9Ovk7y4MOKFiQsYXFhay/cvhrxgzjq/xw9eUN3XvX4BP3hB9SiTvaDap9YXMbi4s35O+yXARd3rVcCXmeBFn561Pmfo9a8Cd3evLwW+2tV8Sff60mnW2q33fAYXozKtfh067hoWvvB3LT94QfWz0+jXnrWuZnCt6mVz2i8GfnTo9aeBjVOu9SdO/90zCMT/6Pq41+dnKWvtlq9kMC5/8ST7daK/5Bg66XXAl7pQvLFr+1MGZ74ATwc+3H0IPwtcNbTtjd12DwGblkGt/wL8F3Bf97O/a38ZcH/3wbsf2L4Mav0z4HBX0yeB5w9t+1tdfx8B3j7tWrv3fwLcNGe7afTrXuA/ge8wGN/dDtwA3NAtD7C7+13uB2am2K9nq/X9wDeGPq+zXftVXZ9+vvuM3LgMat059Hm9m6F/kOb7/Eyz1m6d6xjc8DG83dj71ekHJKlBy3nMXZJ0jgx3SWqQ4S5JDTLcJalBhrskLbGzTTA2z/pvyWDiwcNJ/q7XNt4tI0lLK8krgMcZzDX0wrOsux7YB7y6qr6R5Nk1+KLTGXnmLklLrOaZYCzJTyb5525umX9L8vxu0fXA7uomcusT7GC4S9JysQd4Z1W9BPgD4L1d+/OA5yX5VDcJXq8ZQ504TJKmLMkzGXyr+sODWcuBwfQpMMjp9Qzmrb8COJTkp6vqm2fap+EuSdP3NOCbVfVz8yw7xuBhKd8BvprkSwzC/p6z7VCSNEVV9S0Gwf3r8L1HMp5+tOFHGJy10812+TwGE6KdkeEuSUssyV7gLuDqJMeSbAfeCmxPcnrysNNPjboDeDTJFxlM5PeuGpqCecFjeCukJLXHM3dJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhr0//uqabe9/y3JAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.hist(doggo_bc, bins=50, log=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "49bf9b6f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('9615.ENSCAFP00000064590', 454357.72),\n",
       " ('9615.ENSCAFP00000013612', 560359.7),\n",
       " ('9615.ENSCAFP00000017324', 679915.0),\n",
       " ('9615.ENSCAFP00000053739', 760963.6),\n",
       " ('9615.ENSCAFP00000029000', 857573.3),\n",
       " ('9615.ENSCAFP00000053880', 1753843.1),\n",
       " ('9615.ENSCAFP00000053738', 1368979.5),\n",
       " ('9615.ENSCAFP00000056636', 1104915.4),\n",
       " ('9615.ENSCAFP00000030135', 1762596.6),\n",
       " ('9615.ENSCAFP00000028342', 1512874.1)]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "k = 10\n",
    "\n",
    "highest_BC_indices = np.argpartition(doggo_bc, -k)[-k:]\n",
    "\n",
    "[\n",
    "    (\n",
    "        doggo.get_node_name_from_node_id(node_id),\n",
    "        doggo_bc[node_id]\n",
    "    )\n",
    "    for node_id in highest_BC_indices\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "b131413d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(22048, 14496358, 7.0)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(mouse.get_number_of_nodes(), mouse.get_number_of_directed_edges(), mouse.get_diameter())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "1414a60a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 43min 16s, sys: 1min 58s, total: 45min 15s\n",
      "Wall time: 2min 31s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "mouse_bc = mouse.get_betweenness_centrality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "00e59943",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEFCAYAAAAYKqc0AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/NK7nSAAAACXBIWXMAAAsTAAALEwEAmpwYAAAOwUlEQVR4nO3dbYxc113H8e+vzsOLFIJUG1H5gU2xYzCF0nTlFipVEQ+SXdcxKqHYqoBUJlaKUuAFCIMQSLwyb5AIuERWawVQSWpCFdlkQ0CikRFyozhRUuJYqYybKhtVspO0LoWKYPjzYifJstn13tmZ2fGe/X4kKzNn7tz5n73OLzdnzp6TqkKS1Ja3jbsASdLwGe6S1CDDXZIaZLhLUoMMd0lq0DXjLgBg7dq1NTExMe4yJGlFefLJJ1+uqnXzvXZVhPvExASnT58edxmStKIk+dpCrzksI0kNGmu4J9md5MilS5fGWYYkNWes4V5VJ6rqwI033jjOMiSpOQ7LSFKDDHdJapDhLkkNMtwlqUGGuyQ16Kr4JaZBTBx8eN72Fw7tWuZKJOnq4Tx3SWqQ89wlqUGOuUtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGGe6S1CDDXZIaZLhLUoNGEu5JbkhyOslHRnF+SdKVdQr3JEeTXEjy7Jz2HUmeT3IuycFZL/02cGyYhUqSuut6534fsGN2Q5I1wGFgJ7AN2JdkW5KfAZ4DLgyxTklSHzot+VtVJ5NMzGneDpyrqvMASR4A9gBvB25gJvC/k2Sqqv537jmTHAAOAGzatGnJHZAkvdUg67mvB16c9XwaeH9V3Q2Q5A7g5fmCHaCqjgBHACYnJ2uAOiRJc4xss46qum+xY5LsBnZv3rx5VGVI0qo0yGyZl4CNs55v6LV15nrukjQag4T7E8CWJDcluQ7YCxwfTlmSpEF0nQp5P3AK2JpkOsn+qroM3A08CpwFjlXVmX4+3G32JGk0us6W2bdA+xQwtdQPr6oTwInJyck7l3oOSdJbuUG2JDXIDbIlqUEuHCZJDXJYRpIa5LCMJDXIYRlJapDhLkkNcsxdkhrkmLskNchhGUlqkOEuSQ1yzF2SGuSYuyQ1yGEZSWqQ4S5JDTLcJalBhrskNcjZMpLUIGfLSFKDHJaRpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDXKeuyQ1yHnuktQgh2UkqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDTLcJalBQw/3JD+U5N4kDyb55LDPL0laXKdwT3I0yYUkz85p35Hk+STnkhwEqKqzVXUX8DHgg8MvWZK0mK537vcBO2Y3JFkDHAZ2AtuAfUm29V67DXgYmBpapZKkzjqFe1WdBF6d07wdOFdV56vqNeABYE/v+ONVtRP4+ELnTHIgyekkpy9evLi06iVJ87pmgPeuB16c9XwaeH+SW4GPAtdzhTv3qjoCHAGYnJysAeqQJM0xSLjPq6oeAx7rcmyS3cDuzZs3D7sMSVrVBpkt8xKwcdbzDb22zlzPXZJGY5BwfwLYkuSmJNcBe4Hj/ZzAnZgkaTS6ToW8HzgFbE0ynWR/VV0G7gYeBc4Cx6rqTD8f7p27JI1GpzH3qtq3QPsUTneUpKuOG2RLUoPcIFuSGuTCYZLUoKHPc+/HKOe5Txx8eN72Fw7tGvpnSdLVxmEZSWqQwzKS1CDDXZIa5FRISWqQY+6S1CCHZSSpQYa7JDXIMXdJapBj7pLUIIdlJKlBhrskNchwl6QGGe6S1CBny0hSg5wtI0kNclhGkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNch57pLUIOe5S1KDHJaRpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNeiaUZw0yc8Cu4DvBj5bVf8wis9ZiomDDy/42guHdi1jJZI0Op3v3JMcTXIhybNz2nckeT7JuSQHAarqoaq6E7gL+IXhlixJWkw/wzL3ATtmNyRZAxwGdgLbgH1Jts065Pd6r0uSllHncK+qk8Crc5q3A+eq6nxVvQY8AOzJjD8CHqmqp4ZXriSpi0G/UF0PvDjr+XSv7VPATwO3J7lrvjcmOZDkdJLTFy9eHLAMSdJsI/lCtaruAe5Z5JgjwBGAycnJGkUdkrRaDXrn/hKwcdbzDb22TlzPXZJGY9BwfwLYkuSmJNcBe4HjXd/seu6SNBr9TIW8HzgFbE0ynWR/VV0G7gYeBc4Cx6rqTB/n9M5dkkag85h7Ve1boH0KmFrKh1fVCeDE5OTknUt5vyRpfi4/IEkNcoNsSWqQG2RLUoMclpGkBjksI0kNclhGkhrksIwkNchhGUlqkMMyktQgh2UkqUGGuyQ1yHCXpAb5haokNWgkOzF1dbWtCjlx8OF52184tGuZK5GkwTgsI0kNMtwlqUGGuyQ1yC9UJalB/oaqJDXIYRlJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIOe5S1KDnOcuSQ1yWEaSGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkho09HBP8q4kn03y4LDPLUnq5pouByU5CnwEuFBV757VvgP4E2AN8JmqOlRV54H9qyHcJw4+PG/7C4d2LXMlkvT/db1zvw/YMbshyRrgMLAT2AbsS7JtqNVJkpak0517VZ1MMjGneTtwrnenTpIHgD3Ac13OmeQAcABg06ZNXesdi4Xu0CXpajXImPt64MVZz6eB9UnekeRe4L1JfmehN1fVkaqarKrJdevWDVCGJGmuTnfu/aiqV4C7uhybZDewe/PmzcMuQ5JWtUHu3F8CNs56vqHX1pnruUvSaAwS7k8AW5LclOQ6YC9wfDhlSZIG0Snck9wPnAK2JplOsr+qLgN3A48CZ4FjVXWmnw93mz1JGo2us2X2LdA+BUwt9cOr6gRwYnJy8s6lnkOS9FZD/0K1H61+oeovN0kaNzfIlqQGuXCYJDVorOHuF6qSNBoOy0hSgxyWkaQGGe6S1CDH3CWpQY65S1KDHJaRpAYZ7pLUIMfcJalBjrlLUoMclpGkBhnuktQgw12SGmS4S1KD3KzjKrCSNvdYSbVKq5mzZSSpQQ7LSFKDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAY5z30ZLTRHfNTndw764vzZqTXOc5ekBjksI0kNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDRr68gNJbgA+DbwGPFZVnxv2Z0iSrqzTnXuSo0kuJHl2TvuOJM8nOZfkYK/5o8CDVXUncNuQ65UkddB1WOY+YMfshiRrgMPATmAbsC/JNmAD8GLvsP8ZTpmSpH50GpapqpNJJuY0bwfOVdV5gCQPAHuAaWYC/mmu8B+PJAeAAwCbNm3qt271od/VKJeyEqKrKi6ffn/Wo742V/r71e9nrJS/R0upc7n7NsgXqut58w4dZkJ9PfAF4OeS/DlwYqE3V9WRqpqsqsl169YNUIYkaa6hf6FaVf8BfKLLsattPXdJWi6D3Lm/BGyc9XxDr60z13OXpNEYJNyfALYkuSnJdcBe4Hg/J0iyO8mRS5cuDVCGJGmurlMh7wdOAVuTTCfZX1WXgbuBR4GzwLGqOtPPh3vnLkmj0XW2zL4F2qeAqaFWJEka2FiXH3BYRpJGww2yJalBLhwmSQ1KVY27BpJcBL62xLevBV4eYjkryWrt+2rtN6zevtvv+X1/Vc37W6BXRbgPIsnpqpocdx3jsFr7vlr7Dau37/a7fw7LSFKDDHdJalAL4X5k3AWM0Wrt+2rtN6zevtvvPq34MXdJ0lu1cOcuSZrDcJekBq2YcF9gv9bZr1+f5PO91x+fZ+eoFalDv+9IcjHJ070/vzKOOodtoX17Z72eJPf0fi5fTnLLctc4Kh36fmuSS7Ou+e8vd42jkGRjki8meS7JmSS/Ps8xzV33jv3u/5pX1VX/B1gD/BvwLuA64Blg25xjfhW4t/d4L/D5cde9TP2+A/izcdc6gr5/CLgFeHaB1z8MPAIE+ADw+LhrXsa+3wr83bjrHEG/3wnc0nv8XcBX5vn73tx179jvvq/5Srlzf2O/1qp6DXh9v9bZ9gB/0Xv8IPBTSbKMNY5Cl343qapOAq9e4ZA9wF/WjC8B35PknctT3Wh16HuTqurrVfVU7/G/M7OU+Po5hzV33Tv2u28rJdwX2q913mNqZq35S8A7lqW60enSb5jZs/bLSR5MsnGe11vU9WfTqh9P8kySR5L88LiLGbbesOp7gcfnvNT0db9Cv6HPa75Swl0LOwFMVNWPAv/Im//3onY9xcyaIu8B/hR4aLzlDFeStwN/C/xGVX1r3PUsl0X63fc1Xynh3mW/1jeOSXINcCPwyrJUNzqL9ruqXqmq/+o9/QzwvmWqbdwG3sN3paqqb1XVt3uPp4Brk6wdc1lDkeRaZgLuc1X1hXkOafK6L9bvpVzzlRLuXfZrPQ78cu/x7cA/Ve+biBVs0X7PGW+8jZnxutXgOPBLvdkTHwAuVdXXx13Uckjyfa9/n5RkOzP/Hq/0Gxl6ffoscLaq/niBw5q77l36vZRr3mmbvXGrqstJXt+vdQ1wtKrOJPlD4HRVHWfmh/NXSc4x82XU3vFVPBwd+/1rSW4DLjPT7zvGVvAQZWbf3luBtUmmgT8ArgWoqnuZ2d7xw8A54D+BT4yn0uHr0PfbgU8muQx8B9jbwI0MwAeBXwT+NcnTvbbfBTZB09e9S7/7vuYuPyBJDVopwzKSpD4Y7pLUIMNdkhpkuEtSgwx3SVpmiy0ON8/xH5u1sNhfd3qPs2UkaXkl+RDwbWbWyXn3IsduAY4BP1lV30jyvVV1YbHP8M5dkpbZfIvDJfmBJH+f5Mkk/5zkB3sv3Qkcrqpv9N67aLCD4S5JV4sjwKeq6n3AbwKf7rXfDNyc5F+SfCnJji4nWxG/oSpJLestGvYTwN/MWqn8+t4/rwG2MPNbyxuAk0l+pKq+eaVzGu6SNH5vA75ZVT82z2vTzGxK8t/AV5N8hZmwf2KxE0qSxqi3xO9Xk/w8vLGd4Ht6Lz/EzF07vZUgbwbOL3ZOw12SlllvcbhTwNYk00n2Ax8H9id5BjjDm7uuPQq8kuQ54IvAb1XVoquAOhVSkhrknbskNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ36P7dCAEOc3TsGAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.hist(mouse_bc, bins=50, log=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "ee4d8305",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('10090.ENSMUSP00000025791', 779730.94),\n",
       " ('10090.ENSMUSP00000098066', 808166.94),\n",
       " ('10090.ENSMUSP00000132924', 1171116.9),\n",
       " ('10090.ENSMUSP00000126567', 1206059.6),\n",
       " ('10090.ENSMUSP00000104208', 1640575.1),\n",
       " ('10090.ENSMUSP00000030940', 1978887.8),\n",
       " ('10090.ENSMUSP00000095866', 1521925.5),\n",
       " ('10090.ENSMUSP00000025402', 1847888.2),\n",
       " ('10090.ENSMUSP00000005164', 2436964.8),\n",
       " ('10090.ENSMUSP00000005606', 2299003.8)]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "k = 10\n",
    "\n",
    "highest_BC_indices = np.argpartition(mouse_bc, -k)[-k:]\n",
    "\n",
    "[\n",
    "    (\n",
    "        mouse.get_node_name_from_node_id(node_id),\n",
    "        mouse_bc[node_id]\n",
    "    )\n",
    "    for node_id in highest_BC_indices\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5fefe06f",
   "metadata": {},
   "source": [
    "## Conclusions\n",
    "In conclusion, we have explored the parallel betweenness centrality algorithm as described in Madduri's paper and implemented by GRAPE. We have seen how the algorithm uses `lock-free` data structures and atomic instructions to avoid race conditions and ensure parallelism. We have also discussed the performance trade-offs between different atomic instructions and how to optimize them for specific graph topologies. Finally, we have executed the algorithm on six different graphs, including citation graphs and protein-protein interaction graphs, and plotted the BC scores as histograms. Overall, the results showed that the parallel betweenness centrality algorithm is discretely efficient and relatively scalable. We hope that this tutorial has provided a useful introduction to parallel betweenness centrality and has inspired further exploration of parallel graph algorithms.\n",
    "\n",
    "*Do you have any idea on how to further improve the algorithm performance?*"
   ]
  }
 ],
 "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
}