Re: [igraph] Modularity of Specific Partitions

[Fabio Daolio]

Dear Lucy,

if the network is not too big, you could also try the “spinglass.community” 
method
fixing the number of spins equal to the (maximum) number of partitions you need.

This does not ensure that you will get the optimal partitioning either, nor 
that you
will actually get the number of partitions you want (it could be less), but if 
you play
with the parameters (e.g. by setting a cooling factor very close to 1), you 
should get
reasonably good results in terms of modularity.

Best,
—
Fabio

> On 20 Apr 2015, at 22:33, Tamas Nepusz <address@hidden> wrote:
> 
> 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.
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help