Re: [igraph] Using external software for community detection in R

[Stijn van Dongen]

On Wed, Oct 20, 2010 at 08:05:24PM +0200, Fabio Daolio wrote:
> First of all, thanks again for the great work on the library.
> 
> I'd like to share with you what I'm doing: possibly there's a
> better way to do it, maybe this could be useful to somebody
> else.
> I need to use the MCL algorithm, and I'd also like to try the
> InfoMap algorithm in the near future, using the R interface.
> 
> Let's say that my network is stored in the variable "df", that
> I'd like to pass it to MCL as a list of weighed edge, and that,
> finally, I'd like to assign a membership value to its vertices
> as a result of the community detection.
> 
> Here's what I came up with:
> 
> outfile<-"tmp.txt"
> cmd<-paste("mcl - --abc -o - >",outfile,sep="")
> pw<-pipe(cmd,open="wb")
> write.graph(df,file=pw,format="ncol")
> close(pw)
> 
> pr<-pipe(paste("cat ",outfile,sep=""),open="r")
> lines<-readLines(pr)
> comms<-strsplit(split="\t", lines)
> close(pr)
> 
> for(i in 1:length(comms)){
>       for(n in comms[[i]]){
>               V(df)[which(V(df)$name==n)-1]$memb<-i-1
>       }
> }
> 
> modularity(df,V(df)$memb)
> 
> 
> Basically I set up a pipe for writing the network to MCL,
> whose output is redirected to a temporary file, from which
> I read through another pipe. It works.
> 
> Is there a way to avoid even the creation of that tmp file?
> And is there a quicker way to assign memberships?


I'd be interested to help on an improved interface to MCL.  It could be that an
IPC type solutions with pipes or files is the best solution, but I would expect
it to incur quite a bit of overhead for really big graphs.  If there is
interest in a more integrated solution, the MCL software is reasonably modular,
and calling MCL from C code should be a small step, which I'd be more than
happy to provide. The biggest issue would be creation of the appropriate data
structure in memory.

Finally, it should be very easy to code a C mcl implementation from scratch.
The benefit of integrating with the http://micans.org/mcl code is that it is
IMO very memory efficient and scalable, as it takes care to maintain sparse
graphs with some speed/precision&memory trade-off control.

best,
Stijn

-- 
Stijn van Dongen         >8<        -o)   O<  forename pronunciation: [Stan]
EMBL-EBI                            /\\   Tel: +44-(0)1223-492675
Hinxton, Cambridge, CB10 1SD, UK   _\_/   http://micans.org/stijn