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

[R N]

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