Hi, > I just want to report, that igraph-R Infomap has still not finished computing > after 165,657 minutes (16+ weeks). Compared to the same community detection > done in C++ implementation (4 min) this is a factor of 41414. That makes me > wonder whether or not the Infomap implementation in igraph may have a problem.
The Infomap implementation in igraph is identical to the last implementation of Infomap that was released by the authors under the GNU General Public License - the only part that was added is the conversion to/from igraph's graph data type. Unfortunately this was a long time ago -- Infomap has improved a lot, and as far as I know it was completely rewritten from scratch. The rewritten C++ implementation was released under the AGPL, which is not compatible with igraph's license, so we cannot include that in igraph. So, there are three possible cases here: 1. There is a bug somewhere in the original implementation of Infomap that we have included in igraph that yields such a large runtime for large graphs. 2. There is a bug between the conversion from/to igraph's data type and the Infomap algorithm, and this is the cause of the large runtime that you saw. 3. There is no bug, it just happens to be the case that the old Infomap implementation is not that performant on large graphs. Comparing the implementation in igraph with the _current_ (i.e. re-written, AGPL-based) Infomap implementation does not rule out any of these possibilities, unfortunately. > It does seem to work fine for small graphs but does not stop computing in a > reasonable time for large graphs. Is there a way for me to provide you with > more detailed information? Profiling the current implementation could help us pinpoint where most of the CPU time is spent. I could try profiling the implementation with Instruments.app on Mac OS X, but I'm quite short on spare time so it would help me a lot if you could upload an example graph somewhere and create a small, self-contained C file that loads the graph and runs Infomap on it. I could then compile it and load it into Instruments.app to find the hotspots, and then we'll see whether it could be fixed easily without modifying the source of the algorithm too much. T. _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
