1 Introducción

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

Varias nociones de cohesión dependiendo del interés:

2 Subgrafos

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

Los cliques son subgrafos completos (todos los vértices son accesibles).

Cliques de tamaños más grandes incluyen cliques de tamaños más pequeños. Un clique maximal (clique maximal) es aquel que no es un subconjunto de un clique más grande.

En la práctica, cliques “grandes” son relativamente raros, ya que requieren que el grafo sea denso, mientras que las redes reales son dispersas (parse).

El número clique (clique number) se define como el tamaño del clique más grande.

Otras cantidades de interés son las diadas y las triadas.

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

Estados triádicos dirigidos (directed triadic motifs):

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

2.1 Ejmplo: Zachary

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

Los nodos representan a los miembros de un club de karate observado durante aproximadamente 2 años y los enlaces que conectan dos nodos indican interacciones sociales entre los dos miembros correspondientes.

# datos
suppressMessages(suppressWarnings(library(sand)))
data(karate)
# orden
vcount(karate)
## [1] 34
# tamaño
ecount(karate)
## [1] 78
# cliques
table(sapply(cliques(karate), length))
## 
##  1  2  3  4  5 
## 34 78 45 11  2
# cliques de tamaño 5
cliques(karate)[sapply(cliques(karate), length) == 5]
## [[1]]
## + 5/34 vertices, named, from 4b458a1:
## [1] Mr Hi    Actor 2  Actor 3  Actor 4  Actor 14
## 
## [[2]]
## + 5/34 vertices, named, from 4b458a1:
## [1] Mr Hi   Actor 2 Actor 3 Actor 4 Actor 8
# cliques maximales
table(sapply(max_cliques(karate), length))
## 
##  2  3  4  5 
## 11 21  2  2
# numero clique
clique_num(karate)
## [1] 5

34 cliques de tamaño 1, 78 cliques de tamaño 2, 45 cliques de tamaño 3, … .

Los dos cliques más grandes son maximales. Sólo dos de los 11 cliques de tamaño cuatro son maximales.

El número clique es 5.

2.2 Ejemplo: Yeast

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.

Interacciones entre proteínas que tienen una confianza “alta” y “media”. Las interacciones proteína-proteína prometen revelar aspectos de la compleja red reguladora que subyace a la función celular.

suppressMessages(suppressWarnings(library(igraphdata)))
data(yeast)
# orden
vcount(yeast)
## [1] 2617
# tamaño
ecount(yeast)
## [1] 11855
# numero clique
clique_num(yeast)
## [1] 23

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

2.3 Ejemplo: Blogs

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.

Red de blogs asociados con el SIDA, los 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.

# simplificacion
aidsblog <- simplify(aidsblog)
# censo de estados diadicos
dyad_census(aidsblog)
## $mut
## [1] 3
## 
## $asym
## [1] 177
## 
## $null
## [1] 10405
# censo de estados triadicos
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 marcada unilateralidad en la manera en que los blogs se referencian.

3 Frecuencias relativas

La densidad 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_|-1)\).

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

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

La transitividad de un grafo se define como la fracción de triplas transitivas (triángulos) y se acostumbra a cuantificar 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 triangulos en \(G\) y \(\tau_3(G)\) es el numéro de triplas.

El coeficiente de agrupamiento es una medida de agrupamiento global, que caracteriza la frecuencia relativa con la que las triplas conectadas se acercan para formar triángulos.

El coeficiente de agrupamiento local de un vértice dado se define de manera análoga teniendo en cuenta la incidencia del vértice en las aristas que conforman las triplas.

Un concepto exclusivo de los dígrafos es el de reciprocidad, es decir, la medida en la que hay reciprocidad entre las aristas que conforman la red. Las frecuencias se pueden calcular respecto al número de diadas 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}} \]

3.1 Ejemplo: Zachary (cont.)

# ego network
ego_1  <- induced_subgraph(karate, neighborhood(karate, 1, 1) [[1]])
ego_34 <- induced_subgraph(karate, neighborhood(karate, 1, 34)[[1]])
# densidades
edge_density(karate)
## [1] 0.1390374
edge_density(ego_1)
## [1] 0.25
edge_density(ego_34)
## [1] 0.2091503
# numero de triangulos
sum(count_triangles(karate))
## [1] 135
# transitividad
transitivity(karate)
## [1] 0.2556818
# transividad local
transitivity(karate, type = "local", vids = c(1,34))
## [1] 0.1500000 0.1102941

3.2 Ejemplo: Blogs (cont.)

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

La reciprocidad es bajo bajo cualquier definición.

4 Conectividad

A menudo es uno de los componentes conectados en un grafo \(G=(V,E)\) domina a los demás en magnitud (contiene la gran mayoría de los vértices). Tal componente se denomina componente gigante (giant component).

En la práctica, muchas veces la atención se restringe al componente gigante para llevar a cabo más análisis y modelamiento.

La propiedad del pequeño mundo (small-world property), que se refiere a la situación donde la distancia geodésica entre pares de vértices es generalmente bastante pequeña, y la transitividad es relativamente alta.

Un grafo \(G=(V,E)\) se llama \(k\)-vértice-conectado (\(k\)-vertex-connected) si el número de vértices \(n> k\), y la remoción de cualquier subconjunto de vértices \(X \subset V\) de cardinalidad \(|X| < k\) deja un subgrafo que está conectado.

La vértice-conectividad o conectividad nodal de un grafo \(G=(V,E)\) corresponde al entero más grande tal que \(G\) es \(k\)-vértice-conectado. Alternativamente, también se puede definir como el número mínimo de nodos que deben eliminarse para desconectar el grafo.

Si la eliminación de un conjunto particular de vértices en un grafo desconecta el grafo. Un vértice que desconecta el grafo se denomina vértice de corte o punto de articulación. La identificación de tales vértices puede proporcionar una idea de dónde es vulnerable una red.

Similarmente se definen las nociones para las aristas y digrafos (noción débil y fuerte).

4.1 Ejemplo: Yeast

# red conectada?
is_connected(yeast)
## [1] FALSE
# componentes
comps <- decompose(yeast)
length(comps)
## [1] 92
table(sapply(comps, vcount))
## 
##    2    3    4    5    6    7 2375 
##   63   13    5    6    1    3    1
# tamaño componte gigante
max(sapply(comps, vcount))
## [1] 2375
max(sapply(comps, vcount))/vcount(yeast)
## [1] 0.9075277
# componente gigante
yeast_gc <- decompose(yeast)[[1]]
# mundo pequeño?
mean_distance(yeast_gc)
## [1] 5.09597
diameter(yeast_gc)
## [1] 15
transitivity(yeast_gc)
## [1] 0.4686663
# vertice-conectividad
vertex_connectivity(yeast_gc)
## [1] 1
# arista-conectividad
edge_connectivity(yeast_gc)
## [1] 1
# puntos de articulacion
yeast_cut_vertices <- articulation_points(yeast_gc)
length(yeast_cut_vertices)
## [1] 350
length(yeast_cut_vertices)/vcount(yeast_gc)
## [1] 0.1473684

Por lo tanto, se requiere la eliminación de un solo vértice o arista bien elegida para poder dividir el componente gigante en componentes adicionales.

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