Introducción al paquete igraph para R

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