igraph-help
[Top][All Lists]

## Re: [igraph] Modularity of Specific Partitions

 From: Steward, Lucy Subject: Re: [igraph] Modularity of Specific Partitions Date: Tue, 21 Apr 2015 09:49:39 +0000

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