Re: [igraph] community detection algorithm

[uxzmdlj02]

Oops, important caveat:
In that first implementation it's possible for two distinct groups to  
end up with the same label. The paper describes this on page 9.
I fixed it, though not particularly elegantly, in the way they  
suggest. After the main algorithm runs, cycle through the groups and  
rename any with multiple components by appending ".0",".1",... to the  
end of the group names.
Also, experimenting, the algorithm can give very different results for  
different runs. It seems like the more ticks it takes to finish the  
finer-grained the community structure.
Here's the fixed version:

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("\rtick:",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
        }
    }
    ## now fix any distinct groups with same labels:
    for(i in unique(V(g)$group)){
        ## only bother for connected groups
        if(!is.connected(subgraph(g,V(g)[group==i]))){
            theseNodes <- V(g)[group==i]
            theseClusters <- clusters(subgraph(g,theseNodes))
            ## iterate through the clusters and append their names
            for(j in unique(theseClusters$membership)){
                V(g)[theseNodes[theseClusters$membership==j]]$group <-
                    paste(i,j,sep=".")
            }
        }
    }
    return(g)
}

On Dec 15, 2008, at 11:33 AM, Peter McMahan wrote:

> 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