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 <[email protected]> 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 <[email protected]> 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 >> [email protected] >> https://lists.nongnu.org/mailman/listinfo/igraph-help >> > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help >
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
