scalable clustering embedded vertices

[jovo]

given the embedded graph, cluster the vertices, possibly hooking in to a scalable clustering code, such as kmeans++ or kmeans||

eventually, we will want to consider hooking in to something like mclust (http://cran.r-project.org/web/packages/mclust/index.html) or other highly scalable things, like louvain (http://perso.uclouvain.be/vincent.blondel/research/louvain.html) or Nerstrand (http://sc13.supercomputing.org/sites/default/files/PostersArchive/tech_posters/post193s2-file3.pdf)

[gaborcsardi]

I would need some clarifications here.

• mclust is already implemented in R, so I suppose it does not make much sense to put in igraph (as well).
• the Louvain algorithm is already in igraph.
• they claim that the Nerstrand software is also available for download, so this is also done.

So I am a bit lost with this.

[jovo]

hey gabor - i was just reporting notes from the discussion we all had in carey's office. it seems as if we already have a suitable solution in igraph/R, so perhaps this comment was moot. for clarification, in general, do you find that if something is in R, even if it does not exist in C and/or python, that it is not worth putting in igraph?

[gaborcsardi]

In general, if something is already implemented and freely available, we don't want to include it, unless including it in igraph makes it much more accessible to use (e.g. a hard to use C/C++ library), or the current implementation is inferior. So we would consider including a C/C++ lib, that is expected to be widely used, but probably not a big piece of software (igraph is already huge!), or something that is already in R/Python.

But we/I always decide case by case. E.g. if somebody is (1) willing to program their methods in a way that is easy to include and (2) provide patches/pull requests, complete with docs and testing, then is likely that we include it. Even if people do this, it is a lot of work to go through the code and make sure it passes CRAN checks, etc.

In general the problems with including third party code:

• we don't know this code, and as soon as it is in igraph, we need to support it, fix its bugs, answer questions about it on the igraph mailing list, etc. This can be a pain. I have spent probably months answering questions and hunting bugs in other people's sketchy code.
• we need to follow updates by original authors and merge them with our changes, which is also a pain.
• we want to promote our own methods, and there is plenty of work implementing these in an efficient and user friendly way, so I would rather work on this, than hacking in external libraries.
• there are a lot other smaller issues, like licensing, etc.

[jovo]

understood. so louvain is already in there, mclust is already good, so let's close this one.