Madrid train bombing network
Massimo Franceschet
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:
- Trust-friendship (contact, kinship, links in the telephone center).
- Ties to Al Qaeda and to Osama Bin Laden.
- Co-participation in training camps or wars.
- Co-participation in previous terrorist attacks (Sept 11, Casablanca).
These four were added together providing a “strength of connection” index that ranges from 1 to 4.
Some necessary preprocessing follows. Download the network (edges and weights; names of terrorists) and some auxiliary functions.
Read the network
library(igraph)
source("fun.R")# read edges
edges = matrix(scan("madrid-edges.dat", 0), ncol=3, byrow=TRUE)
# read names
names = scan("madrid-names.dat", "a")
# build graph
g = graph_from_edgelist(edges[,1:2], directed=FALSE)
# add weights
E(g)$weight = edges[,3]
# remove multi-edges
g = simplify(g)
E(g)$weight = E(g)$weight / 2
V(g)$names = names
# delete isolated nodes
g = delete_vertices(g, which(degree(g) == 0))
names = V(g)$names
# nodes are red
V(g)$color = "red"Visualization
coords = layout_with_fr(g)
plot(g, layout=coords, vertex.label=NA, vertex.size = 5)
Centrality
Strength (weighted degree)
d = strength(g)
#d = degree(g)
names(d) = V(g)$names
summary(d)## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 1.000 2.750 6.000 8.812 12.000 43.000hist(d, xlab="Degree", main="Histogram of node weighted degree centrality", breaks=seq(min(d), max(d), (max(d) - min(d))/10))
sort(d, decreasing=TRUE)[1:5]## Jamal Zougam Imad Eddin Barakat Mohamed Chaoui
## 43 35 34
## Amer Azizi Galeb Kalaje
## 27 21plot(g, layout=coords, vertex.label=NA, vertex.size = (d / max(d)) * 10)
PageRank
pr = page_rank(g)$vector
names(pr) = V(g)$names
summary(pr)## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 0.003515 0.006707 0.013920 0.015620 0.018550 0.059020hist(pr, xlab="Pagerank", main="Histogram of node Pagerank centrality", breaks=seq(min(pr), max(pr), (max(pr) - min(pr))/10))
sort(pr, decreasing=TRUE)[1:5]## Jamal Zougam Imad Eddin Barakat Mohamed Chaoui
## 0.05902296 0.04910647 0.04741141
## Amer Azizi Naima Oulad Akcha
## 0.03721520 0.02943030plot(g, layout=coords, vertex.label=NA, vertex.size = (pr / max(pr)) * 10)
Current-flow betweenness
fb = cfb(as_adjacency_matrix(g, attr="weight", sparse=FALSE))
names(fb) = V(g)$names
summary(fb)## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 0.03125 0.04871 0.06304 0.08932 0.11120 0.28680hist(fb, xlab="Flow betweenness", main="Histogram of node flow betweenness centrality", breaks=seq(min(fb), max(fb), (max(fb) - min(fb))/10))
sort(fb, decreasing=TRUE)[1:5]## Jamal Zougam Semaan Gaby Eid Mohamed Chaoui
## 0.2868397 0.2686573 0.2476514
## Imad Eddin Barakat Naima Oulad Akcha
## 0.2314457 0.2109809plot(g, layout=coords, vertex.label=NA, vertex.size = (fb / max(fb)) * 10)
Community detection
# This method is otimal and is computationally heavy
oc = cluster_optimal(g)
modularity(oc)## [1] 0.4376855plot(oc, g, layout=coords, vertex.label=NA, vertex.size=5)
# multi-level optimization of modularity (best among igraph implementations in terms of modularity in this particular case)
c = cluster_louvain(g)
modularity(c) / modularity(oc)## [1] 0.9745163plot(c, g, layout=coords, vertex.label=NA, vertex.size=5)
Network structure
# cohesion structure
b = cohesive_blocks(g)
# print hieararchy of blocks
print(b)## Cohesive block structure:
## B-1 c 1, n 64
## '- B-2 c 2, n 49
## '- B-5 c 4, n 5
## '- B-6 c 4, n 5
## '- B-7 c 3, n 33
## '- B-9 c 4, n 26
## '- B-10 c 5, n 24
## '- B-12 c 10, n 11
## '- B-13 c 10, n 11
## '- B-14 c 8, n 10
## '- B-11 c 4, n 5
## '- B-8 c 3, n 9
## '- B-3 c 5, n 7
## '- B-4 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)) * 20 + 10) 
# graphs from blocks
bg = graphs_from_cohesive_blocks(b, g)
# plot some cohesive graphs
# c 10, n 11
h1 = bg[[12]]
plot(h1, layout=layout_with_fr(h1), vertex.size = 3, vertex.label=NA)
V(g)$color = "white"
n1 = blocks(b)[[12]]
V(g)[n1]$color = "red"
plot(g, layout=coords, vertex.label=NA, vertex.size = 5)
# c 10, n 11
h2 = bg[[13]]
plot(h2, layout=layout_with_fr(h2), vertex.size = 3, vertex.label=NA)
V(g)$color = "white"
n2 = blocks(b)[[13]]
V(g)[n2]$color = "blue"
plot(g, layout=coords, vertex.label=NA, vertex.size = 5)
# c 5, n 24
h3 = bg[[10]]
plot(h3, layout=layout_with_fr(h3), vertex.size = 3, vertex.label=NA)
V(g)$color = "white"
n3 = blocks(b)[[10]]
V(g)[n3]$color = "green"
plot(g, layout=coords, vertex.label=NA, vertex.size = 5)
# average distance (degree of separation)
mean_distance(g)## [1] 2.690972# maximum distance (diameter)
diameter(g)## [1] 6# highlight the diameter
d = get_diameter(g)
E(g)$color = "grey"
E(g)$width = 1
E(g, path=d)$color = "red"
E(g, path=d)$width = 2
V(g)$color = "white"
V(g)[d]$color = "red"
plot(g, layout=coords, vertex.label = NA, vertex.size=5)
# histogram of distances
paths = distance_table(g)$res
names(paths) = 1:length(paths)
barplot(paths / sum(paths), xlab="Distance", ylab="Frequency")
# transitivity
transitivity(g)## [1] 0.5610362# 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)