Graph Exploration
Catherine Matias
October 2023
In this session we will discover the functions of the
igraph package to calculate different statistics of a
graph. Let’s load the igraph library:
library(igraph)##
## Attaching package: 'igraph'## The following objects are masked from 'package:stats':
##
## decompose, spectrum## The following object is masked from 'package:base':
##
## unionas well as two datasets already used during the previous session:
miserab <- read_graph(file='lesmis.gml', format="gml") friends <- read.table(file='Friendship-network_data_2013.csv')
gfriends <- graph_from_data_frame(friends, directed=TRUE) 1. Properties of a simple graph
Let us recall the following functions to determine the order and size of a graph, obtain the list of nodes or edges as well as know if the graph is directed or not:
vcount(miserab)## [1] 77ecount(miserab)## [1] 254V(miserab)## + 77/77 vertices, from 10c9a3a:
## [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
## [26] 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
## [51] 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
## [76] 76 77E(miserab)## + 254/254 edges from 10c9a3a:
## [1] 1-- 2 1-- 3 1-- 4 3-- 4 1-- 5 1-- 6 1-- 7 1-- 8 1-- 9 1--10
## [11] 11--12 4--12 3--12 1--12 12--13 12--14 12--15 12--16 17--18 17--19
## [21] 18--19 17--20 18--20 19--20 17--21 18--21 19--21 20--21 17--22 18--22
## [31] 19--22 20--22 21--22 17--23 18--23 19--23 20--23 21--23 22--23 17--24
## [41] 18--24 19--24 20--24 21--24 22--24 23--24 13--24 12--24 24--25 12--25
## [51] 25--26 24--26 12--26 25--27 12--27 17--27 26--27 12--28 24--28 26--28
## [61] 25--28 27--28 12--29 28--29 24--30 28--30 12--30 24--31 31--32 12--32
## [71] 24--32 28--32 12--33 12--34 28--34 12--35 30--35 12--36 35--36 30--36
## [81] 35--37 36--37 12--37 30--37 35--38 36--38 37--38 12--38 30--38 35--39
## [91] 36--39 37--39 38--39 12--39 30--39 26--40 26--41 25--42 26--42 42--43
## + ... omitted several edgesis.directed(miserab)## [1] FALSEand for the graph gfriends:
vcount(gfriends)## [1] 134ecount(gfriends)## [1] 668V(gfriends)## + 134/134 vertices, named, from 71f6e00:
## [1] 1 3 27 28 32 34 45 46 48 55 61 63 70 72 79
## [16] 80 85 92 101 117 119 120 122 124 125 132 134 147 151 156
## [31] 159 165 170 173 184 190 196 200 201 202 205 211 213 214 219
## [46] 222 232 240 242 245 248 252 255 257 265 268 272 275 277 285
## [61] 312 325 327 335 343 353 364 366 388 407 425 429 440 441 447
## [76] 452 465 468 471 480 486 488 491 492 494 496 498 502 520 531
## [91] 545 564 576 577 587 601 603 605 612 622 624 634 642 674 691
## [106] 694 753 765 769 771 779 797 798 845 857 866 867 869 883 884
## [121] 894 920 959 960 970 974 1228 1332 1401 1485 1519 1594 1828 38E(gfriends)## + 668/668 edges from 71f6e00 (vertex names):
## [1] 1 ->55 1 ->205 1 ->272 1 ->494 1 ->779 1 ->894 3 ->1 3 ->28 3 ->147
## [10] 3 ->272 3 ->407 3 ->674 3 ->884 27->63 27->173 28->202 28->327 28->353
## [19] 28->407 28->429 28->441 28->492 28->545 32->440 32->624 32->797 32->920
## [28] 34->151 34->277 34->502 34->866 45->48 45->79 45->335 45->496 45->601
## [37] 45->674 45->765 46->117 46->196 46->257 46->268 48->45 48->79 48->496
## [46] 55->1 55->170 55->205 55->252 55->272 55->779 55->883 55->894 61->797
## [55] 63->27 63->125 63->173 70->101 70->132 70->240 70->425 70->447 72->407
## [64] 72->674 72->857 79->45 79->48 79->335 79->496 79->601 79->674 79->765
## [73] 80->120 80->285 80->468 80->601 85->190 85->213 85->214 85->335 85->603
## [82] 85->605 85->765 92->468 92->845
## + ... omitted several edgesis.directed(gfriends)## [1] TRUE2. Degree distribution with igraph
When the graph is undirected:
degree(miserab)## [1] 10 1 3 3 1 1 1 1 1 1 1 36 2 1 1 1 9 7 7 7 7 7 7 15 11
## [26] 16 11 17 4 8 2 4 1 2 6 6 6 6 6 3 1 11 3 3 2 1 1 2 22 7
## [51] 2 7 2 1 4 19 2 11 15 11 9 11 13 12 13 12 10 1 10 10 10 9 3 2 2
## [76] 7 7and when its directed, indegrees and outdegrees are obtained with
degree(gfriends, mode="in")## 1 3 27 28 32 34 45 46 48 55 61 63 70 72 79 80
## 11 4 3 10 2 4 8 5 5 9 0 2 5 4 8 5
## 85 92 101 117 119 120 122 124 125 132 134 147 151 156 159 165
## 5 3 8 11 8 4 6 2 7 6 4 3 5 0 0 1
## 170 173 184 190 196 200 201 202 205 211 213 214 219 222 232 240
## 8 2 5 4 6 4 4 3 11 3 3 5 4 3 2 6
## 242 245 248 252 255 257 265 268 272 275 277 285 312 325 327 335
## 3 9 2 7 2 4 7 5 15 3 3 4 2 6 6 6
## 343 353 364 366 388 407 425 429 440 441 447 452 465 468 471 480
## 4 6 6 1 5 12 8 5 3 8 9 8 4 6 2 2
## 486 488 491 492 494 496 498 502 520 531 545 564 576 577 587 601
## 2 3 4 6 8 7 2 6 3 3 3 3 3 2 7 4
## 603 605 612 622 624 634 642 674 691 694 753 765 769 771 779 797
## 5 7 2 7 7 9 8 6 13 5 4 6 4 1 9 10
## 798 845 857 866 867 869 883 884 894 920 959 960 970 974 1228 1332
## 4 5 3 5 2 10 12 3 9 2 5 5 2 2 2 7
## 1401 1485 1519 1594 1828 38
## 4 1 5 2 2 3degree(gfriends, mode="out")## 1 3 27 28 32 34 45 46 48 55 61 63 70 72 79 80
## 6 7 2 8 4 4 7 4 3 8 1 3 5 3 7 4
## 85 92 101 117 119 120 122 124 125 132 134 147 151 156 159 165
## 7 2 9 16 6 3 5 2 9 7 3 10 13 1 2 1
## 170 173 184 190 196 200 201 202 205 211 213 214 219 222 232 240
## 6 3 3 4 5 2 8 5 12 3 2 3 1 3 2 7
## 242 245 248 252 255 257 265 268 272 275 277 285 312 325 327 335
## 3 7 3 7 1 3 9 5 11 3 6 5 2 7 8 3
## 343 353 364 366 388 407 425 429 440 441 447 452 465 468 471 480
## 3 5 5 1 8 13 10 7 5 7 8 5 3 7 2 2
## 486 488 491 492 494 496 498 502 520 531 545 564 576 577 587 601
## 2 3 4 9 8 8 2 5 4 3 3 2 4 2 5 7
## 603 605 612 622 624 634 642 674 691 694 753 765 769 771 779 797
## 6 5 2 8 10 3 7 6 10 2 2 3 9 2 9 5
## 798 845 857 866 867 869 883 884 894 920 959 960 970 974 1228 1332
## 2 6 5 9 2 4 13 2 11 3 6 2 2 2 3 6
## 1401 1485 1519 1594 1828 38
## 4 1 6 2 2 0Empirical distribution of degrees:
degree_distribution(miserab)## [1] 0.00000000 0.22077922 0.12987013 0.07792208 0.03896104 0.00000000
## [7] 0.06493506 0.12987013 0.01298701 0.03896104 0.06493506 0.07792208
## [13] 0.02597403 0.02597403 0.00000000 0.02597403 0.01298701 0.01298701
## [19] 0.00000000 0.01298701 0.00000000 0.00000000 0.01298701 0.00000000
## [25] 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000
## [31] 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000
## [37] 0.01298701degree_distribution(gfriends, mode="out") ## [1] 0.007462687 0.052238806 0.194029851 0.179104478 0.074626866 0.111940299
## [7] 0.074626866 0.104477612 0.067164179 0.052238806 0.029850746 0.014925373
## [13] 0.007462687 0.022388060 0.000000000 0.000000000 0.007462687Graphical representation of this degree empirical distribution:
barplot(degree_distribution(miserab), names.arg=as.character(0:max(degree(miserab))), col='green', main='Degrees for the graph Les Misérables')
Degrees via the adjacency matrix
We can check by hand that the degrees of the nodes are indeed given by the sum of the row or column of the adjacency matrix:
Afriends <- as_adj(gfriends)
sum(Afriends[1,])## [1] 6# rowSums(Afriends) # be careful, that doesn't work because it's not a matrix!
rowSums(as.matrix(Afriends)) # Pay attention to the format of this output!## 1 3 27 28 32 34 45 46 48 55 61 63 70 72 79 80
## 6 7 2 8 4 4 7 4 3 8 1 3 5 3 7 4
## 85 92 101 117 119 120 122 124 125 132 134 147 151 156 159 165
## 7 2 9 16 6 3 5 2 9 7 3 10 13 1 2 1
## 170 173 184 190 196 200 201 202 205 211 213 214 219 222 232 240
## 6 3 3 4 5 2 8 5 12 3 2 3 1 3 2 7
## 242 245 248 252 255 257 265 268 272 275 277 285 312 325 327 335
## 3 7 3 7 1 3 9 5 11 3 6 5 2 7 8 3
## 343 353 364 366 388 407 425 429 440 441 447 452 465 468 471 480
## 3 5 5 1 8 13 10 7 5 7 8 5 3 7 2 2
## 486 488 491 492 494 496 498 502 520 531 545 564 576 577 587 601
## 2 3 4 9 8 8 2 5 4 3 3 2 4 2 5 7
## 603 605 612 622 624 634 642 674 691 694 753 765 769 771 779 797
## 6 5 2 8 10 3 7 6 10 2 2 3 9 2 9 5
## 798 845 857 866 867 869 883 884 894 920 959 960 970 974 1228 1332
## 2 6 5 9 2 4 13 2 11 3 6 2 2 2 3 6
## 1401 1485 1519 1594 1828 38
## 4 1 6 2 2 0degree(gfriends, mode="out") # idem ## 1 3 27 28 32 34 45 46 48 55 61 63 70 72 79 80
## 6 7 2 8 4 4 7 4 3 8 1 3 5 3 7 4
## 85 92 101 117 119 120 122 124 125 132 134 147 151 156 159 165
## 7 2 9 16 6 3 5 2 9 7 3 10 13 1 2 1
## 170 173 184 190 196 200 201 202 205 211 213 214 219 222 232 240
## 6 3 3 4 5 2 8 5 12 3 2 3 1 3 2 7
## 242 245 248 252 255 257 265 268 272 275 277 285 312 325 327 335
## 3 7 3 7 1 3 9 5 11 3 6 5 2 7 8 3
## 343 353 364 366 388 407 425 429 440 441 447 452 465 468 471 480
## 3 5 5 1 8 13 10 7 5 7 8 5 3 7 2 2
## 486 488 491 492 494 496 498 502 520 531 545 564 576 577 587 601
## 2 3 4 9 8 8 2 5 4 3 3 2 4 2 5 7
## 603 605 612 622 624 634 642 674 691 694 753 765 769 771 779 797
## 6 5 2 8 10 3 7 6 10 2 2 3 9 2 9 5
## 798 845 857 866 867 869 883 884 894 920 959 960 970 974 1228 1332
## 2 6 5 9 2 4 13 2 11 3 6 2 2 2 3 6
## 1401 1485 1519 1594 1828 38
## 4 1 6 2 2 0sum(Afriends[,1])## [1] 11colSums(as.matrix(Afriends)) # Pay attention to the format of this output!## 1 3 27 28 32 34 45 46 48 55 61 63 70 72 79 80
## 11 4 3 10 2 4 8 5 5 9 0 2 5 4 8 5
## 85 92 101 117 119 120 122 124 125 132 134 147 151 156 159 165
## 5 3 8 11 8 4 6 2 7 6 4 3 5 0 0 1
## 170 173 184 190 196 200 201 202 205 211 213 214 219 222 232 240
## 8 2 5 4 6 4 4 3 11 3 3 5 4 3 2 6
## 242 245 248 252 255 257 265 268 272 275 277 285 312 325 327 335
## 3 9 2 7 2 4 7 5 15 3 3 4 2 6 6 6
## 343 353 364 366 388 407 425 429 440 441 447 452 465 468 471 480
## 4 6 6 1 5 12 8 5 3 8 9 8 4 6 2 2
## 486 488 491 492 494 496 498 502 520 531 545 564 576 577 587 601
## 2 3 4 6 8 7 2 6 3 3 3 3 3 2 7 4
## 603 605 612 622 624 634 642 674 691 694 753 765 769 771 779 797
## 5 7 2 7 7 9 8 6 13 5 4 6 4 1 9 10
## 798 845 857 866 867 869 883 884 894 920 959 960 970 974 1228 1332
## 4 5 3 5 2 10 12 3 9 2 5 5 2 2 2 7
## 1401 1485 1519 1594 1828 38
## 4 1 5 2 2 3degree(gfriends, mode="in") # idem ## 1 3 27 28 32 34 45 46 48 55 61 63 70 72 79 80
## 11 4 3 10 2 4 8 5 5 9 0 2 5 4 8 5
## 85 92 101 117 119 120 122 124 125 132 134 147 151 156 159 165
## 5 3 8 11 8 4 6 2 7 6 4 3 5 0 0 1
## 170 173 184 190 196 200 201 202 205 211 213 214 219 222 232 240
## 8 2 5 4 6 4 4 3 11 3 3 5 4 3 2 6
## 242 245 248 252 255 257 265 268 272 275 277 285 312 325 327 335
## 3 9 2 7 2 4 7 5 15 3 3 4 2 6 6 6
## 343 353 364 366 388 407 425 429 440 441 447 452 465 468 471 480
## 4 6 6 1 5 12 8 5 3 8 9 8 4 6 2 2
## 486 488 491 492 494 496 498 502 520 531 545 564 576 577 587 601
## 2 3 4 6 8 7 2 6 3 3 3 3 3 2 7 4
## 603 605 612 622 624 634 642 674 691 694 753 765 769 771 779 797
## 5 7 2 7 7 9 8 6 13 5 4 6 4 1 9 10
## 798 845 857 866 867 869 883 884 894 920 959 960 970 974 1228 1332
## 4 5 3 5 2 10 12 3 9 2 5 5 2 2 2 7
## 1401 1485 1519 1594 1828 38
## 4 1 5 2 2 33. Other statistics
Get familiar with the following igraph functions for a
graph \(G\), and apply them to Les
Misérables and gfriends graphs:
components(G)
edge_density(G)
diameter(G, directed=TRUE, unconnected=FALSE)
diameter(G, directed=TRUE, unconnected=TRUE)
get_diameter(G, directed=TRUE)
count_triangles(G)
transitivity(G)
neighbors(G, 1, mode='out')
neighbors(G, 1, mode='in')
neighbors(G, 1, mode='all')
K3 <- cliques(G, min=3, max=3)
K3[[1]]
length(K3)
sum(count_triangles(G))/3
closeness(G,mode="total")
closeness(G)
betweenness(G)
plot(G, vertex.size=betweenness(G))Exercise 2.
- Analyze the graphs from exercise 1 (previous session) with the descriptive statistics you know.
- Make sure you understand what formulas are used by each of the functions above. Do they correspond to the definitions seen in class? Pay particular attention to the cases of directed graphs and the connectivity problem.
- Some statistics only make sense for related graphs. In this case, select the largest connected component of the graph and apply the statistical calculation on this component.
- Count the 2-stars and 3-stars in the graphs.
- Do the same on the famous Karate Club graph (available in
R): In 1977, W. W. Zachary recorded interactions in a karate club for two years. During observation, a conflict developed between the administrator and the instructor.
library(igraphdata)
data(karate)