Asortatividad

Relatoría · Análisis de redes

knitr::opts_chunk$set(message = FALSE, warning = FALSE)

library(igraph)
library(igraphdata)

Introducción

Sea \(G = (V, E)\) un grafo con \(n = |V|\) vértices y \(m = |E|\) aristas. La mezcla (mixing) describe la forma en que los vértices se conectan de acuerdo con alguna característica nodal. Podemos distinguir dos tipos de mezcla: la asortativa y la desasortativa.

Mezcla asortativa

Es aquella en la que los vértices con características iguales o similares tienden a conectarse entre sí.

Mezcla desasortativa

Ocurre cuando las conexiones tienden a darse entre vértices con características diferentes.

Coeficiente de asortatividad

• \(r_a > 0\): predomina la mezcla asortativa.
• \(r_a < 0\): predomina la mezcla desasortativa.
• \(r_a \approx 0\): no existe una tendencia global clara hacia ninguno de los dos patrones.

No existen umbrales universales. La interpretación depende de la estructura de la red, de la distribución de la característica y de los grados de los vértices.

Redes de los ejemplos

Cada sección presenta primero la teoría y después la aplica a una o dos redes del paquete igraphdata:

• Red de amistad (UKfaculty): 81 miembros de una facultad de una universidad del Reino Unido. Es dirigida y ponderada, y cada miembro pertenece a una de cuatro escuelas.
• Red de aeropuertos (USairports): aeropuertos de Estados Unidos conectados por vuelos de pasajeros. Se usan solo los 48 estados continentales y el Distrito de Columbia (485 aeropuertos); Alaska, Hawái y los territorios se excluyen porque funcionan como sistemas aparte. Tiene coordenadas geográficas, estado y número de pasajeros por ruta.

Tipo de característica

La medida apropiada depende de la naturaleza de la característica nodal.

• Una característica categórica identifica clases sin asumir distancias numéricas entre ellas. En este caso se utiliza la asortatividad nominal. Más adelante la usamos en el ejemplo de la red de amistad de una universidad del Reino Unido.
• Una característica numérica asigna valores cuantitativos a los vértices, por ejemplo, la edad. En este caso se utiliza la asortatividad numérica. Más adelante la usamos en el ejemplo de los aeropuertos, con el grado de los vértices como característica.

Características categóricas

Matriz de mezcla

Suponga que cada vértice pertenece a una de \(M\) categorías.

Sea \(E = (e_{ij})\) la matriz de mezcla de tamaño \(M \times M\), donde \(e_{ij}\) representa la fracción de conexiones cuyo primer extremo pertenece a la categoría \(i\) y cuyo segundo extremo pertenece a la categoría \(j\).

En una red no dirigida, cada arista \(\{u, v\}\) se considera en las dos orientaciones, \((u, v)\) y \((v, u)\). De esta forma,

\[ \sum_{i=1}^{M} \sum_{j=1}^{M} e_{ij} = 1. \]

Defina las distribuciones marginales

\[ a_i = \sum_{j=1}^{M} e_{ij}, \qquad b_j = \sum_{i=1}^{M} e_{ij}. \]

En una red no dirigida se tiene que \(a_i = b_i\).

La cantidad

\[ p_{obs} = \sum_{i=1}^{M} e_{ii} \]

es la proporción observada de conexiones entre vértices de la misma categoría. Bajo mezcla independiente, la proporción esperada es

\[ p_{esp} = \sum_{i=1}^{M} a_i b_i. \]

Coeficiente de asortatividad nominal

El coeficiente de asortatividad nominal se define como

\[ r_a = \frac{p_{obs} - p_{esp}}{1 - p_{esp}} = \frac{\sum_{i=1}^{M} e_{ii} - \sum_{i=1}^{M} a_i b_i}{1 - \sum_{i=1}^{M} a_i b_i}. \]

Interpretación

El coeficiente satisface \(-1 \leq r_a \leq 1\).

• \(r_a = 1\): asortatividad perfecta.
• \(r_a = 0\): ausencia de mezcla asortativa neta.
• \(r_a < 0\): mezcla desasortativa.
• El mínimo alcanzable puede ser mayor que \(-1\), dependiendo de la distribución de las categorías y de la estructura de la red.

Un valor cercano a cero no implica ausencia de estructura, ya que distintos patrones de mezcla pueden compensarse. Por ejemplo, con tres categorías \(A\), \(B\) y \(C\), una fuerte concentración de conexiones entre \(A\) y \(B\) puede compensarse con pocas conexiones entre \(B\) y \(C\), produciendo \(r_a \approx 0\). Por ello, conviene analizar conjuntamente \(r_a\) y la matriz de mezcla.

En igraph, la asortatividad nominal se calcula mediante assortativity_nominal().

Ejemplo: Red de amistad

Presentación de la red

Considere la red de amistad entre los miembros de una facultad de una universidad del Reino Unido, estudiada por Nepusz et al. (2008).

Los vértices representan a los miembros de la facultad. Una arista dirigida \((u, v)\) indica que \(u\) declaró a \(v\) como amigo y su peso registra la intensidad de la relación. El atributo Group identifica la escuela a la que pertenece cada miembro.

Los datos están disponibles en el paquete igraphdata.

# datos
data("UKfaculty", package = "igraphdata")
UKfaculty <- upgrade_graph(UKfaculty)

# propiedades básicas
vcount(UKfaculty)

## [1] 81

ecount(UKfaculty)

## [1] 817

is_directed(UKfaculty)

## [1] TRUE

is_weighted(UKfaculty)

## [1] TRUE

is_simple(UKfaculty)

## [1] TRUE

# tamaño de cada escuela
table(V(UKfaculty)$Group)

## 
##  1  2  3  4 
## 33 27 19  2

# visualización
set.seed(123)
plot(
  UKfaculty,
  layout = layout_with_fr,
  vertex.size = 6,
  vertex.color = as.integer(as.factor(V(UKfaculty)$Group)) + 1,
  vertex.frame.color = "black",
  vertex.label = NA,
  edge.arrow.size = 0.2,
  edge.color = "gray70"
)

Asortatividad por escuela

Group es una característica categórica, por lo que debe utilizarse asortatividad nominal. Como la red es dirigida, se usa directed = TRUE.

# escuela de cada miembro
g.types <- V(UKfaculty)$Group

# asortatividad nominal
r.group <- assortativity_nominal(UKfaculty, types = g.types, directed = TRUE)

r.group

## [1] 0.7053802

\(r_a = 0.705\) indica fuerte asortatividad por escuela, es decir, los miembros tienden a declarar como amigos a otros de la misma escuela.

La matriz de mezcla permite observar qué proporción de las conexiones ocurre dentro y entre las escuelas. Como la red es dirigida, cada arista se cuenta una sola vez (de origen a destino), por lo que la matriz no tiene por qué ser simétrica y, en general, \(a_i \neq b_i\).

