Edge_Brandes.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 33,
   "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={}\n",
    "    for v in V:\n",
    "        for e in A.keys():\n",
    "            C[(v,e)] = 0\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",
    "\n",
    "        while S:\n",
    "            w = S.pop()\n",
    "            for v in P[w]:\n",
    "                e[v] = e[v] +  g[w]* (1 + (e[w]/g[w]))\n",
    "                C[(v, w)] = C[(v, w)] + g[v]*(e[w]/g[w] +1)\n",
    "\n",
    "    return C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "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": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAA0HElEQVR4nO3deVxU5cIH8N9sAorDoIIbKuUCpimKqWkIXkUQxd0UcTetNG+Z1eu9Xstu16zMVy01y9IWzUrEmwuy+MamNyxFsK6gkdc9DZRFlBlme//wQiKLgjNz5pn5fT8fP5/bLGd+Tdfzm+ec5zxHZjabzSAiInIScqkDEBER2RKLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInAqLj4iInIpS6gAPoqBUh5hjF5F7pQQlWgPUrkr4t1JjYqAPmru7SB2PiIjskMxsNpulDlFf2ReKsCElD6mn8wEAOoOp8jlXpRxmACF+Xpgf3Ak922mkCUlERHZJuOLblnEWK+JyoTUYUVdymQxwVSqwNMIfU/v72iwfERHZN6EOdd4uvRyU6U33fK3ZDJTpjVgRlwMALD8iIgIg0Igv+0IRJm/OQJneWOXxK9uXQHf5FGRyBQBA0bQ52s77sMpr3FQKfD2vP3r4aGwVl4iI7JQwI74NKXnQGow1Ptds2DNo2jOs1vdqDUZsTMnDpql9rBWPiIgEIcTlDAWlOqSezq/znF5dzGYg+VQ+rpXqLBuMiIiEI0TxxRy7WOfzRSmf4cK6KbjyxcvQnjtR42tkAGIy694OERE5PiEOdeZeKalyycKdPAfPgqp5O8gUKtzMScPvu95A61nvQeXZusrrtAYTcn+7YYu4RERkx4QY8ZVoDbU+59LGD3KXxpApVXB/dAhc2nZF2a9Ha9mO3loRiYhIEEIUn9q1HgNTmQxAzScD1a4qywQiIiJhCVF8/q3UcFFWj2rSlqLszDGYDeUwm4wo/XcydBd+htvDgdVe66qUw791U1vEJSIiOybEOb4JgT5Yc/B0tcfNJiOK0rZBf/0iIJND1dwHXuP+BlWzttVfC2BCbx8bpCUiInsmRPG1cHdBcBcvJOVcrXJJg6KxB1rPXHPP98tkwGA/Ly5cTUREYhzqBIAFIZ3gqlQ06L2uSgXmh3SycCIiIhKRMMXXs50GSyP84aaqX2SzXodJXZRcroyIiAAIVHzA7YWml0Z0hZtKcXvyZh1ksttrdE7t3hgbX5yCzMxM24QkIiK7Jswi1Xc6cbEIG1PykHwqHzLcvji9QsX9+Ab7eWF+SCf08NEgNjYWCxYsQEpKCvz8/CTLTURE0hOy+CpcK9UhJvMidsSlwqRyRWD3R+Dfuikm9K5+B/atW7di+fLlOHToENq1aydRYiIikpoQszpr09zdBU8P6oic2PfRoWUHLJo0pdbXzpo1C0VFRQgNDUVaWhq8vb1tmJSIiOyF0MVXQafTwdXV9Z6vW7RoEa5fv47w8HAkJyfDw8PDBumIiMieCDW5pTZarfa+ig8A/v73v2PAgAEYNWoUysrKrJyMiIjsjdMVn0wmw3vvvQcfHx9MnDgRej0XriYiciZOV3wAIJfL8emnnwIAZs6cCZOp5lseERGR43GY4nNxqd9yZCqVCjt37sTFixexcOFCCDy5lYiI6sFhiq8+I74Kbm5u2LNnDzIyMvDqq69aIRkREdkbp5rVWRMPDw/Ex8cjKCgInp6eePHFFy2cjoiI7IlDFF9DR3wVvLy8kJiYiKCgIGg0GsyePduC6YiIyJ6w+P6rffv2SExMREhICDQaDcaNG2ehdEREZE9YfHfw8/NDXFwcwsLCoFarMXToUAukIyIie+Iwk1vqO6uzNr169cKuXbsQFRWFjIwMi2yTiIjsh8MUnyVGfBWCgoLw6aefYvTo0fj5558ttl0iIpKeQxTfg8zqrM2IESOwdu1ahIeH48yZMxbdNhERSUf4c3xms9mihzrvFBUVVXlHh/T0dLRp08bin0FERLYlfPEZDAbI5XIoldb5V3n22WdRWFiIsLAwpKamolmzZlb5HCIisg3hD3Va+vxeTf7yl78gLCwMERERKC0ttepnERGRdTlE8VnjMOedZDIZVq1ahe7du2Ps2LHQ6XRW/TwiIrIehyg+a4/4gNvl9+GHH8LDwwNTpkyBwWCw+mcSEZHlsfjqQaFQYPv27bhx4waefvpp3tGBiEhAwhefNS5lqIuLiwtiY2Nx8uRJvPTSSyw/IiLBCF98thzxVXB3d8f+/fuRmJiIN99806afTURED0b4yxmkKD4AaNasGRITE/HEE0/A09MT8+fPt3kGIiKqP4coPmvP6qxN69atkZSUhEGDBkGj0WDKlCmS5CAiovvnEMUnxYivwsMPP4z4+HgMHToUHh4eGDFihGRZiIjo3niOzwK6d++Ob7/9FjNnzkRaWpqkWYiIqG7CF5+tZ3XWpl+/ftixYwcmTJiAzMxMqeMQEVEthC8+exjxVRg6dCg2bdqEESNG4NSpU1LHISKiGvAcn4WNGzcOxcXFGDZsGNLT09G+fXupIxER0R0covikmtVZm1mzZqGoqAjDhg1DWloavL29pY5ERET/5RDFZ08jvgqLFi1CYWEhwsPDkZycDA8PD6kjEREReI7Pql5//XUMGDAAkZGRKCsrkzoOERHBAYrPXmZ11kQmk+G9995D+/btMXHiROj1eqkjERE5PeGLz55HfAAgl8uxdetWyGQyzJgxAyaTSepIREROjcVnAyqVCt988w0uXbqEhQsX8o4OREQScojis7dZnTVxc3PD3r17kZGRgWXLlkkdh4jIaXFWpw2p1WrEx8cjKCgInp6eWLx4sdSRiIicDovPxry8vJCUlFRZfrNnz5Y6EhFRvRWU6hBz7CJyr5SgRGuA2lUJ/1ZqTAz0QXN3+z4KJ3zx2fOsztq0a9cOiYmJCAkJgYeHB8aPHy91JCKi+5J9oQgbUvKQejofAKAz/DFhz1V5BWsOnkaInxfmB3dCz3YaiVLWTfjiE23EV6FLly7Yv38/wsLCoFarERoaKnUkIqI6bcs4ixVxudAajKhpjp72vyWYePIq0k4XYGmEP6b297VtyPvgEJNbRCw+AOjVqxd27dqFKVOmICMjQ+o4RES1ul16OSjT11x6dzKbgTK9ESvicrAt46xN8tWHQxSfCLM6axMUFITPPvsMo0ePxk8//SR1HCKiarIvFGFFXC7K9H8c1iw5the/ffoCzq0ag4J9a2p8X5nehBVxuThxschGSe+PQxSfqCO+ChEREVi7di2GDx+OM2fOSB2HiKiKDSl50BqMVR5TujeHx4BJcO9R92karcGIjSl51oxXbzzHZyeioqJQXFyM0NBQpKeno02bNlJHIiJCQakOqafzqx3ebOw3AACgu5IHo76g1vebzUDyqXxcK9XZzWxP4Ud8Is7qrM0zzzyDp556CsOGDcP169eljkNEhJhjFx94GzIAMZkPvh1LEb74HGXEV2HJkiUYPnw4IiIiUFpaKnUcInJyuVdKqlyy0BBagwm5v92wUKIHx+KzMzKZDO+88w66d++OMWPGQKfTSR2JiJxYidZgoe3Yz91phC4+s9mM8vJyoWd11kQmk+HDDz+Ep6cnpkyZAoPBMv/HIyKqL7WrZaaCqF1VFtmOJQhdfDqdDiqVCjKZTOooFqdQKLBt2zbcuHED8+bN4x0diEgS/q3UcFFWrwqzyQizoRwwGQGzCWZDOcwmYw1bAFyVcvi3bmrtqPdN6OJztMOcd3NxcUFsbCxycnLw0ksvsfyIyOYmBPrU+Hjx4a9w/t1xKMmIwc1/J+P8u+NQfPirGl9rBjChd83bkYLQlzM40ozO2ri7uyMuLg7BwcF48803sXTpUqkjEZETad6kEdqrSnG63BUy+R9jJU1QNDRB0fd8v0wGDPbzsptLGQCO+ITg6emJhIQEbN26FRs2bJA6DhE5id9//x2jR4/G78mfw1WlaNA2XJUKzA/pZOFkD4bFJ4jWrVsjKSkJK1euxPbt26WOQ0QOLi4uDgEBAejWrRt+TNiFZSMfgZuqfpXhppJjaYQ/evhorBOygYQ+1OlMxQcADz30EBISEjBkyBB4eHhg5MiRUkciIgdTVlaGl19+GXv37sWOHTsQHBwMAJV3Wajr7gwVZLLbIz3encEKRF+guiG6deuGb7/9FrNnz0ZqaqrUcYjIgWRlZSEwMBDXr19HdnZ2ZelVmNrfF1/P64+wR1rCRSmvNtvT9b+PhT3SEl/P62+XpQdwxCekfv36YceOHZg4cSLi4+PRu3dvqSMRkcBMJhNWr16NVatWYc2aNYiOrn3SSg8fDTZN7YNrpTp8ln4Kqz/ZgfDIcVC7quDfuikm9OYd2K3KGWZ11mbIkCH48MMPMWLECCQnJ8Pf31/qSEQkoAsXLmD69OkwGo344Ycf4Ovre1/va+7ugicfbYbV33+OT2JWWjekhQl/qNNZiw8Axo4di5UrVyIsLAznz5+XOg4RCebrr79GYGAgQkNDkZycfN+lV0HUfbDQIz5Rv3RLmjlzJoqKiipvZ+Tt7S11JCKycyUlJXjuuedw5MgRxMXFoU+fPg3ajqj7YI74HMALL7yASZMmITw8HMXFxVLHISI7dvjwYQQEBKBx48bIzMxscOkB4p5uEr74nG1WZ21ef/11DBw4EJGRkbh165bUcYjIzuj1eixbtgwTJkzA2rVrsWnTJjRp0uSBtinq4EP44hPxS7cGmUyGdevWoX379pg4cSL0evu5BQgRSeuXX37BE088gWPHjuH48eMYNWqURbYr6j5Y6OITdZhtLXK5HFu3boVCocCMGTNgNNa8UjoROQez2YzNmzdjwIABmD59Ovbv349WrVpZbPuiHnUTuvhE/bVhTSqVCl9//TUuX76MhQsX8o4ORE6qoKAA48aNw4YNG5CamooFCxZY/BZuou6DWXwOyM3NDXv27MGRI0ewbNkyqeMQkY0lJCSgZ8+e6Ny5M44cOYJHHnnEKp8j6lE34S9naNasmdQx7JJarUZ8fDwGDRoET09PLF68WOpIRGRlZWVlWLJkCXbv3o1t27Zh8ODBVv08UQcfwhefiMeXbcXLywuJiYkICgqCRqPBnDlzpI5ERFZy4sQJTJkyBd26dUN2djY8PT2t/pksPgmI+qXbUrt27ZCYmIiQkBBoNBqMHz9e6khEZEEmkwlr167FypUrsXr1akybNs3i5/JqI+rgQ+jiE/X4sq116dIF+/fvR1hYGNRqNUJDQ6WOREQWcOnSJcyYMQNlZWX44Ycf8NBDD9n080UdfHByi5Po1asXYmNjMWXKFHz//fdSxyGiBxQTE4PevXsjJCQEqampNi89QNzBh9AjPhZf/TzxxBP47LPPMGbMGBw8eBCPPvqo1JGIqJ5u3LiBP//5zzh06BD27NmDfv36SZZF1AmGHPE5mYiICKxbtw7h4eH49ddfpY5DRPXw/fffIyAgAEqlEsePH5e09ABx98HCj/hEPLEqtcmTJ1fe0eHQoUNo06aN1JGIqA4GgwH/+Mc/sGnTJnzwwQcYO3as1JEAsPgkIeqXbg+eeeYZFBYWYtiwYUhNTUXz5s2ljkRENfj1118xdepUqNVqZGZm2tUPVVEHHzzU6cSWLFmCiIgIREREoLS0VOo4RHQHs9mMrVu3on///oiKisKBAwfsqvQAcffBQhefqDOK7IVMJsPbb7+NRx99FGPGjIFOp5M6EhEBuHbtWuXtg5KTk/HnP/8Zcrn97a5F3Qfb3zdZD6L+2rAnMpkMH374ITw9PREVFQWDwSB1JCKndvDgQfTs2RO+vr44cuQIunfvLnWkWom6D2bxERQKBbZt24abN29i7ty5MJlMUkcicjparRYvvvgiZs6ciU8//RSrV6+2+/2bqPtg4YtPxBOr9sjFxQWxsbE4deoUXnrpJd7OiMiGfv75Z/Tt2xfnz59HdnY2hg4dKnWk+yLqPlj44hPx14a9atKkCfbv34+DBw9ixYoVUschcngmkwnr1q3D4MGDsWjRIuzcuVOoGdai7oOFvZzBaDTCaDRCpVJJHcWheHp6IiEhAUFBQfD09MSCBQukjkTkkC5fvoxZs2ahpKQEGRkZ6Nixo9SR6o2TW2ys4gu31SrkzqR169ZISkrCW2+9he3bt0sdh8jh7N69G71798aAAQOQnp4uZOkBHPHZnKhfuCgeeughxMfHY8iQIVCr1YiMjJQ6EpHwSktL8cILLyA5ORm7d+/G448/LnWkByLqfljYEZ+oX7hIunXrhj179mD27NlITU2VOg6R0I4cOYJevXrBZDIhKytL+NIDOLnF5kT9wkXTt29ffPXVV5g4cSKOHTsmdRwi4RgMBrzxxhsYNWoUVq5ciS1btqBp06ZSx7IIUQcgPNRJ9zRkyBB89NFHGDlyJJKTk+Hv7y91JCIh/Oc//8HUqVPh5uaGzMxMtG3bVupIFmM2m6HT6YQcgAg94mPx2c6YMWOwcuVKhIWF4fz581LHIbJrZrMZn332Gfr27Yvx48cjMTHRoUoPAPR6PZRKJRQKhdRR6k3YEZ+o02hFNnPmzMrbGaWnp8Pb21vqSER25/r163jmmWdw8uTJyuXHHJHIgw9hi0/kL11kL7zwAgoLCxEWFoaUlBR4eHhUPldQqkPMsYvIvVKCEq0Balcl/FupMTHQB83dxTscQlRf3333HWbOnIlx48bh888/d+h9lMj7YBYf1dvy5ctRWFiIkSNHIiEhAb9cK8eGlDykns4HAOgMf6z16aq8gjUHTyPEzwvzgzuhZzuNRKmJrEen0+Fvf/sbvvzyS2zZsgVhYWFSR7I6kScYCl18on7popPJZFi7di1mzJiBP817DUUP/wk6gwk1Le+p/W8JJp68irTTBVga4Y+p/X1tG5jIik6ePIno6Gj4+voiOzsbLVq0kDqSTYg8+ODkFmoQuVyOoc8sx9W2A6HV11x6dzKbgTK9ESvicrAt46xNMhJZk9lsxvr16xEcHIwFCxYgNjbWaUoPEHuehdAjPlG/dEeQfaEIbyX8ArO8+lqpBXvfhfZsNkx6LRRNPKHuPx5Ne94+9FOmN2FFXC56+GjQw0dj49RElnHlyhXMnj0bBQUF+Ne//oXOnTtLHcnmRN4HCzviE/nXhiPYkJIHrcFY43Pq/hPR9tktaP/iTnhPWIaitC+gu5JX+bzWYMTGlLwa30tk7/bs2YNevXohMDAQhw8fdsrSA8QuPo74qN4KSnVIPZ1f6+HNRl4d7vgnGWSQwVD4G1xadQJw+7Bn8ql8XCvVcbYnCePmzZt48cUXkZSUhJiYGAwcOFDqSJISeZ6FsCM+Fp90Yo5dvOdrriVsxPl3x+Py5megcG8Gt459qjwvAxCTee/tENmDo0ePonfv3tBqtcjKynL60gPE3gdzxEf1lnulpMolCzVpHjYfzUKfhu5SLrTnf4JMUfVcoNZgQu5vN6wZk+iBGY1GvP3221i7di3Wr1+PJ598UupIdkPkfbDQxXfnxdNkOyVaw329TiZXwLVdN9z8dzJuHI+Dus+ou7ajt0Y8Ios4e/Yspk2bBpVKhWPHjqFdu3ZSR7IrIs+z4KFOqje1az1/L5lMMBT+Vu3hE0eP4B//+Ad27dqFkydPory83EIJiR7M9u3b8dhjj2HUqFE4ePAgS68GIu+DhR3xifxrQ3T+rdRwUV6p8XCn8WYRtOey4dapL2TKRtCezcLNnFS0GPVKldc1kgMBD3njZv4lfPHFF8jJycG5c+fQoUMHdO3atcoff39/h7mNC9m3oqIizJ8/H1lZWUhMTESvXr2kjmS3WHwSEPlLF92EQB+sOXi65idlMtw4fgDXEjYCZhOUHt7wHDIXjTv3q/oyuRxvzRuN5u5/nDPR6XTIy8tDbm4ucnJykJCQgLVr1+LUqVPw9PSsVoZdu3ZFy5YtIZPJrPmvS04iNTUV06dPR2RkJI4ePYrGjRtLHcmuiTyrk8VH9dbC3QXBXbyQdPIq7r6iQdHYA62i36rz/TIZMNjPq9qlDC4uLujWrRu6detW5XGTyYTz589XFuLx48fx5ZdfIicnB0ajscZC9PX1FfJ2KWR75eXlePXVV/H555/j448/RkREhNSRhCDyPpjFR/Wm0+lg+ukATOZukCnr/4vPVanA/JBO9/16uVwOX19f+Pr6Ijw8vMpzBQUFyMnJqfxz8OBB5OTkID8/H507d65Shl27dkWXLl34/xuqlJubi+joaLRt2xZZWVm81VY9iHy6SejiE3WYLbKKBXk7dOiAJc+NxXtpF1Cmr/vShju5qeRYGuFvseXKWrRogaCgIAQFBVV5/ObNmzh16lRlIX7zzTfIzc3FmTNn0LZt2yplWFGOnp6eFslE9s9sNuODDz7Aq6++ihUrVmDevHk8ZF5PWq0WarVa6hgNInTxifprQ0RmsxkbNmzA8uXLsXLlSjz11FOQyWRo6u6OFXG50BqMdS5ULZPdHunZ6u4MTZo0Qe/evdG7d+8qj+v1epw5c6ayEFNTU7Fp0ybk5uaicePGNU6sadu2LXeKDuTq1auYM2cOrly5gsOHD8PPz0/qSEISeR8sbPGJPMwWzd0L8nbp0qXyuan9fdHDR4ONKXlIPpUPGf64FREAuCrlMOP2Ob35IZ0kX5hapVLBz88Pfn5+GDNmTOXjZrMZly5dQk5OTuW5xNjYWOTk5ODWrVtVRogV/7tjx45QKoX9K+SU9u3bh7lz52LWrFmIjY1Fo0aNpI4kLJGPugn7t1bkXxsi2bt3L+bNm4c5c+bgtddeg0pV/W4MPXw02DS1D66V6hCTeRG5v91AiVYPtasK/q2bYkJv+78Du0wmg4+PD3x8fBAaGlrlucLCwsoyzMnJwccff4ycnBxcvnwZDz/8cLXziH5+fmjSpIlE/yZUk1u3buGll15CXFwcvv76awwaNEjqSMITeR/M4qMa3bx5E4sXL0ZCQgJ27tyJJ5544p7vae7ugqcHdbRBOtvy9PTE448/jscff7zK42VlZfjll18qC3HPnj14++23kZeXB29v72rnEbt27epU92uzF5mZmYiOjkZgYCCysrKg0WikjuQQRD7qxuKjao4ePYro6Gj069cPWVlZXBquFm5ubujRowd69OhR5XGj0YizZ89WFmJGRga2bt2KnJwcKJXKGs8jtm/fHnK5sAsp2SWj0Yh3330Xq1evxrp16xAVFSV1JIci8j5Y6OIT9fiyvbpzQd73338fkyZNkjqSkBQKBTp27IiOHTti5MiRlY+bzWZcvXq1yuUXcXFxyMnJQWFhIfz8/KoVYufOnXkeqgHOnz+P6dOnw2w248cff0SHDh3u/SaqFxafBET+0u0RF+S1PplMhlatWqFVq1YYPHhwledKSkoqzyPm5ubWuoxbxeFTf39/YaeSW9uOHTvw/PPP48UXX8TLL7/MhQysROTBh7DFJ/LxZXtiNpuxfft2LFq0CK+88goWL17MQ24SUKvV6Nu3L/r27Vvl8buXcUtMTMS6deuqLON297lEZ13Grbi4GAsWLMDRo0dx4MABBAYGSh3JoYk8+BCy+Mxms9C/NuxFYWEh5s+fj+zsbCQlJSEgIEDqSHSX+13GLSsrCzt27Khcxq2miTWiLONWUKpDzLGLyL1SghKtAWpXJfxbqTExsPbZwenp6Zg+fTrCw8ORmZnJdTZtQOTik5nNdV12bJ/0ej0aN24MvZ73c2uolJQUzJgxA6NGjcI777wDNzc3qSORhdy9jFvFn/z8fHTq1KlaIXbu3Nku/vtnXyjChpQ8pJ7OB4Aqd/+ouB40xM8L84M7oWc7DYDb+4Lly5djy5Yt+OijjxAZGSlBcufk5+eHPXv2CLkAgJDFd+PGDbRp0wY3bvAO3vVVXl6OZcuW4YsvvsAnn3yC4cOHSx2JbOTuZdwqzieeOXMGbdq0qXYesWvXrjZbxm1bxtl6rwDUt1k5oqOj4e3tjS1btqBly5Y2yUq3dejQAWlpaUJOHBKy+PLz89G1a1cUFBRIHUUoOTk5iI6ORrt27fDxxx/Dy8tL6khkB+5exu3OSTYVy7jdfejUksu43S69nHqt+aqSmVCa/gWWRYXg2WefdcpzmlJr2bIlTpw4IeQPDiGL78KFC3j88cdx8eJFqaMIwWw2Y+PGjVi+fDlWrFiBuXPnckdB91TTMm4Vf27evFnjecSHH364xtV9apN9oQiTN2egTG/843MNelxL3Ajt2SyYtKVQalrBM3gG3Dr2qfJeF4UMO58ZIPkyeM7Kw8MD586dE3JBACEnt3BG5/27evUqZs+ejd9//x2HDx+uss4mUV0asozbpUuXKpdxu/NPbcu4bUjJg9ZgrPKY2WSEsmkLtJryFhQeXij79Sjyv30bbWavh1Lzx+ii3GTGxpQ8bJra5+7Nkg1wcouN/fzzz5g8eTJ+/vlnqaPYtftZZ5PIku5exq3izy+//AJvb+8qZdjmoS54MfUWyo333gVd/uQ5eAyMQhP/gVUed1HK8a//+ZPdrwXraMxmMxQKBYxGo5BHj4Qc8Yn8S8MW7lxn85tvvql2rzoia6nPMm4/HsyBrkPQPW9mbLxZCP31S2jk1b7aczIAMZkXHXKNWHum0+nQqFEjIUsPYPE5nGPHjiE6OhqPPfYY19kku1HTMm4vfH0c/8y6XOf7zEYDCva8C/dHh0DVvPpqQlqDCbm/cXa3rYm+Dxa2+HjxelVGoxHvvPMO1qxZg/feew+TJ0+WOhJRnUq0hjqfN5tNKNi3GlAo0Sz0mTq2w+t5bU30fbCwxSfyrw1LO3fuHKZNmwaFQoGjR4+iffvqh4SI7I3atfbdj9lsxrW492C8WQTvicshU9T+WrUrz13bmuj7YCEXZRT9S7ek7du347HHHsPIkSNx8OBBlh4Jw7+VGi7KmndB1xM2QH/tArwnvAq5qvaRhatSDv/WTa0VkWoh+j5YyBEfL2cAioqKMH/+fGRlZSEhIQG9evWSOhJRvUwI9MGag6erPW4o/h2lWfGAQoWL70+rfLxZ+AK4d6t6VwszgAm9fawdle4i+j5YyOIT/dfGg0pNTcX06dMRGRmJo0ePckFeElILdxcEd/FCUs7VKsuUKT280WHJvnu+XyYDBvt58VIGCYi+D+ahToGUl5djyZIliIqKwgcffID169ez9EhoC0I6wVXZsDtGuCoVmB/SycKJ6H6Ivg8WtvhEnlHUELm5uXj88cdx8uRJZGVlISIiQupIRA+sZzsNlkb4w01Vv12RWa9DZDs9lyuTiOj7YGGLT+RfG/VRsc7mE088gXnz5uHbb7+Ft7e31LGILGZqf18sjegKN5UC97oeWiYD3FQKzH2sOT5dOgcpKSk2yUhVib4P5jk+O3b16lXMmTMHV65cweHDh4W87xXR/Zja3xc9fDTYmJKH5FP5kOH2xekVKu7HN9jPC/NDOqGHjwYDvb/Gk08+ibi4OPTpw/U6bYmTWySg0+nQtKljT2Het28f5s6di1mzZiE2NhaNGjWSOhKRVfXw0WDT1D64VqpDTOZF5P52AyVaPdSuKvi3booJvavegX3w4MHYvHkzRo4cie+++w6PPPKIhOmdi+iDDyGLT/QvvS63bt3CSy+9hLi4OK6zSU6pubvLfa+9OXr0aBQXFyMsLAzp6enw9fW1bjgCIP4+mMVnRyrW2ezTpw+ys7O5zibRfZg+fTqKi4sRGhqK9PR0tGrVSupIDk/0yS3CFp/IX/rdjEYjVq1ahf/93//FunXrEBUVJXUkIqEsXLgQhYWFCAsLQ0pKCjw9PaWO5NBEH3wIW3wif+l3On/+PKZNmwaZTMZ1NokewLJly1BYWIgRI0YgKSmpxhvfkmWIPrmFlzNI6Msvv0SfPn0QERGB//u//2PpET0AmUyG1atXw8/PD+PGjYNOp5M6ksMSfR8sZPGJ/mujqKgI0dHReOONNxAfH4//+Z//gULRsNUriOgPcrkcmzdvRpMmTTBt2jQYjUapIzkkFp8ERP7S09LSEBAQAI1Gg2PHjqF3795SRyJyKEqlEl9++SWuX7+Op59+GuY7FwIlixB9ngWLz0bKy8vxl7/8BZMnT8aGDRuwYcMGrrNJZCWurq745z//iZ9//hmvvPIKy8/CRNwH30nYyS0i/drIzc1FdHQ0WrdujaysLC45RmQD7u7uiIuLQ3BwMDw9PfHXv/5V6kgOQ/Ti44jPisxmMzZt2oSgoCDMnTsXe/fuZekR2VCzZs2QmJiITz75BB988IHUcRyG6PMshB3x2fuX/vvvv2POnDm4fPky0tPT4e/vL3UkIqfUunVrJCUlYdCgQdBoNLxO1gJE2AfXRcgRn73/2ti/fz8CAgLw6KOP4vvvv2fpEUns4YcfRnx8PBYtWoT9+/dLHUd4ohcfR3wWdOvWLbz88svYv38/vvrqKwwaNEjqSET0X927d8e3336LyMhI7Ny5E8HBwVJHEpZo8yzuJuSIzx6LLzMzE4GBgSgqKkJWVhZLj8gO9evXDzt27MDEiRORmZkpdRxh2eM+uD6EKz6z2QydTmc3t+kxGo14++23ER4ejmXLlmH79u3QaDRSxyKiWgwZMgQffvghRowYgdzcXKnjCMneTzfdi3CHOitKTy6XvrPPnz+P6dOnw2w248cff0SHDh2kjkRE92Hs2LEoKSnBsGHDkJ6ezr+79cQRn43Zyxe+Y8cO9OnTB+Hh4fjuu+/4F4dIMDNmzMDixYsRGhqKq1evSh1HKPayH24oIUd8Un7hxcXFWLBgAY4ePYoDBw4gMDBQsixE9GCef/75Krcz4mmK+8PJLTYm5S+NtLQ09OzZE2q1unIyCxGJ7bXXXkNwcDBGjhyJW7duSR1HCKKP+Fh896G8vBx//etfMWnSJKxfvx4bN27kOptEDkImk2HNmjXo2LEjxo8fj/Lycqkj2T0Wn43Z+gs/deoUBgwYgBMnTiArKwsjR4602WcTkW3I5XJ88skncHFx4e2M7sFoNMJoNEKlUkkdpcGELD5bHFuuWGdz4MCBmDNnDvbu3YuWLVta/XOJSBpKpRJfffUVCgoK8Oyzz/KODrWomGchk8mkjtJgQhaftUd8v//+O0aPHo3NmzcjPT0dzz77rND/kYno/lTczig7OxtLliyROo5dEv0wJyBg8Vl7VmdcXBwCAgLwyCOP4Pvvv0fXrl2t9llEZH+aNm2KuLg47Nu3D2+//bbUceyO6DM6AQEvZ7DWr41bt27hlVdewd69e7Fjxw6u40fkxJo3b47ExEQEBQVBo9Hg6aefljqS3XCEER+LD8Dx48cRHR2NgIAAZGdn81oeIkLbtm0rb2fk4eGByZMnSx3JLkh9LbUlOHXxGY1GrF69GqtWrcLatWsRHR1tke0SkWPo2LEj4uPjMXToUKjVakREREgdSXIc8UnAUseXL1y4gOnTp8NoNOLHH3+Er6/vg4cjIofz6KOP4ttvv8WoUaOwa9cuBAUFSR1JUo5QfMJNbrHEl/7VV18hMDAQw4YNQ3JyMkuPiOrUv39/fPnllxg/fjyOHz8udRxJcXKLBB7k+HJxcTGee+45/PDDD4iLi0OfPn0snI6IHNXQoUOxadMmjBgxAsnJyfDz85M6kiQ44pNAQ7/0Q4cOISAgAO7u7sjMzGTpEVG9jRs3DitWrMCwYcNw/vx5qeNIgpNbJKDVauu1TqZer8fy5cuxZcsWfPTRR4iMjLRiOiJydLNmzUJRURFCQ0ORnp4Ob29vqSPZlCOM+IQpvoJSHWKOXUSa/mEodE2Q//Vx+LdSY2KgD5q713y8+fTp04iOjoa3tzeysrK45BgRWcSiRYtQWFiI8PBwJCcnw8PDQ+pINsPis4HsC0XYkJKH1NP5AACdohWgB85mXYar8grWHDyNED8vzA/uhJ7tNABur7O5efNmLF26FK+//jqXHCMii3v99ddRWFiIyMhIxMfHO80dW1h8VrYt4yxWxOVCazCipvVitQYTACDx5FWknS7A0gh/hHVsgqeeegoXLlxAWloalxwjIquQyWRYt24dZsyYgYkTJ2L37t1o1KiR1LGszhFmddrt5JbbpZeDMn3NpXcnsxko0xvx973/Rq+Jf4a/vz8yMjJYekRkVXK5HFu2bIFCocCMGTOc4nZGjjDis8viy75QhBVxuSjTm2p8Xn/9Es6tGouCve9WebzcBDQeOBXRC//iFL+8iEh6KpUK33zzDa5cuYLnnnvO4W9n5AizOu2y+Dak5EFrqP2X0/XETXBp3bnG5/RmYGNKnrWiERFV4+rqij179uDo0aNYunSp1HGsiiM+Kygo1SH1dH6thzdvnkyF3LUJXDv0rPF5sxlIPpWPa6U6K6YkIqqqadOmOHDgAP75z39i1apVUsexGhafFcQcu1jrcybdLRSlb4fnn56qcxsyADGZtW+HiMgaWrRogcTERGzcuBGbN2+WOo5VOMLkFrub1Zl7pQQ6Q83n9orSvoB7z2FQqlvUuQ2twYTc325YIx4RUZ18fHyQlJSE4OBgeHh44Mknn5Q6kkVxxGcFJVpDjY+XXz0D7blsqB8bfZ/b0VsyFhHRfevUqRMOHDiAhQsXIj4+Xuo4FuUIk1vsbsSndq05kvb8TzAUX8XFjbMAAOZyLWA24beC59F61roatqOyak4iorr06NEDu3fvxpgxY7B7924MHDhQ6kgW4QgjPrsrPv9Wargor1Q73OkeEIYmXQdV/nPJD7EwFF9Fs7AF1bbhqpTDv3VTq2clIqrLgAED8MUXX2DcuHFISEhAQECA1JEemCMUn90d6pwQ6FPj43KVKxTunpV/ZCpXyJSNoGhcfY08M4AJvWveDhGRLYWFhWHDhg2IiIjA6dOnpY7zwDi5xQpauLsguIsXknKu1rliiyYousbHZTJgsJ9XrQtXExHZ2oQJE1BcXIxhw4bh0KFD8PER94c5R3xWsiCkE1yViga911WpwPyQThZORET0YObMmYOFCxciNDQU+fn5UsdpMBaflfRsp8HSCH+4qeoXz00lx9IIf/Tw0VgnGBHRA1i8eDHGjx+P4cOHo6SkROo4DeIIszrtsvgAYGp/XyyN6Ao3lQL3uqOQTAa4qRRYGtEVU/v72iQfEVFDvPHGG+jXrx8iIyNRVlYmdZx6c4QRn8xs5yuqnrhYhI0peUg+lQ8Z/rgVEXB79qYZt8/pzQ/pxJEeEQnBZDJh2rRpKC4uxu7du6FSiXP5Vdu2bfHDDz+gbdu2UkdpMLsvvgrXSnWIybyI3N9uoESrh9pVBf/WTTGhd+13YCcisld6vR7jxo2DWq3GF198Abncbg/AVdG8eXOcOnUKLVrUvYKWPROm+IiIHE1ZWRnCw8PRvXt3rF+/HrJ7ndexA02aNMHVq1fh7u4udZQGE+MnBhGRA3Jzc8PevXuRkZGBZcuWSR3nvjjC5Ba7u46PiMiZqNVqxMfHY9CgQfD09MTixYuljlQrg+H2WspKpdjVIXZ6IiIH4OXlhcTERAQFBUGj0WDOnDlSR6qRI8zoBFh8RER2oV27dlVuZzRhwgSpI1XjCMuVASw+IiK70blzZ8TFxSEsLAxqtRrDhg2TOlIVjjLi4+QWIiI7EhAQgNjYWEydOhX/+te/pI5TBYuPiIisYuDAgfj8888xduxYnDhxQuo4lRxhRifA4iMiskvh4eF4//33MXz4cOTl5UkdB4DjjPh4jo+IyE49+eSTKC4uRmhoKA4dOiT5MmEsPiIisrq5c+eiqKgIoaGhSEtLk3SpMEeZ1clDnUREdu7ll1/G6NGjJb+dkaOM+Fh8REQCePPNN9GnTx+MHj1astsZcXILERHZjEwmw/r169GqVStMmjQJer3e5hk44iMiIptSKBT4/PPPYTQaMXv2bJhMpnu/yYJYfEREZHMqlQo7d+7EuXPn8Pzzz8OWd5bj5BYiIpJE48aNsXfvXhw+fBivvfaazT7XUUZ8vJyBiEhAHh4eiI+PR1BQEDw9PbFo0SKrf6ajTG5h8RERCcrb2xtJSUmVtzOaNWuWVT+PIz4iIpJc+/btkZSUhJCQEHh4eGDcuHFW+yytVotmzZpZbfu2wuIjIhJcly5dsH///srbGQ0dOtQqn8PJLUREZDd69eqFXbt2ISoqChkZGVb5DEc51MniIyJyEEFBQfjss88wevRo/PTTTxbfPouPiIjsTkREBN577z0MHz4cv/76q0W3zVmdRERklyZNmlR5R4dDhw6hTZs2Ftmuo4z4WHxERA7o6aefRmFhYeXtjJo3b/7A23SU4uOhTiIiB7VkyRKMHDkSw4cPx40bNx54e5zVSUREdu+tt95Cr169MGbMGGi12gfaFkd8RERk92QyGTZu3AgvLy9ERUXBYDA0eFuOMrmFxUdE5OAqbmek1WoxZ86cBt/OiCM+IiISRqNGjbBr1y78+uuvWLRoUYNuZ8TiIyIioTRu3Bj79u1DWloa/v73v9f7/Y4yuYWXMxARORGNRlN5OyONRoPnn3/+vt/rKCM+Fh8RkZNp2bIlDh48WFl+M2bMuK/3sfiIiEhY7du3R0JCAgYPHgwPDw+MGTOmztebzWbodDoe6iQiInH5+/tj3759GD58OJo2bYohQ4bU+lq9Xg+lUgmFQmHDhNbByS1ERE4sMDAQMTExiIqKwpEjR2p9naMc5gQAmbkhc1qJiMih7N+/H3PmzMHBgwfRvXv3yscLSnWIOXYRWWfzsS/hICaMHgH/VmpMDPRBc3cxD3uy+IiICACwY8cOvPLKK0hNTcUNVTNsSMlD6ul8AIDO8MdF765KOcwAQvy8MD+4E3q200gTuIFYfEREVOmDDz7AO7Hfo1H/ySg3mlFXQ8hkgKtSgaUR/pja39dmGR8UJ7cQEVGlpr2GQ3G+LXSGe4+JzGagTG/EirgcABCm/DjiIyIiAED2hSJM3pyBMr2xyuPGshu4FrcO2rPHIXdTwzN4Bpp0C6nyGjeVAl/P648ePhrbBW4gzuokIiIAwIaUPGgNxmqPX0/8ADKFCj4Lt6FF5Eu4lrgR5fnnqrxGazBiY0qeraI+EBYfERGhoFSH1NP51c7pmcq1uHXqX9AMmgp5Ize4tuuGxp364ea/k6u8zmwGkk/l41qpzoapG4bFR0REiDl2scbHDdcvQSZXQNWsbeVjKu+HoL9rxAcAMgAxmTVvx56w+IiICLlXSqpcslDBpC+DzMWtymNyl8YwlZdVe63WYELubzesltFSWHxERIQSbc13Zper3GDWVS05s+4W5I3canx9iVZv8WyWxuIjIiKoXWu+uk3ZrC3MJiP01y9VPlb++3+g8upQy3ZUVslnSSw+IiKCfys1XJTVK0HeyBWN/R5HUfp2mMq10F48iVt5R9Ck2+Bqr3VVyuHfuqkt4j4QFh8REWFCoE+tzzUbNh9mQzkuvh+Ngj2r0HzYfDSqYcRnBjChd+3bsRdcuYWIiNDC3QXBXbyQlHO12iUNCrem8B7/tzrfL5MBg/28hFi4miM+IiICACwI6QRXZcPut+eqVGB+SCcLJ7IOFh8REQEAerbTYGmEP9xU9asGN5UcSyP8hViuDOChTiIiukPFQtMr4nKhNRgd8u4MXKSaiIiqOXGxCBtT8pB8Kh8y3L44vULF/fgG+3lhfkgnYUZ6FVh8RERUq2ulOsRkXkTubzdQotVD7aqCf+ummNCbd2AnIiISAie3EBGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU2HxERGRU/l/CaPElvp8k78AAAAASUVORK5CYII=",
      "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": 36,
   "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": 37,
   "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": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0, 1): 1.0,\n",
       " (0, 2): 4.0,\n",
       " (1, 0): 1.0,\n",
       " (1, 2): 4.0,\n",
       " (2, 0): 4.0,\n",
       " (2, 1): 4.0,\n",
       " (2, 3): 9.0,\n",
       " (3, 2): 9.0,\n",
       " (3, 4): 4.0,\n",
       " (3, 5): 4.0,\n",
       " (4, 3): 4.0,\n",
       " (4, 5): 1.0,\n",
       " (5, 3): 4.0,\n",
       " (5, 4): 1.0}"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C=brandes(V, A)\n",
    "{x:y for x,y in C.items() if y!=0}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "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": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.edge_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
}