0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ About your Star Wars network: But to make this simpler for you, I recommend importing as "RawJSON" into the variable data, 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$ – Szabolcs Feb 23 '17 at 16:21
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I had tried WeightedAdjacency graph but didn't remember to remove the self-loops. This is extremely helpful! $\endgroup$ – fishbacp Feb 14 '17 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.