Re: [igraph] Need more information about memberships

[Gabor Csardi]

Zhigang Wu,

here is some clarification. I'll use R because it is much quicker to
write the code. It is easy to "translate" it to C

Let's create your graph first

> g <- graph( c(1,2,1,3,1,4, 2,3,2,4, 3,4, 4,5, 5,6,5,7,6,7)-1, dir=FALSE )
> cs <- fastgreedy.community(g)
> cs
$merges
     [,1] [,2]
[1,]    6    5
[2,]    4    7
[3,]    0    2
[4,]    1    9
[5,]    3   10
[6,]   11    8

$modularity
[1] -1.500000e-01 -7.000000e-02  7.000000e-02  1.250000e-01  2.350000e-01
[6]  3.550000e-01 -1.110223e-16

This means that you need to merge vertices #6 and #5 first (7 and 6
in your notation) into cluster #7. Then the new cluster is merged 
with #4 (5), to form cluster #8. So we have #4, #5, #6 (5,6,7) in a cluster
so far. Then come 0 and 2 into #9, (1,3), #1 into this new cluster to form 
cluster #10, #3 to these to form cluster #11. 

At this point we have #4,#5,#6 and #0,#1,#2,#3, (5,6,7 and 1,2,3,4 in
the original notation). Finally #11 and #8 are merged.

If you look at the modularity values, it is clear that the top
modularity is before the last merge, where we had the two clusters.

community.to.membership can be used to transform the merge martix 
into a membership vector. First we check for the highest modularity:

> steps <- which.max(cs$modularity)-1

Then perform 'steps' merges:

> memb <- community.to.membership(g, cs$merges, steps)
> memb
$membership
[1] 0 0 0 0 1 1 1

$csize
[1] 4 3

So we have two communities, one with the first four vertices, and 
the other with the remaining three.

Hope it is clear now,
G.

On Tue, Mar 11, 2008 at 08:38:57AM +0800, Zhigang Wu wrote:
> Hi, Gabor,
> 
>  
> 
> Now I want to use the function “igraph-community-to-membership()” to check the
> community structure results from the merges matrix. It is a pity that I am not
> very clear about the meaning of related parameters. Could you please tell me
> more about it?
> 
>  
> 
> Suppose there is a graph shown as follow:
> 
> community_structure_problem_fig01.jpg
> 
> The graph seems to have obvious community structure. Then what is the merges
> matrix built by igraph-community-fastgreedy()? Furthermore, how can I export
> the two communities (the 4-node complete graph {1, 2, 3, 4} and 3-node 
> complete
> graph {5, 6, 7}) by reading the output parameters (membership and csize) of
> function igraph-community-to-membership()?
> 
>  
> 
> Thanks a lot!
> 
>  
> 
> Regards
> 
>  
> 
> Zhigang Wu
> 
>  
> 
>  
> 



> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help


-- 
Csardi Gabor <address@hidden>    UNIL DGM