How to compare communities in two consecutive graphs

Question

I have the same graph represented at two different times, g.t0 and g.t1. g.t1 differs from g.t0 for having one additional edge but maintains the same vertices.

I want to compare the communities in g.t0 and g.t1, that is, to test whether the vertices moved to a different community from t0 to t1. I tried the following

library(igraph)

m <- matrix(c(0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0),nrow=4,ncol=4)

g.t0 <- graph.adjacency(m)
memb.t0 <- membership(edge.betweenness.community(g.t0))
V(g.t0)
# Vertex sequence:
#   [1] 1 2 3 4
memb.t0
# [1] 1 2 2 3

g.t1 <- add.edges(g.t0,c(1,2))
memb.t1 <- membership(edge.betweenness.community(g.t1))
V(g.t1)
# Vertex sequence:
#   [1] 1 2 3 4
memb.t1
# [1] 1 1 1 2

But of course the problem is that the indexing of the communities always start from 1. Then in the example it seems that all the vertices have moved to a different community, but the most intuitive reading is that actually only the vertex 1 changed community, moving with 2 and 3.

How could I approach the problem of counting the number of vertices that changed communities from t0 to t1?

Answer 1

Actually this is not an easy question. In general you need to match the communities in the two graphs, using some rule or criteria that the matching optimizes. As you can have different number of communities, the matching is not necessarily bijective.

There were several methods and quantities proposed for this problem, a bunch is implemented in igraph, see http://igraph.org/r/doc/compare.html

compare.communities(memb.t1, memb.t0, method="vi")
# [1] 0.4773856
compare.communities(memb.t1, memb.t0, method="nmi")
# [1] 0.7020169
compare.communities(memb.t1, memb.t0, method="rand")
# [1] 0.6666667

See the references in the igraph manual for the details about the methods.