On Fri, May 18, 2012 at 11:22 AM, R N <[email protected]> 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 > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help -- Gabor Csardi <[email protected]> MTA KFKI RMKI _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
