1 Introducción

Conformación y almacenamiento de datos asociados con sistemas complejos.

Un grafo por sí solo (i.e., una colección de vértices y aristas) suele ser insuficiente como representación de una red.

La noción de decoración corresponde a la eventual conjunción de vértices y aristas con otras variables de interés (atributos).

Son esenciales los conceptos y las propiedades fundamentales de la teoría de grafos.

2 Software

La librería igraph proporciona herramientas versátiles para la visualización y el análisis de redes en R, Python y C/C++.

Otras alternativa populares incluyen las librerías:

3 Grafos

Un grafo \(G = (V, E)\) es una estructura que consiste de un conjunto de vértices (nodos) \(V\) y de un conjunto de aristas (enlaces) \(E\), donde los elementos de \(E\) son parejas de la forma \(e=\{u,v\}\) con \(u,v\in V\).

El número de vértices y el número de aristas se conocen como el orden y el tamaño del grafo, respectivamente.

Comúnmente, los vértices del grafo se enumeran con los números enteros: \(1,\ldots,n\) con \(n = |V|\).

Dos grafos que son equivalentes en su estructura a pesar de la enumeración de los vértices se denominan isomorfos.

Un grafo \(H=(V',E')\) es un subgrafo de \(G=(V,E)\) si \(V'\subset V\) y \(E'\subset E\).

Un grafo para el que cada arista \(\{u,v\}\in E\) es tal que \(\{u,v\} \not\equiv \{v,u\}\) para todo \(u,v\in V\) se denomina grafo dirigido o digrafo. De lo contrario se llama grafo no dirigido. Por defecto, el término grafo hace referencia a un grafo no dirigido.

Un multigrafo es aquel que permite múltiples aristas entre el mismo par de vértices y aristas de un vértice a sí mismo. Un grafo que no es un multigrafo se llama grafo simple.

3.1 Ejemplo: grafo no dirigido

# install.packages("igraph")
suppressMessages(suppressWarnings(library(igraph)))

# red no dirigida (definicion manual)
g <- graph_from_literal(1-2, 1-3, 2-3, 2-4, 3-5, 4-5, 4-6, 4-7, 5-6, 6-7)

# nombre
g$name <- "Grafo no dirigido"
  
# clase de objeto
class(g)
## [1] "igraph"
# identificador
graph_id(g)
## [1] "92ea754a-31fd-11ec-8000-010000000000"
# vertices
V(g)
## + 7/7 vertices, named, from 92ea754:
## [1] 1 2 3 4 5 6 7
# orden
vcount(g)
## [1] 7
# aristas
E(g)
## + 10/10 edges from 92ea754 (vertex names):
##  [1] 1--2 1--3 2--3 2--4 3--5 4--5 4--6 4--7 5--6 6--7
# tamaño
ecount(g)
## [1] 10
# aristas (otro formato)
print_all(g)
## IGRAPH 92ea754 UN-- 7 10 -- Grafo no dirigido
## + attr: name (g/c), name (v/c)
## + edges (vertex names):
## 1 -- 2, 3
## 2 -- 1, 3, 4
## 3 -- 1, 2, 5
## 4 -- 2, 5, 6, 7
## 5 -- 3, 4, 6
## 6 -- 4, 5, 7
## 7 -- 4, 6
# ponderado?
is_weighted(g)
## [1] FALSE
# simple?
is_simple(g)
## [1] TRUE
# grafico
plot(g)

Ver https://igraph.org/r/doc/plot.common.html para detalles de visualización.

# red ponderada
wg <- g
E(wg)$weight <- runif(n = ecount(wg))
print(round(x = E(wg)$weight, digits = 4))
##  [1] 0.8016 0.6000 0.8253 0.4374 0.3442 0.6618 0.4143 0.5119 0.6388 0.2677
# ponderado?
is_weighted(wg)
## [1] TRUE

3.2 Ejemplo: red dirigida

# red dirigida (definicion manual)
dg <- graph_from_literal(1-+2, 1-+3, 2++3)

# aristas
E(dg)
## + 4/4 edges from 93153b4 (vertex names):
## [1] 1->2 1->3 2->3 3->2
# cambio de etiquetas
V(dg)$name <- c("Juan", "Maria", "Pedro")

# agregar atributos
V(dg)$genero <- c("M","F","M")

# aristas
E(dg)
## + 4/4 edges from 93153b4 (vertex names):
## [1] Juan ->Maria Juan ->Pedro Maria->Pedro Pedro->Maria
# grafico
plot(dg, vertex.size = 30)

3.3 Ejemplo: multigrafo