# función para construir la matriz de mezcla
# types: característica del primer extremo (origen)
# types.in: característica del segundo extremo (destino); por defecto, la misma
mixing_matrix <- function(graph, types, types.in = types) {
  # si types es factor se respeta el orden de sus niveles
  lev <- if (is.factor(types)) levels(types) else sort(unique(as.character(types)))
  ed  <- ends(graph, E(graph), names = FALSE)

  x <- factor(types[ed[, 1]], levels = lev)
  y <- factor(types.in[ed[, 2]], levels = lev)

  tab <- table(x, y)

  # cada arista no dirigida aporta las dos orientaciones
  if (!is_directed(graph)) tab <- tab + t(tab)

  tab / sum(tab)
}

# matriz de mezcla por escuela
E.group <- mixing_matrix(UKfaculty, g.types)
round(E.group, 3)

##    y
## x       1     2     3     4
##   1 0.388 0.050 0.016 0.017
##   2 0.029 0.306 0.007 0.002
##   3 0.026 0.016 0.118 0.002
##   4 0.013 0.004 0.002 0.002

La matriz muestra una fuerte concentración de conexiones dentro de cada escuela (38.8%, 30.6% y 11.8% en las escuelas 1, 2 y 3) y pocas conexiones entre escuelas. La escuela 4 tiene solo dos miembros, por lo que su peso en la matriz es mínimo.

# mapa de calor de la matriz de mezcla
heatmap(
  E.group,
  Rowv = NA,
  Colv = NA,
  scale = "none",
  xlab = "Escuela del segundo extremo",
  ylab = "Escuela del primer extremo"
)

A partir de esta matriz puede recuperarse directamente el coeficiente.

# proporciones marginales
avec <- rowSums(E.group)   # extremo de salida
bvec <- colSums(E.group)   # extremo de entrada

# proporción observada y esperada dentro de la misma escuela
p.obs <- sum(diag(E.group))
p.esp <- sum(avec * bvec)

# asortatividad calculada desde la matriz de mezcla
r.manual <- (p.obs - p.esp) / (1 - p.esp)

c(p.obs = p.obs, p.esp = p.esp, r.manual = r.manual)

##     p.obs     p.esp  r.manual 
## 0.8139535 0.3685199 0.7053802

El valor coincide con el de igraph (\(r_a \approx 0.705\)). La proporción observada de conexiones dentro de la misma escuela (\(\approx 0.81\)) es mucho mayor que la esperada bajo mezcla independiente (\(\approx 0.37\)).

Características numéricas

Sea \(x_v\) el valor de una característica numérica para el vértice \(v\).

En una red dirigida, cada arista \((u, v)\) diferencia un extremo de salida y uno de entrada. El coeficiente corresponde a la correlación de Pearson entre los valores observados en ambos extremos de las \(m\) aristas. Como los dos extremos tienen distribuciones distintas, cada uno tiene su propia media:

\[ \bar{x}^{\,out} = \frac{1}{m} \sum_{(u,v) \in E} x_u, \qquad \bar{x}^{\,in} = \frac{1}{m} \sum_{(u,v) \in E} x_v, \]

\[ r_a = \frac{\displaystyle \sum_{(u,v) \in E} (x_u - \bar{x}^{\,out})(x_v - \bar{x}^{\,in})} {\sqrt{\displaystyle \sum_{(u,v) \in E} (x_u - \bar{x}^{\,out})^2 \sum_{(u,v) \in E} (x_v - \bar{x}^{\,in})^2}}. \]

En una red no dirigida no existe una orientación natural. Por ello, cada arista \(\{u, v\}\) se considera en ambas orientaciones, \((u, v)\) y \((v, u)\). Si \(E^\star\) denota este conjunto de \(2m\) pares orientados, entonces

\[ \mu_x = \frac{1}{2m} \sum_{(u,v) \in E^\star} x_u, \qquad \sigma_x^2 = \frac{1}{2m} \sum_{(u,v) \in E^\star} (x_u - \mu_x)^2, \]

por lo que

\[ r_a = \frac{\displaystyle \frac{1}{2m} \sum_{(u,v) \in E^\star} (x_u - \mu_x)(x_v - \mu_x)}{\sigma_x^2}. \]

Así, \(r_a\) mide la correlación entre los valores de una característica en vértices conectados.

En igraph, la asortatividad numérica se calcula mediante assortativity().

Asortatividad por grado

Una aplicación particularmente importante utiliza el grado como característica nodal.

En una red no dirigida, si \(k_u\) es el grado del vértice \(u\), la asortatividad por grado \(r_k\) (Newman, 2002) mide la correlación entre los grados de vértices conectados.

• \(r_k > 0\): los vértices de alto grado tienden a conectarse con otros vértices de alto grado, y los de bajo grado, con otros de bajo grado.
• \(r_k < 0\): los vértices de alto grado tienden a conectarse con vértices de bajo grado.

En igraph se calcula con assortativity_degree().

Grado medio de los vecinos

El coeficiente \(r_k\) resume todo el patrón grado–grado en un único número. Una descripción complementaria es

\[ k_{nn}(u) = \frac{1}{k_u} \sum_{v \in N(u)} k_v, \]

donde \(N(u)\) es el conjunto de vecinos de \(u\).

También puede estudiarse el promedio de \(k_{nn}(u)\) entre los vértices con grado \(k\):

\[ k_{nn}(k) = \frac{1}{\left|\{u \in V : k_u = k\}\right|} \sum_{\substack{u \in V \\ k_u = k}} k_{nn}(u). \]

Una tendencia creciente de \(k_{nn}(k)\) es compatible con mezcla asortativa por grado, mientras que una tendencia decreciente es compatible con mezcla desasortativa.

En igraph estas cantidades se obtienen con knn().

Ejemplo: Red de amistad

Asortatividad por grado

La definición de esta sección es para redes no dirigidas, así que ignoramos la dirección y los pesos, uniendo las amistades recíprocas en una sola arista. La versión dirigida se estudia en la sección Redes dirigidas y los pesos en Redes ponderadas.

# versión no dirigida: une amistades recíprocas
uk.und <- as_undirected(UKfaculty, mode = "collapse", edge.attr.comb = list(weight = "sum"))

# asortatividad por grado
(r.degree.uk.und <- assortativity_degree(uk.und, directed = FALSE))

## [1] -0.002440976

\(r_k \approx 0\) indica que la red de amistad es neutra por grado: a diferencia de la escuela, el número de amigos no parece determinar con quién se conecta cada miembro.

Grado medio de los vecinos

# grado medio de los vecinos, ignorando pesos
uk.knn <- knn(uk.und, weights = NA)
round(uk.knn$knn, 2)

