Re: [igraph] community detection algorithm

[Gábor Csárdi]

Thanks everyone, I've added this to the ever growing TODO list. It
seems quite simple to implement it, and the quick R implementation by
Peter can be used to check correctness easily, so there is hope.

Best,
Gabor

On Mon, Dec 15, 2008 at 11:08 PM, Rajarshi Guha <address@hidden> wrote:
> Many thanks!
> On Dec 15, 2008, at 1:26 PM, address@hidden wrote:
>
>> 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
>>>
>>
>>
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM