igraph-help
[Top][All Lists]

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

```