{
  "nbformat_minor": 0, 
  "nbformat": 4, 
  "cells": [
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "%matplotlib inline"
      ], 
      "outputs": [], 
      "metadata": {
        "collapsed": false
      }
    }, 
    {
      "source": [
        "\n# Blockmodel\n\n\nExample of creating a block model using the quotient_graph function in NX.  Data\nused is the Hartford, CT drug users network::\n\n    @article{weeks2002social,\n      title={Social networks of drug users in high-risk sites: Finding the connections},\n      url = {http://dx.doi.org/10.1023/A:1015457400897},\n      doi = {10.1023/A:1015457400897},\n      author={Weeks, Margaret R and Clair, Scott and Borgatti, Stephen P and Radda, Kim and Schensul, Jean J},\n      journal={{AIDS and Behavior}},\n      volume={6},\n      number={2},\n      pages={193--206},\n      year={2002},\n      publisher={Springer}\n    }\n\n\n"
      ], 
      "cell_type": "markdown", 
      "metadata": {}
    }, 
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "# Authors:  Drew Conway <drew.conway@nyu.edu>, Aric Hagberg <hagberg@lanl.gov>\n\nfrom collections import defaultdict\n\nimport matplotlib.pyplot as plt\nimport networkx as nx\nimport numpy\nfrom scipy.cluster import hierarchy\nfrom scipy.spatial import distance\n\n\ndef create_hc(G):\n    \"\"\"Creates hierarchical cluster of graph G from distance matrix\"\"\"\n    path_length = nx.all_pairs_shortest_path_length(G)\n    distances = numpy.zeros((len(G), len(G)))\n    for u, p in path_length:\n        for v, d in p.items():\n            distances[u][v] = d\n    # Create hierarchical cluster\n    Y = distance.squareform(distances)\n    Z = hierarchy.complete(Y)  # Creates HC using farthest point linkage\n    # This partition selection is arbitrary, for illustrive purposes\n    membership = list(hierarchy.fcluster(Z, t=1.15))\n    # Create collection of lists for blockmodel\n    partition = defaultdict(list)\n    for n, p in zip(list(range(len(G))), membership):\n        partition[p].append(n)\n    return list(partition.values())\n\n\nif __name__ == '__main__':\n    G = nx.read_edgelist(\"hartford_drug.edgelist\")\n\n    # Extract largest connected component into graph H\n    H = next(nx.connected_component_subgraphs(G))\n    # Makes life easier to have consecutively labeled integer nodes\n    H = nx.convert_node_labels_to_integers(H)\n    # Create parititions with hierarchical clustering\n    partitions = create_hc(H)\n    # Build blockmodel graph\n    BM = nx.quotient_graph(H, partitions, relabel=True)\n\n    # Draw original graph\n    pos = nx.spring_layout(H, iterations=100)\n    plt.subplot(211)\n    nx.draw(H, pos, with_labels=False, node_size=10)\n\n    # Draw block model with weighted edges and nodes sized by number of internal nodes\n    node_size = [BM.nodes[x]['nnodes'] * 10 for x in BM.nodes()]\n    edge_width = [(2 * d['weight']) for (u, v, d) in BM.edges(data=True)]\n    # Set positions to mean of positions of internal nodes from original graph\n    posBM = {}\n    for n in BM:\n        xy = numpy.array([pos[u] for u in BM.nodes[n]['graph']])\n        posBM[n] = xy.mean(axis=0)\n    plt.subplot(212)\n    nx.draw(BM, posBM, node_size=node_size, width=edge_width, with_labels=False)\n    plt.axis('off')\n    plt.show()"
      ], 
      "outputs": [], 
      "metadata": {
        "collapsed": false
      }
    }
  ], 
  "metadata": {
    "kernelspec": {
      "display_name": "Python 2", 
      "name": "python2", 
      "language": "python"
    }, 
    "language_info": {
      "mimetype": "text/x-python", 
      "nbconvert_exporter": "python", 
      "name": "python", 
      "file_extension": ".py", 
      "version": "2.7.12", 
      "pygments_lexer": "ipython2", 
      "codemirror_mode": {
        "version": 2, 
        "name": "ipython"
      }
    }
  }
}