# multigrafo
mg <- g + edge(c(2,3), c(5,6))
print_all(mg)
## IGRAPH 9336696 UN-- 7 12 -- Grafo no dirigido
## + attr: name (g/c), name (v/c)
## + edges (vertex names):
## 1 -- 2, 3
## 2 -- 1, 3, 3, 4
## 3 -- 1, 2, 2, 5
## 4 -- 2, 5, 6, 7
## 5 -- 3, 4, 6, 6
## 6 -- 4, 5, 5, 7
## 7 -- 4, 6
# simple?
is_simple(mg)
## [1] FALSE
# simplificacion a grafo ponderado
E(mg)$weight <- 1
wg2 <- simplify(mg)
is_simple(wg2)
## [1] TRUE
print_all(wg2)
## IGRAPH 9338d79 UNW- 7 10 -- Grafo no dirigido
## + attr: name (g/c), name (v/c), weight (e/n)
## + edges (vertex names):
## 1 -- 2, 3
## 2 -- 1, 3, 4
## 3 -- 1, 2, 5
## 4 -- 2, 5, 6, 7
## 5 -- 3, 4, 6
## 6 -- 4, 5, 7
## 7 -- 4, 6
E(wg2)
## + 10/10 edges from 9338d79 (vertex names):
##  [1] 1--2 1--3 2--3 2--4 3--5 4--5 4--6 4--7 5--6 6--7
E(wg2)$weight
##  [1] 1 1 2 1 1 1 1 1 2 1

4 Estructuras de datos relacionales

Generalmente los grafos no se definen manualmente ya que la mayoría de las redes en la práctica son grandes.

Los datos para construir un grafo típicamente se almacenarán en un archivo de datos.

4.1 Matriz de adyacencia

La matriz de adyacencia \(\mathbf{Y} = [y_{i,j}]\) asociada con un grafo binario \(G=(V,E)\) con \(n\) vértices es una matriz binaria de \(n\times n\) tal que \(y_{i,j} = 1\) si \(\{i,j\} \in E\) y \(y_{i,j} = 0\) en otro caso.

La diagonal principal de una matriz de adyacencia está llena de ceros estructurales.

La matriz de adyacencia de un grafo no dirigido es necesariamente simétrica. Mientras que la matriz de adyacencia de un grafo dirigido es posiblemente asimétrica.

as_adjacency_matrix(g)
## 7 x 7 sparse Matrix of class "dgCMatrix"
##   1 2 3 4 5 6 7
## 1 . 1 1 . . . .
## 2 1 . 1 1 . . .
## 3 1 1 . . 1 . .
## 4 . 1 . . 1 1 1
## 5 . . 1 1 . 1 .
## 6 . . . 1 1 . 1
## 7 . . . 1 . 1 .
# formato matrix array
Y <- as.matrix(as_adjacency_matrix(g))
print(Y)
##   1 2 3 4 5 6 7
## 1 0 1 1 0 0 0 0
## 2 1 0 1 1 0 0 0
## 3 1 1 0 0 1 0 0
## 4 0 1 0 0 1 1 1
## 5 0 0 1 1 0 1 0
## 6 0 0 0 1 1 0 1
## 7 0 0 0 1 0 1 0
# version vectorizada
vY <- Y[lower.tri(Y)]
print(vY)
##  [1] 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 1 0 1

4.2 Matriz de aristas

Una matriz de aristas es un arreglo de dos columnas conformado por todos los pares de vértices que están unidos por una arista.

# aristas
E(g)
## + 10/10 edges from 92ea754 (vertex names):
##  [1] 1--2 1--3 2--3 2--4 3--5 4--5 4--6 4--7 5--6 6--7
# matriz de aristas
n <- dim(Y)[1]
A <- NULL
for (i in 1:(n-1)) for (j in (i+1):n) if (Y[i,j] == 1) A <- rbind(A, c(i,j))
print(A)
##       [,1] [,2]
##  [1,]    1    2
##  [2,]    1    3
##  [3,]    2    3
##  [4,]    2    4
##  [5,]    3    5
##  [6,]    4    5
##  [7,]    4    6
##  [8,]    4    7
##  [9,]    5    6
## [10,]    6    7

4.3 Ejemplo: Lazega

Red de relaciones de trabajo colaborativo entre miembros de una firma de abogados. Estos datos fueron recolectados con el propósito de estudiar la cooperación entre los actores sociales de una organización, mediante el intercambio de diversos tipos de recursos entre ellos. Disponible en la librería sand de R.

Lazega, E. (2001). The collegial phenomenon: The social mechanisms of cooperation among peers in a corporate law partnership. Oxford University Press on Demand.

# install.packages("sand")
suppressMessages(suppressWarnings(library(sand)))

# datos
head(elist.lazega)
##   V1  V2
## 1 V1 V17
## 2 V2  V7
## 3 V2 V16
## 4 V2 V17
## 5 V2 V22
## 6 V2 V26
class(elist.lazega)
## [1] "data.frame"
# atributos
head(v.attr.lazega)
##   Name Seniority Status Gender Office Years Age Practice School
## 1   V1         1      1      1      1    31  64        1      1
## 2   V2         2      1      1      1    32  62        2      1
## 3   V3         3      1      1      2    13  67        1      1
## 4   V4         4      1      1      1    31  59        2      3
## 5   V5         5      1      1      2    31  59        1      2
## 6   V6         6      1      1      2    29  55        1      1
class(v.attr.lazega)
## [1] "data.frame"
# grafo
g_lazega <- graph_from_data_frame(d = elist.lazega, directed = "F", vertices = v.attr.lazega)

