class15_MCODE_python3_template.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pygraphviz\n",
    "import igraph\n",
    "import numpy\n",
    "import pandas\n",
    "\n",
    "import sys\n",
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'IGRAPH UN-- 13 26 -- \\n+ attr: name (v)'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_graph = pygraphviz.AGraph(\"test.dot\")\n",
    "nodes = test_graph.nodes()\n",
    "edges = test_graph.edges()\n",
    "test_igraph = igraph.Graph.TupleList(edges)\n",
    "test_igraph.summary()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "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=\"600pt\" height=\"600pt\" viewBox=\"0 0 600 600\" version=\"1.1\">\n",
       "<g id=\"surface8\">\n",
       "<rect x=\"0\" y=\"0\" width=\"600\" height=\"600\" 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 580 165.15625 L 524.207031 45.03125 \"/>\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 580 165.15625 L 458.71875 203.601562 \"/>\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 580 165.15625 L 458.3125 133.363281 \"/>\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 524.207031 45.03125 L 458.3125 133.363281 \"/>\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 524.207031 45.03125 L 373.542969 100.535156 \"/>\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 524.207031 45.03125 L 431.484375 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 458.71875 203.601562 L 458.3125 133.363281 \"/>\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 458.71875 203.601562 L 373.542969 100.535156 \"/>\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 458.3125 133.363281 L 373.542969 100.535156 \"/>\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 373.542969 100.535156 L 349.679688 226.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 458.71875 203.601562 L 431.484375 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 458.3125 133.363281 L 431.484375 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 373.542969 100.535156 L 431.484375 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 458.71875 203.601562 L 349.679688 226.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 458.3125 133.363281 L 349.679688 226.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 349.679688 226.527344 L 263.433594 322.414062 \"/>\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 263.433594 322.414062 L 175.78125 416.070312 \"/>\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 175.78125 416.070312 L 93.949219 501.414062 \"/>\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 175.78125 416.070312 L 151.746094 552.136719 \"/>\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 175.78125 416.070312 L 47.960938 439.34375 \"/>\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 93.949219 501.414062 L 151.746094 552.136719 \"/>\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 93.949219 501.414062 L 47.960938 439.34375 \"/>\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 93.949219 501.414062 L 20 580 \"/>\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 151.746094 552.136719 L 47.960938 439.34375 \"/>\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 151.746094 552.136719 L 20 580 \"/>\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 47.960938 439.34375 L 20 580 \"/>\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 590 165.15625 C 590 170.675781 585.523438 175.15625 580 175.15625 C 574.476562 175.15625 570 170.675781 570 165.15625 C 570 159.632812 574.476562 155.15625 580 155.15625 C 585.523438 155.15625 590 159.632812 590 165.15625 \"/>\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 534.207031 45.03125 C 534.207031 50.554688 529.730469 55.03125 524.207031 55.03125 C 518.683594 55.03125 514.207031 50.554688 514.207031 45.03125 C 514.207031 39.507812 518.683594 35.03125 524.207031 35.03125 C 529.730469 35.03125 534.207031 39.507812 534.207031 45.03125 \"/>\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 468.71875 203.601562 C 468.71875 209.121094 464.242188 213.601562 458.71875 213.601562 C 453.199219 213.601562 448.71875 209.121094 448.71875 203.601562 C 448.71875 198.078125 453.199219 193.601562 458.71875 193.601562 C 464.242188 193.601562 468.71875 198.078125 468.71875 203.601562 \"/>\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 468.3125 133.363281 C 468.3125 138.886719 463.835938 143.363281 458.3125 143.363281 C 452.789062 143.363281 448.3125 138.886719 448.3125 133.363281 C 448.3125 127.839844 452.789062 123.363281 458.3125 123.363281 C 463.835938 123.363281 468.3125 127.839844 468.3125 133.363281 \"/>\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 383.542969 100.535156 C 383.542969 106.058594 379.066406 110.535156 373.542969 110.535156 C 368.019531 110.535156 363.542969 106.058594 363.542969 100.535156 C 363.542969 95.015625 368.019531 90.535156 373.542969 90.535156 C 379.066406 90.535156 383.542969 95.015625 383.542969 100.535156 \"/>\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 441.484375 20 C 441.484375 25.523438 437.003906 30 431.484375 30 C 425.960938 30 421.484375 25.523438 421.484375 20 C 421.484375 14.476562 425.960938 10 431.484375 10 C 437.003906 10 441.484375 14.476562 441.484375 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 359.679688 226.527344 C 359.679688 232.050781 355.203125 236.527344 349.679688 236.527344 C 344.15625 236.527344 339.679688 232.050781 339.679688 226.527344 C 339.679688 221.007812 344.15625 216.527344 349.679688 216.527344 C 355.203125 216.527344 359.679688 221.007812 359.679688 226.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 273.433594 322.414062 C 273.433594 327.9375 268.957031 332.414062 263.433594 332.414062 C 257.910156 332.414062 253.433594 327.9375 253.433594 322.414062 C 253.433594 316.894531 257.910156 312.414062 263.433594 312.414062 C 268.957031 312.414062 273.433594 316.894531 273.433594 322.414062 \"/>\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 185.78125 416.070312 C 185.78125 421.59375 181.304688 426.070312 175.78125 426.070312 C 170.257812 426.070312 165.78125 421.59375 165.78125 416.070312 C 165.78125 410.550781 170.257812 406.070312 175.78125 406.070312 C 181.304688 406.070312 185.78125 410.550781 185.78125 416.070312 \"/>\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 103.949219 501.414062 C 103.949219 506.9375 99.472656 511.414062 93.949219 511.414062 C 88.429688 511.414062 83.949219 506.9375 83.949219 501.414062 C 83.949219 495.890625 88.429688 491.414062 93.949219 491.414062 C 99.472656 491.414062 103.949219 495.890625 103.949219 501.414062 \"/>\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 161.746094 552.136719 C 161.746094 557.660156 157.269531 562.136719 151.746094 562.136719 C 146.222656 562.136719 141.746094 557.660156 141.746094 552.136719 C 141.746094 546.613281 146.222656 542.136719 151.746094 542.136719 C 157.269531 542.136719 161.746094 546.613281 161.746094 552.136719 \"/>\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 57.960938 439.34375 C 57.960938 444.867188 53.480469 449.34375 47.960938 449.34375 C 42.4375 449.34375 37.960938 444.867188 37.960938 439.34375 C 37.960938 433.820312 42.4375 429.34375 47.960938 429.34375 C 53.480469 429.34375 57.960938 433.820312 57.960938 439.34375 \"/>\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 580 C 30 585.523438 25.523438 590 20 590 C 14.476562 590 10 585.523438 10 580 C 10 574.476562 14.476562 570 20 570 C 25.523438 570 30 574.476562 30 580 \"/>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<igraph.drawing.Plot at 0x7fac430734a8>"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "igraph.drawing.plot(test_igraph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Original code from True Price at UNC Chapel Hill (https://github.com/trueprice/python-graph-clustering/blob/master/src/mcode.py)\n",
    "\n",
    "def mcode(adj_list, vwp):\n",
    "  \n",
    "  # Stage 1: Vertex Weighting\n",
    "  N = len(adj_list)\n",
    "  edges = [[]]*N\n",
    "  weights = dict((v,1.) for v in range(0,N))\n",
    "\n",
    "  edges=defaultdict(set)\n",
    "  for i in range(0,N):\n",
    "    edges[i]=set(adj_list[i])\n",
    "    \n",
    "  res_clusters = []\n",
    "\n",
    "  for i,v in enumerate(edges):\n",
    "    neighborhood = set((v,)) | edges[v]\n",
    "    # if node has only one neighbor, we know everything we need to know\n",
    "    if len(neighborhood) <= 2: continue\n",
    "\n",
    "    # see if larger k-cores exist\n",
    "    k = 1 # highest valid k-core\n",
    "    while neighborhood:\n",
    "      k_core = neighborhood.copy()\n",
    "      invalid_nodes = True\n",
    "      while invalid_nodes and neighborhood:\n",
    "        invalid_nodes = set(\n",
    "          n for n in neighborhood if len(edges[n] & neighborhood) <= k)\n",
    "        neighborhood -= invalid_nodes\n",
    "      k += 1 # on exit, k will be one greater than we want\n",
    "    # vertex weight = k-core number * density of k-core\n",
    "    weights[v] = (k-1) * (sum(len(edges[n] & k_core) for n in k_core) / \n",
    "      (2. * len(k_core)**2))\n",
    "\n",
    "  # Stage 2: Molecular Complex Prediction\n",
    "  unvisited = set(edges)\n",
    "  num_clusters = 0\n",
    "  for seed in sorted(weights, key=weights.get, reverse=True):\n",
    "    if seed not in unvisited: continue\n",
    "\n",
    "    cluster, frontier = set((seed,)), set((seed,))\n",
    "    w = weights[seed] * vwp\n",
    "    while frontier:\n",
    "      cluster.update(frontier)\n",
    "      unvisited -= frontier\n",
    "      frontier = set(\n",
    "        n for n in set.union(*(edges[n] for n in frontier)) & unvisited\n",
    "        if weights[n] > w)\n",
    "\n",
    "    # haircut: only keep 2-core complexes\n",
    "    invalid_nodes = True\n",
    "    while invalid_nodes and cluster:\n",
    "      invalid_nodes = set(n for n in cluster if len(edges[n] & cluster) < 2)\n",
    "      cluster -= invalid_nodes\n",
    "\n",
    "    if cluster:\n",
    "      res_clusters = res_clusters + [list(cluster)]\n",
    "      num_clusters += 1\n",
    "\n",
    "  return(res_clusters)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run mcode on the adjacency list for your toy graph, with vwp=0.8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3, 4, 5, 6], [8, 9, 10, 11, 12]]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load the Krogan et al. network edge-list data as a Pandas data frame"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "edge_list = "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make an igraph graph and print its summary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'IGRAPH UN-- 2674 7079 -- \\n+ attr: name (v)'"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "krogan_graph = \n",
    "krogan_graph.summary()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run mcode on your graph with vwp=0.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "res = "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get the cluster sizes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[635, 541, 4, 3, 5, 3, 4, 3, 3, 3, 3, 3]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": []
  },
  {
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}