[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Community detection: deterministic vs non-deterministic
From: |
R N |
Subject: |
Re: [igraph] Community detection: deterministic vs non-deterministic |
Date: |
Wed, 23 May 2012 16:56:13 +0300 |
> 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.