igraph-help
[Top][All Lists]

## Re: [igraph] Doubts with community multilevel Python algorithm

 From: Tamas Nepusz Subject: Re: [igraph] Doubts with community multilevel Python algorithm Date: Thu, 2 Jun 2016 21:21:24 +0200

Hi,

In the absence of an example that reproduces the problem, I can only
say that _in theory_, it is possible that some rare cases result in
communities being split when using the multilevel algorithm, although
it is definitely not common (you are the first one to report it).

For instance, consider a subgraph consisting of 3 vertices (a, b and
c) such that a is connected to b, b is connected to c, but a is not
connected to c and there are no other short paths leading from a to c.
In that case, if b belongs to a community X at a given iteration of
the algorithm, it _might_ happen (in rare cases) that both a and c
decide to move themselves to community X while, at the same time, b
decides to leave community X for another one. This would result in
community X being split into two disconnected components. Of course
this is not enough because further iterations of the algorithm might
annihilate one of the components (or both).

T.

On Thu, Jun 2, 2016 at 1:53 PM, Kuu <address@hidden> wrote:
> Unfortunately I work with sensible data and I don't have the option to
> extract information from my PC (I don't even have internet connection, this
> is sent from my smart phone), so I can not send it to you.
>
> El 2/6/2016 13:42, "Tamas Nepusz" <address@hidden> escribiÃ³:
>
> Hello,
>
> Can you send us a graph that reproduces this behaviour?
> T.
>
>
> On Thu, Jun 2, 2016 at 1:31 PM, Kuu <address@hidden> wrote:
>> Hello,
>>
>> I have a graph that has disconnected components and I want to find
>> communities over it. I'm applying directly the community multilevel
>> algorithm, but I'm obtaining communities that aren't connected, which from
>> my point of view, those shouldn't be considered as a valid community.
>>
>> Should I run the algorithm only over connected components?? By reading the
>> original paper I understand that only two communities are merged if
>> they're
>> connected, but maybe I'm not understanding it correctly.
>>
>>
>> Regards,
>> Javier
>>
>>
>> _______________________________________________
>> igraph-help mailing list
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>
> _______________________________________________
> igraph-help mailing list
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
> _______________________________________________
> igraph-help mailing list