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
_______________________________________________
igraph-help mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/igraph-help