Re: [igraph] Modularity in weighted networks

[Tamás Nepusz]

Hello,

I am having an issue with calculating modularities of weighted networks.

[…] To calculate the optimal, I have been using the edge.betweenness.community function as follows: 

The modularity yielded by the edge betweenness method is not necessarily equal to the best modularity that one can obtain on the same network. Calculating the optimal modularity is an NP-hard problem (as far as I know), and although igraph includes a function named optimal.community (which indeed calculates a possible partition corresponding to the optimal modularity on a given network), it is too slow for graphs that consist of more than a handful of vertices. From the code you sent, it seems like your graph includes >50 vertices so I guess that optimal.modularity will indeed be too slow. Furthermore, it does not support edge weights anyway.

The misunderstanding may have come from the fact that edge.betweenness.community indeed optimizes the modularity to derive the final partition, but this does not optimize across all possible partitions of the network. It simply tries all possible cuts of the *dendrogram* that the edge betweenness community detection method (which is a top-down hierarchical method) created. The modularity score that you see is the best among all possible cuts of the dendrogram but not necessarily among all possible cuts of the network.

Consider trying some of the other community detection methods in igraph that also support weights; maybe they yield a better modularity score than the edge betweenness method (which was designed for unweighed networks anyway and I always considered the usage of edge weights in this method as a bit of a “hack”). I would try fastgreedy.community and multilevel.community; they both support weights and run much faster than the edge betweenness method.

All the best,

Tamas