1 Introducción

Las preguntas de interés se pueden formular en términos de algún aspecto de las componentes o de la estructura de la red.

Caracterizar los aspectos fundamentales de la estructura social y la dinámica de la red.

2 Grado

Considere el grafo \(G=(V,E)\). El grado (degree) \(d_v\) de un vértice \(v\in V\) corresponde al número de aristas indicentes en \(v\). Se define \(f_d\) como la fracción de vértices \(v\in V\) tales que \(d_v=d\). La colección \(\{ f_d \}\) se denomina distribución de grado (degree distribución) de \(G\).

En redes ponderadas, la fuerza (strength) de un vértice se define como la suma de los pesos de las aristas incidentes al vértice. La distribución de fuerza/distribución de grado ponderada (strength distribution/weighted degree distribution) se define de manera análoga.

Entender la forma en que los vértices de diferentes grados están relacionados entre sí. Esto se puede lograr mediante el grado promedio de los vecinos de un vértice.

2.1 Ejemplo: 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
# dirigida?
is_directed(karate)
## [1] FALSE
# ponderada?
is_weighted(karate)
## [1] TRUE
# grado
n <- vcount(karate)
d <- degree(karate)
# grafico
par(mfrow = c(1,2))
plot(table(factor(d, levels = 0:n))/n, type = "h", lwd = 4, ylim = c(0,0.5), xlab = "Grado", ylab = "Densidad", main = "", xaxt = "n", col = "gray50")
axis(side = 1, at = seq(from = 0, to = 35, by = 5))
plot(NA, NA, type = "n", xlim = c(0,35), ylim = c(0,0.5), xlab = "Grado", ylab = "Densidad", main = "")
hist(d, freq = F, col = "gray90", border = "gray50", add = T)
title(main = "Distribución de grado", outer = T, line = -2)

# distribucion de grado ponderada
wd <- strength(karate)
# grafico
plot(NA, NA, type = "n", xlim = c(0,50), ylim = c(0,0.1), xlab = "Fuerza", ylab = "Densidad", main = "Distribución de fuerza")
hist(wd, freq = F, col = "gray90", border = "gray50", add = T)

Hay tres grupos distintos de vértices. Los dos vértices más conectados corresponden a los actores 1 y 34, que representan al instructor y al administrador sobre quienes finalmente se dividió el club. El siguiente conjunto de vértices consta de los actores 2, 3, y 33, que son los más cercanos a los actores 1 y 34.

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.

# datos
suppressMessages(suppressWarnings(library(igraphdata)))
data(yeast)
# orden
vcount(yeast)
## [1] 2617
# tamaño
ecount(yeast)
## [1] 11855
# dirigida?
is_directed(yeast)
## [1] FALSE
# ponderada?
is_weighted(yeast)
## [1] FALSE
# grado
d <- degree(yeast)
# distribucion de grado
dd <- degree_distribution(yeast)
# grafico
par(mfrow = c(1,2))
plot(NA, NA, type = "n", xlim = c(0,120), ylim = c(0,0.08), xlab = "Grado", ylab = "Densidad", main = "Distribución de grado")
hist(d, freq = F, col = "gray90", border = "gray50", add = T)
ind <- dd != 0
plot((0:max(d))[ind], dd[ind], log = "xy", col = "blue", xlab = "Log-grado", ylab = "Log-densidad", main = "Distribución de grado (log-log)")

# grado promedio
mnd <- knn(graph = yeast, vids = V(yeast))$knn
plot(d, mnd, log = "xy", col = "blue", xlab = "Log-grado", ylab = "Log-grado promedio de los vecinos")

Hay una fracción sustancial de vértices de grado bastante bajo, pero también hay un número no trivial de vértices con grados en órdenes de magnitud más altos.

Hay un decaimiento aproximadamente lineal en la frecuencia logarítmica en función del grado logarítmico. Si bien es posible resumir la tasa de esta disminución usando regresión lineal simple, son preferibles métodos más sofisticados.

Hay una tendencia a que los vértices de grados superiores se vinculen con vértices similares. Mientras que los vértices de grados inferiores tienden a enlazarse con vértices de grados tanto inferiores como superiores.

3 Centralidad

Las medidas de centralidad están diseñadas para cuantificar la noción de “importancia” de los nodos de una red.

Existen versiones normalizadas de todas las medidas para facilitar la comparación entre grafos y otras medidas. La normalización se logra multiplicando por una constante apropiada.

3.1 Centralidad de cercanía

