Re: [igraph] Modularity of Specific Partitions

[Steward, Lucy]

Thank you for your replies - the fastgreedy method seems to be the logical 
option, whilst still giving results consistent with my previous analysis, so I 
think I’ll proceed with that. 

Thank you so much for your help,
Many thanks
Lucy


On 20 Apr 2015, at 22:04, Fabio Daolio <address@hidden> wrote:

> 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
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help