igraph-help
[Top][All Lists]

 From: Gabor Csardi Subject: Re: [igraph] Need more information about memberships Date: Tue, 11 Mar 2008 13:52:09 +0100 User-agent: Mutt/1.5.13 (2006-08-11)

```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

> 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
>
>
>
> 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