Re: [igraph] Community detection: deterministic vs non-deterministic

[Gábor Csárdi]

On Fri, May 18, 2012 at 11:22 AM, R N <address@hidden> wrote:
>> walktrap is definitely non-deterministic. edge betweenness and fast
>> greedy might be non-deterministic as well, when one needs to break
>> ties.
>
> I ran WT, EB, FG a number (=100) times on the same graph and the resulting
> partitions were the same for each instance of a run (I mean, of
> course, comparing different
> instances of running the same algorithm).

OK, for WT, you are of course right. The algorithm works based on
random walks, but does not perform them, only calculates
vertex-community distances based on them, in a deterministic way,
although I am not sure how it breaks ties.

For EB and FG the question is how you break the ties. In theory this
*could* be non-deterministic, i.e. random breaking of ties. For igraph
it is deterministic (if I remember well), but it might be platform
dependent. I.e. for some graph you might get a different result on a
different platform. This is essentially because of the differences in
numeric representations and operations between platforms.

> As for infomap, I run it N=100 times also for the same graph and then
> compared each partition
> to every other partition (calculating Jaccard similarity of the
> partition pair), resulting in
> N*(N-1)/2=4950 comparisons. For a truly nondeterministic algorithm,
> this would produce
> ~4950 distinct values of similarity indices, as the coincidences are
> very unlikely. In fact, I got
> 902 distinct values. I think, the number of coincidences is somehow
> unlikely high.
> The graphs in question have 1000 vertices and ~2000 edges each. Might
> the above observations
> be produced by some artefact of random number generation?

What is a 'truly non-deterministic algorithm'? Depending on your
definition, yes, infomap might not be 'truly non-deterministic'.

For me 'deterministic' means that it'll always give the same results
(at least on the same platform), and 'non-deterministic' means that it
is not deterministic.

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



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