Re: [igraph] community detection algorithm

[uxzmdlj02]

Hi,
I like the algorithm, nice idea.
I punched out a quick and dirty function for it in R (below). `g` is  
an igraph object. `mode` can be one of "in", "out", or "all",  
specifying how group labels should propegate (`mode` is simply passed  
to the nei() iterator). The returned graph has a new vertex attribute  
called "group". (just tested it on a couple of small graphs, so don't  
know about run time or bugs)
Peter


largeScaleCommunity <- function(g,mode="all"){
    V(g)$group <- as.character(V(g))
    thisOrder <- sample(vcount(g),vcount(g))-1
    t <- 0
    done <- FALSE
    while(!done){
        t <- t+1
        cat(t)
        done <- TRUE ## change to FALSE whenever a node changes groups
        for(i in thisOrder){
            ## get the neighbor group frequencies:
            groupFreq <- table(V(g)[nei(i,mode=mode)]$group)
            ## pick one of the most frequent:
            newGroup <- sample(names(groupFreq) 
[groupFreq==max(groupFreq)],1)
            if(done){done <- newGroup==V(g)[i]$group}
            V(g)[i]$group <- newGroup
        }
    }
    return(g)
}



On Dec 13, 2008, at 9:11 PM, Rajarshi Guha rguha-at-indiana.edu | 
igraph-help| wrote:

> Hi, I came across a community detection algorithm
>
>          http://link.aps.org/doi/10.1103/PhysRevE.76.036106
>
> which appears to avoid the need for minimizing an objective  
> function. Are there any plans/interest on including this into igraph?
>
> -------------------------------------------------------------------
> Rajarshi Guha  <address@hidden>
> GPG Fingerprint: D070 5427 CC5B 7938 929C  DD13 66A1 922C 51E7 9E84
> -------------------------------------------------------------------
> A committee is a life form with six or more legs and no brain.
>         -- Lazarus Long, "Time Enough For Love"
>
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help