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

[R N]

 > 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.

Thank you for explanation. I made this earlier classification
(WT, EB, FG: "deterministic"; spinglass, infomap, label propagation:
"non-deterministic")
from the results I've got using the data I have. ,
The results were obtained on Debian 6.0 x86_64 -- maybe it is interesting,
if the results are platform-dependent.

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

I just thought that "truly non-deterministic algorithm" is the one
that yields a
different result with each run; for instance, if N partitions are obtained by
running an algorithm N times, and then all the partitions are compared pairwise,
each-to-each, the similarity index (e.g., Jaccard similarity) would have
a nearly Gaussian distribution (or other random). But now I see that it is not
necessarily the case; e.g., if n ties are broken randomly at each run,
this would produce 2^n
different values for N>2^n runs.