[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
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)

[Prev in Thread] |
**Current Thread** |
[Next in Thread] |

**[igraph] Function to detect changes in community composition in an evolving network**,
*capitano . nemo* **<=**