modularity for multigraph

[XiaoxiaLin]

The current modularity function in community_louvain.py will always set the edge_weight to 1 in case of multigraph.

for node in graph:
        com = partition[node]
        deg[com] = deg.get(com, 0.) + graph.degree(node, weight=weight)
        for neighbor, datas in graph[node].items():
            edge_weight = datas.get(weight, 1)
            if partition[neighbor] == com:
                if neighbor == node:
                    inc[com] = inc.get(com, 0.) + float(edge_weight)
                else:
                    inc[com] = inc.get(com, 0.) + float(edge_weight) / 2.

For multigraph, we would need edge keys to get the weight:

for node in graph:
    com = partition[node]
    deg[com] = deg.get(com, 0.) + graph.degree(node, weight=weight)
    for neighbor, v in graph[node].items():
        for _, datas in v.items():
            edge_weight = datas.get(weight, 1)
            if partition[neighbor] == com:
                if neighbor == node:
                    inc[com] = inc.get(com, 0.) + float(edge_weight)
                else:
                    inc[com] = inc.get(com, 0.) + float(edge_weight) / 2.

Does it make sense? Is the current best_partition function only work for Graph, and not MultiGraph?

[taynaud]

Hello, The current best_partition has only been tested on graph and never on MultiGraph. Your solution seems reasonable for multigraph, considering that 2 links of weights W1 and W2 is equivalent to 1 link of weight W1+W2.

I think considering this it would be easier and clearer to first transform your Multigraph to a Graph with this hypothesis and then apply louvain method on it rather than implementing more cases for Multigraph in the algorithm.

Best,