I have a question regarding Mathematica's CommunityModularity command for weighted graphs.
I started with a simple 5-node unweighted, undirected network defined in terms of an adjacency matrix A and determined its community partition that maximized the modularity:
A = {{0, 1, 1, 0, 0}, {1, 0, 1, 0, 0}, {1, 1, 0, 1, 1}, {0, 0, 1, 0, 1}, {0, 0, 1, 1, 0}};
NumNodes=Dimensions[A][[1]];
G = AdjacencyGraph[A, VertexLabels -> "Name", VertexSize -> Automatic,
VertexLabelStyle -> Large]
FindGraphCommunities[G]
{{1, 2, 3}, {4, 5}}
The communities {1,2,3} and {4,5} make perfectly good sense if one looks at the graph.
To obtain the correspondingmodularity, I used
CommunityModularity[G, {{1, 2, 3}, {4, 5}}]
.111111.
I then verified this using the modularity matrix method as discussed in the work of Newman (Analysis of weighted networks, PHYSICAL REVIEW E 70, 056131 (2004)) and on Wikipedia at https://en.wikipedia.org/wiki/Modularity_(networks) and at https://www.cs.umd.edu/class/fall2009/cmsc858l/lecs/Lec10-modularity.pdf (p.11-14)
In this case I did the following to create the modularity matrix B:
k = ConstantArray[0, NumNodes];
Do[k[[i]] = Total[A[[i, All]]], {i, 1, NumNodes}]
k
{2, 2, 4, 2, 2}
m = Total[k]/2
6
P = ConstantArray[0, {NumNodes, NumNodes}];
Do[Do[P[[i, j]] = 1/(2*m)*k[[i]]*k[[j]], {i, 1, NumNodes}], {j, 1,NumNodes}]
B = A - P
{{-(1/3), 2/3, 1/3, -(1/3), -(1/3)}, {2/3, -(1/3), 1/ 3, -(1/3),
-(1/3)},{1/3, 1/3, -(4/3), 1/3, 1/3}, {-(1/3), -(1/3),
1/3, -(1/3), 2/3}, {-(1/3), -(1/3), 1/3, 2/3, -(1/3)}}
The membership (column) vector corresponding to the partition {1,2,3}, {4,5} is given by
S = {{1}, {1}, {1}, {-1}, {-1}};
Now, the modularity, in terms of B and S is defined as 1/(4m)S^tB*S:
Modularity = N[(1/(4*m)*Transpose[S].B.S)[[1, 1]]]
.11111
This agrees with the built-in command.
The problem I encounter occurs when A corresponds to a weighted, undirected network. For example,
A = {{0, 3, 7, 0, 0}, {3, 0, 6, 0, 0}, {7, 6, 0, 2, 1}, {0, 0, 2, 0, 4}, {0,
0, 1, 4, 0}};
Mathematica again finds the two communities, {1,2,3} and {4,5}. This also makes sense if one draws the graph and looks at the edge weights.
However, CommunityModularity[G, {{1, 2, 3}, {4, 5}}] again yields .111111 again, when my modularity matrix approach yields .233459.
It appears Mathematica is not taking edge weights into account when computing the modularity. Is there an option I can add somewhere to address this problem?
"RawJSON"
into the variabledata
, then do this:nodes = data[["nodes", All, "value"]]; edges = Values /@ data[["links", All, {"source", "target"}]]; Graph[nodes, DirectedEdge @@@ edges]
. I have to leave now, so I won't be able to answer in full when you post your question. $\endgroup$