Un vértice se considera “importante” si está “cerca” de muchos otros vértices: \[ c_{\textsf{C}}(v) = \frac{1}{\sum_{u\in V} \textsf{d}(v,u)} \] donde \(\textsf{d}(v,u)\) es la distancia geodésica entre \(v\in V\) y \(u\in V\).

3.2 Centralidad de intermediación

Un vértice se considera “importante” si se encuentra “entre” otros pares de vértices. Los vértices que se encuentran en muchos caminos son más críticos para el proceso de comunicación: \[ c_{\textsf{B}}(v) = \sum_{s,t\in V:s\neq t\neq v} \frac{\sigma(s,t\mid v)}{\sigma(s,t)} \] donde \(\sigma(s,t\mid v)\) es el número total de caminos más cortos entre \(s\) y \(t\) que pasan por \(v\), y \(\sigma(s,t)\) es el número total de caminos más cortos entre \(s\) y \(t\) (independientemente de si pasan o no por \(v\)).

3.3 Centralidad propia

Un vértice se considera “importante” si sus vecinos son a su vez “centrales”: \[ c_{\textsf{E}}(v) = \alpha\sum_{\{u,v\}\in E} c(u) \] donde \(\mathbf{c}=(c(1),\ldots,c(n))\) es una solución al problema de vectores propios dado por \(\mathbf{Y}\mathbf{c}=\alpha^{-1}\mathbf{c}\), con \(\mathbf{Y}\) la matriz de adyacencia, y \(\alpha^{-1}\) es el valor propio más grande de \(\mathbf{Y}\) y \(\mathbf{c}\) es el vector propio correspondiente. La convención es reportar los valores absolutos de las entradas de \(\mathbf{c}\).

3.4 Ejemplo : Zachary (cont.)

Una forma atractiva de mostrar centralidades de vértices (para redes de tamaño moderado) es utilizar un diseño radial, con más vértices centrales ubicados más cerca del centro.

suppressMessages(suppressWarnings(library(sna)))
A  <- igraph::as_adjacency_matrix(karate, sparse = F)
g  <- network::as.network.matrix(A)
cg <- sna::degree(g, gmode = "digraph")
cc <- sna::closeness(g, gmode = "digraph")
cb <- sna::betweenness(g, gmode = "digraph")
ce <- sna::evcent(g, gmode = "digraph")
cols <- c("blue", rep("red", 32), "yellow")
par(mfrow = c(2,2))
sna::gplot.target(dat = g, x = cg, main = "Degree", circ.lab = F, circ.col = "skyblue", usearrows = F, vertex.col = cols, edge.col = "darkgray")
sna::gplot.target(dat = g, x = cc, main = "closeness", circ.lab = F, circ.col = "skyblue", usearrows = F, vertex.col = cols, edge.col = "darkgray")
sna::gplot.target(dat = g, x = cb, main = "Betweenness", circ.lab = F, circ.col = "skyblue", usearrows = F, vertex.col = cols, edge.col = "darkgray")
sna::gplot.target(dat = g, x = ce, main = "Eigenvalue", circ.lab = F, circ.col = "skyblue", usearrows = F, vertex.col = cols, edge.col = "darkgray")

3.5 Ejemplo: Blogs

Para digrafos, los vértices de centro (hubs) son “importantes” por la cantidad de vértices “centrales” a los que señalan. Mientras que los vértices de autoridad (authority) son “importantes” por la cantidad de vértices “importantes” que los señalan.

Específicamente, dada una matriz de adyacencia \(\mathbf{Y}\) de una red dirigida, estas medidas se calculan por medio de la centralidad propia que se obtienen de las matrices \(\mathbf{M}_{\textsf{H}}=\mathbf{Y}\mathbf{Y}^{\textsf{T}}\) y \(\mathbf{M}_{\textsf{A}}=\mathbf{Y}^{\textsf{T}}\mathbf{Y}\), respectivamente.

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.

# orden
vcount(aidsblog)
## [1] 146
# tamaño
ecount(aidsblog)
## [1] 187
# dirigida?
is_directed(aidsblog)
## [1] TRUE
# ponderada?
is_weighted(aidsblog)
## [1] FALSE
# centros y autoridades
hs <- igraph::hub_score(aidsblog)$vector
as <- igraph::authority_score(aidsblog)$vector
par(mfrow = c(1,2))
l <- layout_with_kk(aidsblog)
plot(aidsblog, layout = l, main = "Centros", vertex.label = "", vertex.size=10*sqrt(hs))
plot(aidsblog, layout = l, main = "Autoridades", vertex.label = "", vertex.size=10*sqrt(as))