Re: [igraph] Community finding in graphs

[Tamas Nepusz]

Hi,

I remember that once I implemented this using only a few lines of code  
in Python. Basically I sought for all the cliques of size k in the  
graph using Graph.cliques, then I created a clique overlap matrix  
where the rows and the columns of the matrix represented individual  
cliques and the element of the matrix was 1 if the two cliques  
differed only in a single vertex (e.g. the intersection of the two  
cliques was of size k-1), then I created a graph from the clique  
overlap matrix as an adjacency matrix and finally I calculated the  
connected components of the clique overlap graph. The communities  
consist of the vertices involved in the cliques represented by the  
vertices of the connected components of the overlap graph.
(AFAIK this is exactly the same approach that the authors'  
implementation uses in their CFinder program (see http:// 
www.cfinder.org), but of course it could be done more efficiently).

--
T.

On 2007.12.11., at 3:10, MATSUDA, Noriyuki wrote:

> Hi Gabor:
>
>    I just found an intriguing community detection algorithm that  
> tries to
> reflect overlaps
>
> > Gergely Palla, Imre Der始yi, Ill市 Farkas and Tam� Vicsek
> > Uncovering the overlapping community structure of complex networks  
> > in natrue and society
> > Nature 435, 814-818(9 June 2005)
>
>   I'd appreciate if you could implement this into igraph.
>
> At 5:43 PM +0100 07.12.10, Gabor Csardi wrote:
> > http://cneurocvs.rmki.kfki.hu/igraph/doc/html/igraph-Community.html
> >
> > G.
> >
> > On Mon, Dec 10, 2007 at 11:35:34AM -0500, Richard Geddes wrote:
> > > Hi,
> > >
> > > Does the igraph library contain a function to find communities?  I'm
> > > interested in an application that generally solves problems  
> > > described in:
> > >
> > > http://arxiv.org/abs/cond-mat/0408187
> > >
> > > Thanks
> > > Richard
> > >
> > >
> > > _______________________________________________
> > > igraph-help mailing list
> > > address@hidden
> > > http://lists.nongnu.org/mailman/listinfo/igraph-help
> >
> > --
> > Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK
> >
> >
> > _______________________________________________
> > igraph-help mailing list
> > address@hidden
> > http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
> --
> MATSUDA, Noriyuki　<in Kanji> 松 田 紀 之
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help