##  [1] 14.67 19.75 10.57 11.08 16.54 17.92 19.91 22.50 17.25 18.83 18.00 19.69
## [13] 21.00 17.71 18.91 19.29 13.42 22.37 21.88 16.06 19.36 19.60 22.50 20.14
## [25] 20.45 21.38 20.16 20.75 17.02 13.83 19.14 23.89 19.76 23.33 21.65  8.57
## [37] 18.24 15.00 20.64 19.93 22.00 19.53 18.65 14.00 10.11 20.53 16.00 18.80
## [49] 20.94 23.69 20.44 19.41 10.56 19.04 20.67 11.83 22.81 18.32 11.78 22.25
## [61] 13.42 16.81 20.67 23.11 23.38 18.20 24.60 18.00 19.52 25.31 22.88 19.08
## [73] 11.50 13.62 15.56 22.00 18.67 11.80 23.93 20.50 13.43

# grado promedio de los vecinos para cada valor de grado
uk.knnk <- uk.knn$knnk

# promedio por grado
k  <- seq_along(uk.knnk)
ok <- is.finite(uk.knnk)

plot(
  k[ok], uk.knnk[ok],
  type = "b",
  xlab = "Grado",
  ylab = "Grado medio de los vecinos"
)

\(k_{nn}(k)\) oscila entre 14 y 22 sin una tendencia creciente ni decreciente clara. Esto es consistente con \(r_k \approx 0\): los miembros con muchos amigos no se conectan preferentemente con otros muy conectados ni con poco conectados.

Ejemplo: Red de aeropuertos

Presentación de la red

Considere la red de vuelos de pasajeros entre aeropuertos de Estados Unidos en diciembre de 2010, compilada a partir de datos de la Research and Innovative Technology Administration (RITA) del Departamento de Transporte de Estados Unidos.

Los vértices representan aeropuertos. Cada arista dirigida indica vuelos de una aerolínea y tipo de avión entre dos aeropuertos, con atributos como el número de pasajeros, asientos y distancia. Por eso la red original tiene aristas múltiples.

Los datos están disponibles en el paquete igraphdata.

# datos
data("USairports", package = "igraphdata")
USairports <- upgrade_graph(USairports)

# propiedades básicas de la red original
vcount(USairports)

## [1] 755

ecount(USairports)

## [1] 23473

is_directed(USairports)

## [1] TRUE

is_simple(USairports)

## [1] FALSE

Exclusión de Alaska, Hawái y los territorios

La red incluye, además de los 48 estados continentales, aeropuertos de Alaska, Hawái y de territorios como Puerto Rico, las Islas Vírgenes y Guam. Estos aeropuertos están geográficamente separados del resto y forman, en la práctica, sistemas de transporte aparte: Alaska, en particular, tiene muchos aeropuertos pequeños conectados casi solo entre sí.

# estado o territorio de cada aeropuerto
st <- sub(".*,\\s*", "", V(USairports)$City)

# zona: Alaska, Hawái, territorios (PR, VI, TT) o estados continentales (con DC)
zona <- ifelse(st == "AK", "Alaska",
        ifelse(st == "HI", "Hawái",
        ifelse(st %in% c(state.abb, "DC"), "Continental", "Territorios")))

# aeropuertos por zona
table(zona)

## zona
##      Alaska Continental       Hawái Territorios 
##         242         485          11          17

# rutas (sin dirección ni repeticiones) dentro de las zonas excluidas y hacia el continente
fuera  <- zona != "Continental"
g.todo <- simplify(as_undirected(USairports, mode = "collapse"))
ed.z   <- ends(g.todo, E(g.todo), names = FALSE)
f.1    <- fuera[ed.z[, 1]]
f.2    <- fuera[ed.z[, 2]]

c(
  rutas.dentro.excluidas   = sum(f.1 & f.2),
  rutas.hacia.continente   = sum(xor(f.1, f.2))
)

## rutas.dentro.excluidas rutas.hacia.continente 
##                    800                    116

Las zonas excluidas suman 270 de los 755 aeropuertos, con 800 rutas internas y solo 116 hacia el continente. Mantenerlas mezclaría sistemas de transporte con lógicas distintas en un mismo coeficiente. Por ejemplo, la asortatividad por grado pasaría de \(-0.23\) a \(-0.07\), porque los muchos aeropuertos pequeños de Alaska, conectados entre sí, ocultarían el patrón del resto del país. Por eso, de aquí en adelante la red de aeropuertos incluye solo los 48 estados continentales y el Distrito de Columbia.

# red solo con los estados continentales
USairports <- delete_vertices(USairports, fuera)

vcount(USairports)

## [1] 485

ecount(USairports)

## [1] 19512

En la mayoría de los análisis interesa únicamente la existencia de conexiones entre aeropuertos. Por eso se ignora la dirección, se unen los vuelos de ida y vuelta, y se eliminan bucles y aristas múltiples. La versión dirigida se estudia en la sección Redes dirigidas.

# red no dirigida y simple
g <- as_undirected(USairports, mode = "collapse")
g <- simplify(g)

# propiedades básicas de la red simplificada
vcount(g)

## [1] 485

ecount(g)

## [1] 3707

is_simple(g)

## [1] TRUE

Como cada aeropuerto tiene su latitud y longitud en el atributo Position, podemos dibujar la red sobre su ubicación geográfica. Position está en grados-minutos-segundos, por lo que primero lo convertimos a grados decimales.

dms_to_dec <- function(s) {
  signo <- ifelse(substr(s, 1, 1) %in% c("S", "W"), -1, 1)
  d <- substr(s, 2, nchar(s))
  n <- nchar(d)
  signo * (as.numeric(substr(d, 1, n - 4)) +
           as.numeric(substr(d, n - 3, n - 2)) / 60 +
           as.numeric(substr(d, n - 1, n)) / 3600)
}

pos <- strsplit(V(g)$Position, " ")
V(g)$Lat <- dms_to_dec(sapply(pos, `[`, 1))
V(g)$Lon <- dms_to_dec(sapply(pos, `[`, 2))

# visualización con longitud y latitud como coordenadas
plot(
  g,
  layout = cbind(V(g)$Lon, V(g)$Lat),
  vertex.label = NA,
  vertex.size = sqrt(degree(g)) / 2,
  edge.color = adjustcolor("gray", 0.2),
  asp = 0.6
)

# visualización de los aeropuertos con grado al menos 20
deg <- degree(g)
top <- induced_subgraph(g, which(deg >= 20))
top <- delete_vertices(top, which(degree(top) == 0))

set.seed(123)
plot(
  top,
  layout = layout_with_fr,
  vertex.size = 2 + sqrt(degree(top)),
  vertex.color = "steelblue",
  vertex.frame.color = "black",
  vertex.label = NA,
  edge.color = "gray70"
)

Asortatividad por grado

# asortatividad por grado
(r.degree.air <- assortativity_degree(g, directed = FALSE))

## [1] -0.2339831

\(r_k \approx -0.23\) indica una desasortatividad moderada por grado: los aeropuertos con muchas rutas tienden a conectarse con aeropuertos con pocas rutas. Esto es coherente con la organización del transporte aéreo en Estados Unidos: los grandes aeropuertos, como los de Nueva York o Atlanta, reciben vuelos de muchos aeropuertos pequeños de todo el país, mientras que los aeropuertos pequeños rara vez se conectan entre sí.

Grado medio de los vecinos

