1 Introducción

La cohesión se refiere a la medida en que subconjuntos de vértices específicos son cohesivos (adherentes) respecto a la relación que define las aristas.

2 Cliques

Un enfoque para definir la cohesión de una red es mediante la especificación de subgrafos de interés.

Un clan (clique) \(C\) de un grafo \(G=(V,E)\) es un subconjunto de vértices tal que cada par de vértices distintos son adyacentes, i.e., el subgrafo de \(G\) inducido por \(C\) es un grafo completo.

Clanes de tamaños más grandes incluyen clanes de tamaños más pequeños.

¿Cuántos clanes?

# librerias
suppressMessages(suppressWarnings(library(igraph)))
# datos
g <- graph(edges = c(1,2,1,3,1,4,1,5,2,3,2,4,2,5,3,4,3,5,4,5,6,7,6,8,7,8,9,10,1,6,2,9,7,9), directed = F)
Y <- as.matrix(get.adjacency(graph = g, names = F))
# visualización
par(mfrow = c(1,2), mar = c(4, 3, 3, 1))
set.seed(42)
plot(g, vertex.size = 20, vertex.color = 0, vertex.label.color = "black", edge.color = "blue4")
corrplot::corrplot(corr = Y, col.lim = c(0,1), method = "color", tl.col = "black", addgrid.col = "gray", cl.pos = "n")

# orden
vcount(g)
## [1] 10
# tamaño
ecount(g)
## [1] 17
# clan?
c1 <- induced_subgraph(graph = g, vids = c(6,7,8))
ecount(c1) == choose(n = vcount(c1), k = 2)
## [1] TRUE
# frecuencias de clanes
table(sapply(X = cliques(graph = g, min = 1, max = 10), FUN = length))
## 
##  1  2  3  4  5 
## 10 17 11  5  1

Un clan maximal (maximal clique) es un clan que no se puede extender incluyendo algún otro vértice.

# clanes maximales
maximal.cliques(graph = g)
## [[1]]
## + 2/10 vertices, from 5dbb74d:
## [1] 10  9
## 
## [[2]]
## + 3/10 vertices, from 5dbb74d:
## [1] 6 7 8
## 
## [[3]]
## + 2/10 vertices, from 5dbb74d:
## [1] 6 1
## 
## [[4]]
## + 2/10 vertices, from 5dbb74d:
## [1] 7 9
## 
## [[5]]
## + 2/10 vertices, from 5dbb74d:
## [1] 9 2
## 
## [[6]]
## + 5/10 vertices, from 5dbb74d:
## [1] 1 2 5 4 3

Un clan máximo (maximum clique) es el clan maximal más grande.

El número clan (clique number) es el tamaño del clan máximo.

# clanes máximos
largest.cliques(graph = g)
## [[1]]
## + 5/10 vertices, from 5dbb74d:
## [1] 1 2 5 4 3
# número clan
clique.number(graph = g)
## [1] 5

En la práctica, clanes “grandes” son escasos, ya que requieren que el grafo sea denso, pero las redes reales comúnmente son dispersas (sparse).

2.1 Ejemplo: Interacciones sociales

Red de interacciones sociales entre los miembros de un club de karate.

Estos datos fueron recolectados para estudiar la fragmentación que sufrió el club en dos clubes diferentes debido a una disputa entre el director y el administrador.

\(y_{i,j} = 1\) si los miembros \(i\) y \(j\) tuvieron una interacción social en el club y \(y_{i,j} = 0\) en otro caso.

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

Disponible en el paquete igraphdata de R.

Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of anthropological research, 33(4), 452-473.

# librerías
suppressMessages(suppressWarnings(library(igraph)))
suppressMessages(suppressWarnings(library(igraphdata)))
# datos
data(karate)
karate <- upgrade_graph(karate)
# la representación de datos internos a veces cambia entre versiones
Y <- as.matrix(get.adjacency(graph = karate, names = F))
# orden
vcount(karate)
## [1] 34
# tamaño
ecount(karate)
## [1] 78
# dirigida?
is_directed(karate)
## [1] FALSE
# ponderada?
is_weighted(karate)
## [1] TRUE
# visualización
par(mfrow = c(1,1), mar = c(4, 3, 3, 1))
set.seed(123)
plot(karate, layout = layout_with_dh, vertex.size = 10, vertex.frame.color = "black", vertex.label.color = "black", main = "")

# clanes máximos
largest.cliques(graph = karate)
## [[1]]
## + 5/34 vertices, named, from 4b458a1:
## [1] Actor 2 Mr Hi   Actor 4 Actor 3 Actor 8
## 
## [[2]]
## + 5/34 vertices, named, from 4b458a1:
## [1] Actor 2  Mr Hi    Actor 4  Actor 3  Actor 14
# número clan
clique.number(graph = karate)
## [1] 5

