Re: [igraph] Modularity of Specific Partitions

[Tamas Nepusz]

Dear Lucy,

> I am running some modularity analysis, and would like to find the optimal
> modularity of a network partition, whilst specifying the final number of
> communities. For example, I would like to find the best partition of
> a network into 8 communities with the corresponding optimal modularity score.
Most modularity optimization algorithms (including all but one in igraph) are
heuristics, which mean that the community structure that you get in the end is
not necessarily optimal, and we can only expect that the end result is close to
the "real" optimum. This is because finding the community structure that yields
the highest possible modularity for a given network was shown to be
computationally hard [1]. Since the optimality is not guaranteed for the end
result of the algorithms, you can usually just take a community detection
method that is hierarchical (e.g., the fast greedy method or the walktrap
method) and cut the dendrogram at 8 communities if the method ended up with
less than 8 communities in the end. Basically, you are stopping the community
merging process before the method has reached its "optimum", which is not the
true optimum anyway.

[1] http://arxiv.org/abs/physics/0608255

The only exception to the above is the "optimal modularity" method in igraph,
which, as its name implies, finds the community structure that maximizes the
modularity score. Unfortunately this is computationally not feasible for most
graphs -- it scales up only to a handful of vertices, so this is probably not
applicable for your graphs. And even if it would be, you cannot specify the
number of communities in that algorithm.

All the best,
-- 
T.