# grado medio de los vecinos
air.knn <- knn(g)
head(sort(air.knn$knn, decreasing = TRUE), 10)

## AHN MCN VEL MEI VLD CMX MKG PAH ALO ATY 
## 162 162 162 162 162 149 149 149 142 142

# grado promedio de los vecinos para cada valor de grado
air.knnk <- air.knn$knnk

# promedio por grado, en escala logarítmica
k  <- seq_along(air.knnk)
ok <- is.finite(air.knnk)

plot(
  k[ok], air.knnk[ok],
  type = "b",
  log = "xy",
  xlab = "Grado",
  ylab = "Grado medio de los vecinos"
)

Como los grados van de 1 a 162, el gráfico usa escala logarítmica en ambos ejes. \(k_{nn}(k)\) tiene dos tramos:

• Para grados bajos (\(k \lesssim 10\)) la tendencia es irregular y levemente creciente.
• A partir de \(k \approx 10\)–\(20\) la tendencia es claramente decreciente, compatible con mezcla desasortativa: cuanto más grande es el aeropuerto, menor es el grado promedio de sus vecinos.

Predomina el tramo decreciente, lo que es consistente con \(r_k \approx -0.23\). El gráfico muestra además que la desasortatividad se concentra en los aeropuertos medianos y grandes, algo que el valor agregado de \(r_k\) no indica.

Matriz de mezcla por grado

La matriz de mezcla no es exclusiva de las características categóricas. Como el grado toma valores enteros, cada valor de grado puede ser una fila y una columna: \(e_{jk}\) es la fracción de aristas que unen un vértice de grado \(j\) con uno de grado \(k\) (Newman, 2003). Usamos la misma función mixing_matrix(), con los grados como niveles ordenados de menor a mayor. Como g es no dirigida, cada arista aporta sus dos orientaciones y la matriz resulta simétrica.

# grado como factor, con los niveles ordenados numéricamente
k.fac <- factor(deg, levels = sort(unique(deg[deg > 0])))

# matriz de mezcla grado por grado
E.full <- mixing_matrix(g, k.fac)

# dimensión, celdas vacías y valor máximo
dim(E.full)

## [1] 76 76

mean(E.full == 0)

## [1] 0.3237535

max(E.full)

## [1] 0.002158079

# esquina de la matriz: grados 1 a 6
round(E.full[1:6, 1:6], 4)

##    y
## x        1      2      3      4      5      6
##   1 0.0003 0.0004 0.0007 0.0004 0.0001 0.0001
##   2 0.0004 0.0022 0.0011 0.0004 0.0005 0.0004
##   3 0.0007 0.0011 0.0008 0.0009 0.0007 0.0005
##   4 0.0004 0.0004 0.0009 0.0011 0.0009 0.0009
##   5 0.0001 0.0005 0.0007 0.0009 0.0019 0.0013
##   6 0.0001 0.0004 0.0005 0.0009 0.0013 0.0000

La matriz tiene \(76 \times 76 = 5776\) celdas. Cerca de un tercio están vacías y ninguna supera el \(0.22\%\) de las aristas, así que como tabla es imposible de leer.

# mapa de calor de la matriz de mezcla grado por grado
heatmap(
  E.full,
  Rowv = NA,
  Colv = NA,
  scale = "none",
  xlab = "Grado del segundo extremo",
  ylab = "Grado del primer extremo"
)

Matriz de mezcla por clase de grado

Para resumir la matriz anterior, agrupamos los grados en cinco clases y volvemos a usar mixing_matrix().

k.class <- cut(deg,
               breaks = c(-Inf, 2, 5, 20, 50, Inf),
               labels = c("<=2", "3-5", "6-20", "21-50", ">50"))
table(k.class)

## k.class
##   <=2   3-5  6-20 21-50   >50 
##   157   100   130    59    39

E.deg <- mixing_matrix(g, k.class)
round(E.deg, 3)

##        y
## x         <=2   3-5  6-20 21-50   >50
##   <=2   0.003 0.003 0.003 0.005 0.017
##   3-5   0.003 0.009 0.010 0.009 0.020
##   6-20  0.003 0.010 0.029 0.040 0.107
##   21-50 0.005 0.009 0.040 0.069 0.139
##   >50   0.017 0.020 0.107 0.139 0.185

# mapa de calor de la matriz de mezcla
heatmap(
  E.deg,
  Rowv = NA,
  Colv = NA,
  scale = "none",
  xlab = "Clase de grado del segundo extremo",
  ylab = "Clase de grado del primer extremo"
)

La mayor parte de las conexiones involucra aeropuertos de grado alto: la celda más grande es la de >50 con >50 (18.5%), seguida de 21-50 con >50 (13.9%) y 6-20 con >50 (10.7%). En cambio, los aeropuertos de grado bajo (<=2) casi no se conectan entre sí (0.3%), sino sobre todo con aeropuertos de más de 50 rutas.

Comparación de características

Una misma red puede ser asortativa respecto a una característica y desasortativa respecto a otra. Calcular el coeficiente para todas las características disponibles, con la medida adecuada a cada tipo (nominal o numérica), permite identificar cuáles están más asociadas con el patrón de conexión.

Ejemplo: Red de aeropuertos

USairports trae tres atributos de vértice: name (código IATA), City (“Ciudad, ST”) y Position (coordenadas). A partir de ellos y de la estructura de la red tenemos:

• Categóricas: name, City y el estado, extraído de City.
• Numérica: el grado.

# estado de cada aeropuerto
V(g)$State <- sub(".*,\\s*", "", V(g)$City)

as_int <- function(x) as.integer(factor(x))

tabla.asort <- data.frame(
  Caracteristica = c("name (código)", "City", "Estado", "Grado"),
  Tipo   = c(rep("categórica", 3), "numérica"),
  Niveles = c(length(unique(V(g)$name)),
              length(unique(V(g)$City)),
              length(unique(V(g)$State)),
              NA),
  r = c(assortativity_nominal(g, as_int(V(g)$name)),
        assortativity_nominal(g, as_int(V(g)$City)),
        assortativity_nominal(g, as_int(V(g)$State)),
        r.degree.air)
)

tabla.asort <- tabla.asort[order(-tabla.asort$r), ]
knitr::kable(tabla.asort, digits = 3, row.names = FALSE,
             col.names = c("Característica", "Tipo", "Niveles", "$r_a$"))

Característica	Tipo	Niveles	\(r_a\)
Estado	categórica	49	0.093
name (código)	categórica	485	-0.008
City	categórica	456	-0.009
Grado	numérica	NA	-0.234

Lectura de la tabla:

• Estado: es la única característica asortativa, aunque débil (\(\approx 0.09\)): hay algo más de rutas dentro de un mismo estado de lo esperado, pero la mayoría de las rutas cruzan fronteras estatales.
• Grado: desasortativo (\(\approx -0.23\)); los hubs tienden a conectar con aeropuertos menores.
• name y City: son prácticamente identificadores únicos (cada vértice es su propia categoría), por lo que \(p_{obs} \approx 0\) y \(r_a \approx 0\) por construcción; no aportan información sobre la mezcla.

