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

[Tamas Nepusz]

Hi Enzo,

Did you initialise the membership vector by calling igraph_vector_init
before using it in the for loop? If so,, can you send us the complete
source code that reproduces your problem (i.e., a single .c file that
can be compiled)? I don't see any immediate problem with your approach,
but you might have forgotten to initialise something, that's why I'm
asking for a full source code.

-- 
Tamas

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

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

pgp8Rzp4IgdAO.pgp
Description: PGP signature