class08_bc_python3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CSX46 Class Session 8: Betweenness Centrality\n",
    "\n",
    "Objective: implement betweenness centrality based on Newman's algorithm.\n",
    "Test it out on a small Barabasi-Albert graph. Compare to the results obtained using the method `igraph.Graph.betweenness`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import queue\n",
    "import random\n",
    "import igraph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def single_vertex_bfs_with_paths_and_weights(s, g):\n",
    "    # s is the integer index of the vertex that we are at\n",
    "    # g is the graph in adjacency list format\n",
    "    N = len(g)\n",
    "    dists = [-1]*N\n",
    "    dists[s] = 0\n",
    "    # dists is a list (length N) of the known distances to each vertex\n",
    "    weights = [0.]*N\n",
    "    weights[s] = 1.\n",
    "    # weights is a list (length N) of counts of the number of distinct \n",
    "    # backpaths from each vertex to s\n",
    "    paths = [[]]*N\n",
    "    # paths is a list (length N) of the lists of backpath edges toward s\n",
    "    work = queue.Queue()\n",
    "    work.put(s)\n",
    "    orders = []\n",
    "    while not work.empty():\n",
    "        u = work.get()\n",
    "        u_neighbors = g[u]\n",
    "        for v in u_neighbors:\n",
    "            if dists[v] < 0:  # we haven't visited this vertex before\n",
    "                dists[v] = dists[u] + 1\n",
    "                weights[v] = weights[u]\n",
    "                work.put(v)\n",
    "                orders = [v] + orders\n",
    "                paths[v] = paths[v] + [u]\n",
    "            else:             # we have visited this vertex before\n",
    "                if dists[v] == dists[u] + 1:\n",
    "                    paths[v] = paths[v] + [u]\n",
    "                    weights[v] = weights[u] + weights[v]\n",
    "    return [dists, paths, weights, orders]\n",
    "\n",
    "def all_vertices_betweenness_centrality(g):\n",
    "    N = len(g)\n",
    "    final_scores = [0]*N\n",
    "    for s in range(0,N):\n",
    "        ret_vals = single_vertex_bfs_with_paths_and_weights(s, g)\n",
    "        dists = ret_vals[0]\n",
    "        paths = ret_vals[1]\n",
    "        weights = ret_vals[2]\n",
    "        orders = ret_vals[3]\n",
    "        scores = [1]*N\n",
    "        for v in orders:\n",
    "            neighbors = paths[v]\n",
    "            for neighbor in neighbors:\n",
    "                ratio = weights[neighbor]/weights[v]\n",
    "                scores[neighbor] = scores[neighbor] + scores[v]*ratio\n",
    "        for u in range(0,N):\n",
    "            final_scores[u] = final_scores[u] + scores[u]\n",
    "    for s in range(0,N):\n",
    "        final_scores[s] = (final_scores[s] - 2*N + 1)/2.0\n",
    "    return final_scores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"200pt\" height=\"200pt\" viewBox=\"0 0 200 200\" version=\"1.1\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-0\">\n",
       "<path style=\"stroke:none;\" d=\"M 0.703125 2.46875 L 0.703125 -9.875 L 7.703125 -9.875 L 7.703125 2.46875 Z M 1.484375 1.703125 L 6.921875 1.703125 L 6.921875 -9.078125 L 1.484375 -9.078125 Z M 1.484375 1.703125 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-1\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.453125 -9.296875 C 3.742188 -9.296875 3.207031 -8.945312 2.84375 -8.25 C 2.488281 -7.550781 2.3125 -6.5 2.3125 -5.09375 C 2.3125 -3.695312 2.488281 -2.644531 2.84375 -1.9375 C 3.207031 -1.238281 3.742188 -0.890625 4.453125 -0.890625 C 5.171875 -0.890625 5.707031 -1.238281 6.0625 -1.9375 C 6.414062 -2.644531 6.59375 -3.695312 6.59375 -5.09375 C 6.59375 -6.5 6.414062 -7.550781 6.0625 -8.25 C 5.707031 -8.945312 5.171875 -9.296875 4.453125 -9.296875 Z M 4.453125 -10.390625 C 5.597656 -10.390625 6.472656 -9.9375 7.078125 -9.03125 C 7.679688 -8.125 7.984375 -6.8125 7.984375 -5.09375 C 7.984375 -3.375 7.679688 -2.0625 7.078125 -1.15625 C 6.472656 -0.25 5.597656 0.203125 4.453125 0.203125 C 3.304688 0.203125 2.429688 -0.25 1.828125 -1.15625 C 1.222656 -2.0625 0.921875 -3.375 0.921875 -5.09375 C 0.921875 -6.8125 1.222656 -8.125 1.828125 -9.03125 C 2.429688 -9.9375 3.304688 -10.390625 4.453125 -10.390625 Z M 4.453125 -10.390625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-2\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.734375 -1.15625 L 4 -1.15625 L 4 -8.953125 L 1.53125 -8.453125 L 1.53125 -9.71875 L 3.984375 -10.203125 L 5.359375 -10.203125 L 5.359375 -1.15625 L 7.609375 -1.15625 L 7.609375 0 L 1.734375 0 Z M 1.734375 -1.15625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-3\">\n",
       "<path style=\"stroke:none;\" d=\"M 2.6875 -1.15625 L 7.5 -1.15625 L 7.5 0 L 1.03125 0 L 1.03125 -1.15625 C 1.550781 -1.695312 2.265625 -2.425781 3.171875 -3.34375 C 4.078125 -4.257812 4.644531 -4.847656 4.875 -5.109375 C 5.3125 -5.609375 5.617188 -6.03125 5.796875 -6.375 C 5.972656 -6.71875 6.0625 -7.054688 6.0625 -7.390625 C 6.0625 -7.929688 5.867188 -8.375 5.484375 -8.71875 C 5.109375 -9.0625 4.613281 -9.234375 4 -9.234375 C 3.570312 -9.234375 3.117188 -9.15625 2.640625 -9 C 2.160156 -8.851562 1.644531 -8.625 1.09375 -8.3125 L 1.09375 -9.71875 C 1.644531 -9.9375 2.160156 -10.101562 2.640625 -10.21875 C 3.128906 -10.332031 3.578125 -10.390625 3.984375 -10.390625 C 5.035156 -10.390625 5.875 -10.125 6.5 -9.59375 C 7.132812 -9.070312 7.453125 -8.367188 7.453125 -7.484375 C 7.453125 -7.054688 7.375 -6.65625 7.21875 -6.28125 C 7.0625 -5.90625 6.773438 -5.460938 6.359375 -4.953125 C 6.242188 -4.828125 5.878906 -4.445312 5.265625 -3.8125 C 4.660156 -3.175781 3.800781 -2.289062 2.6875 -1.15625 Z M 2.6875 -1.15625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-4\">\n",
       "<path style=\"stroke:none;\" d=\"M 5.6875 -5.5 C 6.34375 -5.363281 6.851562 -5.070312 7.21875 -4.625 C 7.59375 -4.175781 7.78125 -3.625 7.78125 -2.96875 C 7.78125 -1.957031 7.429688 -1.175781 6.734375 -0.625 C 6.046875 -0.0703125 5.066406 0.203125 3.796875 0.203125 C 3.367188 0.203125 2.925781 0.15625 2.46875 0.0625 C 2.019531 -0.0195312 1.550781 -0.144531 1.0625 -0.3125 L 1.0625 -1.640625 C 1.445312 -1.421875 1.867188 -1.253906 2.328125 -1.140625 C 2.785156 -1.023438 3.257812 -0.96875 3.75 -0.96875 C 4.613281 -0.96875 5.269531 -1.132812 5.71875 -1.46875 C 6.175781 -1.8125 6.40625 -2.3125 6.40625 -2.96875 C 6.40625 -3.570312 6.191406 -4.039062 5.765625 -4.375 C 5.347656 -4.71875 4.765625 -4.890625 4.015625 -4.890625 L 2.828125 -4.890625 L 2.828125 -6.015625 L 4.078125 -6.015625 C 4.753906 -6.015625 5.269531 -6.148438 5.625 -6.421875 C 5.988281 -6.703125 6.171875 -7.097656 6.171875 -7.609375 C 6.171875 -8.128906 5.984375 -8.53125 5.609375 -8.8125 C 5.242188 -9.09375 4.710938 -9.234375 4.015625 -9.234375 C 3.640625 -9.234375 3.234375 -9.191406 2.796875 -9.109375 C 2.367188 -9.023438 1.894531 -8.894531 1.375 -8.71875 L 1.375 -9.953125 C 1.894531 -10.097656 2.382812 -10.207031 2.84375 -10.28125 C 3.300781 -10.351562 3.734375 -10.390625 4.140625 -10.390625 C 5.191406 -10.390625 6.019531 -10.148438 6.625 -9.671875 C 7.238281 -9.203125 7.546875 -8.5625 7.546875 -7.75 C 7.546875 -7.175781 7.382812 -6.695312 7.0625 -6.3125 C 6.738281 -5.925781 6.28125 -5.65625 5.6875 -5.5 Z M 5.6875 -5.5 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-5\">\n",
       "<path style=\"stroke:none;\" d=\"M 5.296875 -9 L 1.8125 -3.5625 L 5.296875 -3.5625 Z M 4.921875 -10.203125 L 6.671875 -10.203125 L 6.671875 -3.5625 L 8.125 -3.5625 L 8.125 -2.40625 L 6.671875 -2.40625 L 6.671875 0 L 5.296875 0 L 5.296875 -2.40625 L 0.6875 -2.40625 L 0.6875 -3.734375 Z M 4.921875 -10.203125 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-6\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.515625 -10.203125 L 6.9375 -10.203125 L 6.9375 -9.046875 L 2.78125 -9.046875 L 2.78125 -6.546875 C 2.976562 -6.609375 3.175781 -6.65625 3.375 -6.6875 C 3.570312 -6.726562 3.773438 -6.75 3.984375 -6.75 C 5.117188 -6.75 6.019531 -6.4375 6.6875 -5.8125 C 7.351562 -5.1875 7.6875 -4.34375 7.6875 -3.28125 C 7.6875 -2.175781 7.34375 -1.316406 6.65625 -0.703125 C 5.976562 -0.0976562 5.015625 0.203125 3.765625 0.203125 C 3.335938 0.203125 2.898438 0.164062 2.453125 0.09375 C 2.015625 0.0195312 1.554688 -0.0859375 1.078125 -0.234375 L 1.078125 -1.625 C 1.492188 -1.40625 1.921875 -1.238281 2.359375 -1.125 C 2.796875 -1.019531 3.253906 -0.96875 3.734375 -0.96875 C 4.523438 -0.96875 5.148438 -1.171875 5.609375 -1.578125 C 6.066406 -1.992188 6.296875 -2.5625 6.296875 -3.28125 C 6.296875 -3.988281 6.066406 -4.546875 5.609375 -4.953125 C 5.148438 -5.367188 4.523438 -5.578125 3.734375 -5.578125 C 3.367188 -5.578125 3 -5.535156 2.625 -5.453125 C 2.257812 -5.378906 1.890625 -5.253906 1.515625 -5.078125 Z M 1.515625 -10.203125 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-7\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.625 -5.65625 C 4 -5.65625 3.503906 -5.441406 3.140625 -5.015625 C 2.785156 -4.585938 2.609375 -4.007812 2.609375 -3.28125 C 2.609375 -2.539062 2.785156 -1.957031 3.140625 -1.53125 C 3.503906 -1.101562 4 -0.890625 4.625 -0.890625 C 5.238281 -0.890625 5.726562 -1.101562 6.09375 -1.53125 C 6.457031 -1.957031 6.640625 -2.539062 6.640625 -3.28125 C 6.640625 -4.007812 6.457031 -4.585938 6.09375 -5.015625 C 5.726562 -5.441406 5.238281 -5.65625 4.625 -5.65625 Z M 7.359375 -9.984375 L 7.359375 -8.71875 C 7.015625 -8.882812 6.664062 -9.007812 6.3125 -9.09375 C 5.957031 -9.1875 5.609375 -9.234375 5.265625 -9.234375 C 4.347656 -9.234375 3.648438 -8.925781 3.171875 -8.3125 C 2.691406 -7.695312 2.421875 -6.765625 2.359375 -5.515625 C 2.617188 -5.910156 2.953125 -6.210938 3.359375 -6.421875 C 3.765625 -6.640625 4.210938 -6.75 4.703125 -6.75 C 5.722656 -6.75 6.53125 -6.4375 7.125 -5.8125 C 7.726562 -5.1875 8.03125 -4.34375 8.03125 -3.28125 C 8.03125 -2.226562 7.71875 -1.382812 7.09375 -0.75 C 6.476562 -0.113281 5.65625 0.203125 4.625 0.203125 C 3.4375 0.203125 2.53125 -0.25 1.90625 -1.15625 C 1.289062 -2.0625 0.984375 -3.375 0.984375 -5.09375 C 0.984375 -6.707031 1.363281 -7.992188 2.125 -8.953125 C 2.894531 -9.910156 3.921875 -10.390625 5.203125 -10.390625 C 5.554688 -10.390625 5.90625 -10.351562 6.25 -10.28125 C 6.601562 -10.21875 6.972656 -10.117188 7.359375 -9.984375 Z M 7.359375 -9.984375 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-8\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.15625 -10.203125 L 7.71875 -10.203125 L 7.71875 -9.625 L 4 0 L 2.5625 0 L 6.046875 -9.046875 L 1.15625 -9.046875 Z M 1.15625 -10.203125 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-9\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.453125 -4.84375 C 3.796875 -4.84375 3.28125 -4.664062 2.90625 -4.3125 C 2.53125 -3.96875 2.34375 -3.488281 2.34375 -2.875 C 2.34375 -2.257812 2.53125 -1.773438 2.90625 -1.421875 C 3.28125 -1.066406 3.796875 -0.890625 4.453125 -0.890625 C 5.109375 -0.890625 5.625 -1.066406 6 -1.421875 C 6.375 -1.773438 6.5625 -2.257812 6.5625 -2.875 C 6.5625 -3.488281 6.375 -3.96875 6 -4.3125 C 5.625 -4.664062 5.109375 -4.84375 4.453125 -4.84375 Z M 3.0625 -5.4375 C 2.476562 -5.582031 2.019531 -5.859375 1.6875 -6.265625 C 1.351562 -6.671875 1.1875 -7.164062 1.1875 -7.75 C 1.1875 -8.5625 1.476562 -9.203125 2.0625 -9.671875 C 2.644531 -10.148438 3.441406 -10.390625 4.453125 -10.390625 C 5.460938 -10.390625 6.257812 -10.148438 6.84375 -9.671875 C 7.425781 -9.203125 7.71875 -8.5625 7.71875 -7.75 C 7.71875 -7.164062 7.550781 -6.671875 7.21875 -6.265625 C 6.882812 -5.859375 6.425781 -5.582031 5.84375 -5.4375 C 6.507812 -5.28125 7.023438 -4.972656 7.390625 -4.515625 C 7.765625 -4.066406 7.953125 -3.519531 7.953125 -2.875 C 7.953125 -1.882812 7.648438 -1.125 7.046875 -0.59375 C 6.441406 -0.0625 5.578125 0.203125 4.453125 0.203125 C 3.328125 0.203125 2.460938 -0.0625 1.859375 -0.59375 C 1.253906 -1.125 0.953125 -1.882812 0.953125 -2.875 C 0.953125 -3.519531 1.140625 -4.066406 1.515625 -4.515625 C 1.890625 -4.972656 2.40625 -5.28125 3.0625 -5.4375 Z M 2.5625 -7.609375 C 2.5625 -7.085938 2.726562 -6.675781 3.0625 -6.375 C 3.394531 -6.082031 3.859375 -5.9375 4.453125 -5.9375 C 5.046875 -5.9375 5.507812 -6.082031 5.84375 -6.375 C 6.175781 -6.675781 6.34375 -7.085938 6.34375 -7.609375 C 6.34375 -8.140625 6.175781 -8.550781 5.84375 -8.84375 C 5.507812 -9.144531 5.046875 -9.296875 4.453125 -9.296875 C 3.859375 -9.296875 3.394531 -9.144531 3.0625 -8.84375 C 2.726562 -8.550781 2.5625 -8.140625 2.5625 -7.609375 Z M 2.5625 -7.609375 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-10\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.53125 -0.21875 L 1.53125 -1.46875 C 1.882812 -1.300781 2.238281 -1.175781 2.59375 -1.09375 C 2.945312 -1.007812 3.296875 -0.96875 3.640625 -0.96875 C 4.546875 -0.96875 5.238281 -1.269531 5.71875 -1.875 C 6.207031 -2.488281 6.484375 -3.421875 6.546875 -4.671875 C 6.285156 -4.285156 5.953125 -3.984375 5.546875 -3.765625 C 5.140625 -3.554688 4.691406 -3.453125 4.203125 -3.453125 C 3.179688 -3.453125 2.367188 -3.757812 1.765625 -4.375 C 1.171875 -5 0.875 -5.847656 0.875 -6.921875 C 0.875 -7.960938 1.179688 -8.800781 1.796875 -9.4375 C 2.421875 -10.070312 3.25 -10.390625 4.28125 -10.390625 C 5.46875 -10.390625 6.367188 -9.9375 6.984375 -9.03125 C 7.609375 -8.125 7.921875 -6.8125 7.921875 -5.09375 C 7.921875 -3.488281 7.539062 -2.203125 6.78125 -1.234375 C 6.019531 -0.273438 4.992188 0.203125 3.703125 0.203125 C 3.347656 0.203125 2.992188 0.164062 2.640625 0.09375 C 2.285156 0.03125 1.914062 -0.0703125 1.53125 -0.21875 Z M 4.28125 -4.546875 C 4.90625 -4.546875 5.394531 -4.753906 5.75 -5.171875 C 6.113281 -5.597656 6.296875 -6.179688 6.296875 -6.921875 C 6.296875 -7.648438 6.113281 -8.226562 5.75 -8.65625 C 5.394531 -9.082031 4.90625 -9.296875 4.28125 -9.296875 C 3.664062 -9.296875 3.175781 -9.082031 2.8125 -8.65625 C 2.445312 -8.226562 2.265625 -7.648438 2.265625 -6.921875 C 2.265625 -6.179688 2.445312 -5.597656 2.8125 -5.171875 C 3.175781 -4.753906 3.664062 -4.546875 4.28125 -4.546875 Z M 4.28125 -4.546875 \"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface20\">\n",
       "<rect x=\"0\" y=\"0\" width=\"200\" height=\"200\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1;stroke:none;\"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 62.8125 121.882812 L 105.226562 142.5 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 62.8125 121.882812 L 20 112.734375 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 62.8125 121.882812 L 27.632812 156.300781 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 62.8125 121.882812 L 50.296875 68.730469 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 105.226562 142.5 L 143.636719 161.082031 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 62.8125 121.882812 L 60.8125 174.285156 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 50.296875 68.730469 L 40.433594 20 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 62.8125 121.882812 L 92.597656 85.023438 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 143.636719 161.082031 L 180 180 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 72.8125 121.882812 C 72.8125 127.40625 68.335938 131.882812 62.8125 131.882812 C 57.289062 131.882812 52.8125 127.40625 52.8125 121.882812 C 52.8125 116.359375 57.289062 111.882812 62.8125 111.882812 C 68.335938 111.882812 72.8125 116.359375 72.8125 121.882812 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 115.226562 142.5 C 115.226562 148.023438 110.75 152.5 105.226562 152.5 C 99.703125 152.5 95.226562 148.023438 95.226562 142.5 C 95.226562 136.980469 99.703125 132.5 105.226562 132.5 C 110.75 132.5 115.226562 136.980469 115.226562 142.5 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 30 112.734375 C 30 118.257812 25.523438 122.734375 20 122.734375 C 14.476562 122.734375 10 118.257812 10 112.734375 C 10 107.214844 14.476562 102.734375 20 102.734375 C 25.523438 102.734375 30 107.214844 30 112.734375 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 37.632812 156.300781 C 37.632812 161.824219 33.15625 166.300781 27.632812 166.300781 C 22.109375 166.300781 17.632812 161.824219 17.632812 156.300781 C 17.632812 150.777344 22.109375 146.300781 27.632812 146.300781 C 33.15625 146.300781 37.632812 150.777344 37.632812 156.300781 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 60.296875 68.730469 C 60.296875 74.253906 55.820312 78.730469 50.296875 78.730469 C 44.773438 78.730469 40.296875 74.253906 40.296875 68.730469 C 40.296875 63.207031 44.773438 58.730469 50.296875 58.730469 C 55.820312 58.730469 60.296875 63.207031 60.296875 68.730469 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 153.636719 161.082031 C 153.636719 166.601562 149.15625 171.082031 143.636719 171.082031 C 138.113281 171.082031 133.636719 166.601562 133.636719 161.082031 C 133.636719 155.558594 138.113281 151.082031 143.636719 151.082031 C 149.15625 151.082031 153.636719 155.558594 153.636719 161.082031 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 70.8125 174.285156 C 70.8125 179.804688 66.335938 184.285156 60.8125 184.285156 C 55.289062 184.285156 50.8125 179.804688 50.8125 174.285156 C 50.8125 168.761719 55.289062 164.285156 60.8125 164.285156 C 66.335938 164.285156 70.8125 168.761719 70.8125 174.285156 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 50.433594 20 C 50.433594 25.523438 45.957031 30 40.433594 30 C 34.910156 30 30.433594 25.523438 30.433594 20 C 30.433594 14.476562 34.910156 10 40.433594 10 C 45.957031 10 50.433594 14.476562 50.433594 20 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 102.597656 85.023438 C 102.597656 90.546875 98.117188 95.023438 92.597656 95.023438 C 87.074219 95.023438 82.597656 90.546875 82.597656 85.023438 C 82.597656 79.5 87.074219 75.023438 92.597656 75.023438 C 98.117188 75.023438 102.597656 79.5 102.597656 85.023438 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 190 180 C 190 185.523438 185.523438 190 180 190 C 174.476562 190 170 185.523438 170 180 C 170 174.476562 174.476562 170 180 170 C 185.523438 170 190 174.476562 190 180 \"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-1\" x=\"58.363281\" y=\"128.730469\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-2\" x=\"100.652344\" y=\"149.253906\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-3\" x=\"15.734375\" y=\"119.582031\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-4\" x=\"23.207031\" y=\"163.148438\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-5\" x=\"45.894531\" y=\"75.484375\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-6\" x=\"139.253906\" y=\"167.835938\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-7\" x=\"56.308594\" y=\"181.128906\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-8\" x=\"36.003906\" y=\"26.753906\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-9\" x=\"88.144531\" y=\"91.871094\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-10\" x=\"175.597656\" y=\"186.847656\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<igraph.drawing.Plot at 0x7fe94816f780>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random.seed(1337)\n",
    "g = igraph.Graph.Barabasi(10)   \n",
    "g_adjlist = g.get_adjlist()\n",
    "igraph.drawing.plot(g, bbox=[0,0,200,200], vertex_label=list(range(0, 10)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[32.0, 14.0, 0.0, 0.0, 8.0, 8.0, 0.0, 0.0, 0.0, 0.0]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_vertices_betweenness_centrality(g_adjlist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[32.0, 14.0, 0.0, 0.0, 8.0, 8.0, 0.0, 0.0, 0.0, 0.0]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.betweenness(directed=False)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}