[Top][All Lists]

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

[igraph] Function to detect changes in community composition in an evolv

From: capitano . nemo
Subject: [igraph] Function to detect changes in community composition in an evolving network
Date: Sun, 27 Apr 2014 00:59:53 +0000
User-agent: autistici.org webmail

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

  # 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


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
    # 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
# 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}
# # 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)

reply via email to

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