class18_markovclust_python3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CSX46 Class Session 18: Markov Clustering\n",
    "\n",
    "In today's notebook we will analyze a small network described in a file `test.dot` in an edge-list format called `dot` (from the GraphViz command-line toolset for graph visualization, which can be accessed from python using the `pygraphviz` python package). We will implement a Markov clustering algorithm and run it on the graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pygraphviz\n",
    "import igraph\n",
    "import numpy\n",
    "import pandas\n",
    "import csv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the static clsas method `pygrahpviz.AGraph` to load the file `shared/test.dot` and return an object of class `pygraphviz.agraph.AGraph` containing an undirected graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "pygraphviz.agraph.AGraph"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_graph = pygraphviz.AGraph(\"shared/test.dot\")\n",
    "type(test_graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get the set of edges (as a list of pairlists) using the `pygraphviz.agraph.AGraph.edges()` method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('1', '2'), ('1', '6'), ('1', '7'), ('2', '7'), ('2', '4')]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edges = test_graph.edges()\n",
    "edges[0:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make an `igraph.Graph` object from the `edges` list using the static method `igraph.Graph.TupleList()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'IGRAPH UN-- 13 26 -- \\n+ attr: name (v)'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_igraph = igraph.Graph.TupleList(edges)\n",
    "test_igraph.summary()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Draw a plot of the graph using the function `igraph.drawing.plot()`. Use the `igraph.Graph.vs()` to get a VertexSet and index into it using `name`; that will give you a list of vertex names to pass to the `plot` function as argument `vertex_label`. How many distinct network communities do you expect to get from Markov clustering?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "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=\"300pt\" height=\"300pt\" viewBox=\"0 0 300 300\" 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 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-2\">\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-3\">\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-4\">\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-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 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-7\">\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-8\">\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-9\">\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",
       "<symbol overflow=\"visible\" id=\"glyph0-10\">\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",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface2\">\n",
       "<rect x=\"0\" y=\"0\" width=\"300\" height=\"300\" 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 20 130.496094 L 20.355469 230.6875 \"/>\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 20 130.496094 L 68.292969 147.683594 \"/>\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 20 130.496094 L 57.105469 194.558594 \"/>\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 20.355469 230.6875 L 57.105469 194.558594 \"/>\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 20.355469 230.6875 L 81.523438 246.378906 \"/>\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 20.355469 230.6875 L 48.574219 280 \"/>\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 68.292969 147.683594 L 57.105469 194.558594 \"/>\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 68.292969 147.683594 L 81.523438 246.378906 \"/>\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 57.105469 194.558594 L 81.523438 246.378906 \"/>\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 81.523438 246.378906 L 109.769531 170.527344 \"/>\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 68.292969 147.683594 L 48.574219 280 \"/>\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 57.105469 194.558594 L 48.574219 280 \"/>\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 81.523438 246.378906 L 48.574219 280 \"/>\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 68.292969 147.683594 L 109.769531 170.527344 \"/>\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 57.105469 194.558594 L 109.769531 170.527344 \"/>\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 109.769531 170.527344 L 154.890625 135.621094 \"/>\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 154.890625 135.621094 L 200.09375 103.417969 \"/>\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 200.09375 103.417969 L 248.378906 131.410156 \"/>\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 200.09375 103.417969 L 229.605469 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 200.09375 103.417969 L 241.871094 73.507812 \"/>\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 248.378906 131.410156 L 229.605469 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 248.378906 131.410156 L 241.871094 73.507812 \"/>\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 248.378906 131.410156 L 280 46.714844 \"/>\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 229.605469 20 L 241.871094 73.507812 \"/>\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 229.605469 20 L 280 46.714844 \"/>\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 241.871094 73.507812 L 280 46.714844 \"/>\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 130.496094 C 30 136.019531 25.523438 140.496094 20 140.496094 C 14.476562 140.496094 10 136.019531 10 130.496094 C 10 124.972656 14.476562 120.496094 20 120.496094 C 25.523438 120.496094 30 124.972656 30 130.496094 \"/>\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.355469 230.6875 C 30.355469 236.210938 25.878906 240.6875 20.355469 240.6875 C 14.835938 240.6875 10.355469 236.210938 10.355469 230.6875 C 10.355469 225.164062 14.835938 220.6875 20.355469 220.6875 C 25.878906 220.6875 30.355469 225.164062 30.355469 230.6875 \"/>\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 78.292969 147.683594 C 78.292969 153.207031 73.816406 157.683594 68.292969 157.683594 C 62.769531 157.683594 58.292969 153.207031 58.292969 147.683594 C 58.292969 142.164062 62.769531 137.683594 68.292969 137.683594 C 73.816406 137.683594 78.292969 142.164062 78.292969 147.683594 \"/>\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 67.105469 194.558594 C 67.105469 200.082031 62.628906 204.558594 57.105469 204.558594 C 51.582031 204.558594 47.105469 200.082031 47.105469 194.558594 C 47.105469 189.035156 51.582031 184.558594 57.105469 184.558594 C 62.628906 184.558594 67.105469 189.035156 67.105469 194.558594 \"/>\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 91.523438 246.378906 C 91.523438 251.902344 87.046875 256.378906 81.523438 256.378906 C 76 256.378906 71.523438 251.902344 71.523438 246.378906 C 71.523438 240.855469 76 236.378906 81.523438 236.378906 C 87.046875 236.378906 91.523438 240.855469 91.523438 246.378906 \"/>\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 58.574219 280 C 58.574219 285.523438 54.097656 290 48.574219 290 C 43.050781 290 38.574219 285.523438 38.574219 280 C 38.574219 274.476562 43.050781 270 48.574219 270 C 54.097656 270 58.574219 274.476562 58.574219 280 \"/>\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 119.769531 170.527344 C 119.769531 176.050781 115.292969 180.527344 109.769531 180.527344 C 104.246094 180.527344 99.769531 176.050781 99.769531 170.527344 C 99.769531 165.003906 104.246094 160.527344 109.769531 160.527344 C 115.292969 160.527344 119.769531 165.003906 119.769531 170.527344 \"/>\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 164.890625 135.621094 C 164.890625 141.144531 160.414062 145.621094 154.890625 145.621094 C 149.367188 145.621094 144.890625 141.144531 144.890625 135.621094 C 144.890625 130.101562 149.367188 125.621094 154.890625 125.621094 C 160.414062 125.621094 164.890625 130.101562 164.890625 135.621094 \"/>\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 210.09375 103.417969 C 210.09375 108.941406 205.617188 113.417969 200.09375 113.417969 C 194.570312 113.417969 190.09375 108.941406 190.09375 103.417969 C 190.09375 97.894531 194.570312 93.417969 200.09375 93.417969 C 205.617188 93.417969 210.09375 97.894531 210.09375 103.417969 \"/>\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 258.378906 131.410156 C 258.378906 136.933594 253.902344 141.410156 248.378906 141.410156 C 242.855469 141.410156 238.378906 136.933594 238.378906 131.410156 C 238.378906 125.886719 242.855469 121.410156 248.378906 121.410156 C 253.902344 121.410156 258.378906 125.886719 258.378906 131.410156 \"/>\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 239.605469 20 C 239.605469 25.523438 235.128906 30 229.605469 30 C 224.082031 30 219.605469 25.523438 219.605469 20 C 219.605469 14.476562 224.082031 10 229.605469 10 C 235.128906 10 239.605469 14.476562 239.605469 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 251.871094 73.507812 C 251.871094 79.03125 247.394531 83.507812 241.871094 83.507812 C 236.347656 83.507812 231.871094 79.03125 231.871094 73.507812 C 231.871094 67.984375 236.347656 63.507812 241.871094 63.507812 C 247.394531 63.507812 251.871094 67.984375 251.871094 73.507812 \"/>\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 290 46.714844 C 290 52.238281 285.523438 56.714844 280 56.714844 C 274.476562 56.714844 270 52.238281 270 46.714844 C 270 41.191406 274.476562 36.714844 280 36.714844 C 285.523438 36.714844 290 41.191406 290 46.714844 \"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-1\" x=\"15.421875\" y=\"137.25\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-2\" x=\"16.089844\" y=\"237.535156\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-3\" x=\"63.792969\" y=\"154.53125\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-4\" x=\"52.675781\" y=\"201.3125\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-5\" x=\"77.121094\" y=\"253.132812\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-6\" x=\"44.148438\" y=\"286.847656\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-7\" x=\"105.386719\" y=\"177.28125\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-8\" x=\"150.441406\" y=\"142.46875\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-9\" x=\"195.691406\" y=\"110.265625\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-1\" x=\"239.167969\" y=\"138.257812\"/>\n",
       "  <use xlink:href=\"#glyph0-10\" x=\"248.075195\" y=\"138.257812\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-1\" x=\"220.628906\" y=\"26.847656\"/>\n",
       "  <use xlink:href=\"#glyph0-2\" x=\"229.536133\" y=\"26.847656\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-1\" x=\"232.753906\" y=\"80.351562\"/>\n",
       "  <use xlink:href=\"#glyph0-6\" x=\"241.661133\" y=\"80.351562\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-1\" x=\"270.96875\" y=\"53.46875\"/>\n",
       "  <use xlink:href=\"#glyph0-1\" x=\"279.875977\" y=\"53.46875\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<igraph.drawing.Plot at 0x7f78fe441630>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "igraph.drawing.plot(test_igraph, bbox=[0, 0, 300, 300], vertex_label=test_igraph.vs()['name'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the fun part. Implement a markov cluster function!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def markov_cluster(graph):\n",
    "    # you will need to construct an adjacency matrix; use the get_adjacency() method and then \n",
    "    # reference the '.data' attribute of the object (of class igraph.datatypes.Matrix) \n",
    "    # that was returned from `get_adjacency()`.\n",
    "    adj_mat = numpy.matrix(graph.get_adjacency().data)\n",
    "    \n",
    "    # need to know the number of vertices; use shape (and indexing to element zero) to get that\n",
    "    N = adj_mat.shape[0]\n",
    "    \n",
    "    # you will need to compute the vertex degrees as a numpy array\n",
    "    vertex_degrees = numpy.array(graph.degree())\n",
    "    \n",
    "    # make a transition matrix in two steps:\n",
    "    # first, compute the sum of the adjacency matrix and a parity matrix\n",
    "    #   (the parity matrix can be made using using numpy.diag)\n",
    "    # second, compute the inverse of the vertex_degrees diagonal matrix using numpy.diag\n",
    "    #   and numpy.inalg.inv (inverse should always exist b/c we assume the graph is void-free)\n",
    "    trans_mat_new = (adj_mat + numpy.diag([1]*N)) * numpy.linalg.inv(numpy.diag(vertex_degrees + 1))\n",
    "    \n",
    "    # initialize the \"current\" transition matrix as all zeros\n",
    "    trans_mat = numpy.zeros([N, N])\n",
    "    \n",
    "    # set an iteration counter to zero; we will hard-code a max of 20 iterations below\n",
    "    iter_count = 0\n",
    "    \n",
    "    # while the fractional change in the transition matrix (by Frobenius norm) is less than 0.01 and\n",
    "    # iterations is less than 20....\n",
    "    \n",
    "        # note: use numpy.linalg.norm(    , ord=\"fro\"); we are going to compute this norm for the difference\n",
    "        # _and_ for the average of the current transition matrix and the new transition matrix; compute the ratio\n",
    "        \n",
    "    while ((numpy.linalg.norm(trans_mat_new - trans_mat, ord=\"fro\")/\n",
    "        numpy.linalg.norm(0.5*(trans_mat_new + trans_mat), ord=\"fro\")) > 0.01 and iter_count < 20):\n",
    "        \n",
    "        # assign the new transition matrix to be the current transition matrix\n",
    "        trans_mat = trans_mat_new\n",
    "        \n",
    "        # apply the expansion step with r=2, using numpy.linalg.matrix_power(   , 2)\n",
    "        trans_mat_new = numpy.linalg.matrix_power(trans_mat_new, 2)\n",
    "        \n",
    "        # note: trans_mat_new is still a left stochastic matrix (you can check it to be sure)\n",
    "        \n",
    "        # now apply the inflation step with s=2, using numpy.power(  , 2)\n",
    "        trans_mat_new = numpy.power(trans_mat_new, 2)\n",
    "        \n",
    "        # compute column sums using numpy.sum(   , axis=0)\n",
    "        column_sums = numpy.sum(trans_mat_new, axis=0)\n",
    "        \n",
    "        # make a matrix of the column sums using numpy.repeat(    , N, axis=0); call it trans_mat_div\n",
    "        trans_mat_div = numpy.repeat(column_sums, N, axis=0)\n",
    "        \n",
    "        # normalize the inflated matrix by element_wise dividing by trans_mat_div using numpy.divide\n",
    "        trans_mat_new = numpy.divide(trans_mat_new, trans_mat_div)\n",
    "        \n",
    "        # increment the iteration counter\n",
    "        iter_count += 1\n",
    "        print(\"just completed iteration: \" + str(iter_count))\n",
    "        \n",
    "    # threshold the transition matrix at 1e-10, into a binary matrix (containing only 0 or 1 in each element)\n",
    "    trans_mat_new[trans_mat_new < 1e-10]=0\n",
    "    trans_mat_new[trans_mat_new > 1e-10]=1\n",
    "    \n",
    "    # take the transpose matrix and make a data frame out of it\n",
    "    trans_mat_df = pandas.DataFrame(trans_mat_new.transpose())\n",
    "    \n",
    "    # each row is a \"signature\" corresponding to a specific cluster; drop duplicate rows\n",
    "    cluster_signatures = trans_mat_df.drop_duplicates()\n",
    "    \n",
    "    # count the clusters and assign a numeric cluster ID to each cluster, by setting the `index` variable\n",
    "    cluster_signatures.index=range(cluster_signatures.shape[0])\n",
    "    \n",
    "    # use pandas.merge to compute the index for each signature in the original matrix (before you dropped duplicates)\n",
    "    # - make sure to call reset_index on each of the data frames that you are passing to merge\n",
    "    # - in the merge call, for the left_on argument, specify the columns of cluster_signatures (list format)\n",
    "    # - in the marge call, for the right_on argument, specify the columns of trans_mat_df (list_format)\n",
    "    merged_df = pandas.merge(cluster_signatures.reset_index(),\n",
    "                 trans_mat_df.reset_index(),\n",
    "                 left_on=cluster_signatures.columns.tolist(),\n",
    "                 right_on=trans_mat_df.columns.tolist())\n",
    "    \n",
    "    # return the \"index_x\" column of merged_df, in list format\n",
    "    return(merged_df[\"index_x\"].tolist())\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run your code on test_igraph and print the results!  How many iterations did it take?  Do the clusters make sense?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "just completed iteration: 1\n",
      "just completed iteration: 2\n",
      "just completed iteration: 3\n",
      "just completed iteration: 4\n",
      "just completed iteration: 5\n",
      "just completed iteration: 6\n",
      "just completed iteration: 7\n",
      "just completed iteration: 8\n",
      "just completed iteration: 9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "markov_cluster(test_igraph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now see if you can load in a larger graph (from the Krogan et al. paper) in edge-list (SIF) format. Load the file `shared/krogan.sif` using pandas.read_csv(). Run the graph through your `markov_cluster` code. How many clusters do you get? What is the histogram of cluster sizes?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pandas.read_csv(\"shared/krogan.sif\", \n",
    "                     sep=\"\\t\", \n",
    "                     quoting=csv.QUOTE_NONE,\n",
    "                     names=[\"species1\",\"species2\"])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>species1</th>\n",
       "      <th>species2</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>AAC3</td>\n",
       "      <td>PMR1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>AAP1</td>\n",
       "      <td>GUD1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>AAP1</td>\n",
       "      <td>TRS31</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>AAP1</td>\n",
       "      <td>GCN3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>AAP1</td>\n",
       "      <td>MDY2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  species1 species2\n",
       "0     AAC3     PMR1\n",
       "1     AAP1     GUD1\n",
       "2     AAP1    TRS31\n",
       "3     AAP1     GCN3\n",
       "4     AAP1     MDY2"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'IGRAPH UN-- 2674 7079 -- \\n+ attr: name (v)'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "krogan_graph = igraph.Graph.TupleList(df.values.tolist())\n",
    "krogan_graph.summary()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "just completed iteration: 1\n",
      "just completed iteration: 2\n",
      "just completed iteration: 3\n",
      "just completed iteration: 4\n",
      "just completed iteration: 5\n",
      "just completed iteration: 6\n",
      "just completed iteration: 7\n",
      "just completed iteration: 8\n",
      "just completed iteration: 9\n",
      "just completed iteration: 10\n",
      "just completed iteration: 11\n",
      "just completed iteration: 12\n"
     ]
    }
   ],
   "source": [
    "clust_ids = markov_cluster(krogan_graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "650"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(clust_ids)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAMsElEQVR4nO3df6hf913H8efLpjpxSltzDSGp3qpBieCycamV7Y+6oqbtMBVGadEtjEr8o4UOJpLtn6pQiH+4zYEW4lqawewW3GaDLWqJheof63q71a4/LI0zpQlpcmf3ozKopHv7xz0h38R7c5P7vT963/f5gMs953PO995PP/Q+czj3+/3eVBWSpF5+ZLUnIElaesZdkhoy7pLUkHGXpIaMuyQ1tGG1JwCwcePGmpycXO1pSNKa8vTTT3+7qibmOva2iPvk5CTT09OrPQ1JWlOSvDLfMW/LSFJDxl2SGjLuktSQcZekhoy7JDVk3CWpIeMuSQ0Zd0lqyLhLUkNvi1eorobJvY/Me+zovptXcCaStPS8cpekhoy7JDVk3CWpIeMuSQ0Zd0lqyLhLUkPGXZIaMu6S1JBxl6SGjLskNWTcJakh4y5JDRl3SWrIuEtSQ8Zdkhoy7pLUkHGXpIaMuyQ1ZNwlqSHjLkkNGXdJamjBuCe5OsnjSV5I8nySu4fxq5I8luTl4fOVw3iSfCbJkSTPJnnPcv9HSJLOdTFX7qeBj1XVduA64M4k24G9wOGq2gYcHvYBbgS2DR97gPuWfNaSpAtaMO5VdaKqvj5svwG8CGwBdgEHhtMOALcM27uAz9WsrwJXJNm85DOXJM3rku65J5kE3g08CWyqqhPDodeATcP2FuDVkYcdG8bO/1p7kkwnmZ6ZmbnEaUuSLuSi457kncCXgI9W1fdHj1VVAXUp37iq9lfVVFVNTUxMXMpDJUkLuKi4J7mc2bB/vqq+PAyfPHO7Zfh8ahg/Dlw98vCtw5gkaYVczLNlAtwPvFhVnxw5dAjYPWzvBh4eGf/w8KyZ64Dvjdy+kSStgA0Xcc57gQ8B30zyzDD2CWAfcDDJHcArwK3DsUeBm4AjwA+AjyzpjCVJC1ow7lX1b0DmOXzDHOcXcOeY85IkjcFXqEpSQ8Zdkhoy7pLUkHGXpIaMuyQ1ZNwlqSHjLkkNGXdJasi4S1JDxl2SGjLuktSQcZekhoy7JDVk3CWpIeMuSQ0Zd0lqyLhLUkPGXZIaMu6S1JBxl6SGjLskNWTcJakh4y5JDRl3SWrIuEtSQ8Zdkhoy7pLUkHGXpIaMuyQ1ZNwlqSHjLkkNGXdJasi4S1JDxl2SGjLuktSQcZekhhaMe5IHkpxK8tzI2J8kOZ7kmeHjppFjH09yJMlLSX57uSYuSZrfxVy5PwjsnGP8U1W1Y/h4FCDJduA24FeGx/x1ksuWarKSpIuzYNyr6gng9Yv8eruAL1TVm1X1X8AR4Nox5idJWoRx7rnfleTZ4bbNlcPYFuDVkXOODWOSpBW02LjfB/wCsAM4AfzFpX6BJHuSTCeZnpmZWeQ0JElzWVTcq+pkVb1VVT8E/oazt16OA1ePnLp1GJvra+yvqqmqmpqYmFjMNCRJ81hU3JNsHtn9XeDMM2kOAbcl+bEk1wDbgK+NN0VJ0qXasNAJSR4Crgc2JjkG3ANcn2QHUMBR4A8Bqur5JAeBF4DTwJ1V9dbyTF2SNJ8F415Vt88xfP8Fzr8XuHecSUmSxuMrVCWpIeMuSQ0Zd0lqyLhLUkPGXZIaMu6S1JBxl6SGjLskNWTcJamhBV+huh5N7n1kzvGj+25e4ZlI0uJ45S5JDRl3SWrIuEtSQ8Zdkhoy7pLUkHGXpIaMuyQ1ZNwlqSHjLkkNGXdJasi4S1JDxl2SGjLuktSQcZekhoy7JDVk3CWpIeMuSQ0Zd0lqyLhLUkPGXZIaMu6S1JBxl6SGjLskNWTcJakh4y5JDRl3SWrIuEtSQwvGPckDSU4leW5k7KokjyV5efh85TCeJJ9JciTJs0nes5yTlyTN7WKu3B8Edp43thc4XFXbgMPDPsCNwLbhYw9w39JMU5J0KRaMe1U9Abx+3vAu4MCwfQC4ZWT8czXrq8AVSTYv1WQlSRdnsffcN1XViWH7NWDTsL0FeHXkvGPD2P+TZE+S6STTMzMzi5yGJGkuY/9CtaoKqEU8bn9VTVXV1MTExLjTkCSNWGzcT5653TJ8PjWMHweuHjlv6zAmSVpBi437IWD3sL0beHhk/MPDs2auA743cvtGkrRCNix0QpKHgOuBjUmOAfcA+4CDSe4AXgFuHU5/FLgJOAL8APjIMsxZkrSABeNeVbfPc+iGOc4t4M5xJyVJGo+vUJWkhoy7JDVk3CWpIeMuSQ0Zd0lqyLhLUkPGXZIaMu6S1JBxl6SGjLskNWTcJakh4y5JDRl3SWrIuEtSQ8Zdkhoy7pLUkHGXpIaMuyQ1ZNwlqSHjLkkNGXdJasi4S1JDG1Z7AmvJ5N5H5j12dN/NKzgTSbowr9wlqSHjLkkNGXdJasi4S1JDxl2SGjLuktSQcZekhoy7JDVk3CWpodavUL3QK0olqTOv3CWpIeMuSQ0Zd0lqaKx77kmOAm8AbwGnq2oqyVXAF4FJ4Chwa1V9Z7xpSpIuxVJcuf9GVe2oqqlhfy9wuKq2AYeHfUnSClqO2zK7gAPD9gHglmX4HpKkCxg37gX8c5Knk+wZxjZV1Ylh+zVg01wPTLInyXSS6ZmZmTGnIUkaNe7z3N9XVceT/AzwWJL/GD1YVZWk5npgVe0H9gNMTU3NeY4kaXHGunKvquPD51PAV4BrgZNJNgMMn0+NO0lJ0qVZdNyT/ESSnzyzDfwW8BxwCNg9nLYbeHjcSUqSLs04t2U2AV9Jcubr/G1V/WOSp4CDSe4AXgFuHX+akqRLsei4V9W3gHfNMf7fwA3jTEqSNB5foSpJDRl3SWrIuEtSQ8Zdkhoy7pLUkHGXpIaMuyQ11PpvqK6kxf691qP7bl7imUiSV+6S1JJxl6SGjLskNWTcJakh4y5JDRl3SWrIuEtSQ8Zdkhoy7pLUkHGXpIZ8+4FVdqG3LfCtCSQtllfuktSQcZekhoy7JDVk3CWpIeMuSQ0Zd0lqyLhLUkPGXZIaMu6S1JBxl6SGjLskNWTcJakh3zjsbexCbyo2nwu92ZhvUiatH165S1JDXrk3s5irfUn9eOUuSQ0Zd0lqyLhLUkPLds89yU7gL4HLgM9W1b7l+l5aHSt5f3+pn83jM4fU3bLEPcllwF8BvwkcA55KcqiqXliO76fxzRe7tRA6Q31xXKf1Zbmu3K8FjlTVtwCSfAHYBRj3Nebt8uybt8s8LmSp59g1uP4jszJSVUv/RZMPAjur6g+G/Q8Bv1ZVd42cswfYM+z+EvDSIr/dRuDbY0y3G9fjXK7HWa7FuTqsx89V1cRcB1btee5VtR/YP+7XSTJdVVNLMKUWXI9zuR5nuRbn6r4ey/VsmePA1SP7W4cxSdIKWK64PwVsS3JNkh8FbgMOLdP3kiSdZ1luy1TV6SR3Af/E7FMhH6iq55fje7EEt3aacT3O5Xqc5Vqcq/V6LMsvVCVJq8tXqEpSQ8Zdkhpa03FPsjPJS0mOJNm72vNZaUkeSHIqyXMjY1cleSzJy8PnK1dzjislydVJHk/yQpLnk9w9jK/X9XhHkq8l+fdhPf50GL8myZPDz8wXhyc8rAtJLkvyjST/MOy3Xos1G/eRtzi4EdgO3J5k++rOasU9COw8b2wvcLiqtgGHh/314DTwsaraDlwH3Dn8/7Be1+NN4P1V9S5gB7AzyXXAnwOfqqpfBL4D3LGKc1xpdwMvjuy3Xos1G3dG3uKgqv4XOPMWB+tGVT0BvH7e8C7gwLB9ALhlRSe1SqrqRFV9fdh+g9kf4i2s3/WoqvqfYffy4aOA9wN/N4yvm/VIshW4GfjssB+ar8VajvsW4NWR/WPD2Hq3qapODNuvAZtWczKrIckk8G7gSdbxegy3IZ4BTgGPAf8JfLeqTg+nrKefmU8Dfwz8cNj/aZqvxVqOuxZQs89zXVfPdU3yTuBLwEer6vujx9bbelTVW1W1g9lXiF8L/PIqT2lVJPkAcKqqnl7tuayktfw3VH2Lg7mdTLK5qk4k2czsVdu6kORyZsP++ar68jC8btfjjKr6bpLHgV8HrkiyYbhiXS8/M+8FfifJTcA7gJ9i9m9NtF6LtXzl7lsczO0QsHvY3g08vIpzWTHDPdT7gRer6pMjh9brekwkuWLY/nFm/7bCi8DjwAeH09bFelTVx6tqa1VNMtuJf6mq36P5WqzpV6gO/xJ/mrNvcXDvKk9pRSV5CLie2bcuPQncA/w9cBD4WeAV4NaqOv+Xru0keR/wr8A3OXtf9RPM3ndfj+vxq8z+kvAyZi/iDlbVnyX5eWaffHAV8A3g96vqzdWb6cpKcj3wR1X1ge5rsabjLkma21q+LSNJmodxl6SGjLskNWTcJakh4y5JDRl3SWrIuEtSQ/8HKMswGXsvntwAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from matplotlib import pyplot as plt\n",
    "import collections\n",
    "counts = [count for count in dict(collections.Counter(clust_ids)).values()]\n",
    "bins = numpy.array(range(0, max(counts)))\n",
    "plt.hist(counts, bins=bins)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}