Jose A. Rodriguez of the University of Barcelona created a network of the individuals involved in the bombing of commuter trains in Madrid on March 11, 2004. Rodriguez used press accounts in the two major Spanish daily newspapers (El Pais and El Mundo) to reconstruct the terrorist network. The names included were of those people suspected of having participated and their relatives. Rodriguez specified 4 kinds of ties linking the individuals involved:

These four were added together providing a strength of connection index that ranges from 1 to 4.

Dataset

Data challenges

  1. Use k-connected components to find the cohesive groups of terrorists. Highlight the cohesive groups in the graph
  2. Apply different node removal strategies to stress the resilience of the network

Analysis

library(igraph)

Read dataset

terrorists = read_csv("names.csv")
## Parsed with column specification:
## cols(
##   name = col_character()
## )
ties = read_csv("edges.csv")
## Parsed with column specification:
## cols(
##   from = col_integer(),
##   to = col_integer(),
##   weight = col_integer()
## )
terrorists = mutate(terrorists, id = 1:nrow(terrorists)) %>% select(id, everything())

# make graph
g = graph_from_data_frame(ties, directed = FALSE, vertices = tibble(1:nrow(terrorists)))

Cohesive groups

# cohesion structure
b = cohesive_blocks(g)

# print hieararchy of blocks
print(b)
## Cohesive block structure:
## B-1                      c  0, n 70
## '- B-2                   c  1, n 64
##    '- B-3                c  2, n 49
##       '- B-6             c  4, n  5
##       '- B-7             c  4, n  5
##       '- B-8             c  3, n 33
##          '- B-10         c  4, n 26
##             '- B-11      c  5, n 24
##                '- B-13   c 10, n 11
##                '- B-14   c 10, n 11
##                '- B-15   c  8, n 10
##          '- B-12         c  4, n  5
##       '- B-9             c  3, n  9
##    '- B-4                c  5, n  7
##    '- B-5                c  2, n  3
# plot hieararchy of blocks with nodes labelled with block cohesion and size proportional to block size
s = sapply(blocks(b), FUN =length)
plot_hierarchy(b, vertex.label=cohesion(b), vertex.size=(s / max(s)) * 10 + 10) 

# graphs from blocks
bg = graphs_from_cohesive_blocks(b, g)
coords = layout_with_fr(g)

# plot some cohesive graphs
# c 10, n 11
h1 = bg[[13]]
plot(h1, layout=layout_with_fr(h1), vertex.size = 3, vertex.label=NA)

V(g)$color = "white"
n1 = blocks(b)[[13]]
V(g)[n1]$color = "red"
plot(g, layout=coords, vertex.label=NA, vertex.size = 5)

# c 10, n 11
h2 = bg[[14]]
plot(h2, layout=layout_with_fr(h2), vertex.size = 3, vertex.label=NA)

V(g)$color = "white"
n2 = blocks(b)[[14]]
V(g)[n2]$color = "blue"
plot(g, layout=coords, vertex.label=NA, vertex.size = 5)

# c 5, n 24
h3 = bg[[11]]
plot(h3, layout=layout_with_fr(h3), vertex.size = 3, vertex.label=NA)

V(g)$color = "white"
n3 = blocks(b)[[11]]
V(g)[n3]$color = "green"
plot(g, layout=coords, vertex.label=NA, vertex.size = 5)

Percolation

# percolation removes nodes from a graph and computes 
# the size of the giant connected component
# INPUT
# g: graph to percolate
# size: number of nodes to remove 
# d: removal vector
# OUTPUT
# giant: a vector with sizes of giant components when nodes are removed
percolate = function(g, size, d) {
  
  giant = vector()
  
  # initial size of giant component
  c = components(g)
  giant[1] = max(c$csize)
  
  names(d) = 1:length(d)
  d = sort(d, decreasing=TRUE)
  vital = as.integer(names(d[1:size]))
  
  for (i in 1:size) {
    c = components(delete_vertices(g, vital[1:i]))
    giant[i+1] = max(c$csize)
  }
  return(giant)
}


# resilience
size = vcount(g)/2
# random
rand = percolate(g, size, d = sample(V(g), size))    
# degree
deg = percolate(g, size, d = degree(g))    
# pagerank
pr = percolate(g, size, d=page_rank(g)$vector)    
# betweenness
bet = percolate(g, size, d = betweenness(g))    

plot(0:size, deg, type = "l", col=1, xlab="Number of removed nodes", ylab="Size of giant component")
lines(0:size, pr, col=2)
lines(0:size, bet, col=3)
lines(0:size, rand, col=4)
lines(0:size, rep(vcount(g)/2, size+1), lty=2)
legend(x = "bottomleft", legend = c("deg", "pr", "btw", "rand"), lty = 1, col = 1:4)