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

[Tamás Nepusz]

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

To complicate things further, it might be the case that an algorithm produces a 
deterministic result when being run on one particular machine, and a different 
but also deterministic result when being run on another machine. E.g., the edge 
betweenness community detection method has to choose between multiple edge 
removals when there is more than one edge in the network with the same maximal 
edge betweenness score. It might be the case that the algorithm chooses a 
particular edge when run on a 32-bit Windows machine and a different one when 
run on a 64-bit Linux machine -- but it will choose the _same_ edge when run 
again on the _same_ machine. I'd call this "weakly non-deterministic" behaviour.

-- 
T.