search

taynaud / python-louvain

Louvain Community Detection
BSD 3-Clause "New" or "Revised" License
964 stars 200 forks source link

Improper way of calculating modularity for weighted graphs #71

Closed Lemour-sudo closed 2 years ago

Lemour-sudo commented 4 years ago

In the modularity function in the community_louvain.py script, the number of links in the graph is incorrect for weighted graphs whenever there is at least one edge with a weight not equal to one. For example: Say you have a graph with 2 nodes: (0, 1). Node 0 has a self-edge of weight=2, node 1 has a self-edge of weight=1, and the third edge of weight=2 connects node 0 and node 1. In total you have m=3 edges. However the algorithm in the modularity function detects a total of 5 edges (because it sums up the edge weights instead of counting the edges themselves). Therefore the modularity of graphs with all edges of weight=1 will be correct BUT will be incorrect if there is at least one edge with a weight not equal to 1.

taynaud commented 3 years ago

links is not very well named, it should be total degree. I think the definition of modularity expects more a total degree than a number of links ?