[graph-tool-tickets] [graph-tool] Ticket #92: Incorrect modularity evaluation
graph-tool
webmaster at skewed.de
Tue Feb 28 10:30:47 UTC 2012
#92: Incorrect modularity evaluation
new defect
---------------------------------------------------------------------
Reporter: gamma2 at users.sourceforge.net
Owner: tiago peixoto
Priority: normal
Milestone: (None)
---------------------------------------------------------------------
The current implementation of the modularity mixes edge weights and unweighted degrees.
Given the modularity definition:
Q = 1/(2m) * sum_ij [ A(i,j) - k(i)*k(j)/(2m) ] d(c_i,c_j)
In the code, while A(i,j) uses the weights, k(i)*k(j) is calculated using just the degree of the vertices, instead of summing the weights of the edges.
The paper where Newman defined the weighted modularity is http://arxiv.org/pdf/condmat/0407503.pdf , page 7, formula 9. I know you refer to the 2006's paper, where only vertex degree is used, however the notation is the same.
You can easily check it by creating a graph with 2 vertices, connected by an edge with weight 0.1, and putting them in the same community. Using your modularity implementation, without passing the weights, you correctly get 0.0 as answer. If you call modularity and pass the weights, you get -9.0, which is way out of the [-0.5,1] range of the modularity definition.
A (rough) patch is attached. Its complexity is a bit higher than the previous version, O(V^2 ), but I'm working on an improvement.
--
Ticket URL: <URL:http://graph-tool.skewed.de/ticket/92>
graph-tool <URL:http://graph-tool.skewed.de/>
An efficient python module for graph analysis and manipulation.
More information about the graph-tool-tickets
mailing list