igraph-help
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] trying to understand edge betweeness community detection im


From: Enzo Tagliazucchi
Subject: Re: [igraph] trying to understand edge betweeness community detection implemented in igraph (re-send)
Date: Thu, 21 May 2009 17:39:19 -0400

Gabor,

I don't get the same values. When running the following code (which prints the modularity values obtained by the merges, without constructing the membership vector),

#include <igraph.h>
#include <stdio.h>
int main(void)
{
     FILE *fp;  
     printf("Abriendo el archivo... \n");   
    fp = fopen("karate.txt", "r");
 
     igraph_t graph;
     igraph_read_graph_edgelist(&graph, fp, 0, 0);
     igraph_matrix_t merges;
     igraph_vector_t result;
     igraph_vector_t membership;
     igraph_vector_t modularity;
     long int largo;
     igraph_vector_init( &result, 0);
     igraph_vector_init( &membership, 0);
    igraph_vector_init( &modularity, 0);
     igraph_matrix_init( &merges, 0,0);
    int nodes;
    int steps;
     nodes = 34;
     int i;    
    igraph_community_fastgreedy(&graph, NULL, &merges, &modularity);
      for (i=0 ;i< nodes;i++)  {   
     printf( "%f\n", VECTOR(modularity)[i] )   ;
       }
     igraph_destroy(&graph);
     return 0;
}

When running this code, I get the following modularity values,

-0.049803
-0.037640
-0.013971
-0.001479
0.017751
0.049063
0.061226
0.078485
0.094675
0.111111
0.123192
0.145874
0.157709
0.169050
0.180227
0.196992
0.208169
0.219181
0.229372
0.239563
0.253369
0.269149
0.289448
0.299310
0.311144
0.320513
0.329553
0.338264
0.349359
0.362837
0.375986
0.380671
0.371795

These are rather different from the ones I got by the anterior procedure. Also, if I take a look at the membership vector at the last merge, I get the following membership vector,

20.000000
18.000000
0.000000
4.000000
1.000000
17.000000
15.000000
19.000000
0.000000
10.000000
4.000000
16.000000
8.000000
1.000000
9.000000
3.000000
4.000000
15.000000
0.000000
2.000000
0.000000
5.000000
10.000000
6.000000
14.000000
7.000000
7.000000
8.000000
13.000000
1.000000
8.000000
10.000000
12.000000
11.000000


If the membership vector is supposed to have in each entry the ID component of the corresponding node, this just make any sense to me as the membership vector corresponding to the last merge. I've checked the vector for other methods (edge betweeness for example).  The network should be divided in two parts approximately by the Girvan-Newman algorithm, when all merges but one are being performed. However, I get the membership vector,

7.000000
4.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
3.000000
2.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
1.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
5.000000
0.000000
0.000000
6.000000


All this implies to me that either:
a)  something is going wrong with the algorithms or my code (unlikely to me)
b)  I've problems interpretating the results of the algorithms  (this might be the case)

Thanks for the support thus far (and for the patience)

Enzo




On Thu, May 21, 2009 at 4:39 PM, Gábor Csárdi <address@hidden> wrote:
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


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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]