2.2 Ejemplo: Interacciones proteína-proteína

Red de interacción de proteínas de levadura.

Las interacciones proteína-proteína prometen revelar aspectos del sistema regulatorio que subyace a la función celular.

Los nodos corresponden a proteínas y solo se consideran aquellas interacciones que tienen una confianza “moderada” y “alta”.

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

Disponible en el paquete igraphdata de R.

Von Mering, C., Krause, R., Snel, B., Cornell, M., Oliver, S. G., Fields, S., & Bork, P. (2002). Comparative assessment of large-scale data sets of protein–protein interactions. Nature, 417(6887), 399-403.

# datos
data(yeast)
yeast <- upgrade_graph(yeast)
# la representación de datos internos a veces cambia entre versiones
# orden
vcount(yeast)
## [1] 2617
# tamaño
ecount(yeast)
## [1] 11855
# dirigida?
is_directed(yeast)
## [1] FALSE
# ponderada?
is_weighted(yeast)
## [1] FALSE
# número clan
clique.number(graph = yeast)
## [1] 23

El número clan es relativamente pequeño (incluso para redes “grandes”).

3 Díadas y tríadas

Otras cantidades de interés son las díadas y las tríadas.

¿Cuáles son los estados diádicos no dirigidos y dirigidos?

¿Y los triádicos?

Estados triádicos no dirigidos (undirected triadic motifs):

Estados triádicos dirigidos (directed triadic motifs):

Davis, J.A. and Leinhardt, S. (1972). The Structure of Positive Interpersonal Relations in Small Groups. In J. Berger (Ed.), Sociological Theories in Progress, Volume 2, 218-251. Boston: Houghton Mifflin.

Un censo de los estados diádicos o triádicos proporciona una medida de la conectividad de una red.

3.1 Ejemplo: Blogs de SIDA

Red de blogs de SIDA, pacientes y sus redes de apoyo.

Un enlace dirigido de un blog a otro indica que el primero tiene un enlace al segundo en su página web.

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

Disponible en el paquete sand de R.

Miller, H. J. (2007). Societies and cities in the age of instant access. In Societies and cities in the age of instant access (pp. 3-28). Springer, Dordrecht.

# librerías
suppressMessages(suppressWarnings(library(sand)))
# data
data(aidsblog)
aidsblog <- upgrade_graph(aidsblog)
# la representación de datos internos a veces cambia entre versiones
# orden
vcount(aidsblog)
## [1] 146
# tamaño
ecount(aidsblog)
## [1] 187
# dirigida?
is_directed(aidsblog)
## [1] TRUE
# ponderada?
is_weighted(aidsblog)
## [1] FALSE
# visualización
set.seed(123)
par(mfrow = c(1,1), mar = c(4, 3, 3, 1))
plot(aidsblog, layout = layout_with_kk, vertex.label = NA, vertex.size = 5, vertex.frame.color = 1, edge.arrow.size = 0.5, main = "")

# simple?
is_simple(aidsblog)
## [1] FALSE
# simplificación
aidsblog <- simplify(aidsblog)
# censo de estados diádicos
#   mut   The number of pairs with mutual connections.
#   asym  The number of pairs with non-mutual connections.
#   null  The number of pairs with no connection between them.
dyad_census(aidsblog)
## $mut
## [1] 3
## 
## $asym
## [1] 177
## 
## $null
## [1] 10405
# censo de estados triádicos
#   003   A,B,C, the empty graph.
#   012   A->B, C, the graph with a single directed edge.
#   102   A<->B, C, the graph with a mutual connection between two vertices.
#   021D  A<-B->C, the out-star.
#   021U  A->B<-C, the in-star.
#   021C  A->B->C, directed line.
#   111D  A<->B<-C.
#   111U  A<->B->C.
#   030T  A->B<-C, A->C.
#   030C  A<-B<-C, A->C.
#   201   A<->B<->C.
#   120D  A<-B->C, A<->C.
#   120U  A->B<-C, A<->C.
#   120C  A->B->C, A<->C.
#   210   A->B<->C, A<->C.
#   300   A<->B<->C, A<->C, the complete graph.
triad_census(aidsblog)
##  [1] 484621  20717    300   2195     39     74      1    112      4      0
## [11]      2      0     15      0      0      0

La gran mayoría de los estados son nulos y de los que no lo son, casi todos son asimétricos, lo que indica una unilateralidad (asimetría) preponderante en la manera en que los blogs se referencian.

4 Densidad

La densidad (density) de un grafo se define como la frecuencia relativa de las aristas observadas respecto al potencial de aristas.

