Community Detection In Python
1 MCL clustering (using external software)
This code was sent to the igraph-help mailing list by Chris Wj, see the thread here: http://lists.gnu.org/archive/html/igraph-help/2008-12/msg00109.html For more about this algorithm and the required software, see http://www.micans.org/mcl/
Improved Version (1/5/09)
This version creates subgraphs as images using GraphViz
def generate_mcl_matrix(G): mcifile = "" mclheader = ( ("\n(mclheader\n"), ("mcltype matrix\n"), ( "dimensions %sx%s\n)\n" % (G.vcount(), G.vcount()) ), ("(mclmatrix\n"), ("begin\n") ) for mhline in mclheader: mcifile += mhline for v in G.vs: mcifile += str(v.index) + " " for n in G.neighbors(v.index): mcifile += str(n) + " " mcifile += " $\n" mcifile += ")\n" return mcifile def create_graph_image(mcl_line, base_name, G): from subprocess import Popen nodes = mcl_line.split() nodes = nodes[1:-1] subG = G.subgraph([int(node) for node in nodes]) subG.write_dot(base_name+".dot") cmd = "dot -T png -o " + base_name + ".png " + base_name + ".dot" Popen(cmd, shell=True) def run_mcl_cluster(G): from subprocess import Popen, PIPE mcistr = generate_mcl_matrix(G) print mcistr + "\n" cmd = "mcl - -scheme 6 -I 1.6 -o -" p = Popen(cmd, stdout=PIPE, stdin=PIPE, stderr=PIPE, shell=True) sout,serr = p.communicate(mcistr) p.wait() print "return code: %i\n" % p.returncode if p.returncode==0 and len(sout)>0: lines = sout.splitlines() idx_begin = lines.index("begin")+1 idx_end = lines[idx_begin:].index(")")+idx_begin num = 0 for line in lines[idx_begin:idx_end]: print line create_graph_image(line, "mcl-ex-"+str(num), G) num+=1 if __name__ == "__main__": G = igraph.Graph.Read_GraphML("ow.graphml") print "Edges: " + str(G.ecount()) print "Nodes: " + str(G.vcount()) G.simplify() # create labels from the id's so that GraphViz outputs subgraphs with original labels for n in G.vs: n['label']=n['id'][1:] run_mcl_cluster(G)
Original Version:
import igraph def igraph_to_mcl_matrix(): from subprocess import Popen, PIPE from cStringIO import StringIO G1 = igraph.Graph(n=3) G1.add_edges(((0,1),(0,2),(1,2))) mcifile = StringIO() mclheader = ( ("\n(mclheader\n"), ("mcltype matrix\n"), ( "dimensions %sx%s\n)\n" % (G1.vcount(), G1.vcount()) ), ("(mclmatrix\n"), ("begin\n") ) mcifile.writelines(mclheader) for v in G1.vs: mcifile.write(str(v.index) + " ") for n in G1.neighbors(v.index): mcifile.write(str(n) + " ") mcifile.write(" $\n") mcifile.write(")\n") mcifile.seek(0) cmd = "mcl - -o -" p = Popen(cmd, stdout=PIPE, stdin=PIPE, stderr=PIPE) sout,serr = p.communicate(mcifile.read()) p.wait() #print "return code: %i\n" % p.returncode if p.returncode==0 and len(sout)>0: lines = sout.splitlines() idx_begin = lines.index("begin")+1 idx_end = lines[idx_begin:].index(")")+idx_begin for line in lines[idx_begin:idx_end]: print line
page revision: 3, last edited: 01 Jul 2009 15:58