Vertix_Brandes.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "def brandes(V, A):\n",
    "    \"Compute betweenness centrality in an unweighted graph.\"\n",
    "    # Brandes algorithm\n",
    "    # see http://www.cs.ucc.ie/~rb4/resources/Brandes.pdf\n",
    "    C = dict((v,0) for v in V)\n",
    "    for s in V:\n",
    "        S = []\n",
    "        P = dict((w,[]) for w in V)\n",
    "        g = dict((t, 0) for t in V); g[s] = 1\n",
    "        d = dict((t,-1) for t in V); d[s] = 0\n",
    "        Q = deque([])\n",
    "        Q.append(s)\n",
    "        while Q:\n",
    "            v = Q.popleft()\n",
    "            S.append(v)\n",
    "            for w in A[v]:\n",
    "                if d[w] < 0:\n",
    "                    Q.append(w)\n",
    "                    d[w] = d[v] + 1\n",
    "                if d[w] == d[v] + 1:\n",
    "                    g[w] = g[w] + g[v]\n",
    "                    P[w].append(v)\n",
    "        e = dict((v, 0) for v in V)\n",
    "        while S:\n",
    "            # print(s)\n",
    "            w = S.pop()\n",
    "            for v in P[w]:\n",
    "                e[v] = e[v] + ((g[v]/g[w]) * (1 + e[w]))\n",
    "            if w != s:\n",
    "                # print(w, e[w])\n",
    "                C[w] = C[w] + e[w]\n",
    "            \n",
    "            # print(C)\n",
    "        # print(\"___\")\n",
    "    # reduce C/2 to get the centrality\n",
    "    for v in V:\n",
    "        C[v] = C[v] / 2\n",
    "    return C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "# G=nx.gnp_random_graph(4,0.3)\n",
    "G=nx.Graph()\n",
    "G.add_nodes_from(range(6))\n",
    "G.add_edge(0,1)\n",
    "G.add_edge(0,2)\n",
    "G.add_edge(1,2)\n",
    "G.add_edge(2,3)\n",
    "G.add_edge(3,4)\n",
    "G.add_edge(3,5)\n",
    "G.add_edge(4,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAqxUlEQVR4nO3deXhU9b0/8PdsySSEkIWEAJkEIZAUKlSCEMErIAkoGEINS0TgXmKZoWBt/YHtrdjnWtFaqa1SBWUABQIiBUlZEsgCJOhFFgGBeyEgalayh5B1kszM+f3BTWrMwpKZOTPnvF/P0+eJMydnPoE+efP5bkchCIIAIiIimVCKXQAREZEjMfiIiEhWGHxERCQrDD4iIpIVBh8REckKg4+IiGSFwUdERLLC4CMiIllh8BERkaww+IiISFYYfEREJCsMPiIikhUGHxERyQqDj4iIZIXBR0REssLgIyIiWWHwERGRrDD4iIhIVhh8REQkKww+IiKSFQYfERHJCoOPiIhkRS12AUREZB8VdU3Yc7YQOSU1qDGZ4a1VIyLIG3Mig+Hv5S52eaJRCIIgiF0EERHZzoWCaqzLuo7sa+UAgCazte09rVoJAcCk8AAsmxiGUTofcYoUEYOPiEhCtp/MxRupOTCZLejut7tCAWjVKqyaHoEFUYMcVp8z4FAnEZFE3A69K2hssd7xWkEAGlsseCP1CgDIKvzY8RERScCFgmokbDyJxhZLu9ctjbWoTF0LU+55KD284Tvx39FrxKR213hoVNilj8LIYB/HFSwiruokIpKAdVnXYTJbOrxelf4BFCoNgn+1HX1jV6IyfT2ay/PaXWMyW7A+67qjShUdg4+IyMVV1DUh+1p5hzk9a7MJDVdPwOexBVC6eUCrGwHPsHGo/99j7a4TBODY1XJU1jU5sGrxMPiIiFzcnrOFnb5uriqCQqmCxm9g22uawAfQ8qOODwAUAPac6/w+UsPgIyJycTklNe22LLSytjRC4e7R7jWluyeszY0drjWZrcgprrVbjc6EwUdE5OJqTOZOX1dqPCA0tQ85oakBSjePTq+vMbXYvDZnxOAjInJx3trOd6ap/QZCsFrQUlXU9lpz2ffQBIR2cR+NXepzNgw+IiIXFxHkDXd1x1/nSjctPMMfQfXnO2BtNsFUeBkN10+h14jJHa7VqpWI6N/bEeWKjsFHROTiZkcGd/me39RlEMzNKHzvWVTs/wv8py6DWycdnwBg9uiu7yMlPLmFiMjF9fVyx8RhAci4UtphS4PKozcC41/p9vsVCmByeIBsDq5mx0dEJAHLJ4XBXXV/v9K1ahWWTQqzcUXOi8FHRCQBD/RRQv0/+6ESOp7e0h0PjRKrpkfI5rgygMFHROTyGhoa8NRTT+HfgoBX40bCQ6OCQtH99ygUt8/oXDX9J7I6oBrgIdVERC6tqakJcXFxCAwMxJYtW6BUKnGxsBrrs67j2NVyKHB7c3orpdUMjZsbJocHYNmkMFl1eq0YfERELspsNmPu3LlQKBTYtWsX1Or26xUr65qw51whcoprUWNqgbmxFv+dshundr4rm4UsnWHwERG5IKvVikWLFqGyshL//Oc/4e5+5yAzm83w8fFBUVER+vTp44AqnRPn+IiIXIwgCFi2bBkKCgrw2Wef3VXoAYBarcbo0aNx5swZO1fo3Bh8REQuRBAErFy5EufOncOBAwfg6el5T98/btw4nDp1yk7VuQYGHxGRC/njH/+IjIwMHD58GN7e3vf8/ePGjcPJkyftUJnrYPAREbmIt99+Gzt37kRGRgb8/Pzu6x6tHZ+cl3cw+IiIXMCHH36IdevWITMzE/369bvv+wQHB0OtViM3N9d2xbkYBh8RkZNLSkrC66+/jszMTOh0uh7dS6FQyH6ej8FHROTE9u7di5deegnp6ekYMmSITe7J4CMiIqd0+PBhLF26FKmpqRg+fLjN7hsVFSXr4OMGdiIiJ5SdnY3Zs2dj3759GD9+vE3vXVdXh6CgIFRVVcHNzc2m93YF7PiIiJzM6dOnMWfOHHz66ac2Dz0A8PLywuDBg3Hx4kWb39sVMPiIiJzIxYsXERsbi82bN2PKlCl2+xw57+dj8BEROYmrV6/iiSeewN///nfExsba9bPkvMCFwUdE5ARyc3MRExOD119/HfPmzbP758k5+Li4hYhIZDdu3MBjjz2GX//61/jVr37lkM+0WCzw9fVFbm7ufZ8C46rY8RERiai8vBwxMTF47rnnHBZ6AKBSqRAZGYnTp0877DOdBYOPiEgk1dXVmDZtGuLi4vD73//e4Z8v1/18DD4iIhHU1dVhxowZePTRR/HGG2+IUoNc5/k4x0dE5GAmkwkzZsxAaGgoNm3aBKVSnB6kuLgYP/3pT1FRUQGFQiFKDWJgx0dE5EAtLS2YM2cOAgICsHHjRtFCDwD69++PXr164fr166LVIAYGHxGRg1gsFixcuBDA7ScuqFQqkSuS53Ang4+IyAGsViuWLFmC8vJy7N69GxqNRuySADD4iIjIDgRBwG9+8xtcvXoV+/btg1arFbukNnIMPi5uISKys1WrVuHQoUM4evQofHx8xC6nnYaGBgQEBKCystKpAtme2PEREdnRm2++ieTkZKSlpTld6AGAp6cnwsPD8fXXX4tdisMw+IiI7OS9997D5s2bkZmZiYCAALHL6ZLcntTA4CMisoOPPvoIf/nLX5CZmYkBAwaIXU635DbPx+AjIrKxXbt24ZVXXkFGRgYGDRokdjl3JLfg4+IWIiIbOnDgAH7xi18gIyMDI0eOFLucu2K1WuHn54dvvvnGqYdkbYUdHxGRjRw5cgTPPfccDhw44DKhBwBKpRIPP/ywbLo+Bh8RkQ2cOHECCQkJ2L17N8aOHSt2OfdMTsOdDD4ioh46d+4cZs2ahaSkJEycOFHscu6LnIKPc3xERD1w+fJlTJkyBevWrcPTTz8tdjn3raysDMOGDUNVVZWoB2c7grR/OiIiO/r2228xdepUrFmzxqVDDwACAwPh5+eHq1evil2K3TH4iIjuQ0FBAaKjo/HKK6+0PXHB1clluJPBR0R0j0pLSxEdHY3ly5dj6dKlYpdjMww+IiLqoKqqClOnTsUzzzyDlStXil2OTckl+Li4hYjoLtXW1iI6OhqPPvoo3n77bSgUCrFLsimTyQR/f3+Ul5fD09NT7HLshh0fEdFdaGhowFNPPYWHHnpIkqEHAFqtFsOHD8e5c+fELsWuGHxERHfQ1NSE+Ph46HQ6rF+/XpKh1yoqKkryw50MPiKibpjNZsyfPx8eHh7YsmWL5Pe4yeERRdL+GyQi6gGr1YrExETU19dj586dUKvVYpdkd3JY4MLgIyLqhCAIWL58OXJzc7F37164u7uLXZJDhIWFob6+HsXFxWKXYjcMPiKiHxEEAb/97W9x9uxZHDx4UNIrHH9MoVBg7Nixku76GHxERD+yevVqpKWl4fDhw/D29ha7HIeT+nAng4+I6Af+9re/Yfv27cjIyICfn5/Y5YhC6sHHDexERP/HaDTizTffxPHjx6HT6cQuRzSVlZV44IEHcPPmTahUKrHLsTl2fEREAHbs2IHXXnsNGRkZsg49APD390dQUBAuX74sdil2weAjItlLTk7GihUrkJaWhrCwMLHLcQpSHu5k8BGRrKWlpcFgMCA1NRUjRowQuxynweAjIpKg48ePY8GCBUhOTsbo0aPFLsepSDn4uLiFiGTpzJkzmDFjBj755BNER0eLXY7TaW5uhq+vL0pLS+Hl5SV2OTbFjo+IZOfSpUuIjY3F5s2bGXpdcHNzw8iRI/HVV1+JXYrNMfiISFauXbuGJ554Au+++y5iY2PFLsepSXW4k8FHRLKRl5eHmJgYrF69GgkJCWKX4/Sk+qQGBh8RyUJxcTGmTJmCFStWIDExUexyXELrs/mkthSEwUdEkldRUYHo6GgkJibihRdeELsclzFo0CCYzWYUFhaKXYpNMfiISNJu3bqFadOmYebMmXj55ZfFLselKBQKSc7zMfiISLLq6+sxY8YMjB8/Hn/605/ELsclMfiIiFyEyWTCrFmzMHToUKxduxYKhULsklySFIOPG9iJSHJaWloQHx8PDw8PfPLJJ5J8woCjVFdXIzg4GNXV1VCr1WKXYxPs+IhIUiwWCxYtWgSr1YqkpCSGXg/5+PhAp9Ph0qVLYpdiMww+IpIMq9UKg8GA0tJS7N69G25ubmKXJAlSG+5k8BGRJAiCgBdffBGXL1/G/v374eHhIXZJktG6n08qGHxEJAl/+MMfcPz4caSmpkruUGWxSa3j4+IWInJ5b731FrZu3Yrs7GwEBASIXY7kmM1m+Pj4oKioCH369BG7nB5jx0dELm3dunUwGo3IyMhg6NmJWq3GQw89hDNnzohdik0w+IjIZW3ZsgVvvfUWMjMzMXDgQLHLkTQpDXcy+IjIJe3evRsvv/wy0tPT8cADD4hdjuRJKfg4x0dELiclJQWJiYlIT0/HqFGjxC5HFvLz8zFmzBiUlpa6/Ck47PiIyKUcPXoUixcvxv79+xl6DqTT6aBSqZCbmyt2KT3G4CMil/Hll18iISEB//jHPzBu3Dixy5EVhUIhmf180jh4jYhcVkVdE/acLUROSQ1qTGZ4a9WICPLGnMhg+Hu5t113/vx5zJo1C1u3bsWkSZPEK1jGWuf5XP3p9ZzjIyJRXCioxrqs68i+Vg4AaDJb297TqpUQAEwKD8CyiWFwqyvG448/jvfffx/x8fEiVUzHjh3DqlWrcOLECbFL6REGHxE53PaTuXgjNQcmswXd/QZSKAA3lQKN/70dr//HE1i0aJHjiqQOamtrERQUhJs3b7r0Oaic4yMih7odelfQ2NJ96AGAIABNZgFuUc9AOewxxxRIXerduzcGDx6Mixcvil1Kj3COj4gc5kJBNd5IzUFjy7+GNQVzCyrT18OU+zWspjqofYLgO/Hf4TFkTNs1ZkGJN1JzMDLYByODfUSonFqNGzcOJ0+exJgxY+58sZNix0dEDrMu6zpMZku71wSrBerefRE0/8/QvbgLPo8tRPm+t2CuLm13nclswfqs644slzohhY3sDD4icoiKuiZkXyvvMLypdNPC59+ehdqnHxQKJTzDxkLdpx+aStqHnCAAx66Wo7KuyYFV049JYUsDg4+IHGLP2cK7us5SfxMtVUVwCwjp8J4CwJ5zd3cfso/hw4ejpKQEVVVVYpdy3xh8ROQQOSU17bYsdEawmFGx/214PTgFGn9dh/dNZityimvtVSLdBZVKhcjISJw+fVrsUu4bg4+IHKLGZO72fUGwouLgXwGVGn4xS7u8Lre4FIWFhbBYLF1eQ/bl6vN8XNVJRA7hre36140gCKhM/Tss9dUInPMqFKqur73y9TmMXbMYlZWVGDBgAEJCQhAaGoqQkJAOX/fq1cseP4rsjRs3Dhs3bhS7jPvGDexE5BAfZl/HX9OvoqWT0c7Kw++juex79Et4HUo3jy7voVUr8WLMMBgeG4KmpiYUFhYiPz8feXl5yM/P7/B1r169ugzG0NBQBAYGuvyTBsRw48YNPPjgg6ioqHDJPz8GHxHZVVVVFbZt24YNW3agceoqQKVp9775VhmKPkgEVBoolKq21/2eWA6vEZPbXeuuVuLE7x5vd4ZnVwRBQHl5eZfBmJeXh9raWuh0ui47Rp1OB61Wa5s/CInR6XQ4evQohg4dKnYp94zBR0Q2JwgCvvjiC2zYsAEHDx7EU089Bb1ej+15nsi4UnrHE1s6o1AA04b3w4cLbLdxuqGhAQUFBV0GY1FREXx9fbvsGENCQuDn5+eSXU9Pxc1bgH5RcfAcENbt4eLOiMFHRDZTWVmJbdu2wWg0AgD0ej0WLVoEf39/ALdPbknYeBKNLfe+MMVDo8IufZRDT26xWCwoLS3tcig1Ly8PLS0tbaHYWTAOHDgQGo3mzh/mIloPFz9yuRiCIMCq+FeX/uPDxUfpfESrszsMPiLqEUEQ8Pnnn8NoNOLgwYOIjY2FXq/Ho48+2mkn9K+zOrvf2vBDHholVk3/CRZEDbJh5bZRU1PTFoQ/7hjz8/NRUlKCfv36dTqU2vp1nz59xP4x7sq9HC6uVauwanqEU/6dMfiI6L5UVlZi69atMBqNUCqV0Ov1WLhwYVt31x2p/AK9G2azGUVFRV12jHl5eVCr1d0GY//+/aFSqe78YXYkpX+wMPiI6K4JgoDjx4/DaDQiJSUFsbGxMBgMmDBhwj3Pc10srMb6rOs4drUcCtzenN6qdchscngAlk0Kk/TB1IIg4ObNm10GY35+vuhbNzoboq45ewD1l46guTwXvX4yEX2ferHT7xVjiPpOGHxEdEcVFRVtc3dKpRIGgwELFy6En59fj+9dWdeEPecKkVNcixpTC7y1GkT0743Zo51/kYSjiL11Q5/0VYdFSQ1XTwAKBRq/PwehpbnL4LPHoqSeYvARUacEQUB2djaMRiNSU1MRFxcHvV6P8ePHy3IVozPr6daN0NBQBAcHd7p1o6KuCRPeOtrlcXM3jyfBUlPRZfAB97YNxRF4cgsRtVNRUdE2d6dWq2EwGPD+++/bpLsj+1AoFAgMDERgYGCXz8nrbOtGVlbWHbdufKMeBEHo2fxi6+HihseG9Og+tsLgIyIIgoCsrCwYjUYcOnQIcXFx+Pjjj/HII4+wu5MIT09PhIeHIzw8vNP3O9u6ce3aNXxhsaDZZ1iPPtvZDhdn8BHJWHl5eVt35+bmBoPBgPXr18PX11fs0sjBVCoVBgwYgAEDBuCRRx5pez1x6xkczSnr8f1rTC09voetMPiIZEYQBBw7dgxGoxGHDx/GrFmzsGXLFnZ31KnuDhe/t/s4zyZ+Bh+RTJSVlbV1d1qtFgaDAR988AG7O+pWRJA33NUlHRa3CFYL0Po/wQrB3AwoVe3OW22lVSsR0b+3o0q+I67qJJIwq9Xa1t2lpaXh5z//OfR6PaKiotjd0V3palVn9ec7cOu/d7Z7rc+EZ+Dzb892uIezrepk8BFJUFlZGbZs2YKNGzfCw8MDBoMBzz77LHx8fMQujVxQZ/v47pYz7uPjE9iJJMJqteLIkSOYO3cuhg0bhpycHCQlJeHChQtYvnw5Q4/u2/JJYdCq729Lg1atwrJJYTauqGfY8RG5uNLS0rbuztPTk90d2YWUzurk4hYiF2S1WnH06FEYjUZkZGTg6aefxo4dOzB27FjO3ZFdtIaXFA4XZ8dH5EJKS0vx8ccfY+PGjfDy8mrr7lzlsTbk+qRwuDiDj8jJtc7dtXZ38fHxMBgMePjhh9ndkWhc+XBxBh+RkyopKWmbu+vduzcMBgPmz5/P7o6ohzjHR+RErFYrMjMzYTQaceTIEcTHx2Pnzp3s7ohsiB0fkRMoKSlpm7vr06dPW3fn7e0tdmlEksOOj0gkVqsVGRkZMBqNOHr0KGbPno1du3ZhzJgx7O6I7IgdH5GDFRcXt3V3vr6+MBgMeOaZZ9jdETkIOz4iB2jt7jZs2IBjx45hzpw52L17NyIjI9ndETkYOz4iO7px4wY+/vhjbNq0qa27mz9/Pnr3dp6T6onkhh0fkY1ZLJa2ubtjx45h7ty52LNnDyIjI8UujYjAjo/IZm7cuIGPPvoImzZtQt++faHX6/HMM8+wuyNyMuz4iHrAYrEgPT0dRqMRWVlZmDt3Lj777DN2d0ROzGU6voq6Juw5W4ickhrUmMzw1qoREeSNOZHOfzwOSc8Pu7uAgADo9XokJCSwuyNyAU4ffBcKqrEu6zqyr5UDQLunALceiDopPADLJoZhlM5HnCJJFiwWC9LS0mA0GpGdnY158+ZBr9dj9OjRYpdGRPfAqYPv9vOfXP8RGOTaioqK2rq7wMBAGAwGJCQkwMvLS+zSiOg+OO0c37089FAQgMYWC95IvQIADD/qMYvFgsOHD8NoNOLzzz/HvHnzkJyczO6OSAKcsuO7UFCNhI0n0dhi6fT9lqoi3Nj8PHpFTEDf2JXt3vPQqLBLH+W0z4Ei51ZYWNjW3QUFBcFgMGDevHns7ogkRCl2AZ1Zl3UdJnPnoQcAVekfwr3/0E7fM5ktWJ913V6lkQRZLBakpKRg5syZGDlyJEpKSrBv3z6cPn0azz33HEOPSGKcbqizoq4J2dfKu5zTq7+cDaW2FzT+ETBXF3d4XxCAY1fLUVnXxNWe1K3CwkJs3rwZmzdvRv/+/aHX6/HJJ58w6Igkzuk6vj1nC7t8z9rUgOrPd8D38V90ew8FgD3nur4PyZfFYsHBgwfburuysjLs378fp06dYndHJBNO1/HllNS027LwQ9XHk+A1airU3n27vYfJbEVOca09yiMXVVBQ0NbdDRw4EHq9Hjt37kSvXr3ELo2IHMzpOr4ak7nT15tLv4Mp7wK8H467q/vcamy2ZVnkgsxmMw4cOIDY2FiMGjUK5eXlOHjwIE6ePInExESGHpFMOV3H563tvCRT/iWYb5WicP1iAIDQbAIEK4orfo3+i9d2uP5g8m488Md5CA0NRUhICEJCQtq+Dg0NhU6n4y8+ifphdxccHAy9Xo9PP/2Uf99EBMAJtzN8mP0t3sm81mG409pigtDU2PbfNaf3wnyrFH7TlkPl2afdtVq1Er+aPBhPhKqRl5eH/Px85Ofnt32dl5eHgoIC9OrVq10Y/jggAwMD+aw0F2E2m5Gamgqj0YgTJ05g/vz5WLJkCUaNGiV2aUTkZJyu45sdGYx3Mq91eF2p0QIabdt/KzRaKNRuHUIPAAQACWMHwd/LHUOGDOn0cwRBQHl5ebswzM/PxxdffNH2dV1dHXQ6XYdusTUgdTod3N25clRM+fn5bd2dTqeDwWDArl272N0RUZecruMDAH3SV8i4UtrtMWVdUSiAacP74cMFY3pcR319PQoKCjp0i60dZFFREfz8/DrtFlu/9vX1lW3XaK+DxVu7uw0bNuDkyZNt3d3IkSNtWD0RSZVTBt+dTm7pjiNPbrFYLCgpKelyODU/Px9ms7nLecaQkBAMHDgQarXTNd49Yq+DxfPy8tq6u9DQUBgMBsyZMweenp42/gmISMqcMviAezurs5WHRolV03/iVGd13rp1qy0UOwvG0tJSBAUFdTnPGBoa6lKPurH1weJmsxkpKSnYsGEDTp06hWeffRZLlizBgw8+aPviiUgWnDb4AHk8naGlpQVFRUUdhlF/GJBubm5dzjOGhoYiKCgISqX4O1Ns+Y+VvLw8bNq0CR999BEGDRoEvV7P7o6IbMKpgw8ALhZWY33WdRy7Wg4Fbm9Ob9U6bDY5PADLJoVJ8mBqQRBQVVXV5TxjXl4ebt68ieDg4C6HU3U6nd0Do6vh6YoDb8OUewHWFhNUvXzhHRWP3qOmtbumdXj6J/16ISUlBUajEadOncKCBQuwZMkS/PSnP7Vr7UQkL04ffK0q65qw51whcoprUWNqwdHDKfiPn0/F89MjZX8mp8lkaluE01kwFhQUwNvbu9vh1L59+/ZoEU5XC5Kay/Og8R0AhVqDlsoClHzyewTOeRXuQWFt1ygABKMS3279TwwePBh6vR6zZ89md0dEduEyqyr8vdxheOxfWxMWZKyFri4E/l7jRazKOWi1WgwdOhRDh3b+xAqr1YqysrJ2YZibm4vs7Oy21xoaGqDT6bocTg0ODoabm1un9+/uYHG3gNAf/JcCCihgvlncLvgEAEWCD/YcOIzxkVyZSUT25TLB92Pjxo3DqVOnkJiYKHYpTk+pVCIoKAhBQUEYO3Zsp9fU1dWhoKCgXbeYmZnZFpQ3btxA3759Ow3Gr+p9cTu+OleZth71l45AMDfBrd8QeAzpuNXETaPBpfpe4D9jiMjeXGao88dOnz4NvV6Pr7/+WuxSZMFisaC4uLjTecYc33EwB3f/ZHLBakFTUQ5M+ZfQJ2o2FKqO/+b6+c8G4p15P7PTT0BEdJvLBl9TUxP8/PxQVlbGUzpElrj1DI7mlN3VtZWH34embwi8x8zs8N6UiEBs/veHbV0eEVE74q+Bv0/u7u548MEH8dVXX4ldiux1dbB4p6xWmG92fIDw7ftobFQREVHXXDb4gH/N85G4IoK84a7u+H8lS3016i9nw9rcCMFqQeN3Z1F/JRvaQT/rcK1WrUREf9fZqE9ErstlF7cAt4Pvs88+E7sM2evqYHEoFKg9fwiVaesBwQp1n0D4TlkCz6HjOlwqAJg9Otj+xRKR7LnsHB8AfPvtt5g4cSIKCwvFLkX2nOVgcSKiO3Hpoc7BgwejqakJRUVFYpcie8snhUGrVt3X92rVKiybFHbnC4mIbMClg0+hUHCez0mM0vngcd9qCOame/q+22d1RkjyuDkick4uHXwAF7g4i927dyP5L/8Pv5owEB4aFe50+plCcfuMTmd7mgYRSR+Dj3osJSUFzz//PA4dOoSVs8Zhlz4K04b3g7taCe2PVntq1Uq4q5WYNrwfdumjGHpE5HAuvbgFAKqrq6HT6XDz5k3JPdDVFRw9ehQJCQk4cOAAxo1rv1rzxweLe2s1iOjfG7NH9+wJ7EREPeHywQcAERER2LVrF0aNGiV2KbLy5ZdfIi4uDv/4xz8wadIkscshIrorLj/UCXC4Uwznz5/HrFmzsHXrVoYeEbkUBh/dsytXrmD69OlYv349nnzySbHLISK6Jww+uiffffcdpk6dijVr1iA+Pl7scoiI7pkk5vhaWlrg4+OD4uJieHt7i12OZBUWFuKxxx7DSy+9hF/+8pdil0NEdF8k0fFpNBo89NBDfFKDHZWVlSE6OhrLli1j6BGRS5NE8AEc7rSnqqoqxMTEYN68eVi5cqXY5RAR9QiDj7pVW1uLJ598EtHR0Xj11VfFLoeIqMckMccHAHl5eYiKisKNGzeguNN5WXRXGhoaMH36dISHh+PDDz/knysRSYJkOr6QkBAIgoD8/HyxS5GE5uZmzJ49G8HBwVi/fj1Dj4gkQzLBxyc12I7ZbMb8+fPh7u6OLVu2QKW6v8cNERE5I8kEH8B5PluwWq1ITExEbW0tPv30U55/SkSSw+CjNoIg4Pnnn0dubi6Sk5Ph7s6DpIlIeiSzuAUAampqMGDAANy8eRMajUbsclyKIAj43e9+h2PHjuHIkSM8CICIJEtSHZ+3tzcGDRqES5cuiV2Ky3n99ddx6NAhHD58mKFHRJImqeADONx5P9555x0kJSUhIyMD/v7+YpdDRGRXDD6ZMxqNWLt2LTIzMxEUFCR2OUREdsfgk7EdO3bgtddeQ2ZmJkJCQsQuh4jIISS1uAW4vQfN19cX+fn58PX1Fbscp/XPf/4TS5cuxZEjRzBixAixyyEichjJdXxqtRqjR4/GmTNnxC7FaaWnp0Ov1yMlJYWhR0SyI7ngAzjc2Z3PP/8czz77LJKTkxEZGSl2OUREDsfgk5EzZ84gPj4eO3fuxIQJE8Quh4hIFJKb4wOAoqIi/OxnP0NZWRkPV/4/ly5dQkxMDIxGI2bOnCl2OUREopFkxzdw4EC4u7vj+++/F7sUp3Dt2jU88cQTePfddxl6RCR7kgw+gMOdrfLy8hATE4PVq1cjISFB7HKIiETH4JOw4uJiREdHY8WKFUhMTBS7HCIipyDp4Dt58qTYZYimoqICMTExWLx4MV544QWxyyEichqSXNwCAHV1dejXrx+qqqpk93idW7du4fHHH8fUqVPx5ptvil0OEZFTkWzH5+XlhbCwMFy4cEHsUhyqvr4eM2bMwPjx4/GnP/1J7HKIiJyOZIMPkN88n8lkwqxZszB06FCsXbuWWzmIiDrB4JOIlpYWzJ07F35+fti0aROUSkn/1RIR3TdJ/3aMioqSRfBZLBYsWrQIVqsVSUlJUKlUYpdEROS0JLu4BbgdCH5+fvjuu+8k+4BVq9UKvV6P77//HgcPHoSHh4fYJREROTVJd3wqlQpjxozB6dOnxS7FLgRBwIsvvojLly9j3759DD0iorsg6eADpD3P94c//AHHjx9HamoqvLy8xC6HiMglyCL4pLiR/c9//jP27t2L9PR0+Pj4iF0OEZHLkPQcHwCUlJRg+PDhqKyslMzy/vfffx/vvPMOjh8/joEDB4pdDhGRS5F8xxcUFITevXvjm2++EbsUm9iyZQvWrFmDI0eOMPSIiO6D5IMPkM483+7du/Hyyy8jIyMDgwYNErscIiKXxOBzESkpKXj++edx6NAhhIeHi10OEZHLkkXwufpG9qNHj2Lx4sXYv38/Ro0aJXY5REQuTfKLWwCgsbERffv2RWVlJbRardjl3JMvv/wSM2fOxJ49ezBx4kSxyyEicnmy6Pg8PDwQERGB8+fPi13KPTl//jzi4uKwbds2hh4RkY3IIvgA15vnu3LlCqZPn44PPvgATz75pNjlEBFJhqyCz1U2sn/33XeYOnUq1qxZg/j4eLHLISKSFFkFnyt0fIWFhYiOjsaqVauwcOFCscshIpIc2QTfsGHDUF1djbKyMrFL6VJZWRmio6OxbNkyLF26VOxyiIgkSTbBp1Qq8fDDDztt11dVVYWYmBgkJCRg5cqVYpdDRCRZsgk+wHmHO2tra/Hkk08iOjoa//Vf/yV2OUREkiar4HPGjewNDQ2IjY3FQw89hLffflsyB2kTETkrWWxgb1VeXo6hQ4eiqqoKSqX4md/U1IRZs2bB398f27Ztc4qaiIikTla/aQMCAuDv74+rV6+KXQrMZjPmz58PDw8PbNmyhaFHROQgsvtt6wzzfFarFYmJiaivr8fOnTuhVqtFrYeISE5kGXxibmQXBAHLly9Hbm4u9u7dC3d3d9FqISKSI1kGn1gdnyAI+O1vf4uzZ8/i4MGD8PT0FKUOIiI5k9XiFgAwmUzw9/dHeXm5w4Pntddew549e5CVlQU/Pz+HfjYREd0mu45Pq9VixIgROHv2rEM/929/+xu2b9+OjIwMhh4RkYhkF3yA4/fzGY1GvPfeezhy5Aj69evnsM8lIqKOZBl8jpzn27FjB1577TVkZGRAp9M55DOJiKhrDD47Sk5OxooVK5CWloawsDC7fx4REd2ZLINvyJAhaGhoQHFxsd0+Iy0tDQaDAampqRgxYoTdPoeIiO6NLINPoVBg7Nixduv6jh8/jgULFiA5ORmjR4+2y2cQEdH9kWXwAfbbyH7mzBnMnj0bO3fuxIQJE2x+fyIi6hlZB5+tO75Lly4hNjYWmzdvRnR0tE3vTUREtiG7DeytqqqqMGjQINy8eRMqlarH97t27RomT56Mv/71r0hISLBBhUREZA+y7fj8/PwQFBSEy5cv9/heeXl5iImJwerVqxl6REROTrbBB9hmI3txcTGmTJmCFStWIDEx0UaVERGRvcg6+Ho6z1dRUYHo6GgkJibihRdesGFlRERkLwy++wy+W7duYdq0aYiLi8PLL79s48qIiMheZLu4BQCam5vh5+eHkpISeHl53fX31dfXY+rUqYiMjMTatWuhUCjsWCUREdmSrDs+Nzc3jBw5El999dVdf4/JZEJcXBzCw8Px7rvvMvSIiFyMrIMPuLeN7C0tLZg7dy78/f2xceNGKJWy/+MjInI5sv/NfbfzfBaLBQsXLoQgCEhKSrLJ3j8iInI8tdgFiG3YyEic2XwYv9l1HjUmM7y1akQEeWNOZDD8vdwBAFarFXq9HuXl5UhJSYGbm5vIVRMR0f2S7eKWCwXVWJd1HdnXymEymaBQ/yvMtGolBACTwgPwy4lD8PHbr+LMmTNIT0+/p0UwRETkfGQZfNtP5uKN1ByYzBZ099MrFIBSsMD9f1NwYttb8PHxcViNRERkH7Kb47sdelfQ2NJ96AGAIAAWqGAdNQsHc6odUh8REdmXrDq+CwXVSNh4Eo0tlnavl+z4TzTduAqF8vaCFVVvfwzUb2h3jYdGhV36KIwM9nFUuUREZAeyWtyyLus6TGZLp+/5TV2K3qOmdfm9JrMF67Ou48MFY+xVHhEROYBshjor6pqQfa38jsObXREE4NjVclTWNdm2MCIicijZBN+es4Xdvl+dtRUFa+ejJOklmPIudnqNAsCec93fh4iInJtshjpzSmrQZLZ2+p7v5MXQ+OugUGlQf+U4yj5bjf6L/w6Nb/9215nMVuQU1zqiXCIishPZdHw1JnOX77kPCIfS3RMKtQZeD06B+8CfoPHbzs/vrDG12KtEIiJyANkEn7f2HppbhQJA55OB3lqNbQoiIiJRyCb4IoK84a7u+ONaTXVo/O4sBHMzBKsFdf97DE0F/wOPwZEdrtWqlYjo39sR5RIRkZ3IZo5vdmQw3sm81uF1wWpB9fHtaKkqBBRKaPyDEfD0K9D4Dex4LYDZo4MdUC0REdmLbIKvr5c7Jg4LQMaV0nZbGlSefdD/P9654/crFMDk8IC2g6uJiMg1yWaoEwCWTwqDVn1/jxPSqlVYNinMxhUREZGjySr4Rul8sGp6BDw09/Zje2iUWDU9gseVERFJgGyGOlstiBoEAHf9dAatWoVV0yPavo+IiFybrA6p/qGLhdVYn3Udx66WQ4Hbm9NbtT6Pb3J4AJZNCmOnR0QkIbINvlaVdU3Yc64QOcW1qDG1wFurQUT/3pg9OpgLWYiIJEj2wUdERPIiq8UtREREDD4iIpIVBh8REckKg4+IiGSFwUdERLLC4CMiIllh8BERkaww+IiISFYYfEREJCsMPiIikhUGHxERyQqDj4iIZIXBR0REssLgIyIiWWHwERGRrDD4iIhIVhh8REQkKww+IiKSFQYfERHJCoOPiIhkhcFHRESy8v8BZ9ZE6J+gHJYAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "nx.draw(G, with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of edges: 7\n"
     ]
    }
   ],
   "source": [
    "# List of Nodes\n",
    "V = list(G.nodes())\n",
    "# List of Edges\n",
    "# Edges of the graph\n",
    "E = list(G.edges())\n",
    "print(\"Number of edges:\", len(E))\n",
    "# generate a Dictionary of adjacent vertices\n",
    "A = dict((v, []) for v in V)\n",
    "for (u, v) in E:\n",
    "    A[u].append(v)\n",
    "    A[v].append(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5]\n",
      "{0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2, 4, 5], 4: [3, 5], 5: [3, 4]}\n"
     ]
    }
   ],
   "source": [
    "print(V)\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 0.0, 1: 0.0, 2: 6.0, 3: 6.0, 4: 0.0, 5: 0.0}"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "brandes(V, A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0, 1): 1.0,\n",
       " (0, 2): 4.0,\n",
       " (1, 2): 4.0,\n",
       " (2, 3): 9.0,\n",
       " (3, 4): 4.0,\n",
       " (3, 5): 4.0,\n",
       " (4, 5): 1.0}"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# unnormalized betweenness centrality\n",
    "\n",
    "nx.betweenness_centrality(G,normalized=False)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.4 64-bit",
   "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.4"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "6bf3ebb51ba865f281ce1f84b3745d1f53cddfef84166cfb0862af6341610cdf"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}