1 Introducción

Conformación, almacenamiento y gestión de datos relacionales:

Un grafo por sí solo (una colección de vértices y aristas) suele ser insuficiente para representar todos los atributos una red.

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

La teoría de grafos es fundamental para analizar redes sociales.

2 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 \(|V|\) y el número de aristas \(|E|\) se conocen como el orden y el tamaño del grafo, respectivamente.

Los vértices del grafo se enumeran con los números enteros \(1,\ldots,n\) o \(0,\ldots,n-1\), donde \(n = |V|\).

2.1 Grafos y digrafos

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 o simplemente grafo.

3 Multigrafos

Un multigrafo es aquel grafo 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 denomina grafo simple.

Paquete multinet en R.

3.1 Ejemplo: red binaria no dirigida

# install.packages("igraph")
suppressMessages(suppressWarnings(library(igraph)))
# red binaria no dirigida
g <- graph_from_literal(1-2, 1-3, 2-3, 2-4, 3-5, 4-5, 4-6, 4-7, 5-6, 6-7)
# otra manera
# g <- graph(edges = c(1,2, 1,3, 2,3, 2,4, 3,5, 4,5, 4,6, 4,7, 5,6, 6,7), directed = FALSE)
# clase de objeto
class(g)
## [1] "igraph"
# identificador
graph_id(g)
## [1] "ecce5a48-97ba-11ee-8000-010000000000"
# vértices
V(g)
## + 7/7 vertices, named, from ecce5a4:
## [1] 1 2 3 4 5 6 7
# orden
vcount(g)
## [1] 7
# aristas
E(g)
## + 10/10 edges from ecce5a4 (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 ecce5a4 UN-- 7 10 -- 
## + attr: 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
# ponderada?
is_weighted(g)
## [1] FALSE
# simple?
is_simple(g)
## [1] TRUE
# visualización
set.seed(123)
plot(g, main = "Red binaria no dirigida")

3.2 Ejmplo: red ponderada no dirigida

# red ponderada no dirigida
wg <- g
E(wg)$weight <- round(runif(n = ecount(wg)), 3)
# pesos
E(wg)$weight
##  [1] 0.403 0.352 0.122 0.991 0.936 0.939 0.407 0.772 0.388 0.033
# ponderada?
is_weighted(wg)
## [1] TRUE
# visualización
set.seed(123)
plot(wg, edge.width = 5*E(wg)$weight, main = "Red ponderada no dirigida")

3.3 Ejemplo: red binaria dirigida

# red binaria dirigida
dg <- graph_from_literal(1-+2, 1-+3, 2++3)
# aristas
E(dg)
## + 4/4 edges from ed102f9 (vertex names):
## [1] 1->2 1->3 2->3 3->2
# etiquetas
V(dg)$name <- c("Juan", "Maria", "Pedro")
# agregar 'sexo' como atributo
V(dg)$sexo <- c("M","F","M")
# aristas
E(dg)
## + 4/4 edges from ed102f9 (vertex names):
## [1] Juan ->Maria Juan ->Pedro Maria->Pedro Pedro->Maria
# visualización
set.seed(123)
plot(dg, vertex.size = 35, main = "Red binaria dirigida")

3.4 Ejemplo: multigrafo

# multigrafo
mg <- g + edge(c(1,1), c(1,2), c(1,3))
print_all(mg)
## IGRAPH ed2c6de UN-- 7 13 -- 
## + attr: name (v/c)
## + edges (vertex names):
## 1 -- 1, 1, 2, 2, 3, 3
## 2 -- 1, 1, 3, 4
## 3 -- 1, 1, 2, 5
## 4 -- 2, 5, 6, 7
## 5 -- 3, 4, 6
## 6 -- 4, 5, 7
## 7 -- 4, 6
# simple?
is_simple(mg)
## [1] FALSE
# simplificación
E(mg)$weight <- 1
wg2 <- simplify(mg)
# simple?
is_simple(wg2)
## [1] TRUE
# ponderada?
is_weighted(wg2)
## [1] TRUE
# aristas
# se pierden los bucles
E(wg2)
## + 10/10 edges from ed2e175 (vertex names):
##  [1] 1--2 1--3 2--3 2--4 3--5 4--5 4--6 4--7 5--6 6--7
# pesos
E(wg2)$weight
##  [1] 2 2 1 1 1 1 1 1 1 1

4 Estructuras de datos

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

Los datos para construir un grafo comúnmente se almacenarán en un archivo de datos (.txt, .csc, .dat, etc.).

4.1 Matriz de adyacencia

La matriz de adyacencia o socio-matriz \(\mathbf{Y} = [y_{i,j}]\) asociada con un grafo \(G=(V,E)\) de orden \(n\) 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.

La matriz de adyacencia de un grafo dirigido es posiblemente asimétrica.

4.2 Ejemplo: red binaria no dirigida

# red binaria no dirigida
g <- graph_from_literal(1-2, 1-3, 2-3, 2-4, 3-5, 4-5, 4-6, 4-7, 5-6, 6-7)
# visualización
set.seed(123)
plot(g, main = "Red binaria no dirigida")

# matriz de adyacencia
A <- get.adjacency(g)
# clase de objeto
class(A)
## [1] "dgCMatrix"
## attr(,"package")
## [1] "Matrix"
print(A)
## 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 <- get.adjacency(g, sparse = F)
# clase de objeto
class(Y)
## [1] "matrix" "array"
# simétrica?
isSymmetric(Y)
## [1] TRUE
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
# versión vectorizada exhaustiva
(yvec1 <- Y[lower.tri(Y)])
##  [1] 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 1 0 1
# versión vectorizada indexada
(yvec2 <- which(yvec1 == 1))
##  [1]  1  2  7  8 13 16 17 18 19 21

4.3 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.

4.4 Ejemplo: red binaria no dirigida (cont.)

# 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))
# clase de objeto
class(A)
## [1] "matrix" "array"
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.5 Ejemplo: Trabajo colaborativo

Red de relaciones de trabajo colaborativo entre los miembros de una firma de abogados (SG&R).

Estos datos fueron recolectados para estudiar la cooperación entre los actores de una organización.

\(y_{i,j} = 1\) si los miembros \(i\) y \(j\) trabajaron juntos en al menos un caso y \(y_{i,j} = 0\) en otro caso.

Una descripción completa de los datos se puede encontrar aquí.

Disponible en el paquete 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
# clase de objeto
class(elist.lazega)
## [1] "data.frame"
# dimensión
dim(elist.lazega)
## [1] 115   2
# grafo
g_lazega <- graph_from_data_frame(d = elist.lazega, directed = "F", vertices = v.attr.lazega)
# ver también 'graph_from_edgelist' y 'graph_from_adjacency_matrix'}
V(g_lazega)$name <- 1:vcount(g_lazega)
# matriz de adyacencia
Y_lazega <- get.adjacency(g_lazega, sparse = F)
# 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
# visualización
par(mfrow = c(1,2))
# grafo
set.seed(123)
plot(g_lazega, vertex.size = 9, vertex.label.color = "black", vertex.color = NA, vertex.frame.color = "black", edge.color = "blue4", main = "Trabajo colaborativo")
# matriz de adyacencia
corrplot::corrplot(corr = Y_lazega, method = "color", tl.col = "black", addgrid.col = "gray90", cl.pos = "n")

5 Referencias