[igraph] Function to detect changes in community composition in an evolving network

[capitano . nemo]

Hi list

I share a possible solution to compare the evolution of the community 
structure over time. I came up with a function that I think produces 
quite intuitive results. I like to know what you think and whether it 
makes sense.

My problem first. I want to find out in a series of successive graphs 
(g), representing at different time (t) the relations among a given set 
of nodes, the number of nodes that changed community, stayed in the same 
community, or were not active at that time (thus with no relation).

For each g I run the edge betweenness algorithm

   ebc <- edge.betweenness.community(g)

and I create a vector with the id of each node and named after the 
detected community.

   memb <- V(g)$static_id
   names(memb) <- membership(ebc)

I will then have something like

  memb
  # 1  2  2  3  4  4  5  6  6  6
  # 1  2  3  4  5  6  7  8  9 10

Now, I define a threshold value of 2/3 to compare two communities. That 
is, a community at time t (vertex_comm1) is the same community at time t 
+ 1 (vertex_comm2) if the number of the vertices the two communities 
have in common

  length(intersect(vertex_comm1, vertex_comm2))

divided by the number of vertices of the community at time t

  length(vertex_comm1)

is less that 2/3.

And here the whole function to compare the communities:

compare_communities <- function (memb1, memb2, ratio) {
  # Create empty list to be returned by function
  vertex_dynamic <- list()
  vertex_dynamic[['missing']] <- 0
  vertex_dynamic[['changed']] <- 0
  vertex_dynamic[['same']] <- 0
  for (vertex in memb1) {
    # vertex_comm1 <- find community of vertex in comm1
    vertex_comm1 <- unname(memb1[names(memb1) %in% 
names(memb1[match(vertex,memb1)])])
    # vertex_comm2 <- find community of vertex in comm2
    vertex_comm2 <- unname(memb2[names(memb2) %in% 
names(memb2[match(vertex,memb2)])])
    if (length(vertex_comm2)==0) {
      vertex_dynamic[['missing']] <- vertex_dynamic[['missing']] + 1
      next
    }
    # Evaluating special case when community at t1 is size 1
    if (length(vertex_comm1)==1 & length(vertex_comm2)>1) {
      vertex_dynamic[['changed']] <- vertex_dynamic[['changed']] + 1
      next
    }
    # Similarity is evaluated by comparing the number of common elements 
with the number
    # of elements in the community at t1
    similarity <- length(intersect(vertex_comm1, vertex_comm2)) / 
length(vertex_comm1)
    if (similarity < ratio) {vertex_dynamic[['changed']] <- 
vertex_dynamic[['changed']] + 1}
    else {vertex_dynamic[['same']] <- vertex_dynamic[['same']] + 1}
  }
  return(vertex_dynamic)
}
# # To test
# memb1 <- c(1,2,3,4,5,6,7,8,9,10)
# names(memb1) <- c(1,2,2,3,4,4,5,6,6,6)
# memb2 <- c(1,2,3,4,5,6,7,9,10)
# names(memb2) <- c(1,1,1,2,3,3,4,5,6)