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

[Gábor Csárdi]

Actually, I get exactly the same modularity scores (up to numerical
precision) for both the community finding algorithm and
igraph_modularity.

Where are the 17 clusters here? Your program just prints the
modularity scores and those seem to be ok, at least for the karate
graph.

Gabor

On Thu, May 21, 2009 at 6:27 PM, Enzo Tagliazucchi <address@hidden> wrote:
> Hi Tamas,
>
> here is the whole code i'm using:
>
>
>
> #include <igraph.h>
> #include <stdio.h>
>
>
> int main(void)
> {
>      FILE *fp;
>      fp = fopen("/karate.txt", "r");
>
>      igraph_t graph;
>      igraph_real_t modularity;
>      igraph_read_graph_edgelist(&graph, fp, 0, 0);      // read graph
>      igraph_matrix_t merges;
>      igraph_vector_t result;
>      igraph_vector_t membership;
>      igraph_vector_init( &result, 0);
>      igraph_vector_init( &membership, 0);
>      igraph_matrix_init( &merges, 0,0);
>      int nodes = 34;
>      int i;
>
>      igraph_community_fastgreedy(&graph, NULL, &merges, NULL);
>
>       for (i=0 ;i< nodes;i++)  {             // this is the loop to check
> modularity values obtained while increasing the number of merges
>
>         igraph_community_to_membership(&merges,  nodes,  i, &membership,
> NULL);
>         igraph_modularity(&graph ,&membership, &modularity, NULL);
>     printf( "%f\n", modularity )   ;
>
>        }
>
>      igraph_destroy(&graph);
>      return 0;
> }
>
>
>
> On Thu, May 21, 2009 at 6:35 AM, Tamas Nepusz <address@hidden> wrote:
>>
>> 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
>>
>>
>> _______________________________________________
>> 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