Community detection with InfoMap algorithm producing one massive module

Question

I am using the InfoMap algorithm in the igraph package to perform community detection on a directed and non-weighted graph (34943 vertices, 206366 edges). In the graph, vertices represent websites and edges represent the existence of a hyperlink between websites.

A problem I have encountered after running the algorithm is that the majority of vertices have a membership in a single massive community (32920 or 94%). The rest of the vertices are dispersed into hundreds of other tiny communities.

I have tried different settings with the nb.trials parameter (i.e. 50, 100, and now running 500). However, this doesn't seem to change the result much.

I am feeling rather exasperated because the run-time on the algorithm is quite high, so I have to wait each time for the results (with no luck yet!!).

Many thanks.

Answer 1

Thanks for all the excellent comments. In the end, I got it working by downloading and running the source code for Infomap, which is available at: http://www.mapequation.org/code.html.

Due to licence issues, the latest code has not been integrated with igraph.

This solved the problem of too many nodes being 'lumped' into a single massive community.

Specifically, I used the following options from the command line: -N 10 --directed --two-level --map

Kudos to Martin Rosvall from the Infomap project for providing me with detailed help to resolve this problem.

For the interested reader, here is more information about this issue:

When a network collapses into one major cluster, it is most often because of a very dense and random link structure ... In the code for directed networks implemented in iGraph, teleportation is encoded. If many nodes have no outlinks, the effect of teleportation can be significant because it randomly connect nodes. We have made new code available here: http://www.mapequation.org/code.html that can cluster network without encoding the random teleportation necessary to make the dynamics ergodic. For details, see this paper: http://pre.aps.org/abstract/PRE/v85/i5/e056107

Answer 2

I was going to put this in a comment, but it ended up being too long and hard to read in that format, so this is a tangentially related answer.

One thing you should do is assess whether the algorithm is doing a good job at finding community structure. You can try to visualise your network to establish:

1. Is the algorithm returning community structures that make sense? Maybe there is one massive community?
2. If not does the visualisation provide insight as to why?

This will help inform your next steps. Maybe the structure of the network requires a different algorithm?

One thing I find useful for large networks is plotting your edges as a heatmap. This is simple to do if you have your edges stored in an adjacency matrix.

For this, you can use the image function, passing in your matrix of edges as the argument z. Hopefully this will allow you to see by eye the community structure.

However you also want to assess the correctness of your algorithm, so you want to sort the nodes (rows and columns of your adjacency matrix) by the community they've been assigned to.

Another thing to note is that if your edges are directed it may be more difficult to assess by eye as edges can appear on either side of the diagonal of the heatmap. One thing you can do is instead plot the underlying graph -- that is the adjacency matrix assuming your edges are undirected.

If your algorithm is doing a good job, you would expect to see square blocks along the diagonal, one for each detected community.