Re: [igraph] trying to understand edge betweeness community detection implemented in igraph (re-send)

[Enzo Tagliazucchi]

Gabor,

thanks for the swift reply. I seem to have some problem when passing from merge to membership. For example, I use

igraph_community_fastgreedy(&graph, NULL, &merges, &modularity);

to search for community structure and store the modularity results. The greatest modularity seems to be 0.362837 just before the final merge. 

Now, if I do it another way, storing the membership vector for incresing number of steps taken in the merge, and then find the modularity associated with that membership vector, using the following code:

  igraph_community_fastgreedy(&graph, NULL, &merges, NULL);               // find the merges

      for (i=0 ;i< nodes;i++)  {    
        igraph_community_to_membership(&merges,  nodes,  i, &membership, NULL);             // pass to membership, after "i" merges
        igraph_modularity(&graph ,&membership, &modularity, NULL);                                      // find modularity associated to that membership
    printf( "%f\n", modularity )   ;                                                                                                 // print modularity
       }


When I do this, I find rather different results (see at the end of this mail). Even by visual inspection, the results seem to be nonsense (for example, like 17 different clusters at the lasts steps of the merge). So I'm confused and I think that I'm doing something wrong when constructing the membership vector...

Enzo

PD: I get this modularities when I do it the second way:

-0.049803
-0.046022
-0.043228
-0.059993
-0.041831
-0.041831
-0.008218
-0.033859
-0.019642
-0.018245
-0.021778
-0.008958
-0.012738
-0.005588
0.034024
0.017012
0.028189
0.040927
0.046022
0.018409
0.049638
0.045201
0.055227
0.034845
0.029011
0.041502
0.045447
0.045447
0.041502
0.045447
0.045447
0.032216
0.041995
0.032216

)

On Thu, May 21, 2009 at 2:37 AM, Gábor Csárdi <address@hidden> wrote:

Hi Enzo,

On Thu, May 21, 2009 at 8:16 AM, Enzo Tagliazucchi <address@hidden> wrote:
>  (sorry for duplicate!)
>
>
> Hi all Igraphers,
>
> I'm trying to get a grasp of the community detection algorithms implemented
> in igraph, focusing in Girvan-Newman. Unfortunately, I'm getting nowhere.
> I'm working (as you'd probably guess) with Zachary Karate Club graph to test
> my results.
>
> My first and most fundamental question will be: what is the format of the
> membership vector? If a have 34 nodes, I expect to find a list of 34 numbers
> which would be the list of the 34  nodes components ID?

It is actually exactly that:

g <- graph.full(5) %du% graph.full(5) %du% graph.full(5)
g <- add.edges(g, c(0,5, 0,10, 5, 10))
ebc <- edge.betweenness.community(g)
community.to.membership(g, ebc$merges, steps=12)
$membership
 [1] 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2

$csize
[1] 5 5 5

> Is the merging from
> leaf nodes to bigger clusters or in reverse?

You mean agglomerative vs. divisive? The algorithm is divisive, but
the merges are represented in an agglomerative way.

> I couldn't find much help in the igraph documentation , so any help will be
> greatly appreciated!

See e.g. http://igraph.sourceforge.net/doc/R/community.edge.betweenness.html
(which is the same as ?edge.betweenness.community)

merges  Logical constant, whether to return the merge matrix
representing the hierarchical community structure of the network. This
argument is called merges, even if the community structure algorithm
itself is divisive and not agglomerative: it builds the tree from top
to bottom. There is one line for each merge (ie. split) in matrix, the
first line is the first merge (last split). The communities are
identified by integer number starting from zero. Community ids smaller
than ‘N’, the number of vertices in the graph, belong to singleton
communities, ie. individual vertices. Before the first merge we have
‘N’ communities numbered from zero to ‘N-1’. The first merge, the
first line of the matrix creates community ‘N’, the second merge
creates community ‘N+1’, etc.

Gabor

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



--
Gabor Csardi <address@hidden>     UNIL DGM


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