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
Unless otherwise stated, the content of this page is licensed under GNU Free Documentation License.