Processing math: 48%

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āˆˆ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,ā€¦,n o 0,ā€¦,nāˆ’1, donde n=|V|.

2.1 Grafos y digrafos

Un grafo para el que cada arista {u,v}āˆˆ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