[BioC] identifying network communities in a protein-protein interaction graph

[Stijn van Dongen]

      Hi All, hi Avril,

On Mon, Jan 18, 2010 at 05:10:53PM -0000, Coghlan, Avril wrote:
> Dear all,
> I am wondering is there any function available in Bioconductor or other
> R libraries for detecting network communities in protein-protein
> interaction graphs (where a "network community" is defined as a part of
> a network that has more internal connections than to the rest of the
> network)?


Can I just point out that 'network community detection' is exactly the same
thing as network clustering, aka graph clustering?

I wrote and maintain MCL, a generic cluster algorithm for graphs, which has
been used for PPI graphs by various people I believe
   (see e.g. http://www.biomedcentral.com/1471-2105/7/488/abstract).

Someone else mentioned igraph. There is code available in igraph to
call MCL externally, see
   http://igraph.wikidot.com/community-detection-in-python
Quite likely they implement other (popular) algorithms as well.

Rob Gevers wrote R code to call MCL externally from R:
   http://www.rob-gevers.com/pmwiki.php/MclR/MclR

These two solutions require installing MCL separately from
   http://micans.org/mcl

An important aspect in clustering PPI graphs is, I believe, the quality of the
input. I recommend preprocessing it to make sure that there are no nodes of
very high degree.  One approach is to use a k-nearest neighbour approach,
keeping edges only if they are in the list of top k edges (according to
similarity) for both of the incident nodes. MCL has additional options to
facilitate this kind of processing. Should you be interested, I would be glad
to help.

I have not used Rob's code myself, but it looks nice in that it is simple, uses
the prefered exchange format, and should be easily modifiable to accommodate
for example passing of additional MCL parameters. I'd be glad to hear any
feedback or suggestions (which I'll try to pass on).

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