Redes dirigidas

En una red dirigida, los extremos de una arista cumplen funciones diferentes.

En una arista \((u, v)\), \(u\) es el origen y \(v\) el destino. Por tanto, la mezcla puede depender de características distintas en ambos extremos.

Para atributos numéricos, assortativity() permite especificar mediante values los valores asociados al extremo de salida y mediante values.in los valores asociados al extremo de entrada.

Esto permite estudiar, por ejemplo, si los actores con valores altos en una característica tienden a dirigir conexiones hacia actores con valores altos en otra.

En particular, con el grado hay cuatro asortatividades posibles (Foster et al., 2010), según qué grado se use en cada extremo de la arista \((u, v)\):

Variante	Origen \(u\)	Destino \(v\)	Pregunta
salida–entrada	\(k_u^{out}\)	\(k_v^{in}\)	¿quién declara mucho elige a quien recibe mucho?
salida–salida	\(k_u^{out}\)	\(k_v^{out}\)	¿quién declara mucho elige a quien también declara mucho?
entrada–entrada	\(k_u^{in}\)	\(k_v^{in}\)	¿quién es muy elegido elige a quien también es muy elegido?
entrada–salida	\(k_u^{in}\)	\(k_v^{out}\)	¿quién es muy elegido elige a quien declara mucho?

assortativity_degree(directed = TRUE) calcula solo la primera.

Ejemplo: Red de amistad

# grados de salida y de entrada
k.out <- degree(UKfaculty, mode = "out")
k.in  <- degree(UKfaculty, mode = "in")

# las cuatro asortatividades por grado
r.dir <- c(
  "salida-entrada"  = assortativity(UKfaculty, values = k.out, values.in = k.in,  directed = TRUE),
  "salida-salida"   = assortativity(UKfaculty, values = k.out, values.in = k.out, directed = TRUE),
  "entrada-entrada" = assortativity(UKfaculty, values = k.in,  values.in = k.in,  directed = TRUE),
  "entrada-salida"  = assortativity(UKfaculty, values = k.in,  values.in = k.out, directed = TRUE)
)

round(r.dir, 3)

##  salida-entrada   salida-salida entrada-entrada  entrada-salida 
##           0.038           0.061           0.122           0.090

assortativity_degree(directed = TRUE) coincide con la variante salida–entrada:

# asortatividad por grado dirigida
(r.degree.uk <- assortativity_degree(UKfaculty, directed = TRUE))

## [1] 0.03805201

Las cuatro son positivas pero débiles. La más alta es entrada–entrada (\(\approx 0.12\)): los miembros más elegidos como amigos tienden levemente a elegir a otros también muy elegidos. La variante salida–entrada, que es la única que calcula assortativity_degree(), es la más baja (\(\approx 0.04\)), por lo que reportar solo esa subestima la mezcla por grado de la red.

Matriz de mezcla por grado dirigida

En una red dirigida, la matriz de mezcla por grado compara el grado de salida del origen (filas) con el grado de entrada del destino (columnas), que es la variante que usa assortativity_degree() (Newman, 2003). La matriz no tiene por qué ser simétrica.

# niveles comunes: todos los valores de grado de salida y de entrada
lev.k <- sort(unique(c(k.out, k.in)))

# matriz de mezcla: salida del origen vs. entrada del destino
E.full.uk <- mixing_matrix(
  UKfaculty,
  types    = factor(k.out, levels = lev.k),
  types.in = factor(k.in,  levels = lev.k)
)

# dimensión, celdas vacías y valor máximo
dim(E.full.uk)

## [1] 30 30

mean(E.full.uk == 0)

## [1] 0.5955556

max(E.full.uk)

## [1] 0.01468788

# mapa de calor de la matriz de mezcla dirigida grado por grado
heatmap(
  E.full.uk,
  Rowv = NA,
  Colv = NA,
  scale = "none",
  xlab = "Grado de entrada del destino",
  ylab = "Grado de salida del origen"
)

La matriz es de \(30 \times 30\) y el \(60\%\) de sus celdas está vacío. Además, los grados de salida llegan hasta 41 y los de entrada solo hasta 24. Agrupamos los grados en cuatro clases para leerla mejor.

# clases de grado
cortes <- c(-Inf, 5, 10, 15, Inf)
clases <- c("<=5", "6-10", "11-15", ">15")

E.deg.uk <- mixing_matrix(
  UKfaculty,
  types    = cut(k.out, cortes, clases),
  types.in = cut(k.in,  cortes, clases)
)
round(E.deg.uk, 3)

##        y
## x         <=5  6-10 11-15   >15
##   <=5   0.009 0.060 0.007 0.020
##   6-10  0.020 0.095 0.037 0.060
##   11-15 0.009 0.075 0.073 0.106
##   >15   0.021 0.154 0.124 0.131

# marginales: fracción de aristas que sale de cada clase y que llega a cada clase
round(rowSums(E.deg.uk), 3)

##   <=5  6-10 11-15   >15 
## 0.095 0.212 0.263 0.430

round(colSums(E.deg.uk), 3)

##   <=5  6-10 11-15   >15 
## 0.058 0.384 0.241 0.317

# mapa de calor de la matriz de mezcla dirigida
heatmap(
  E.deg.uk,
  Rowv = NA,
  Colv = NA,
  scale = "none",
  xlab = "Clase de grado de entrada del destino",
  ylab = "Clase de grado de salida del origen"
)

La matriz no es simétrica. Por ejemplo, el \(15.4\%\) de las aristas va de miembros que declaran muchos amigos (salida >15) a miembros con entrada 6-10, pero solo el \(6.0\%\) va en el sentido de las clases opuestas (salida 6-10 a entrada >15). Las marginales también difieren: los miembros con salida >15 originan el \(43\%\) de las aristas, mientras que los de entrada 6-10 reciben el \(38\%\). Es decir, unos pocos miembros declaran muchas amistades, pero las amistades recibidas están más repartidas.

Grado medio de los vecinos dirigido

En una red dirigida, \(k_{nn}\) también se desdobla: se puede promediar el grado de entrada o de salida de los vértices a los que \(u\) apunta, o de los que apuntan a \(u\). Calculamos las dos combinaciones que corresponden a las variantes salida–entrada (la más baja) y entrada–entrada (la más alta).

# grado de entrada promedio de los vértices a los que u apunta, por grado de salida de u
knn.out.in <- knn(UKfaculty, mode = "out", neighbor.degree.mode = "in", weights = NA)$knnk

# grado de entrada promedio de los vértices que apuntan a u, por grado de entrada de u
knn.in.in  <- knn(UKfaculty, mode = "in",  neighbor.degree.mode = "in", weights = NA)$knnk

par(mfrow = c(1, 2))

ok <- is.finite(knn.out.in)
plot(
  which(ok), knn.out.in[ok],
  type = "b",
  xlab = "Grado de salida",
  ylab = "Grado de entrada medio de los vecinos",
  main = "Salida - entrada"
)

