El grafo out.contiguous-usa representa 48 estados de EEUU que comparten frontera (eliminando Alaska y Hawaii, que no están conectadas a ningún otro estado) e incluyendo el distrito de Columbia. Dos estados comparten frontera si existe una arista que los une.
library(igraph)
library(magrittr)
library(knitr)
library(dplyr)
library(nnet)
usa_states <- read.table('./out.contiguous-usa', sep=' ', comment.char='%') %>%
graph_from_data_frame(directed=FALSE)
plot(usa_states, layout=layout.kamada.kawai)
is.connected(usa_states)
## [1] TRUE
is.directed(usa_states)
## [1] FALSE
is.weighted(usa_states)
## [1] FALSE
Se trata de un grafo no dirigido, no conexo y no ponderado.
Una lista de adyacencias es una opción interesante. Una matriz de adyacencias contendría demasiados ceros y supondría un gasto en memoria innecesario.
states_degree <- degree(usa_states)
hist(states_degree)
kable(data.frame(states_degree), col.names=c('Estado y Nº de Estados vecinos'))
Estado y Nº de Estados vecinos | |
---|---|
1 | 4 |
6 | 6 |
11 | 4 |
12 | 3 |
17 | 6 |
21 | 3 |
25 | 2 |
28 | 3 |
2 | 2 |
3 | 5 |
33 | 6 |
38 | 6 |
34 | 5 |
41 | 4 |
18 | 4 |
42 | 7 |
7 | 3 |
22 | 5 |
26 | 5 |
48 | 1 |
43 | 3 |
35 | 4 |
8 | 8 |
4 | 4 |
39 | 4 |
31 | 4 |
49 | 3 |
19 | 6 |
46 | 3 |
29 | 3 |
13 | 4 |
14 | 5 |
23 | 5 |
44 | 5 |
9 | 6 |
16 | 4 |
30 | 6 |
36 | 6 |
5 | 8 |
15 | 5 |
27 | 6 |
10 | 4 |
20 | 6 |
24 | 2 |
32 | 2 |
37 | 4 |
40 | 2 |
45 | 5 |
47 | 3 |
is_connected(usa_states)
## [1] TRUE
independent_states <- induced_subgraph(usa_states, c('5', '8', '27', '33', '34', '42'))
is_connected(independent_states)
## [1] TRUE
plot(independent_states)
Como el conjunto de estados original se formaba una componente conexa, por lo tanto, para que este conjunto de estados independientes pueda ser viajado completamente sin necesidad de volver a EEUU (conjunto de estados que no se han independizado), basta con que este conjunto de estados independientes sea conexo.
Como vemos gracias a la función is_connected y al gráfico, se puede apreciar que se puede visitar el conjunto de estados independientes sin necesidad de entrar a EEUU.
cat('Estados con más fronteras con otros estados\n')
## Estados con más fronteras con otros estados
states_degree[which.is.max(states_degree)]
## 8
## 8
cat('\n')
cat('Estado más importante según el concepto de Eigen Centrality, además de su valor Eigen Centrality \n')
## Estado más importante según el concepto de Eigen Centrality, además de su valor Eigen Centrality
eigen <- eigen_centrality(usa_states)$vector
eigen[which.is.max(eigen)]
## 8
## 1
Eligiría el estado número 8, porque además de ser uno de los que más fronteras tiene con otros estados junto con el 5, es el más importante según Eigen Centrality (estado más importante en función del número de vecinos y la importancia de los mismos).
largest.cliques(usa_states)
## [[1]]
## + 3/49 vertices, named:
## [1] 47 22 23
##
## [[2]]
## + 3/49 vertices, named:
## [1] 47 22 46
##
## [[3]]
## + 3/49 vertices, named:
## [1] 45 30 44
##
## [[4]]
## + 3/49 vertices, named:
## [1] 45 30 26
##
## [[5]]
## + 3/49 vertices, named:
## [1] 45 26 27
##
## [[6]]
## + 3/49 vertices, named:
## [1] 45 42 27
##
## [[7]]
## + 3/49 vertices, named:
## [1] 45 42 44
##
## [[8]]
## + 3/49 vertices, named:
## [1] 40 38 16
##
## [[9]]
## + 3/49 vertices, named:
## [1] 37 33 35
##
## [[10]]
## + 3/49 vertices, named:
## [1] 37 33 34
##
## [[11]]
## + 3/49 vertices, named:
## [1] 32 3 31
##
## [[12]]
## + 3/49 vertices, named:
## [1] 24 21 22
##
## [[13]]
## + 3/49 vertices, named:
## [1] 20 36 19
##
## [[14]]
## + 3/49 vertices, named:
## [1] 20 36 39
##
## [[15]]
## + 3/49 vertices, named:
## [1] 20 39 38
##
## [[16]]
## + 3/49 vertices, named:
## [1] 20 38 15
##
## [[17]]
## + 3/49 vertices, named:
## [1] 20 17 15
##
## [[18]]
## + 3/49 vertices, named:
## [1] 20 17 19
##
## [[19]]
## + 3/49 vertices, named:
## [1] 10 13 9
##
## [[20]]
## + 3/49 vertices, named:
## [1] 10 6 9
##
## [[21]]
## + 3/49 vertices, named:
## [1] 10 6 7
##
## [[22]]
## + 3/49 vertices, named:
## [1] 27 5 31
##
## [[23]]
## + 3/49 vertices, named:
## [1] 27 5 42
##
## [[24]]
## + 3/49 vertices, named:
## [1] 27 26 25
##
## [[25]]
## + 3/49 vertices, named:
## [1] 15 14 38
##
## [[26]]
## + 3/49 vertices, named:
## [1] 15 14 11
##
## [[27]]
## + 3/49 vertices, named:
## [1] 36 49 39
##
## [[28]]
## + 3/49 vertices, named:
## [1] 36 49 35
##
## [[29]]
## + 3/49 vertices, named:
## [1] 36 33 19
##
## [[30]]
## + 3/49 vertices, named:
## [1] 36 33 35
##
## [[31]]
## + 3/49 vertices, named:
## [1] 30 23 29
##
## [[32]]
## + 3/49 vertices, named:
## [1] 30 28 29
##
## [[33]]
## + 3/49 vertices, named:
## [1] 30 28 26
##
## [[34]]
## + 3/49 vertices, named:
## [1] 16 14 38
##
## [[35]]
## + 3/49 vertices, named:
## [1] 16 14 12
##
## [[36]]
## + 3/49 vertices, named:
## [1] 44 41 43
##
## [[37]]
## + 3/49 vertices, named:
## [1] 44 41 42
##
## [[38]]
## + 3/49 vertices, named:
## [1] 23 21 22
##
## [[39]]
## + 3/49 vertices, named:
## [1] 14 11 12
##
## [[40]]
## + 3/49 vertices, named:
## [1] 13 17 9
##
## [[41]]
## + 3/49 vertices, named:
## [1] 31 3 5
##
## [[42]]
## + 3/49 vertices, named:
## [1] 4 6 5
##
## [[43]]
## + 3/49 vertices, named:
## [1] 4 6 7
##
## [[44]]
## + 3/49 vertices, named:
## [1] 4 1 5
##
## [[45]]
## + 3/49 vertices, named:
## [1] 8 19 18
##
## [[46]]
## + 3/49 vertices, named:
## [1] 8 19 33
##
## [[47]]
## + 3/49 vertices, named:
## [1] 8 42 5
##
## [[48]]
## + 3/49 vertices, named:
## [1] 8 42 34
##
## [[49]]
## + 3/49 vertices, named:
## [1] 8 18 9
##
## [[50]]
## + 3/49 vertices, named:
## [1] 8 34 33
##
## [[51]]
## + 3/49 vertices, named:
## [1] 8 6 5
##
## [[52]]
## + 3/49 vertices, named:
## [1] 8 6 9
##
## [[53]]
## + 3/49 vertices, named:
## [1] 41 34 42
##
## [[54]]
## + 3/49 vertices, named:
## [1] 3 1 5
##
## [[55]]
## + 3/49 vertices, named:
## [1] 3 1 2
##
## [[56]]
## + 3/49 vertices, named:
## [1] 17 18 9
##
## [[57]]
## + 3/49 vertices, named:
## [1] 17 18 19
Esto se produce en hasta 57 ocasiones. Un ejemplo: 34, 41 y 42.
diameter(usa_states)
## [1] 11
all_shortest_paths(usa_states,'40','13')$res
## [[1]]
## + 5/49 vertices, named:
## [1] 40 38 15 17 13
##
## [[2]]
## + 5/49 vertices, named:
## [1] 40 38 20 17 13
##
## [[3]]
## + 5/49 vertices, named:
## [1] 40 16 14 11 13
##
## [[4]]
## + 5/49 vertices, named:
## [1] 40 38 14 11 13
##
## [[5]]
## + 5/49 vertices, named:
## [1] 40 38 15 11 13
##
## [[6]]
## + 5/49 vertices, named:
## [1] 40 16 12 11 13
Existen hasta 6 caminos cortos por los que hay que atravesar 5 estados.
adjacency_matrix <- as_adj(usa_states)
adjacency_matrix %>%
as.matrix() %>%
isSymmetric()
## [1] TRUE
La matriz de adyacencia de este grafo sí es simétrica porque se trata de un grafo no ponderado y no dirigido.
usa_states <- usa_states + vertex('49', '50')
is.connected(usa_states)
## [1] FALSE
plot(usa_states)
El grafo se ha convertido en una componente no conexa porque los estados añadidos no comparten frontera con ningún estado.