Karate club community detection by Girvan-Newman algorithm

gistfile1.py

# -*- coding: utf-8 -*-
# Girvan Newman algorithmを使って空手クラブネットワークのコミュニティが分割していく様子を出力
# Zachary's karate club(空手クラブのネットワーク)のデータ取得元URL
# http://www-personal.umich.edu/~mejn/netdata/


import networkx as NX
import networkx.readwrite.gml as NRG
import networkx.algorithms.centrality as NC
import pylab as P


def updateGraph(G):
    ebc = NC.edge_betweenness(G)
    max = 0
    medge = None
    for k, v in ebc.iteritems():
        if max < v:
            medge, max = k, v
        G.delete_edge(medge)
    return G


def drawGraph(G, pos, output):
    NX.draw(G, pos)
    P.savefig(output)
    P.draw()
    P.close()

G = NRG.read_gml("karate.gml")
eNum = G.number_of_edges()
pos = NX.spring_layout(G)
for i in range(eNum):
    output = "img/karate%(id)02d.png" % {"id": i}
    drawGraph(G, pos, output)
    updateGraph(G)