Para un subgrafo \(H=(V_H,E_H)\) del grafo \(G=(V,E)\), la densidad se calcula como \[ \textsf{den(H)}=\frac{|E_H|}{|V_H|(|V_H|-1)/2}\,. \] En el caso de un digrafo el denominador debe ser \(|V_H|(|V_H|-1)\).

La densidad asume valores entre 0 y 1 y se puede interpretar como una medida de qué tan cerca se encuentra \(H\) de ser un clan.

4.1 Ejemplo: Interacciones sociales

# densidad
ecount(karate)/(vcount(karate)*(vcount(karate)-1)/2)
## [1] 0.1390374
edge_density(graph = karate)
## [1] 0.1390374
mean(Y[lower.tri(Y, diag = F)])
## [1] 0.1390374
mean(Y[upper.tri(Y, diag = F)])
## [1] 0.1390374
# ego networks
g_1  <- induced_subgraph(graph = karate, vids = neighborhood(graph = karate, order = 1, nodes = 1) [[1]])
g_34 <- induced_subgraph(graph = karate, vids = neighborhood(graph = karate, order = 1, nodes = 34)[[1]])
# densidades
edge_density(graph = g_1)
## [1] 0.25
edge_density(graph = g_34)
## [1] 0.2091503

5 Transitividad global

Una tripla está constituida por tres nodos que están conectados por dos (tripla abierta) o tres (tripla cerrada) aristas.

La transitividad (transitivity) de un grafo se cuantifica por medio del coeficiente de agrupamiento (clustering coeffitient) que se calcula como \[ \textsf{cl} (G) =\frac{\text{no. triplas cerradas}}{\text{no. triplas}} =\frac{3\times \text{no. triángulos}}{\text{no. triplas}} = \frac{3\tau_\triangle(G)}{\tau_3(G)}\,, \] donde \(\tau_\triangle(G)\) es el número de triángulos de \(G\) y \(\tau_3(G)\) es el número de triplas.

El coeficiente de agrupamiento es una medida de agrupamiento global que caracteriza la propensión con la que las triplas forman triángulos.

5.1 Ejemplo

# datos
h <- graph(edges = c(1,2,1,3,2,3,1,4), directed = F)
# visualización
set.seed(123)
plot(h, vertex.size = 20, vertex.color = 0, vertex.label.color = "black", edge.color = "blue4")

# número de triángulos por vértice
count_triangles(graph = h)
## [1] 1 1 1 0
# vértices que son parte de un triángulo
triangles(graph = h)
## + 3/4 vertices, from 5f1bd7e:
## [1] 1 2 3
# conteos de estados triádicos
(mot <- motifs(graph = h, size = 3))
## [1] NA NA  2  1
# transitividad
3*mot[4]/(mot[3] + 3*mot[4])
## [1] 0.6
transitivity(graph = h, type = "global")
## [1] 0.6

5.2 Ejemplo

# datos
g <- graph(edges = c(1,2,1,3,1,4,1,5,2,3,2,4,2,5,3,4,3,5,4,5,6,7,6,8,7,8,9,10,1,6,2,9,7,9), directed = F)
# visualización
set.seed(42)
plot(g, vertex.size = 20, vertex.color = 0, vertex.label.color = "black", edge.color = "blue4")

# número de triángulos por vértice
count_triangles(graph = g)
##  [1] 6 6 6 6 6 1 1 1 0 0
# vértices que son parte de un triángulo
sort(triangles(graph = g))
## + 33/10 vertices, from 5f31f3a:
##  [1] 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 7 8
# conteos de estados triádicos
(mot <- motifs(graph = g, size = 3))
## [1] NA NA 15 11
# transitividad global
3*mot[4]/(mot[3] + 3*mot[4])
## [1] 0.6875
transitivity(graph = g, type = "global")
## [1] 0.6875

6 Transitividad local

El coeficiente de agrupamiento del vértice \(v\in V\) se define teniendo en cuenta la incidencia de \(v\) en las aristas que conforman las triplas: \[ \textsf{cl}(v) = \frac{\text{no. triplas cerradas que incluyen a $v$}}{k_v(k_v-1)/2}\,, \] donde \(k_v\) es el grado del nodo \(v\).

El coeficiente de agrupamiento de un vértice es una medida de agrupamiento local que cuantifica qué tan cerca están los vecinos del vértice de ser un clan.

Alternativamente, el coeficiente de agrupamiento global también se puede definir como el promedio de los coeficientes de agrupamiento locales de todos los vértices: \[ \textsf{cl} (G) = \frac{1}{|V|}\sum_{v\in V} \textsf{cl}(v)\,. \]

6.1 Ejemplo