# ver tambien
# graph_from_edgelist
# graph_from_adjacency_matrix

# simple?
is_simple(g_lazega)
## [1] TRUE
# ponderado?
is_weighted(g_lazega)
## [1] FALSE
# orden
vcount(g_lazega)
## [1] 36
# tamaño
ecount(g_lazega)
## [1] 115
# atributos
vertex_attr_names(g_lazega)
## [1] "name"      "Seniority" "Status"    "Gender"    "Office"    "Years"    
## [7] "Age"       "Practice"  "School"
# grafico
plot(g_lazega, vertex.label = NA, vertex.size = 6, edge.color = "gray50", vertex.frame.color = 1)
title(main = "Lazega")

5 Algunos conceptos fundamentales de la teoría de grafos

5.1 Adyacencia

Se dice que dos vértices \(u, v \in V\) son adyacentes (vecinos) lo que se denota con \(u\sim v\) si \(u\) y \(v\) están conectados por alguna arista en \(E\).

# vecinos del vertice 1
neighbors(graph = g, v = 1)
## + 2/7 vertices, named, from 92ea754:
## [1] 2 3

Un vértice se llama asilado (isolated) si no es adyacente a ningún otro nodo (un grafo se puede representar con una matriz de aristas más una lista de vértices aislados).

Un vértice \(v \in V\) es incidente (incident) en una arista \(e \in E\) si \(e=\{v,u\}\) para algún \(u\in V\).

El grado (degree) de un vértice \(v\) se define como el número de aristas incidentes en \(v\).

# grados
degree(g)
## 1 2 3 4 5 6 7 
## 2 3 3 4 3 3 2

Para dígrafos, el grado de entrada (in-degree) y el grado de salida (out-degree) de un vértice se definen como el número de aristas que apuntan hacia dentro y hacia fuera del vértice, respectivamente.

# grado de entrada
degree(graph = dg, mode = "in")
##  Juan Maria Pedro 
##     0     2     2
# grado de salida
degree(graph = dg, mode = "out")
##  Juan Maria Pedro 
##     2     1     1

5.2 Movimiento

Una caminata (walk) de \(v_0\) a \(v_\ell\) es una secuencia alternante \(\{v_0,e_1,v_1,e_2,v_2,\ldots,v_{\ell-1},e_\ell,v_\ell\}\) donde los puntos extremos de \(e_i\) son \(\{v_{i-1}, v_i\}\) para \(i=1,\ldots,\ell\). Se dice que la longitud de esta caminata es \(\ell\). Pueden haber caminatas abiertas o cerradas.

  • 1->2->3->4->5->3 es una caminata abierta.
  • 1->2->3->4->5->3->1 es una caminta cerrada.

Un sendero (trail) es una caminata abierta en la que no se repite ninguna arista (se pueden repetir vértices).

  • 1->3->8->6->3->2 es un sendero.

Un circuito (circuit) es un sendero cerrado, i.e., una caminata sin aristas repetidas para la cual los vértices inicial y final son los mismos (se pueden repetir vértices).

  • 1->2->4->3->6->8->3->1 es un circuito.

Un ciclo (cycle) es una caminata con longitud de al menos tres sin aristas repetidas, para la cual los vértices inicial y final son los mismos, y además todos los demás vértices son distintos.

  • 1->2->4->3->1 es un ciclo.

Los grafos que no contienen ciclos se denominan acíclicos (acycle).

Se dice que un vértice \(v\) es accesible desde otro vértice \(u\) si existe una caminata desde \(u\) hasta \(v\).

Se dice que un grafo está conectado si cada vértice es accesible desde todos los demás.

Grafos conectados con 5 vértices:

Una componente de un grafo es un subgrafo conectado maximalmente, i.e., un subgrafo para el cual la adición de cualquier otro vértice arruina la propiedad de conectividad.

Grafo con tres componentes conectadas:

# conectado?
is_connected(g)
## [1] TRUE
# componentes
clusters(g)
## $membership
## 1 2 3 4 5 6 7 
## 1 1 1 1 1 1 1 
## 
## $csize
## [1] 7
## 
## $no
## [1] 1

Un dígrafo está conectado débilmente si el grafo subyacente no dirido (resultado de remover la direccionalidad) está conectado, y se llama conectado fuertemente si cada vértice es accesible desde todos los demás mediante una caminata dirigida.

# conectado debilmente?
is_connected(graph = dg, mode = "weak")
## [1] TRUE
# conectado fuertemente?
is_connected(graph = dg, mode = "strong")
## [1] FALSE

5.3 Distancia

La distancia geodésica entre dos vértices de un grafo se define como la longitud del camino más corto entre los vértices (se establece igual a infinito si no existen caminos).

El valor de la distancia más grande un grafo se llama diámetro del grafo.

# diametro
diameter(g)
## [1] 3