ok <- is.finite(knn.in.in)
plot(
  which(ok), knn.in.in[ok],
  type = "b",
  xlab = "Grado de entrada",
  ylab = "Grado de entrada medio de los vecinos",
  main = "Entrada - entrada"
)

par(mfrow = c(1, 1))

Ambas curvas crecen para grados bajos e intermedios y luego se estabilizan o bajan levemente: en salida–entrada suben hasta un grado de salida de \(\approx 10\), y en entrada–entrada hasta un grado de entrada de \(\approx 15\). El tramo creciente es más largo y claro en entrada–entrada, que es la variante con mayor coeficiente (\(\approx 0.12\)): los miembros que reciben muchas amistades son elegidos por otros que también reciben muchas. Esto contrasta con la versión no dirigida de la sección Asortatividad por grado, donde \(k_{nn}(k)\) no mostraba tendencia: al ignorar la dirección, los patrones de salida y de entrada se mezclan.

Ejemplo: Red de aeropuertos

Hasta ahora usamos la red de aeropuertos como no dirigida. Sin embargo, la red original sí es dirigida: cada arista va del aeropuerto de origen al de destino del vuelo. Conservamos la dirección y unimos solo las aristas múltiples (distintas aerolíneas en la misma ruta y sentido).

# red dirigida y simple
g.dir <- simplify(USairports)

# propiedades básicas
vcount(g.dir)

## [1] 485

ecount(g.dir)

## [1] 6640

is_directed(g.dir)

## [1] TRUE

# grados de salida y de entrada
k.out.air <- degree(g.dir, mode = "out")
k.in.air  <- degree(g.dir, mode = "in")

# las cuatro asortatividades por grado
r.dir.air <- c(
  "salida-entrada"  = assortativity(g.dir, values = k.out.air, values.in = k.in.air,  directed = TRUE),
  "salida-salida"   = assortativity(g.dir, values = k.out.air, values.in = k.out.air, directed = TRUE),
  "entrada-entrada" = assortativity(g.dir, values = k.in.air,  values.in = k.in.air,  directed = TRUE),
  "entrada-salida"  = assortativity(g.dir, values = k.in.air,  values.in = k.out.air, directed = TRUE)
)

round(r.dir.air, 3)

##  salida-entrada   salida-salida entrada-entrada  entrada-salida 
##          -0.276          -0.275          -0.273          -0.272

A diferencia de la red de amistad, las cuatro variantes son prácticamente iguales (\(\approx -0.27\)). La razón está en la reciprocidad (proporción de aristas \((u, v)\) para las que también existe \((v, u)\)) y en la relación entre los grados de entrada y salida de cada vértice:

# reciprocidad y correlación entre grado de entrada y de salida
data.frame(
  Red = c("Amistad", "Aeropuertos"),
  Reciprocidad = c(reciprocity(UKfaculty), reciprocity(g.dir)),
  Cor.entrada.salida = c(
    cor(k.in, k.out),
    cor(k.in.air, k.out.air)
  )
)

##           Red Reciprocidad Cor.entrada.salida
## 1     Amistad    0.5875153          0.4896634
## 2 Aeropuertos    0.8834337          0.9965288

• En los aeropuertos, casi todas las rutas tienen vuelo de regreso (reciprocidad \(\approx 0.88\)) y cada aeropuerto tiene prácticamente el mismo número de destinos que de orígenes (correlación \(\approx 0.997\)). Entonces \(k^{in} \approx k^{out}\), y da igual qué grado se use en cada extremo.
• En la red de amistad, solo el \(\approx 59\%\) de las amistades declaradas son recíprocas y el número de amigos declarados se relaciona poco con el número de veces que se es elegido (correlación \(\approx 0.49\)). Por eso las cuatro variantes difieren y vale la pena calcularlas.

Así, la dirección aporta información sobre la mezcla cuando la red es poco recíproca. En redes casi recíprocas, como la de aeropuertos, la versión no dirigida resume bien el patrón.

Redes ponderadas

En una red ponderada, el grado y la fuerza de un vértice \(u\) se definen, respectivamente, como

\[ k_u = |N(u)|, \qquad s_u = \sum_{v \in N(u)} w_{uv}, \]

donde \(w_{uv}\) es el peso de la arista entre \(u\) y \(v\).

Los pesos pueden incorporarse de dos formas (Barrat et al., 2004):

• Como característica nodal, usando la fuerza \(s_u\) de cada vértice:

  \[ r_s = \operatorname{Cor}(s_u, s_v). \]

• Como peso de las conexiones, de modo que cada arista contribuye según \(w_{uv}\):

  \[ r_w = \frac{\sum_{(u,v)} w_{uv} (x_u - \bar{x}_w)(x_v - \bar{y}_w)} {\sqrt{\sum_{(u,v)} w_{uv} (x_u - \bar{x}_w)^2 \sum_{(u,v)} w_{uv} (x_v - \bar{y}_w)^2}}, \]

  donde

  \[ \bar{x}_w = \frac{\sum_{(u,v)} w_{uv} x_u}{\sum_{(u,v)} w_{uv}}, \qquad \bar{y}_w = \frac{\sum_{(u,v)} w_{uv} x_v}{\sum_{(u,v)} w_{uv}}. \]

La primera opción incorpora los pesos en los atributos nodales; la segunda pondera directamente las conexiones.

assortativity() no admite pesos de arista, así que \(r_w\) se calcula directamente a partir de la fórmula.

# asortatividad ponderada: correlación de Pearson ponderada por w
r_weighted <- function(x.from, x.to, w) {
  xbar <- sum(w * x.from) / sum(w)
  ybar <- sum(w * x.to)   / sum(w)

  sum(w * (x.from - xbar) * (x.to - ybar)) /
    sqrt(sum(w * (x.from - xbar)^2) * sum(w * (x.to - ybar)^2))
}

Con todos los pesos iguales a 1, \(r_w\) coincide con la asortatividad sin pesos, lo que sirve para comprobar la función.

Ejemplo: Red de amistad

Fuerza como característica nodal

El peso de cada arista es la intensidad de la amistad. Como la red es dirigida, se compara la fuerza de salida del origen con la fuerza de entrada del destino.

# fuerza de salida y de entrada
s.out <- strength(UKfaculty, mode = "out")
s.in  <- strength(UKfaculty, mode = "in")

(r.strength.uk <- assortativity(UKfaculty, values = s.out, values.in = s.in, directed = TRUE))

## [1] 0.04555874

\(r_s \approx 0.05\): la intensidad total de las amistades de cada miembro no se relaciona con la de sus amigos.

Pesos en las conexiones

Ahora el peso no se usa como característica, sino para ponderar cada arista en la correlación del grado (salida del origen frente a entrada del destino).

# extremos de cada arista y pesos
ed <- ends(UKfaculty, E(UKfaculty), names = FALSE)
w  <- E(UKfaculty)$weight

