igraph_community_label_propagation crashes if component has all negative initial values

[Nick Hamblet]

The following R code:

library(igraph)
label.propagation.community(graph(c(1,2),n=3,directed=FALSE), initial=c(-1,-1,0))

causes R to abort, with a Backtrace and Memory Map outputted. The top of the backtrace suggests that the issue is in the modularity calculation:

*** glibc detected *** /usr/lib64/R/bin/exec/R: double free or corruption (out): 0x00000000025b70f0 ***
======= Backtrace: =========
/lib64/libc.so.6(+0x78bb6)[0x7f36a5287bb6]
/lib64/libc.so.6(cfree+0x73)[0x7f36a528e483]
~/R/x86_64-pc-linux-gnu-library/2.15/igraph/libs/igraph.so(igraph_vector_destroy+0x11)[0x7f36a
11de681]
~/R/x86_64-pc-linux-gnu-library/2.15/igraph/libs/igraph.so(igraph_modularity+0x34e)[0x7f36a0fb
5a1e]
~/R/x86_64-pc-linux-gnu-library/2.15/igraph/libs/igraph.so(igraph_community_label_propagation+0x9b6)[0x7f36a0fb6af6]
~/R/x86_64-pc-linux-gnu-library/2.15/igraph/libs/igraph.so(R_igraph_community_label_propagation+0xa5)[0x7f36a1167715]

A similar issue can be achieved directly with
> modularity(graph(c(1,2),n=2,directed=FALSE), c(0,0))
but note that
> modularity(graph(c(1,2),n=2,directed=FALSE), c(1,1))
does not fail. It seems like this suggests that the issue was introduced when igraph switched from 0-indexing to 1-indexing, though I do not know for certain.

[Gábor Csárdi (gabor.csardi)]

OK, I cannot really reproduce this on OSX, but I think I found the bug. Is this right, Tamas?

=== modified file 'src/community.c'
--- src/community.c 2012-11-19 20:30:26 +0000
+++ src/community.c 2013-02-01 01:58:56 +0000
@@ -1940,7 +1940,7 @@ int igraph_community_label_propagation(c
     }
     /* Check if the labels used are valid, initialize membership vector */
     for (i=0; i<no_of_nodes; i++) {
- if (VECTOR(*initial)[i] < -1) {
+ if (VECTOR(*initial)[i] <= -1) {
         VECTOR(*membership)[i] = 0;
       } else {
         VECTOR(*membership)[i] = VECTOR(*initial)[i] + 1;

[Tamás Nepusz (ntamas)]

Yes, this is probably right; any negative number in the "initial" vector should denote a node without a label. Maybe it would be even better to use VECTOR(*initial)[i] < 0 because theoretically the user could put -0.5 into the "initial" vector to denote an unlabeled vertex. And we should also use floor(VECTOR(*initial)[i])+1 in the other branch of the condition

[Gábor Csárdi (gabor.csardi)]

OK, I fixed this, but there is still something wrong here:

library(igraph)
label.propagation.community(graph(c(1,2), n=3, dir=FALSE),
                             initial=c(-1,-1,1))$membership
# [1] 0 0 1
label.propagation.community(graph(c(1,2), n=3, dir=FALSE),
                             initial=c(-1,1,-1))$membership
# [1] 1 1 0
label.propagation.community(graph(c(1,2), n=3, dir=FALSE),
                             initial=c(-1,1,1))$membership
# [1] 1 1 1

I am not sure where the zeros come from, but this seems to be another bug.

[Tamás Nepusz (ntamas)]

Zero means "no label", which happens if all the initial labels are defined to be missing in a connected component. E.g., in the first case, neither node 1 nor node 2 has a label in the initial configuration, and since they are in a separate component, they will never acquire one. I believe it is consistent with the initial conditions.

[Gábor Csárdi (gabor.csardi)]

Probably fixed in revision #3070 (0.6-main) and #3113 (0.7-main), but I am not completely sure, since I have never seen the segmentation faults and did not find anything wrong with modularity().

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/130