# datos
g <- graph(edges = c(1,2,1,3,1,4,1,5,2,3,2,4,2,5,3,4,3,5,4,5,6,7,6,8,7,8,9,10,1,6,2,9,7,9), directed = F)
# visualización
set.seed(42)
plot(g, vertex.size = 20, vertex.color = 0, vertex.label.color = "black", edge.color = "blue4")

# intransitividad local del vértice 1
count_triangles(graph = g)
##  [1] 6 6 6 6 6 1 1 1 0 0
degree(graph = g)
##  [1] 5 5 4 4 4 3 3 2 3 1
6/(5*(5-1)/2)
## [1] 0.6
transitivity(graph = g, type = "local")
##  [1] 0.6000000 0.6000000 1.0000000 1.0000000 1.0000000 0.3333333 0.3333333
##  [8] 1.0000000 0.0000000       NaN
# transitividad global alternativa
mean(transitivity(graph = g, type = "local", vids = V(g)), na.rm = T)
## [1] 0.6518519

6.2 Ejemplo: Interacciones sociales

# transitividad
transitivity(graph = karate, type = "global")
## [1] 0.2556818
# intransitividad local
transitivity(karate, type = "local", vids = c(1,34))
## [1] 0.1500000 0.1102941

7 Reciprocidad

Un concepto exclusivo de los dígrafos es la reciprocidad, i.e., la propensión con la que hay reciprocidad de aristas en la red.

Las frecuencias se pueden calcular respecto al número de díadas o de aristas: \[ \textsf{rec}(G) = \frac{\text{no. aristas reciprocas}}{\text{no. aristas}}\,, \] o alternativamente, \[ \textsf{rec}(G) = \frac{\text{no. diadas reciprocas}}{\text{no. diadas no reciprocas}}\,. \]

7.1 Ejemplo: Blogs de SIDA

# reciprocidad (aristas)
reciprocity(aidsblog, mode = "default")
## [1] 0.03278689
# reciprocidad (díadas)
reciprocity(aidsblog, mode = "ratio")
## [1] 0.01666667

8 Conectividad

Comúnmente una de las componentes conectadas de un grafo \(G=(V,E)\) domina a las demás en magnitud. Tal componente se denomina componente gigante (giant component).

En la práctica, la atención se restringe a la componente gigante para llevar a cabo tanto el análisis como el modelamiento.

Un grafo \(G=(V,E)\) se llama \(k\)-conectado (\(k\)-connected) si \(|V|>k\) y la remoción de cualquier subconjunto de vértices \(X \subset V\) tal que \(|X| < k\) da como resultado un subgrafo que continua estando conectado.

La conectividad nodal de un grafo \(G=(V,E)\) corresponde al entero más grande \(k\) tal que \(G\) es \(k\)-conectado.

Alternativamente, también se puede definir como el número mínimo de nodos que deben eliminarse para desconectar el grafo.

Un vértice que la ser removido desconecta el grafo se denomina vértice de corte (cut vertex) o punto de articulación (articulation point).

La identificación de tales vértices proporciona una idea de dónde es vulnerable una red.

8.1 Ejemplo

# datos
f <- graph(edges = c(1,2,1,3,2,3,1,4,4,5), directed = F)
# visualización
set.seed(123)
plot(f, vertex.size = 20, vertex.color = 0, vertex.label.color = "black", edge.color = "blue4")

# red conectada?
is_connected(f)
## [1] TRUE
# k-conectividad
vertex_connectivity(f)
## [1] 1
edge_connectivity(f)
## [1] 1
# puntos de articulación
articulation_points(f)
## + 2/5 vertices, from 5f645e1:
## [1] 4 1

8.2 Ejemplo: Interacciones proteína-proteína

# red conectada?
is_connected(yeast)
## [1] FALSE
# componentes
componentes <- decompose(yeast)
length(componentes)
## [1] 92
table(sapply(X = componentes, FUN = vcount))
## 
##    2    3    4    5    6    7 2375 
##   63   13    5    6    1    3    1
# tamaño de la componte gigante
max(sapply(X = componentes, FUN = vcount))
## [1] 2375
max(sapply(X = componentes, FUN = vcount))/vcount(yeast)
## [1] 0.9075277
# componente gigante
yeast_gc <- decompose(yeast)[[1]]
# vértice-conectividad
vertex_connectivity(yeast_gc)
## [1] 1
# arista-conectividad
edge_connectivity(yeast_gc)
## [1] 1
# puntos de articulación
yeast_cv <- articulation_points(yeast_gc)
length(yeast_cv)
## [1] 350
length(yeast_cv)/vcount(yeast_gc)
## [1] 0.1473684

Se requiere la eliminación de un solo vértice o una sola arista para dividir el componente gigante en componentes adicionales.

Aproximadamente el 15% de los vértices son puntos de articulación.

9 Referencias