# sin pesos y con pesos
rw.uk <- r_weighted(k.out[ed[, 1]], k.in[ed[, 2]], w)
c(
  r.k = r_weighted(k.out[ed[, 1]], k.in[ed[, 2]], rep(1, length(w))),
  r.w = rw.uk
)

##        r.k        r.w 
## 0.03805201 0.14051261

Sin pesos se recupera \(r_k \approx 0.04\). Al ponderar por intensidad, \(r_w \approx 0.14\): las amistades más intensas se dan con más frecuencia entre miembros de grado similar que las amistades débiles.

Ejemplo: Red de aeropuertos

El peso de cada ruta es el número de pasajeros. Para conservarlo, volvemos a construir la red no dirigida sumando los pasajeros de las aristas que se unen, ya que simplify() por defecto descarta los atributos de arista.

# red no dirigida conservando los pasajeros
g.w <- as_undirected(USairports, mode = "collapse",
                     edge.attr.comb = list(Passengers = "sum", "ignore"))
g.w <- simplify(g.w, edge.attr.comb = list(Passengers = "sum", "ignore"))

Fuerza como característica nodal

# fuerza: pasajeros totales de cada aeropuerto
s.air <- strength(g.w, weights = E(g.w)$Passengers)

(r.strength.air <- assortativity(g.w, values = s.air, directed = FALSE))

## [1] -0.1926203

\(r_s \approx -0.19\), algo menor en magnitud que por grado: los aeropuertos con mucho tráfico tienden a conectarse con aeropuertos de poco tráfico.

Pesos en las conexiones

Como la red es no dirigida, cada arista se considera en ambas orientaciones.

# grado, extremos y pesos en ambas orientaciones
k.air  <- degree(g.w)
ed     <- ends(g.w, E(g.w), names = FALSE)
k.from <- c(k.air[ed[, 1]], k.air[ed[, 2]])
k.to   <- c(k.air[ed[, 2]], k.air[ed[, 1]])
w      <- rep(E(g.w)$Passengers, 2)

# sin pesos y con pesos
rw.air <- r_weighted(k.from, k.to, w)
c(
  r.k = r_weighted(k.from, k.to, rep(1, length(w))),
  r.w = rw.air
)

##        r.k        r.w 
## -0.2339831 -0.2353459

Sin pesos se recupera \(r_k \approx -0.23\). Al ponderar por pasajeros, \(r_w \approx -0.24\): el coeficiente prácticamente no cambia. Las rutas con más pasajeros siguen el mismo patrón de mezcla que el conjunto de rutas, a diferencia de la red de amistad, donde ponderar cambió notablemente el coeficiente.

Modelo nulo

Un valor de asortatividad distinto de cero no implica necesariamente un patrón no aleatorio. Para evaluarlo, se compara con un modelo nulo.

Permutación de etiquetas

Para atributos categóricos, una opción simple es permutar las etiquetas entre los vértices, manteniendo fijos la red y el tamaño de cada categoría.

En la red de amistad, se permutan las etiquetas de escuela \(B\) veces para generar la distribución nula de \(r_a\). El valor \(p\) bilateral se calcula como

\[ p = \frac{1 + \sum_{b=1}^{B} \mathbb{I}\left( \left| r_a^{(b)} \right| \geq \left| r_a^{\text{obs}} \right| \right)}{B + 1}. \]

Así, \(p\) representa la proporción de permutaciones con una asortatividad al menos tan extrema como la observada.

# distribución nula por permutación de etiquetas
B <- 999
r.null <- numeric(B)

set.seed(123)
for (b in 1:B) {
  r.null[b] <- assortativity_nominal(
    UKfaculty,
    types = sample(g.types),
    directed = TRUE
  )
}

# valor p de permutación bilateral
p.value.group <- (1 + sum(abs(r.null) >= abs(r.group))) / (B + 1)

p.value.group

## [1] 0.001

\(p = 0.001\), el mínimo posible con \(B = 999\), indica que una asortatividad por escuela tan extrema como la observada sería muy poco probable bajo el modelo nulo. Hay fuerte evidencia de mezcla no aleatoria.

# rango del eje x
xlim <- range(c(r.null, r.group))
xlim <- xlim + c(-0.05, 0.05) * diff(xlim)

# distribución de referencia
hist(
  r.null,
  breaks = 25,
  probability = TRUE,
  xlim = xlim,
  col = "gray90",
  border = "gray60",
  xlab = "Coeficiente de asortatividad",
  ylab = "Densidad",
  main = ""
)

# asortatividad observada
abline(v = r.group, lwd = 2, lty = 2)

# etiqueta
text(
  r.group,
  par("usr")[4] * 0.9,
  labels = expression(r[a]^obs),
  pos = 2
)

Modelo nulo que preserva los grados

Si el interés está en la asortatividad por grado, una referencia natural consiste en aleatorizar las aristas preservando la secuencia de grados (en redes dirigidas, los grados de entrada y salida).

Red de amistad

# asortatividad observada por grado
r.degree.uk

## [1] 0.03805201

# distribución nula preservando los grados de entrada y salida
B <- 999
r.null.uk <- numeric(B)

set.seed(123)
for (b in 1:B) {
  # aleatorizar aristas conservando la secuencia de grados
  g.null <- rewire(UKfaculty, with = keeping_degseq(niter = 10 * ecount(UKfaculty)))

  # asortatividad por grado bajo el modelo nulo
  r.null.uk[b] <- assortativity_degree(g.null, directed = TRUE)
}

# valor p bilateral
p.value <- (1 + sum(abs(r.null.uk) >= abs(r.degree.uk))) / (B + 1)

# resultados
p.value

## [1] 0.998

\(r_k \approx 0.04\) indica una asortatividad por grado prácticamente nula. Como \(p = 0.998\), casi todas las redes generadas bajo el modelo nulo presentan una asortatividad por grado de magnitud mayor que la observada. Por tanto, no hay evidencia de una asortatividad por grado más extrema que la esperada por la secuencia de grados.

# rango del eje x
xlim <- range(c(r.null.uk, r.degree.uk))
xlim <- xlim + c(-0.05, 0.05) * diff(xlim)

# distribución nula
hist(
  r.null.uk,
  breaks = 25,
  probability = TRUE,
  xlim = xlim,
  col = "gray90",
  border = "gray60",
  xlab = "Asortatividad por grado",
  ylab = "Densidad",
  main = ""
)

# asortatividad observada
abline(v = r.degree.uk, lwd = 2, lty = 2)

# etiqueta
text(
  r.degree.uk,
  par("usr")[4] * 0.9,
  labels = expression(r[k]^obs),
  pos = 2
)

Red de aeropuertos

# asortatividad observada por grado
r.degree.air

## [1] -0.2339831

# distribución nula preservando los grados
B <- 999
r.null.air <- numeric(B)

set.seed(123)
for (b in 1:B) {
  # aleatorizar aristas conservando la secuencia de grados
  g.null <- rewire(g, with = keeping_degseq(niter = 10 * ecount(g)))

  # asortatividad por grado bajo el modelo nulo
  r.null.air[b] <- assortativity_degree(g.null, directed = FALSE)
}

