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] 15
# size of components
c$csize
## [1] 82 1 1 1 1 3 1 2 1 2 1 1 1 1 1
table(c$csize)
##
## 1 2 3 82
## 11 2 1 1
# membeship of nodes
c$membership
## [1] 1 1 1 1 1 2 1 3 1 1 1 1 1 1 4 5 1 1 1 1 1 6 1
## [24] 1 1 1 1 7 1 8 1 1 1 1 9 1 10 11 1 1 1 1 1 1 1 1
## [47] 1 1 1 1 1 1 1 12 13 1 1 1 14 1 1 1 6 1 6 1 1 1 15
## [70] 1 10 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [93] 1 1 1 1 1 1 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] 7
# print edges of biconnected components
bc$component_edges
## [[1]]
## + 1/187 edge from e01c769:
## [1] 4--76
##
## [[2]]
## + 1/187 edge from e01c769:
## [1] 37--81
##
## [[3]]
## + 1/187 edge from e01c769:
## [1] 68--73
##
## [[4]]
## + 1/187 edge from e01c769:
## [1] 7--18
##
## [[5]]
## + 1/187 edge from e01c769:
## [1] 77--80
##
## [[6]]
## + 1/187 edge from e01c769:
## [1] 39--44
##
## [[7]]
## + 181/187 edges from e01c769:
## [1] 12--94 53--94 92--94 5--53 8--53 8--92 23--92 54--92 62--92 22--54
## [11] 11--22 14--62 16--62 29--62 29--66 43--66 62--66 51--85 82--85 17--51
## [21] 24--51 50--88 57--88 6--57 30--57 36--57 14--99 29--99 36--99 38--99
## [31] 12--36 33--36 3--72 24--72 27--72 45--72 52--72 56--72 11--27 25--27
## [41] 3--91 49--91 62--91 78--91 87--91 58--87 5--96 11--96 12--96 29--96
## [51] 67--96 24--67 52--67 13--71 30--71 38--71 52--71 12--52 23--52 10--89
## [61] 44--89 67--89 72--89 18--95 70--95 89--95 2--78 51--78 70--78 3--42
## [71] 6--42 10--42 6--45 9--45 21--45 58--98 79--98 9--79 16--79 26--79
## [81] 33--79 55--79 59--79 73--79 14--73 36--81 40--81 41--81 43--81 30--40
## [91] 1--41 25--41 8--84 14--84 32--84 41--84 43--84 64--84 14--64 46--64
## + ... omitted several edges
# print nodes of biconnected components
bc$components
## [[1]]
## + 2/100 vertices, from e01c769:
## [1] 76 4
##
## [[2]]
## + 2/100 vertices, from e01c769:
## [1] 81 37
##
## [[3]]
## + 2/100 vertices, from e01c769:
## [1] 73 68
##
## [[4]]
## + 2/100 vertices, from e01c769:
## [1] 18 7
##
## [[5]]
## + 2/100 vertices, from e01c769:
## [1] 80 77
##
## [[6]]
## + 2/100 vertices, from e01c769:
## [1] 44 39
##
## [[7]]
## + 90/100 vertices, from e01c769:
## [1] 94 53 92 54 22 62 66 29 85 51 88 57 99 36 72 56 27 91 87 96 67 71 52
## [24] 89 95 18 70 78 3 42 45 98 79 73 81 40 41 84 64 46 55 9 75 21 76 83
## [47] 69 33 65 35 93 17 61 49 59 82 63 48 16 25 60 14 32 30 10 97 20 26 15
## [70] 47 24 5 58 43 8 74 77 86 34 44 23 50 38 19 13 6 11 12 2 1
# size of bicomponents
cl = bc$components
size = sapply(cl, length)
length(size)
## [1] 7
table(size)
## size
## 2 90
## 6 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 3, n 99
## '- B-3 c 4, n 94
# plot hieararchy of blocks
plot_hierarchy(b)
# nodes from blocks
blocks(b)
## [[1]]
## + 100/100 vertices, from e137696:
## [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]]
## + 99/100 vertices, from e137696:
## [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 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
##
## [[3]]
## + 94/100 vertices, from e137696:
## [1] 1 3 4 5 6 7 8 9 10 12 13 14 15 16 17 19 20
## [18] 22 23 24 26 27 28 29 30 31 32 33 34 35 36 37 38 39
## [35] 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
## [52] 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
## [69] 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
## [86] 92 93 94 95 96 97 98 99 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 1 1 1 1 1 1
##
## $csize
## [1] 10
##
## $no
## [1] 1
# 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)
