Calculating Network Modularity for Weighted Graphs

Question

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?

Answer 1

As of Version 10, CommunityModularity functionality is now available in the built-in Wolfram Language function "GraphAssortativity".

Anyway, we can still use the CommunityModularity function through GraphUtilities package.

The problem in your code is that you do not use as input a weighted adjacency matrix.You have to substitute AdjacencyGraph with WeightedAdjacencyGraph. Remember to remove self-loop (using ReplaePart):

  Needs["GraphUtilities`"]
adj = {{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}};
gW = WeightedAdjacencyGraph[ReplacePart[adj, {j_, j_} -> \[Infinity]],VertexLabels -> "Name", VertexSize -> Automatic, VertexLabelStyle -> Large];
com=FindGraphCommunities[gW];
CommunityModularity[gW, com]

and the output is not anymore .1111. I found 0.12.