# valor p bilateral
p.value <- (1 + sum(abs(r.null.air) >= abs(r.degree.air))) / (B + 1)

# resultados
p.value

## [1] 1

\(r_k \approx -0.23\) indica una desasortatividad moderada por grado. Como \(p = 1\), todas las redes generadas bajo el modelo nulo presentan una desasortatividad por grado de magnitud mayor que la observada. Por tanto, no hay evidencia de una desasortatividad por grado más extrema que la esperada por la secuencia de grados.

# rango del eje x
xlim <- range(c(r.null.air, r.degree.air))
xlim <- xlim + c(-0.05, 0.05) * diff(xlim)

# distribución nula
hist(
  r.null.air,
  breaks = 25,
  probability = TRUE,
  xlim = xlim,
  col = "gray90",
  border = "gray60",
  xlab = "Asortatividad por grado",
  ylab = "Densidad",
  main = ""
)

# asortatividad observada
abline(v = r.degree.air, lwd = 2, lty = 2)

# etiqueta
text(
  r.degree.air,
  par("usr")[4] * 0.9,
  labels = expression(r[k]^obs),
  pos = 2
)

Asortatividad y modularidad

Existe una relación estrecha entre la asortatividad nominal y la modularidad. Si las categorías de los vértices definen una partición fija, la asortatividad nominal no normalizada (que solo usa el numerador de la expresión) coincide con la modularidad de dicha partición cuando se ignoran los pesos.

Ejemplo: Red de amistad

Las escuelas (Group) definen una partición fija de los miembros de la facultad. Como la red es dirigida, ambas medidas se calculan en su versión dirigida, y se ignoran los pesos.

# asortatividad nominal no normalizada
r.nominal.uk <- assortativity_nominal(
  UKfaculty,
  types = g.types,
  directed = TRUE,
  normalized = FALSE
)
r.nominal.uk

## [1] 0.4454336

# modularidad de la partición por escuela
Q.uk <- modularity(
  UKfaculty,
  membership = g.types,
  weights = NA,
  directed = TRUE
)
Q.uk

## [1] 0.4454336

Ambas valen \(\approx 0.445\), así que coinciden. La asortatividad evalúa una característica nodal previamente definida, mientras que la detección de comunidades busca una partición con alta estructura interna.

Ejemplo: Red de aeropuertos

Modularidad de la partición por estado

El estado de cada aeropuerto define una partición fija. Comprobamos que su modularidad coincide con la asortatividad nominal no normalizada.

# estado de cada aeropuerto
v.state <- as.integer(factor(sub(".*,\\s*", "", V(g)$City)))

# asortatividad nominal no normalizada
r.nominal.state <- assortativity_nominal(
  g,
  types = v.state,
  directed = FALSE,
  normalized = FALSE
)
r.nominal.state

## [1] 0.0897881

# modularidad de la partición por estado
Q.state <- modularity(g, membership = v.state)
Q.state

## [1] 0.0897881

Ambas valen \(\approx 0.09\).

Detección de comunidades

Buscamos ahora la partición con mayor modularidad usando el algoritmo de Louvain (Blondel et al., 2008). El resultado puede variar levemente entre ejecuciones, por eso se fija la semilla.

# comunidades por Louvain
set.seed(123)
cl.air <- cluster_louvain(g)

# número de comunidades y modularidad
length(cl.air)

## [1] 13

modularity(cl.air)

## [1] 0.2947641

# tamaño de las comunidades
sort(sizes(cl.air), decreasing = TRUE)

## Community sizes
##   1   2   5   8   4   6   9   3   7  11  12  10  13 
## 136 118  81  52  51  16  10   8   4   3   3   2   1

La partición encontrada tiene \(Q \approx 0.29\), más de tres veces la de la partición por estado: las rutas se organizan en grupos más cohesionados que los estados.

# estados más frecuentes en las comunidades más grandes
state.name.v <- sub(".*,\\s*", "", V(g)$City)
top.cl <- order(sizes(cl.air), decreasing = TRUE)[1:6]

for (c in top.cl) {
  tab <- sort(table(state.name.v[membership(cl.air) == c]), decreasing = TRUE)
  cat("Comunidad", c, "(", sizes(cl.air)[c], "aeropuertos):",
      paste(names(tab)[1:min(5, length(tab))], tab[1:min(5, length(tab))], collapse = ", "), "\n")
}

## Comunidad 1 ( 136 aeropuertos): NY 18, FL 14, PA 12, NC 8, MI 7 
## Comunidad 2 ( 118 aeropuertos): CA 31, TX 14, OR 9, WA 9, AZ 7 
## Comunidad 5 ( 81 aeropuertos): MI 12, MN 8, WI 8, FL 7, IA 7 
## Comunidad 8 ( 52 aeropuertos): AZ 8, MT 8, WY 8, NE 7, CO 5 
## Comunidad 4 ( 51 aeropuertos): TX 13, LA 7, AR 6, MS 5, GA 3 
## Comunidad 6 ( 16 aeropuertos): MO 7, IL 3, AL 1, AR 1, CO 1

# similitud entre comunidades y estados (información mutua normalizada)
compare(membership(cl.air), v.state, method = "nmi")

## [1] 0.4098743

Las comunidades son, en su mayoría, regiones geográficas.

Comunidades sobre el mapa

# comunidades sobre longitud y latitud
plot(
  g,
  layout = cbind(V(g)$Lon, V(g)$Lat),
  vertex.color = membership(cl.air),
  vertex.label = NA,
  vertex.size = sqrt(degree(g)) / 2,
  edge.color = adjustcolor("gray", 0.2),
  asp = 0.6
)

El mapa muestra que las comunidades encontradas solo a partir de las rutas, sin usar las coordenadas, corresponden en buena medida a regiones geográficas: los aeropuertos se conectan sobre todo con aeropuertos de su misma región.

Referencias

Barrat, A., Barthélemy, M., Pastor-Satorras, R., & Vespignani, A. (2004). The architecture of complex weighted networks. Proceedings of the National Academy of Sciences, 101(11), 3747–3752.

Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008, P10008.

Foster, J. G., Foster, D. V., Grassberger, P., & Paczuski, M. (2010). Edge direction and the structure of networks. Proceedings of the National Academy of Sciences, 107(24), 10815–10820.

Nepusz, T., Petróczi, A., Négyessy, L., & Bazsó, F. (2008). Fuzzy communities and the concept of bridgeness in complex networks. Physical Review E, 77, 016107.

Newman, M. E. J. (2002). Assortative mixing in networks. Physical Review Letters, 89, 208701.

Newman, M. E. J. (2003). Mixing patterns in networks. Physical Review E, 67, 026126.

Research and Innovative Technology Administration (RITA), U.S. Department of Transportation. Datos de vuelos de pasajeros, diciembre de 2010. Disponibles en el paquete igraphdata como USairports.