Title
Uno de los paquetes que nos permite realizar
análisis de redes en R es
igraph. Proporciona rutinas y funciones para crear y manipular
grafos con facilidad.
Como ejemplo, vamos a crear un gráfico no dirigido ponderado para luego calcular el camino más corto entre dos vértices. Para calcular esta ruta, igraph emplea en este caso el algoritmo de Dijkstra.
Reproducimos el siguiente ejemplo, que ilustra el algoritmo de Dijkstra, en R.
Para obtener un grafo no dirigido ponderado necesitamos crear un listado de aristas (edgelist) con los pesos de cada
arista (o distancias entre ellas). Creamos tres columnas, las dos primeras representan la conexión (las aristas) entre los vértices y la tercera los pesos de cada arista. Al incorporar
weight en el título de la columna, igraph asignará como atributo el peso de las aristas a las parejas de vértices.
Datos: listado de aristas
La primera opción es importar el CSV que contiene los datos.
data <- read.csv("datos.csv", sep = ";")
data
var1 var2 weight
1 1 2 7
2 1 3 9
3 2 3 10
4 2 4 15
5 3 4 11
6 3 6 2
7 4 5 6
8 5 6 9
9 6 1 14
La segunda opción consiste en escribir directamente los datos en R. Creamos el
data frame data que editamos con la función
edit.
data <- edit(data.frame())
En el Data Editor, donde navegamos como en una hoja de cálculo, rellenamos los datos. Cambiamos el nombre de la tercera columna haciendo clic sobre el título y escribimos
weight. El resultado final será:
Si en el data frame no tuviéramos como título de la columna weight, podemos asignar el atributo peso posteriormente. Asumiendo que la columna con los pesos sea var3, el código sería:
E(g)$weight = data$var3
igraph
Con el siguiente código creamos un igraph a partir del data frame anterior y lo representamos.
install.packages("igraph") # Descarga e instala igraph
library("igraph") # Carga igraph
# Empezamos a usar igraph ---------------
g <- graph.data.frame(data, directed = FALSE) # Crea igraph
class(g) # Clase del objeto
V(g)$name # Nombres de los vértices
E(g)$weight # Peso de las aristas
tkplot(g) # Gráfico dinámico
plot(g, edge.label = paste(E(g)$weight, sep = "")) # Gráfico de abajo
Camino más corto
Calculamos el camino más corto en función de la distancia total recorrida (suma de pesos) y la secuencia de vértices de la misma.
# Camino más corto entre 1 y 5
sp <- shortest.paths(g, v = "1", to = "5")
sp[] # Distancia
gsp <- get.shortest.paths(g, from = "1", to = "5")
V(g)[gsp$vpath[[1]]] # Secuencia de vértices
> sp[] # Distancia
## 5
## 1 20
> V(g)[gsp$vpath[[1]]] # Secuencia de vértices
## Vertex sequence:
## [1] "1" "3" "6" "5"
Matriz de adyacencia
A continuación calculamos la matriz de adyacencia (distancia entre nodos adyacentes).
# Matriz de adyacencia con ceros
adj <- get.adjacency(g, attr='weight', sparse = FALSE)
adj
1 2 3 4 5 6
1 0 7 9 0 0 14
2 7 0 10 15 0 0
3 9 10 0 11 0 2
4 0 15 11 0 6 0
5 0 0 0 6 0 9
6 14 0 2 0 9 0
Matriz de distancias
La matriz de distancias con el camino más corto entre todos los nodos. Y entre dos nodos concretos: 1 y 5.
# Matriz de distancias
distMatrix <- shortest.paths(g, weights = E(g)$weight)
distMatrix[1, 5]
1 2 3 4 5 6
1 0 7 9 20 20 11
2 7 0 10 15 21 12
3 9 10 0 11 11 2
4 20 15 11 0 6 13
5 20 21 11 6 0 9
6 11 12 2 13 9 0
## [1] 20
Todos los caminos más cortos
Para obtener todos los caminos más cortos desde un nodo.
# Caminos más cortos desde 1
allsp <- get.all.shortest.paths(g, from = "1")
str(allsp)
List of 2
$ res :List of 6
..$ : num 1
..$ : num [1:2] 1 2
..$ : num [1:2] 1 3
..$ : num [1:3] 1 3 4
..$ : num [1:4] 1 3 6 5
..$ : num [1:3] 1 3 6
$ nrgeo: num [1:6] 1 1 1 1 1 1
Entradas relacionadas:
Calcular el trayecto recomendado entre dos estaciones con igraph
Calcular el número de transbordos en una ruta con igraph
Nube de datos