[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Different results from fastgreedy.community on different sy
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] Different results from fastgreedy.community on different systems |
Date: |
Mon, 11 Feb 2013 21:23:03 +0100 |
> 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