library(igraph)
Random graph
n = 100
p = 1.75/n
g = sample_gnp(n, p)
coords = layout_with_fr(g)
plot(g, layout=coords, vertex.size = 3, vertex.label=NA)
Connected components
# get the components
c = components(g)
# connected?
is_connected(g)
## [1] FALSE
# number of components
c$no
## [1] 23
# size of components
c$csize
## [1] 70 7 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
table(c$csize)
##
## 1 2 7 70
## 19 2 1 1
# membeship of nodes
c$membership
## [1] 1 1 2 3 1 1 1 4 1 1 1 1 5 1 1 1 1 2 6 2 1 1 1
## [24] 1 7 1 8 1 1 1 1 1 1 9 1 10 1 1 1 1 1 1 1 1 2 1
## [47] 1 1 1 1 1 1 5 11 2 1 1 1 1 1 1 1 2 1 12 1 1 13 1
## [70] 14 1 1 1 1 1 1 1 15 1 1 16 17 18 19 20 2 1 1 1 21 1 7
## [93] 1 1 1 1 22 23 1 1
# get the giant component
nodes = which(c$membership == which.max(c$csize))
# color in red the nodes in the giant component
V(g)$color = "white"
V(g)[nodes]$color = "red"
plot(g, layout=coords, vertex.size = 3, vertex.label=NA)
Biconnected components
n = 100
p = 4/n
g = sample_gnp(n, p)
coords = layout_with_fr(g)
plot(g, layout=coords, vertex.size = 3, vertex.label=NA)
bc = biconnected_components(g)
# number of bicomponents
bc$no
## [1] 11
# print edges of biconnected components
bc$component_edges
## [[1]]
## + 1/191 edge:
## [1] 59--79
##
## [[2]]
## + 1/191 edge:
## [1] 76--89
##
## [[3]]
## + 1/191 edge:
## [1] 26--55
##
## [[4]]
## + 1/191 edge:
## [1] 53--92
##
## [[5]]
## + 1/191 edge:
## [1] 49--52
##
## [[6]]
## + 1/191 edge:
## [1] 25--87
##
## [[7]]
## + 1/191 edge:
## [1] 29--47
##
## [[8]]
## + 1/191 edge:
## [1] 50--74
##
## [[9]]
## + 1/191 edge:
## [1] 24--50
##
## [[10]]
## + 181/191 edges:
## [1] 7-- 96 19-- 96 21-- 81 66-- 81 7-- 66 19-- 66 39-- 72 60-- 72
## [9] 29-- 39 32-- 60 46-- 60 56-- 60 20-- 56 10-- 87 46-- 87 46-- 91
## [17] 48-- 91 8-- 48 27-- 48 48-- 64 18-- 77 45-- 77 61-- 77 64-- 77
## [25] 44-- 69 45-- 69 33-- 45 44-- 61 35-- 52 44-- 52 41--100 44--100
## [33] 52--100 60--100 63--100 68--100 82--100 24-- 41 33-- 41 37-- 41
## [41] 27-- 92 28-- 92 84-- 92 1-- 28 8-- 84 38-- 84 6-- 38 6-- 94
## [49] 79-- 94 84-- 94 15-- 79 17-- 79 19-- 79 46-- 79 51-- 79 73-- 79
## [57] 43-- 97 58-- 97 78-- 97 85-- 97 90-- 97 71-- 90 29-- 85 35-- 85
## [65] 17-- 98 26-- 98 35-- 98 93-- 98 29-- 93 89-- 93 4-- 89 6-- 89
## [73] 4-- 88 13-- 88 35-- 88 37-- 88 60-- 88 41-- 99 57-- 99 62-- 99
## + ... omitted several edges
##
## [[11]]
## + 1/191 edge:
## [1] 1--9
# print nodes of biconnected components
bc$components
## [[1]]
## + 2/100 vertices:
## [1] 79 59
##
## [[2]]
## + 2/100 vertices:
## [1] 89 76
##
## [[3]]
## + 2/100 vertices:
## [1] 55 26
##
## [[4]]
## + 2/100 vertices:
## [1] 92 53
##
## [[5]]
## + 2/100 vertices:
## [1] 52 49
##
## [[6]]
## + 2/100 vertices:
## [1] 87 25
##
## [[7]]
## + 2/100 vertices:
## [1] 47 29
##
## [[8]]
## + 2/100 vertices:
## [1] 74 50
##
## [[9]]
## + 2/100 vertices:
## [1] 50 24
##
## [[10]]
## + 88/100 vertices:
## [1] 96 7 81 66 72 39 60 56 87 10 91 48 64 77 69 45 61
## [18] 44 52 100 41 92 28 84 38 94 79 97 90 85 98 26 93 89
## [35] 88 4 99 95 43 86 78 73 51 83 80 71 12 13 65 37 33
## [52] 27 31 68 15 75 36 58 11 54 34 42 62 30 17 57 5 82
## [69] 63 18 14 70 46 32 29 24 3 40 22 20 16 35 21 8 23
## [86] 19 6 1
##
## [[11]]
## + 2/100 vertices:
## [1] 9 1
# size of bicomponents
cl = bc$components
size = sapply(cl, length)
length(size)
## [1] 11
table(size)
## size
## 2 88
## 10 1
# highlight the largest bi-component
giant = cl[[which.max(size)]]
V(g)$color = "white"
V(g)[giant]$color = "red"
plot(g, layout=coords, vertex.label=NA, vertex.size=5)
Cohesive blocks (k-connected components)
n = 100
p = 6/n
g = sample_gnp(n, p)
coords = layout_with_fr(g)
plot(g, layout=coords, vertex.size = 3, vertex.label=NA)
# This is computationally heavy
b = cohesive_blocks(g)
# print hieararchy of blocks
print(b)
## Cohesive block structure:
## B-1 c 1, n 100
## '- B-2 c 2, n 98
## '- B-3 c 3, n 96
## '- B-4 c 4, n 82
# plot hieararchy of blocks
plot_hierarchy(b)
# nodes from blocks
blocks(b)
## [[1]]
## + 100/100 vertices:
## [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
## [18] 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
## [35] 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
## [52] 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
## [69] 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
## [86] 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
##
## [[2]]
## + 98/100 vertices:
## [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
## [18] 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
## [35] 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
## [52] 52 53 54 55 56 57 58 59 61 62 63 64 65 66 67 68 69
## [69] 70 71 72 73 74 75 76 77 78 79 80 81 82 84 85 86 87
## [86] 88 89 90 91 92 93 94 95 96 97 98 99 100
##
## [[3]]
## + 96/100 vertices:
## [1] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
## [18] 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
## [35] 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
## [52] 53 54 55 56 57 58 59 61 62 63 64 65 66 67 68 69 71
## [69] 72 73 74 75 76 77 78 79 80 81 82 84 85 86 87 88 89
## [86] 90 91 92 93 94 95 96 97 98 99 100
##
## [[4]]
## + 82/100 vertices:
## [1] 2 3 4 5 6 7 8 11 12 15 16 17 18 19 20 21 22
## [18] 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
## [35] 40 41 43 44 45 46 47 49 50 51 53 54 55 56 58 59 61
## [52] 62 63 64 65 66 67 71 74 75 76 77 78 79 80 81 82 84
## [69] 86 87 88 89 90 91 92 93 94 95 96 97 98 100
# graphs from blocks
bg = graphs_from_cohesive_blocks(b, g)
# plot most cohesive graph
c = cohesion(b)
h = bg[[which.max(c)]]
plot(h, layout=layout_with_fr(h), vertex.size = 3, vertex.label=NA)
# connectivity of the graph
vertex_connectivity(h)
## [1] 4
Weakly and strongly connected components of directed graphs
n = 10
p = 2/n
g = sample_gnp(n, p, directed=TRUE)
coords = layout_with_fr(g)
plot(g, layout=coords, vertex.size = 6, vertex.label=NA, edge.arrow.size = 0.5, edge.curved = TRUE)
# weak components
components(g, mode="weak")
## $membership
## [1] 1 1 1 1 2 2 1 1 1 1
##
## $csize
## [1] 8 2
##
## $no
## [1] 2
# strong components
c = components(g, mode="strong")
nodes = which(c$membership == which.max(c$csize))
# color in red the nodes in the giant component
V(g)$color = "white"
V(g)[nodes]$color = "red"
plot(g, layout=coords, vertex.size = 6, vertex.label=NA, edge.arrow.size = 0.5, edge.curved = TRUE)
Resilience
# 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)
}
# Preferential attachment graph
g = sample_pa(n = 100, m = 2, directed=FALSE)
coords = layout_with_fr(g)
plot(g, layout=coords, vertex.label=NA, vertex.size = 5)
# 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)
g = sample_gnp(n=100, p=5/100)
coords = layout_with_fr(g)
plot(g, layout=coords, vertex.size = 3, vertex.label=NA)
# 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)
