Network modularity

Usage
1

I have been exploring recently the igraph (R) documentation, because I’m interested in calculating network modularities for undirected weighted graphs. Currently, I have that calculations done in Mathematica:

GraphAssortativity[G, FindGraphCommunities[G], 
   "Normalized" -> False]

Is there any way in which I can calculate this (or something similar) using the R implementation of igraph?

Thanks in advance for any advice.

2

R/igraph 1.3 does not support calculating assortativity without normalization. This feature has been implemented in the recently released C/igraph 0.10, and will be present in whichever R/igraph is based on that (1.4 or 2.0). Until then, you would need to implement this calculation from scratch, if you need it.

3

Thank you for your answer! It’s good that it will be avaible in the future. I will try to implement it from scratch, as you suggested.

4

I have tried to implement it from scratch using R/igraph. This is my code using a simple example:

edgelist = matrix(c(1,3, 2,1, 3,6, 4,6, 1,5, 5,4, 6,1), 
                  nrow=7, ncol=2, byrow=TRUE)  # Example edge list

G = igraph::graph_from_edgelist(edgelist) # Graph created

igraph::E(G)$weight = c(0.1, 0.2, 0.2, 0.15, 0.3, 0.3, 0.1) # Added weights

communities = c(1,1,2,2,2,2) # Example communities

m = igraph::gsize(G) # Total number of edges

k = igraph::strength(G) # Weighted degrees

delta = outer(communities, communities, FUN="==") # 1 if same community, else 0

w = igraph::as_adjacency_matrix(G, type="both", attr="weight", sparse=FALSE) # Weighted adjacency matrix

modularity = 1/(2*m) * sum((w - k %o% k / (2*m)) * delta) # Modularity

Using this code, I obtained Q = 0.0401, while in Mathematica and Python I obtained Q = 0.0741.

I tried the first equation that can be found in the NetworkX documentation. However, I haven’t obtained the same results.

Do you know why this R/igraph code gives a different result?

Thanks in advance for any help.

5

I’m sorry, I have to correct what I said above. The non-normalized “nominal” assortativity is actually the same as modularity, just as you show in your last post. So you can use modularity in R/igraph.

> modularity(G, communities, weights=E(G)$weight, directed = T)
[1] 0.09876543
> modularity(G, communities, weights=E(G)$weight, directed = F)
[1] 0.07407407

The default calculation is directed for directed graphs, which is what you have here. So use directed=F if you want undirected.

The assortativity implementation in C/igraph 0.10 which I mentioned does not actually support weights. So if you need weights, then you’d have to use modularity() anyway.

Comparison with Mathematica and IGraph/M:

In[352]:= 
edges = Partition[{1, 3, 2, 1, 3, 6, 4, 6, 1, 5, 5, 4, 6, 1}, 2];

In[353]:= weights = {0.1, 0.2, 0.2, 0.15, 0.3, 0.3, 0.1};

In[354]:= membership = {1, 1, 2, 2, 2, 2};

In[355]:= 
g = Graph[Range[6], DirectedEdge @@@ edges, EdgeWeight -> weights];

In[356]:= communities = IGMembershipToPartitions[g, membership]
Out[356]= {{1, 2}, {3, 4, 5, 6}}

In[357]:= IGModularity[g, communities, DirectedEdges -> True]
Out[357]= 0.0987654

In[358]:= IGModularity[g, communities, DirectedEdges -> False]
Out[358]= 0.0740741

In[359]:= GraphAssortativity[g, communities, "Normalized" -> False]
Out[359]= 0.0987654
6

Regarding your code, the problems are:

  • m should be the sum of weights
  • There’s a mix of directed an undirected concepts. k is undirected because mode='all' was the default. w is directed because the graph itself is directed.

Here’s an implementation of the directed version:

m = sum(E(G)$weight) # Total number of edges

kin = igraph::strength(G, mode='in') # Weighted degrees
kout = igraph::strength(G, mode='out') # Weighted degrees

delta = outer(communities, communities, FUN="==") # 1 if same community, else 0

w = igraph::as_adjacency_matrix(G, type="both", attr="weight", sparse=FALSE) # Weighted adjacency matrix

modularity = 1/m * sum((w - kin %o% kout / m) * delta) # Modularity

And undirected:

m = sum(E(G)$weight) # Total number of edges

kin = igraph::strength(G, mode='all') # Weighted degrees

delta = outer(communities, communities, FUN="==") # 1 if same community, else 0

w = igraph::as_adjacency_matrix(igraph::as.undirected(G), type="both", attr="weight", sparse=FALSE) # Weighted adjacency matrix

modularity = 1/(2*m) * sum((w - k %o% k / (2*m)) * delta) # Modularity
1 Like
7

Finally, just in case you were not aware, python-igraph is igraph’s Python interface and IGraph/M is its Mathematica interface. You can use much of the igraph functionality from those languages as well.

8

Thank you so much for your time and attention.

It’s weird, but I hadn’t found the modularity() function in the R/igraph documentation. It’s good that it’s implemented, it is very useful.

Thank you also for checking my code. I see the problems now. It has been valuable for me to learn, despite being implemented at the end.

Great job working on igraph, congratulations!

9

You can look for functions in the index: igraph R manual pages. The documentation does need some updates and editing, but modularity is mostly fine.