Re: [igraph] Different results from fastgreedy.community on different systems

[Tamás Nepusz]

> 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