94.1. Vecinos que también son vecinos entre sí
C92 estudió cuántas conexiones tiene cada nodo. C93 mostró que esas conexiones pueden ensamblarse en caminos y componentes con propiedades globales muy distintas. Ahora aparece una estructura intermedia, la de cómo se conectan entre sí los vecinos de un nodo.
Supongamos que un nodo tiene tres vecinos:
Podemos preguntar si existen también las aristas
Si muchas de ellas están presentes, los vecinos de forman un grupo local densamente conectado.
Esta idea conduce al coeficiente de agrupamiento local.
En grafos no dirigidos simples, su unidad elemental es el triángulo.
El triángulo es el patrón mínimo en que tres nodos están conectados por pares y da la forma local de cierre más elemental. Si está conectado con y con , la arista cierra la terna.
C94 desarrollará esta noción y después la ampliará hacia patrones pequeños más generales, llamados motivos cuando se comparan contra una referencia apropiada.
94.2. Triángulo
En un grafo simple no dirigido, un triángulo es un conjunto de tres nodos
para el cual existen las tres aristas
En el grafo base de C91 aparecen dos:
y
La arista conecta ambos sectores, pero no participa en ninguno de esos triángulos.
El número total de triángulos es, por tanto,
Contar triángulos da una primera medida de cierre local, pero depende fuertemente del tamaño y densidad de la red.
Por eso suele normalizarse respecto del número de triángulos que podrían existir alrededor de cada nodo.
94.3. Triángulos alrededor de un nodo
Sea el número de triángulos que contienen al nodo .
En el grafo base,
Todos los nodos participan en un triángulo.
Sin embargo, eso no significa que todos tengan el mismo grado de agrupamiento.
Los nodos tienen grado dos.
Sus dos vecinos están conectados entre sí, por lo que todas las conexiones posibles entre vecinos existen.
Los nodos y tienen grado tres.
Solo un par entre sus tres vecinos está conectado.
Para normalizar el número de triángulos necesitamos contar cuántos pares de vecinos podrían existir.
94.4. Número de pares posibles entre vecinos
Si un nodo tiene grado
tiene
pares no ordenados de vecinos.
Cada uno de esos pares es una oportunidad para cerrar un triángulo con .
Si todos los pares están conectados, el vecindario de forma un clique.
Si ninguno lo está, no existe cierre triangular alrededor de .
El número
funciona como denominador natural para medir qué fracción de conexiones posibles entre vecinos aparece realmente.
94.5. Coeficiente de agrupamiento local
Para
definimos
Equivalentemente,
Por construcción,
Si todos los vecinos de están conectados entre sí.
Si ningún par de vecinos cierra un triángulo alrededor de .
La cantidad describe la densidad dentro del vecindario inmediato del nodo.
94.6. Agrupamiento local en el grafo base
Para ,
Entonces
Lo mismo ocurre para .
Para ,
Por tanto,
Análogamente,
El vector de agrupamiento es
Los nodos y conectan regiones localmente más cerradas con la arista puente , por lo que sus vecindarios contienen pares no conectados.
94.7. ¿Qué hacer cuando ?
Si un nodo tiene grado cero o uno,
La fórmula produce una división por cero.
Existen dos convenciones frecuentes.
Una trata como no definido porque no existe oportunidad de formar un triángulo.
Otra asigna
NetworkX utiliza esta segunda convención.
Las dos opciones tienen consecuencias para promedios de agrupamiento.
En una red con muchos nodos de grado cero o uno, incluirlos como cero puede reducir el promedio local respecto de una convención que los excluya.
Por tanto, la convención debe declararse cuando sea material para la comparación.
94.8. Promedio del agrupamiento local
Una medida global simple es
En el grafo base,
Entonces
Esta medida da el mismo peso a cada nodo.
Un nodo de grado dos y otro de grado veinte contribuyen cada uno con un único valor .
Existe otra medida global de cierre que pondera de manera diferente las oportunidades de formar triángulos.
94.9. Triples conectados
Consideremos un nodo central unido a dos vecinos distintos y .
La configuración es un triple conectado centrado en .
El número de triples posibles centrados en es
Sumando sobre todos los nodos,
En el grafo base,
Cada triángulo contiene tres triples cerrados, uno por cada elección del nodo central.
Como existen dos triángulos, triples están cerrados.
94.10. Transitividad global
La transitividad se define como
En el ejemplo,
El promedio local era
Los dos valores difieren. La diferencia aparece porque la transitividad pondera implícitamente a cada nodo por el número de pares de vecinos que tiene.
Los nodos de grado mayor generan más triples y, por tanto, tienen más influencia sobre la transitividad.
94.11. Promedio local y transitividad responden a preguntas distintas
El promedio
puede interpretarse como el agrupamiento del nodo promedio, bajo la convención elegida para grados pequeños.
La transitividad responde aproximadamente a qué fracción está cerrada entre todas las oportunidades de cierre triangular de la red.
La primera asigna peso uniforme a nodos y la segunda a triples centrados.
Cuando los grados son heterogéneos, ambas ponderaciones pueden producir valores bastante diferentes.
El paquete incluye un grafo compuesto por un clique unido a una cola lineal. Allí el promedio de los y la transitividad difieren claramente.
94.12. Triángulos mediante álgebra matricial
Sea la matriz de adyacencia de un grafo simple no dirigido.
C93 mostró que
cuenta paseos de longitud .
Entonces cuenta paseos cerrados de longitud tres que comienzan y terminan en .
Cada triángulo que contiene a produce dos recorridos:
e
Por tanto,
para grafos simples no dirigidos.
El paquete verifica esta identidad nodo por nodo.
94.13. Número total de triángulos mediante la traza
Sumando la identidad anterior,
Ahora bien, cada triángulo se cuenta una vez por cada uno de sus tres nodos:
Entonces
En el grafo base,
y por tanto
La relación muestra otra vez cómo una estructura combinatoria puede aparecer codificada en operaciones matriciales.
94.14. Mismo grado, agrupamiento opuesto
Retomemos dos redes de C92–C93.
Primero, el ciclo
Todos los nodos tienen grado dos.
Ningún par de vecinos de un nodo está conectado entre sí.
Por tanto, para todos los nodos.
Ahora tomemos dos triángulos desconectados.
Cada nodo también tiene grado dos.
Sus dos vecinos, en cambio, sí están conectados.
Entonces para todos.
La secuencia de grados es idéntica y el agrupamiento es exactamente opuesto.
94.15. La distribución de grado no determina triángulos
El ejemplo anterior demuestra algo más fuerte que una diferencia de promedios.
Las dos redes comparten exactamente:
Por tanto, comparten toda la distribución de grado.
Sin embargo, una contiene cero triángulos y la otra dos.
La información sobre cuántos vecinos tiene cada nodo no determina cómo esos vecinos se conectan entre sí.
C94 introduce así un nivel estructural nuevo respecto de C92.
94.16. El agrupamiento tampoco determina accesibilidad global
En los dos triángulos, para todos los nodos.
Sin embargo, la red está desconectada.
Solo el 40 % de los pares pertenecen a la misma componente.
Un agrupamiento local alto no implica buena accesibilidad global.
El ciclo tiene agrupamiento cero y es completamente conectado.
Esta comparación une C93 y C94. El grado describe conexiones inmediatas, el agrupamiento describe el cierre entre vecinos y la accesibilidad describe la existencia de caminos. Ninguna de estas propiedades sustituye a las demás.
94.17. Clausura local y redundancia
Si los vecinos de están conectados entre sí, existen rutas alternativas de longitud dos entre algunos pares del vecindario.
En un triángulo , eliminar una arista todavía deja una ruta de dos pasos entre sus extremos.
Por ello, los triángulos pueden asociarse con redundancia local.
Convertir esa observación en una afirmación universal de robustez, sin embargo, sería un exceso. La relevancia depende del proceso que circula por la red, de las direcciones, los pesos y la capacidad.
Un triángulo topológico puede no dar una ruta funcional equivalente si una de las aristas tiene capacidad casi nula. C94 se limita a la estructura.
94.18. Agrupamiento en redes dirigidas
En un digrafo, tres nodos pueden conectarse de muchas maneras distintas.
La configuración
es diferente de
Ambas tienen tres aristas sobre tres nodos.
La primera es una triada transitiva o feed-forward loop.
La segunda es un ciclo dirigido.
Una única noción de «triángulo» pierde esa diferencia de orientación.
Existen varias definiciones de clustering dirigido según qué configuraciones se consideren cerradas.
La definición debe corresponder a la pregunta.
94.19. Feed-forward loop
Consideremos:
La información o influencia puede llegar desde hasta directamente o a través de .
La matriz de adyacencia no es simétrica.
En el censo triádico estándar, esta configuración corresponde al tipo
El paquete verifica que el grafo de tres nodos contiene exactamente una triada y ninguna .
La etiqueta describe la orientación y no acredita ninguna función regulatoria particular.
94.20. Ciclo dirigido
Ahora usemos
La configuración forma un ciclo de tres nodos.
En el censo triádico estándar corresponde a
El paquete verifica una triada y cero .
Ambos patrones contienen tres nodos y tres aristas.
La dirección distingue arquitecturas diferentes.
94.21. De patrón a motivo
En análisis de redes se utiliza el término motivo de red para patrones pequeños que aparecen con una frecuencia particular respecto de un modelo de referencia.
La palabra «motivo» no debería utilizarse simplemente como sinónimo de subgrafo.
Encontrar diez feed-forward loops no dice todavía si son muchos o pocos. Necesitamos saber qué número esperaríamos bajo una red comparable generada por un mecanismo de referencia, porque la inferencia requiere una comparación.
94.22. El denominador del motivo es un modelo
Supongamos una red dirigida con siete nodos y diez aristas.
Podemos construir redes aleatorias que preserven solo:
y
Después contamos cuántas triadas aparecen en cada réplica.
La distribución resultante da una referencia para ese modelo específico. Podríamos elegir, en cambio, otro modelo que preserve además grados de entrada y salida.
La frecuencia esperada de triadas cambiaría.
Por tanto, una afirmación de sobre-representación depende del conjunto de restricciones que definimos como «azar comparable».
C96 desarrollará el papel de los modelos de referencia.
94.23. Ejemplo computacional de referencia
El paquete construye un digrafo pequeño que contiene una triada transitiva y un ciclo dirigido entre otras conexiones.
Después genera 1000 digrafos aleatorios con el mismo número de nodos y aristas, sin lazos.
En cada uno calcula el censo triádico.
La distribución de conteos muestra que «observado» solo adquiere significado relativo después de fijar una referencia.
El ejemplo es didáctico y no pretende demostrar un motivo biológico o social real.
94.24. Un z-score de motivos necesita cautela
Si una referencia produce media
y desviación estándar
puede calcularse
Este número estandariza la discrepancia respecto del ensamble aleatorio.
Un grande, sin embargo, no demuestra por sí solo que el patrón tenga una función causal. También puede depender de restricciones omitidas en el modelo nulo, de la dependencia entre subgrafos, del número de motivos examinados, del tamaño finito de la red o del proceso de observación.
La comparación estadística es un paso previo a cualquier explicación funcional.
94.25. Motivos inducidos y no inducidos
Supongamos que buscamos el patrón
Si además existe la arista
¿seguimos contando esa terna como una cadena de longitud dos?
Depende de la definición.
Un subgrafo no inducido puede contar el patrón aunque existan aristas adicionales entre los mismos nodos.
Un subgrafo inducido exige que el patrón incluya exactamente todas las aristas presentes entre los nodos seleccionados.
En censos triádicos dirigidos, las categorías suelen corresponder a patrones inducidos completos sobre tres nodos.
Las dos convenciones responden a preguntas distintas y producen conteos diferentes.
94.26. Solapamiento entre motivos
Un mismo nodo o una misma arista puede pertenecer a muchos triángulos o motivos.
Por tanto, los conteos de subgrafos no son necesariamente observaciones independientes.
En un clique grande, los triángulos comparten numerosas aristas.
Esto importa al interpretar variabilidad y significación.
No podemos imaginar automáticamente cada aparición como un evento independiente.
La geometría de solapamiento forma parte de la estructura de orden superior.
94.27. Agrupamiento en redes ponderadas
Si los pesos contienen información relevante, binarizar puede desperdiciarla.
Existen varias definiciones de clustering ponderado que incorporan intensidades de las aristas de un triángulo.
Algunas utilizan medias geométricas de pesos normalizados; otras ponderan de modo distinto los triples.
No existe una única extensión universal del clustering binario. Por tanto, antes de reportar «clustering ponderado» debemos indicar qué definición se utilizó y qué significa un peso alto.
C91 ya mostró que un peso puede significar fuerza o costo, de modo que la semántica sigue siendo necesaria aquí.
94.28. Umbral y agrupamiento
Tomemos la matriz ponderada de contactos utilizada desde C91.
Definimos una arista binaria mediante
Al cambiar , no solo cambia el número de aristas.
También cambian los triángulos y las oportunidades de cierre.
El paquete calcula agrupamiento medio y transitividad para
Ambas medidas cambian de manera sustancial al mover el umbral.
94.29. El agrupamiento no tiene por qué decrecer con el umbral
Aumentar el umbral solo puede eliminar aristas.
El coeficiente
es una razón.
Eliminar ciertas aristas puede reducir el numerador y el denominador de formas diferentes.
Por ello, aunque el número de triángulos no puede aumentar al eliminar aristas, el coeficiente de agrupamiento puede aumentar en algunos nodos o umbrales.
La monotonicidad del número de aristas no implica monotonicidad del clustering.
La distinción pesa al interpretar análisis de sensibilidad.
94.30. Triángulos esperados dependen de la densidad
En una red más densa existen más oportunidades de formar triángulos incluso sin un mecanismo específico de cierre local.
Por eso comparar el número bruto de triángulos entre redes de densidades diferentes puede ser poco informativo.
Una red con diez veces más aristas puede contener muchos más triángulos por simple combinatoria.
El clustering normaliza parcialmente por oportunidades locales, pero las comparaciones entre redes también pueden requerir modelos de referencia.
C96 introducirá la red aleatoria como herramienta explícita para responder:
94.31. Cierre triádico como mecanismo hipotético
En redes sociales se habla de cierre triádico cuando una relación futura entre y se vuelve más probable si ambos están conectados con .
Ese es un mecanismo temporal.
Un coeficiente de clustering alto en una red estática es una propiedad descriptiva y no acredita que las aristas se hayan formado mediante cierre triádico.
La misma estructura podría surgir de proximidad espacial, de pertenencia a un grupo, de homofilia, de restricciones institucionales o de la proyección de eventos compartidos. La descripción estructural y el mecanismo generador deben separarse.
94.32. El motivo estructural frente al módulo funcional
Una triada o motivo pequeño describe organización local.
Una comunidad o módulo describe una estructura de escala mayor.
Un nodo puede participar en muchos motivos que atraviesen comunidades.
También pueden existir comunidades grandes con baja densidad de un motivo particular.
C99 estudiará comunidades y modularidad. Interpretar «motivo» como una mini-comunidad induce a error, porque son conceptos construidos a escalas y preguntas diferentes.
94.33. Motivos y causalidad
Un patrón dirigido como
puede sugerir una arquitectura de feed-forward.
Si las flechas indican correlación temporal, mensajería o flujo observado, en cambio, la interpretación causal sigue dependiendo de cómo fueron definidas.
El nombre del motivo no transforma las aristas en mecanismos causales.
La advertencia de C91 permanece intacta:
Una teoría funcional de motivos necesita información adicional sobre dinámica e intervención.
94.34. Censos de pequeños subgrafos
Para tres nodos no dirigidos existen pocas posibilidades estructurales.
En grafos dirigidos aparecen muchas más porque cada par admite ausencia de arista, una dirección, la dirección opuesta o reciprocidad.
El censo triádico clasifica todas las ternas de nodos según su patrón dirigido inducido.
La suma de los conteos debe igualar
Esta identidad da una verificación básica de un censo completo.
Las etiquetas como o codifican el número y tipo de díadas mutuas, asimétricas y nulas, además de la orientación específica.
94.35. Escala combinatoria
El número de subconjuntos de nodos en una red de tamaño es
Para motivos pequeños y redes moderadas, la enumeración directa puede ser posible.
Cuando y crecen, el número de candidatos aumenta rápidamente.
Además, si queremos comparar contra miles de redes de referencia, el costo se multiplica.
Por eso el análisis de motivos puede requerir algoritmos especializados, muestreo o restricciones sobre el tamaño del patrón.
Una pregunta estructural simple puede exigir un cálculo que no lo es.
94.36. Agrupamiento observado y red observada
C91 distinguió el grafo latente del grafo observado.
El clustering es muy sensible a errores locales de aristas.
Si faltan enlaces entre vecinos, destruimos triángulos.
Si aparecen falsos positivos, podemos crearlos.
Una tasa de error de aristas aparentemente pequeña puede afectar de manera no lineal el número de triángulos porque cada arista puede participar en muchos de ellos.
Por eso la incertidumbre de medición de la red debe considerarse antes de interpretar diferencias pequeñas de clustering.
94.37. Triples abiertos y cerrados
Un triple centrado puede estar abierto si falta la arista , o cerrado si esa arista existe.
Para un nodo ,
cuenta todas las oportunidades de formar un triple centrado.
Si es el número de triángulos que contienen a , entonces el número de triples cerrados centrados en es
El número de triples abiertos es
Por tanto,
Esta formulación es útil porque convierte el clustering en una comparación entre oportunidades de cierre y cierres realizados.
También muestra qué información se pierde al reportar solo . Dos nodos pueden tener el mismo coeficiente y números absolutos de oportunidades muy distintos.
Un nodo con grado dos y un triángulo tiene
Un nodo con grado veinte y todos sus pares de vecinos conectados también tiene
La proporción es idéntica en ambos casos, mientras la escala del vecindario difiere por completo.
Por eso conviene interpretar clustering junto con grado.
94.38. El mismo número de triángulos con agrupamientos distintos
El número bruto de triángulos tampoco determina el clustering.
Supongamos dos nodos que participan cada uno en un triángulo:
Si el primero tiene grado dos,
Si el segundo tiene grado diez,
La misma cantidad de triángulos representa una fracción completamente distinta de las oportunidades locales de cierre.
Esta es la razón para normalizar por
La normalización, en cambio, introduce la limitación inversa señalada antes, porque deja de expresar cuántos triángulos absolutos existen.
Triángulos y clustering deberían tratarse como descriptores complementarios.
94.39. Intensidad de un triángulo ponderado
En una red ponderada podemos preguntar, más allá de si las tres aristas de un triángulo existen, cuán intensas son conjuntamente.
Una construcción posible utiliza la media geométrica:
Si una de las tres aristas tiene peso muy pequeño, la intensidad del triángulo disminuye aunque las otras dos sean grandes.
Después pueden construirse coeficientes de clustering ponderado normalizando estas intensidades.
La elección de media geométrica no es inevitable. Otras definiciones ponderan los triángulos de otra manera.
Por eso una cifra de clustering ponderado debe acompañarse de su fórmula.
Además, si los pesos representan costos en vez de fuerzas, una gran intensidad numérica puede significar precisamente una relación menos favorable. La semántica de C91 vuelve a ser necesaria.
94.40. Motivos y múltiples comparaciones
Una red dirigida puede contener numerosos tipos de triadas y patrones mayores.
Si examinamos muchos patrones y seleccionamos retrospectivamente aquel con la discrepancia más grande respecto del modelo de referencia, aumentamos la probabilidad de encontrar alguna aparente sobre-representación por azar.
El problema es análogo a cualquier análisis con múltiples comparaciones.
Además, los conteos de motivos distintos no son independientes porque las mismas aristas pueden participar en varios subgrafos.
Una inferencia formal puede necesitar controlar multiplicidad o evaluar conjuntamente un perfil de motivos.
En esta etapa basta una regla metodológica:
y
deben definirse antes de convertir un conteo llamativo en una afirmación estructural fuerte.
La búsqueda exploratoria sigue siendo útil, pero sus resultados deben identificarse como exploratorios.
94.41. Verificación computacional
El paquete reproducible utiliza el grafo base de seis nodos.
Verifica que todos los nodos participan en un triángulo:
Confirma la identidad
y
El número total de triples centrados es por lo que la transitividad es
El agrupamiento local medio es
En el contraste de grado idéntico, el ciclo presenta clustering cero y dos triángulos separados presentan clustering uno para todos los nodos.
El ejemplo dirigido verifica una triada en el feed-forward loop y una en el ciclo dirigido.
Finalmente, una referencia de 1000 redes aleatorias con igual número de nodos y aristas produce distribuciones no degeneradas de ambos conteos triádicos, ilustrando que la evaluación de un motivo depende de la referencia elegida.
Se ejecutaron 33 comprobaciones automáticas y las 33 resultaron satisfactorias.
94.42. Qué queda establecido
El agrupamiento local cuantifica qué fracción de pares de vecinos de un nodo están conectados.
Para un grafo simple no dirigido,
El promedio de los y la transitividad global no son la misma medida porque ponderan de forma diferente las oportunidades de cierre.
La secuencia de grados no determina triángulos. Un ciclo y dos triángulos separados pueden tener exactamente los mismos grados y clustering opuesto.
La matriz de adyacencia codifica triángulos a través de
En redes dirigidas, distintos patrones de tres nodos deben distinguirse por orientación.
Un patrón frecuente solo se convierte en candidato a motivo respecto de una referencia explícita. El modelo de referencia forma parte de la afirmación.
C95 estudiará la centralidad y las distintas respuestas que dan sus definiciones a preguntas distintas. Allí veremos por qué grado, cercanía, intermediación y centralidades espectrales pueden ordenar los mismos nodos de maneras distintas sin que una sea universalmente «la correcta».
Referencias
- Fagiolo, G. (2007). Clustering in complex directed networks. Physical Review E, 76(2), 026107. https://doi.org/10.1103/PhysRevE.76.026107
- Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002). Network motifs: Simple building blocks of complex networks. Science, 298(5594), 824–827. https://doi.org/10.1126/science.298.5594.824
- Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press.
- Onnela, J.-P., Saramäki, J., Kertész, J., & Kaski, K. (2005). Intensity and coherence of motifs in weighted complex networks. Physical Review E, 71(6), 065103. https://doi.org/10.1103/PhysRevE.71.065103
- Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature, 393, 440–442. https://doi.org/10.1038/30918
Recursos reproducibles
Descargar recursos del capítulo (ZIP, 199 kB).
9 archivos CSV · 4 figuras · 1 programa Python.
El programa se ha ejecutado en una carpeta vacía y genera los archivos de datos y figuras incluidos en el paquete.