2013/2/11 Tamás Nepusz
<address@hidden>
> I am doing some research on networks and I find that fastgreedy.community returns different results when run on different PC.
fastgreedy.community is not fully deterministic because the original algorithm does not specify what should happen when more than one possible merge of communities would yield exactly the same increase in the modularity score. igraph chooses one of the possible merges quasi-randomly. "Quasi-randomly" means that there are no explicitly generated random numbers involved (the algorithm will always give the same result on the same machine), but it is unpredictable which of the possible merges igraph will perform. It is quite likely that in your case igraph chooses one of the possible merges on one machine and another one of the possible merges on another machine. Since the two merges are equivalent "locally" (they yield the same local increase in modularity) but not "globally" (one of them leads to a more advantageous situation than the other), it can happen that the final result differs both in terms of the number of communities and in terms of the actual modularity score.
To illustrate one possible source of randomness: igraph maintains a list of "neighboring communities" for each community and sorts the list by modularity gain in descending order. Sorting is done by the qsort function of the standard C library. Different qsort implementations may break ties in different ways; for instance, the man page of qsort on my machine says this:
"The algorithms implemented by qsort(), qsort_r(), and heapsort() are not stable; that is, if two
members compare as equal, their order in the sorted array is undefined."
This can easily lead to the behaviour I described above.
Best,
Tamas
_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help