Issue #41 new

Wrong implementation of modularity

Ben Vo
created an issue

There is a serious mistake of implementation of function def modularity(partition, graph) in init.py file. This is the code causing the mistake:

 if partition[neighbor] == com :
                if neighbor == node :
                    inc[com] = inc.get(com, 0.) + float(weight)
                else :
                    inc[com] = inc.get(com, 0.) + float(weight) / 2.

It is wrong to process self-looping edge like above. The self-looping edge should be processed exactly same to normal edges (u,v) u!=v .

This is very serious because Louvain contains a re-creating graph which includes self-looping edges. When modularity is wrongly computed, the whole community detection will be wrong.

This is the code to test modularity value of python-louvain. The result is 0.331111111111 while the correct modularity must be 0.313775510204

edges = [(1, 2, 1), (1, 3, 1), (1, 4, 1),
             (2, 3, 1), (3, 4, 1), (4, 5, 1),
             (4, 6, 1), (5, 6, 1), (5, 7, 1),
             (5, 8, 1), (6, 7, 1), (6, 8, 1),
             (7, 8, 1), (7, 9, 1), (1,1,1)]
    G = nx.Graph()
    membership = {1: 1, 2: 1, 3: 1, 4: 1,
                  5: 2, 6: 2, 7: 2, 8: 2,
                  9: 3}
    import community
    for e in edges:
        G.add_edge(e[0], e[1], weight=e[2])
    print community.modularity(membership, G)

Comments (1)

  1. Log in to comment