Re: [igraph] Choosing between different methods of detecting communities

[Gábor Csárdi]

On Wed, Oct 3, 2012 at 10:46 AM, Tamás Nepusz <address@hidden> wrote:
>> I am not sure, because the results are different from the same algorithm in 
>> SNAP, which also implement Girvan-Newman's algorithm while only unweighted 
>> version.
>
> The edge betweenness algorithm is not deterministic in the sense that it is 
> free to make a (possibly random) choice when there are two or more edges with 
> the same edge betweenness. Therefore, it is not guaranteed that different 
> implementations give exactly the same results, unless there are no ties in 
> edge betweenness values throughout the course of the algorithm.

The other option is that either igraph or SNAP are wrong (or both of
them, probably unlikely).

This would be quite easy to check, all you need to do is to look at
the edge-betweenness values used for eliminating the edges from the
graph, and the sequence of the eliminated edges themselves. These
should match in the igraph and SNAP output, until the first ties, i.e.
multiple edges with the same edge betweenness.

If you send me your graph and the SNAP output, then I can check it.

G.

> --
> T.
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI