Modularity calculation for directed graphs in `cluster_edge_betweenness` and `cluster_infomap`

I’m interested in clustering (large) directed unweighted graphs. Both the clustering functions mentioned above offer the calculation of modularity. But this posting reports an error because:

The manual for igraph v1.3.4 does not go into detail on pages 74 and 78. modularity = TRUE is the default in both functions. Is the error mentioned above not relevant anymore because the igraph developers implemented modularity for directed graphs? Sorry if I missed that.
Or, and I’ve seen this elsewhere, would directedness information be dropped for this calculation?
Thank you!

modularity() does support directed graphs in igraph 1.3 (I don’t recall in which version this was implemented, possibly earlier). The definition of directed modularity should be added to the docs. For now, you’ll find it in the C/igraph docs: igraph Reference Manual

The Infomap algorithm does not use modularity internally in any way. This change does not affect the result. modularity=TRUE simply requests a calculation of modularity after the Infomap algorithm was completed, and now this will take edge directions into account.

As for cluster_edge_betweenness(), let’s rehash how the Girvan–Newman algorithm works:

  1. Compute the betweenness of all edges.
  2. Remove the edge with the highest betweenness.
  3. If this removal increases the number of connected components, we record the “split” we have just seen. This will be used for constructing a dendrogram.
  4. Repeat from 1 until no edges are left.

The output is now a hierarchical clustering represented as a dendrogram. To get one specific community structure, we need to decide where to cut the dendrogram. The cut is chosen so as to maximize modularity.

When the graph is directed, then step 1 (edge betweenness) and the modularity calculation take into account edge directions. Step 3 does not, i.e. the function still checks when the weakly connected component count increases.

Normally, this algorithm is used for undirected graphs. While this function replicates the same steps for directed ones, I will leave it to you to decide whether the output is useful in this case, or to search the literature on directed generalizations of this algorithm.

1 Like