Re: [igraph] Community detection: deterministic vs non-deterministic

[Charles Novaes de Santana]

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 <address@hidden> 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
> address@hidden
> 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