Dear all, There is a paper published last year on PLOS Comp Biol in which the authors used the concept of "distance between networks" to break the ties.
Andrade et al (2011): http://dx.plos.org/10.1371/journal.pcbi.1001131 Andrade et al (2008): http://www.sciencedirect.com/science/article/pii/S0375960108009158 Considering a pair of networks i and j that have the same number of nodes, they call "distance between networks" as a measure calculated using the shortest paths and the diameter of i and j, as defined by Andrade et al (2008). If i is equal to j the distance is 0, if i and j are completely different (if i is a complete network and j is a network with no edges, or vice-versa) the distance is 1. Andrade et al (2011) perform the EB algorithm and in parallel evaluate the distance between the network in the step t and in the step t+1 of the EB. The value of the distance is higher when the removal of an edge breaks the network in modules. So, the distance could be a non-deterministic parameter to break the ties of the module analysis. Did I explain my idea? In attach I send an example of the function "distance between networks" I have written, if you would like to use or adapt to your needs. All the best, Charles On Wed, May 23, 2012 at 3:56 PM, R N <[email protected]> wrote: > > 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. > > Thank you for explanation. I made this earlier classification > (WT, EB, FG: "deterministic"; spinglass, infomap, label propagation: > "non-deterministic") > from the results I've got using the data I have. , > The results were obtained on Debian 6.0 x86_64 -- maybe it is interesting, > if the results are platform-dependent. > >> What is a 'truly non-deterministic algorithm'? Depending on your >> definition, yes, infomap might not be 'truly non-deterministic'. > > I just thought that "truly non-deterministic algorithm" is the one > that yields a > different result with each run; for instance, if N partitions are obtained by > running an algorithm N times, and then all the partitions are compared > pairwise, > each-to-each, the similarity index (e.g., Jaccard similarity) would have > a nearly Gaussian distribution (or other random). But now I see that it is not > necessarily the case; e.g., if n ties are broken randomly at each run, > this would produce 2^n > different values for N>2^n runs. > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help -- Um axé! :) -- Charles Novaes de Santana http://www.imedea.uib-csic.es/~charles PhD student - Global Change Laboratorio Internacional de Cambio Global Department of Global Change Research Instituto Mediterráneo de Estudios Avanzados(CSIC/UIB) Calle Miquel Marques 21, 07190 Esporles - Islas Baleares - España Office phone - +34 971 610 896 Cell phone - +34 660 207 940
distance.R
Description: Binary data
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
