Re: [igraph] InfoMap and Isolated Vertices

[Nick Eubank]

Thanks a lot Emmanuel, both for the original integration of infomap and this detailed followup!

On Fri Jan 16 2015 at 5:42:36 AM Emmanuel Navarro <address@hidden> wrote:

Hi,

Sorry, I do not monitor so much igraph ML these days. Thanks to twitter, Nick points me this topic.

Good remarks.
I get back into this and indeed it seems false to say that Infomap (in igraph) do not work with isolated vertices (=degree zero).

By the way, this was true with Walktrap, but I just discover that it is no more the case :
https://github.com/igraph/igraph/commit/3465b4e60c587a412ae175a3f70a0f486613bf93

Infomap use random walks with "teleportation", thus isolated nodes (= degree zero) or disconnected components do not cause convergence issue (or other math problem).

And I do not remember implementation tricks that may raise issue with isolated nodes.

I also run it on some test graphs (with isolated nodes) it just work perfectly...

So I should say that I don't know why I wrote that in the documentation...

I do not have historical versions of my work (this was done before igraph mv to git and I lost my local bzr) so unfortunately I can't make archeology to better understand it. (maybe just a wrong copy from Walktrap documentation)

However for large networks it may be an optimization to run infomap on each disconnected components (isolated nodes are trival disconnected components). Indeed disconnected components are clearly largest possible communities, and so it is not necessary for Infomap to deal (= compute random walks) with the entire graph. However as greedy optimization in infomap "follow" the links to seek communities, i'm not sure this will really change anything in term of time complexity...

On Thu, Jan 15, 2015 at 8:59 PM, Tamas Nepusz <address@hidden> wrote:

> Since infomap is random-walk based, I _think_ the code would require some
> accommodation for disconnected components (like tunneling or code to
> iterate over components). But it's also possible that infomap has been
> updated since that comment was written and it's no longer relevant.
AFAIK the version of Infomap in igraph is essentially the same as an older
implementation written by Martin Rosvall. He has rewritten Infomap since and
released the new version under a license which is incompatible with igraph's
license, hence we have to stick to the old version in igraph. I don't know what
limitations the old version has, but since it's the same as Martin's old
implementation, I guess the limitations are also the same.

Yep, I can confirm. Infomap in igraph is the older implementation written by Martin Rosvall. I just refactor the code (structure, naming, etc.) to better understand it and make it more readable (and igraph compatible in term of memory managment) but I ditn't change any math computation.

++

Emmanuel
 

T.

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help