93.1. Del vecino inmediato a la estructura global
C92 estudió cuántas conexiones tiene cada nodo. El grado responde a una pregunta local:
Dos redes con la misma secuencia de grados, sin embargo, pueden organizar esas conexiones de forma completamente distinta.
Para estudiar cómo se encadenan las aristas necesitamos introducir:
Estas nociones transforman una colección de vínculos locales en una geometría de red.
La distancia entre dos nodos ya no depende de su separación visual en un dibujo. Depende del número o costo de aristas que deben recorrerse para pasar de uno a otro.
La accesibilidad pregunta algo todavía más básico:
C93 se concentra en esas definiciones antes de avanzar hacia agrupamiento o centralidad.
93.2. Paseo
Sea un grafo
Un paseo de longitud es una secuencia
tal que cada par consecutivo está unido por una arista.
Un paseo puede repetir nodos y aristas.
Por ejemplo, en el grafo base de C91:
es un paseo de longitud cuatro.
El nodo aparece dos veces.
Los paseos son matemáticamente útiles porque las potencias de la matriz de adyacencia los cuentan de manera natural, aunque todavía no dan la noción más económica de conexión entre dos nodos.
93.3. Sendero y camino simple
La terminología puede variar entre textos, por lo que conviene fijarla.
Llamaremos sendero a un paseo que no repite aristas.
Llamaremos camino simple a un paseo que no repite vértices.
Todo camino simple es un sendero.
Un sendero puede repetir algún vértice siempre que no reutilice aristas.
Para problemas de distancia en grafos sin pesos negativos, un recorrido mínimo entre dos nodos puede elegirse simple. Si repitiera un ciclo, eliminar ese ciclo no aumentaría la longitud.
Por eso, cuando hablamos de «camino mínimo», normalmente podemos imaginar una secuencia sin repeticiones innecesarias.
93.4. Longitud de un camino
En un grafo no ponderado, la longitud de un camino es el número de aristas recorridas.
El camino
tiene longitud
La longitud pertenece al grafo abstracto, con independencia de las longitudes geométricas con que se dibujen las aristas.
En una red ponderada, en cambio, puede definirse un costo total sumando pesos interpretados como longitudes o costos. Esa diferencia reaparecerá más adelante en el capítulo.
93.5. Distancia geodésica
Para dos nodos y , la distancia geodésica no ponderada es
En el grafo base,
La distancia representa la longitud de un camino mínimo.
Puede haber varios caminos mínimos distintos con la misma longitud.
La distancia es única como número aunque la ruta que la realiza no sea única.
93.6. La matriz de distancias
Si ordenamos los nodos como
la matriz completa de distancias es
Como el grafo es no dirigido,
por lo que
La diagonal es cero porque
93.7. Un camino mínimo concreto
Desde hasta , uno de los caminos mínimos es
Su longitud es tres.
El paquete reconstruye esta ruta mediante búsqueda en anchura.
La figura destaca una ruta particular, pero la distancia es una propiedad del grafo, no del algoritmo de dibujo ni de las coordenadas visuales.
93.8. Triángulo métrico
La distancia geodésica en un grafo no ponderado no dirigido satisface propiedades de una métrica sobre cada componente conectada.
En particular,
y
La última desigualdad se entiende porque concatenar un camino mínimo de a con uno de a produce algún recorrido de a .
El camino mínimo directo nunca puede ser más largo que ese recorrido concatenado.
93.9. Alcanzabilidad
Decimos que es alcanzable desde si existe al menos un camino de a .
En un grafo no dirigido, si alcanza a , entonces alcanza a .
Esta relación divide el grafo en componentes conectadas.
Dos nodos están en la misma componente si existe un camino entre ellos.
En el grafo base todos los seis nodos pertenecen a una única componente.
Por tanto, todos los pares tienen una distancia finita.
93.10. Componentes conectadas
Una componente conectada es un subconjunto maximal de nodos dentro del cual todos los pares son alcanzables.
«Maximal» significa que no podemos añadir otro nodo del grafo sin perder esa propiedad.
Si una red tiene varias componentes, no existe camino entre nodos de componentes distintas.
En tal caso se utiliza a menudo
para expresar que no existe distancia finita entre ellos.
El infinito indica aquí ausencia de ruta, no una ruta extremadamente larga.
93.11. La distancia media requiere una convención
Para una red conectada podemos definir la distancia media entre pares:
En el grafo base,
En una red desconectada aparecen distancias infinitas.
Entonces el promedio ordinario sobre todos los pares deja de ser finito.
Una práctica es calcular distancias solo dentro de pares alcanzables. Otra es trabajar por componente. Otra utiliza transformaciones como que asignan cero a pares no alcanzables.
Estas convenciones responden a preguntas distintas y deben declararse.
93.12. Excentricidad
Para un nodo en una componente conectada, su excentricidad es
Describe qué tan lejos se encuentra su nodo alcanzable más distante.
En el grafo base,
La excentricidad resume una propiedad global de cada nodo.
No debe confundirse con grado. y tienen grado tres, pero lo relevante aquí es que ningún nodo queda a más de dos pasos de ellos.
93.13. Radio y diámetro
El radio de un grafo conectado es
El diámetro es
En el grafo base,
Los nodos cuya excentricidad coincide con el radio forman el centro del grafo.
Aquí son y
Estas nociones describen geometría de distancias, todavía lejos de una teoría general de centralidad, que se tratará en C95.
93.14. El grado no determina la accesibilidad
C92 presentó un ejemplo que vuelve a servir aquí.
Consideremos un ciclo de seis nodos:
Todos los nodos tienen grado dos.
Ahora consideremos dos triángulos separados.
También allí todos los nodos tienen grado dos.
Por tanto, ambas redes comparten exactamente la secuencia
También comparten
y varianza de grado cero.
Sin embargo, sus accesibilidades globales son distintas.
93.15. Ciclo frente a dos triángulos
En el ciclo existe un camino entre todo par de nodos.
La fracción de pares no ordenados alcanzables es
En dos triángulos separados, cada componente contiene tres nodos.
Cada triángulo aporta
pares alcanzables.
En total:
El número total de pares posibles, en cambio, es
Por tanto, la fracción alcanzable es
C92 no podía distinguir ambas redes, mientras C93 sí lo consigue.
93.16. Distancias dentro de esas dos redes
En el ciclo , el diámetro es
La distancia media es
En cada triángulo separado, todos los pares dentro de una componente están directamente conectados:
Si promediáramos solo sobre pares alcanzables, obtendríamos distancia media uno.
Eso podría dar la impresión de una red «más compacta».
Ocurre, sin embargo, que el 60 % de los pares ni siquiera puede comunicarse.
Por eso una distancia media condicionada a alcanzabilidad debe acompañarse de información sobre conectividad global.
93.17. Matriz de adyacencia y paseos
Sea la matriz de adyacencia.
Una propiedad central es:
cuenta el número de paseos de longitud desde hasta en un grafo simple no dirigido.
Para , indica si existe una arista.
Para ,
que cuenta cuántos nodos intermedios permiten un paseo
Así, álgebra matricial y recorridos de red quedan conectados directamente.
93.18. Recuperar distancias mediante potencias
Para dos nodos distintos en un grafo no ponderado,
El paquete calcula
y recupera exactamente la matriz de distancias del grafo base.
Por ejemplo,
pero
porque existe
Entonces
Las potencias cuentan paseos; la primera potencia positiva identifica la longitud mínima.
93.19. Los paseos y los caminos simples se cuentan distinto
El valor
incluye recorridos que pueden repetir nodos o aristas.
Por tanto, no debe interpretarse automáticamente como número de caminos simples.
En redes con ciclos, el número de paseos aumenta rápidamente porque podemos dar vueltas y volver a pasar por nodos ya visitados.
Esta diferencia importa cuando utilizamos álgebra matricial para razonar sobre rutas.
La existencia de un término positivo demuestra un paseo, pero su multiplicidad no equivale en general a rutas simples independientes.
93.20. Búsqueda en anchura
Para un grafo no ponderado, la búsqueda en anchura, BFS por breadth-first search, explora la red por capas.
Desde un origen , la capa 0 contiene solo , la capa 1 sus vecinos directos, la capa 2 los nodos no visitados que se alcanzan desde la capa 1. Las capas siguientes continúan del mismo modo.
La primera vez que BFS alcanza un nodo determina una distancia mínima desde .
En el grafo base, desde :
El paquete implementa BFS explícitamente y compara sus resultados con NetworkX.
93.21. Complejidad de BFS
Con una representación mediante listas de adyacencia, BFS tiene complejidad
Cada nodo se visita esencialmente una vez y cada arista se examina un número acotado de veces.
Para una red dispersa grande, esto puede ser mucho más eficiente que construir sucesivamente potencias densas de la matriz de adyacencia.
La equivalencia matemática entre métodos deja abierta la equivalencia computacional, de modo que una representación útil debe considerar tanto estructura como escala.
93.22. En una red dirigida la accesibilidad deja de ser simétrica
En un grafo dirigido puede existir
sin que exista
El paquete construye:
Desde podemos alcanzar todos los demás nodos.
Desde , no podemos alcanzar ninguno distinto de .
La matriz de alcanzabilidad es por ello asimétrica.
93.23. Componentes fuertemente conectadas
En una red dirigida, un conjunto es fuertemente conectado si cada nodo puede alcanzar a todos los demás siguiendo la dirección de las aristas.
En el ejemplo aparecen tres componentes fuertemente conectadas:
Dentro de podemos circular entre todos los nodos.
Dentro de , también.
El nodo forma una componente fuerte trivial de un solo nodo.
La arista permite llegar a , pero no volver.
93.24. Conectividad débil
Si ignoramos temporalmente las direcciones y reemplazamos cada arista dirigida por una conexión no dirigida, el ejemplo completo es conectado.
Decimos entonces que el digrafo es débilmente conectado.
Una red puede ser débilmente conectada sin ser fuertemente conectada, porque ambas propiedades responden a preguntas diferentes.
Para flujos que realmente respetan la dirección, la conectividad débil puede sobrestimar accesibilidad funcional.
93.25. Matriz de alcanzabilidad
Podemos definir
Si incluimos el camino trivial de longitud cero,
En un grafo no dirigido, es simétrica.
En un grafo dirigido no necesariamente.
La matriz pierde la longitud concreta de los caminos y conserva la pregunta binaria de existencia. Es otra compresión de la estructura.
93.26. Distancias dirigidas
En un digrafo definimos como la longitud del camino dirigido más corto de a .
Entonces puede ocurrir:
y
La distancia dirigida no es una métrica simétrica sobre todo el conjunto de nodos, de modo que trasladar sin cambios las intuiciones métricas del caso no dirigido induce a error. La orientación altera la geometría accesible.
93.27. En redes ponderadas hay que decidir primero qué significa el peso
Supongamos que una arista tiene peso
¿Es una conexión larga o fuerte?
La respuesta depende de la semántica.
Si representa distancia, tiempo o costo, un peso menor suele ser preferible en un camino mínimo.
Si representa fuerza, capacidad o afinidad, un peso mayor suele significar una conexión «mejor».
Usar el mismo algoritmo de distancia sin transformar el peso puede invertir el significado del problema.
93.28. Un ejemplo de fuerza interpretada erróneamente como costo
Consideremos tres nodos:
Las fuerzas son:
La conexión directa es la más fuerte.
Si usamos esos pesos directamente como costos, el camino directo cuesta diez.
La ruta
cuesta
Un algoritmo de camino mínimo elegiría la vía indirecta.
El cálculo sería correcto respecto del costo suministrado, pero la semántica sería equivocada.
93.29. Transformar fuerza en costo
Una transformación elemental posible para pesos positivos es
Entonces la arista fuerte tiene costo
Las otras dos tienen costo cada una.
La ruta indirecta cuesta
Ahora el camino mínimo vuelve a ser la arista directa.
Esta transformación no es universal. En otras aplicaciones puede utilizarse
o alguna función derivada del mecanismo físico.
La elección debe justificarse por qué significa acumular costos a lo largo de una ruta.
93.30. Cuando los pesos sí son costos
Tomemos ahora:
Si esos valores representan verdaderamente costo, la ruta
tiene costo dos y supera a la conexión directa de costo cinco.
Aquí el algoritmo de camino mínimo tiene la interpretación deseada.
La misma estructura de números puede describir fenómenos opuestos según su significado.
93.31. Dijkstra y pesos no negativos
Para grafos con costos no negativos, el algoritmo de Dijkstra encuentra caminos mínimos desde un origen de forma eficiente.
Su corrección depende de que, una vez fijada cierta distancia mínima, una arista posterior no pueda reducirla mediante un costo negativo inesperado.
Si existen pesos negativos interpretados como costos, Dijkstra deja de ser el algoritmo general apropiado.
Esto obliga a elegir algoritmos compatibles con la estructura matemática de los pesos, sin invalidar las redes con pesos negativos.
93.32. El camino mínimo frente al camino más probable
Supongamos que cada arista tiene una probabilidad de transmisión
La probabilidad de una ruta, bajo supuestos de independencia, es el producto
Maximizar ese producto equivale a minimizar
Por tanto, una transformación
convierte una maximización multiplicativa en un problema aditivo de caminos mínimos.
Este ejemplo muestra por qué la semántica determina la transformación adecuada. No existe una noción única de «distancia ponderada».
93.33. Caminos mínimos múltiples
Dos nodos pueden estar unidos por varios caminos de longitud mínima.
En tal caso, la distancia geodésica sigue siendo un único número, pero la redundancia de rutas puede ser distinta.
Una red con diez geodésicas alternativas no es operacionalmente idéntica a otra con una sola, aunque ambas tengan
C93 no desarrollará medidas de redundancia o robustez de rutas. El punto es que la matriz de distancias comprime información, de modo que conservar solo no permite reconstruir cuántos caminos mínimos existían.
93.34. Accesibilidad como conjunto
Para un nodo , definamos su conjunto alcanzable:
En una red dirigida puede ser útil separar:
para nodos alcanzables desde , y
para nodos que pueden alcanzar a .
En el digrafo del ejemplo,
mientras
Esta asimetría existe aunque ambos nodos formen parte de la misma componente débil.
93.35. La accesibilidad y la centralidad son propiedades distintas
Un nodo desde el que pueden alcanzarse muchos otros tiene una propiedad relevante, aunque todavía no hemos definido una centralidad general.
Dos nodos pueden alcanzar el mismo número de destinos y hacerlo a distancias muy diferentes.
También pueden diferir en número de rutas alternativas, dirección, peso o posición entre otros nodos.
C95 comparará varias definiciones de centralidad porque «ser importante» no corresponde a una única propiedad matemática.
C93 mantiene la pregunta más elemental:
93.36. Agregar tiempo puede fabricar caminos imposibles
Supongamos dos contactos temporales:
ocurre a las 15:00,
y
ocurrió a las 10:00.
La red agregada del día contiene
Sin embargo, una señal que parte de a las 15:00 no puede utilizar una interacción de con ocurrida cinco horas antes.
El camino existe en el grafo agregado, pero no es temporalmente realizable.
Por ello, accesibilidad estática puede sobrestimar accesibilidad en redes temporales.
El currículo retomará estas cuestiones cuando trate redes dinámicas.
93.37. Distancia topológica y distancia física
Dos nodos pueden estar geográficamente lejos y conectados por una sola arista.
Entonces,
También pueden estar físicamente muy cerca y requerir muchos pasos en la red.
La palabra «distancia» debe acompañarse de su definición.
Una distancia topológica cuenta aristas, una distancia ponderada suma costos, una distancia física utiliza coordenadas espaciales y una distancia semántica puede surgir de otra función. Mezclar esas escalas produce interpretaciones incorrectas.
93.38. Comparar redes requiere convenciones compatibles
Si una red considera cada arista con longitud uno y otra utiliza tiempos de viaje, sus distancias no son directamente comparables.
Si una incluye pares desconectados como infinito y otra promedia solo dentro de la mayor componente, sus distancias medias tampoco representan la misma cantidad.
Antes de comparar:
debemos verificar que coincidan el tipo de grafo, la semántica del peso, la regla para pares no alcanzables, la ventana temporal y la definición de nodo y arista. La precisión numérica deja intacta cualquier discrepancia en el objeto medido.
93.39. Clausura transitiva y accesibilidad booleana
Las potencias de cuentan paseos mediante aritmética ordinaria.
Si solo queremos saber si existe alguno, podemos reemplazar la suma y el producto ordinarios por operaciones booleanas.
Conceptualmente, la matriz de alcanzabilidad puede escribirse como la clausura de
hasta longitudes suficientes:
para un grafo finito de nodos, interpretando la expresión entrada por entrada.
No necesitamos caminos simples de longitud mayor que para demostrar alcanzabilidad entre dos nodos distintos, porque si una ruta repite un vértice podemos eliminar el ciclo correspondiente.
En un grafo dirigido, esta construcción produce la clausura transitiva.
La clausura pierde cuántas rutas existen y cuáles son sus longitudes exactas. Conserva únicamente la relación
Es, por tanto, una representación más comprimida que la matriz de distancias.
93.40. Un árbol BFS preserva distancias desde un origen, no toda la red
Durante una búsqueda en anchura desde , cada nodo descubierto recibe un padre.
Las aristas
forman un árbol de búsqueda para los nodos alcanzables.
Ese árbol conserva una propiedad muy concreta:
para todos los alcanzados por BFS.
El árbol, en cambio, no conserva necesariamente las distancias entre pares que excluyen al origen, ni tampoco las rutas alternativas.
En el grafo base, el árbol BFS desde puede incluir una sola de varias conexiones disponibles dentro de los triángulos.
Por ello, reducir una red a un árbol de caminos mínimos desde un origen es útil para navegación desde ese origen, pero no es una representación equivalente del grafo.
La distinción volverá a pesar cuando se analicen robustez y redundancia.
93.41. Distancia media de pares alcanzables puede ser engañosa
Volvamos al ciclo y a los dos triángulos.
En el ciclo:
de los pares son alcanzables y la distancia media es
En los dos triángulos, si ignoramos los pares desconectados, la distancia media entre pares alcanzables es
Si reportáramos únicamente ese segundo número, la red fragmentada parecería «mejor conectada».
La paradoja aparente surge porque cambiamos silenciosamente el denominador.
En una red contamos todos los pares; en la otra excluimos el 60 % de pares imposibles.
Una descripción mínimamente suficiente de una red desconectada debería acompañar la distancia condicionada con alguna medida de cobertura, por ejemplo:
Esto separa la proximidad entre quienes pueden conectarse de la capacidad global de conexión.
93.42. Distancia con horizonte máximo
En algunos sistemas no basta con que exista un camino.
Puede existir una restricción operacional:
Definamos entonces la accesibilidad a pasos:
Para , recuperamos vecinos directos.
Al aumentar , el conjunto crece hasta alcanzar toda la componente accesible.
Esta familia permite distinguir:
En procesos reales, cada paso puede implicar demora, pérdida de información o probabilidad de fallo.
Por tanto, dos nodos técnicamente alcanzables pueden no ser equivalentes si uno requiere dos pasos y otro veinte.
C93 no introduce todavía una función universal que convierta longitud en «influencia». Solo hace explícita la escala de pasos sobre la cual formulamos accesibilidad.
93.43. Costos negativos y ciclos negativos
En una red ponderada, permitir costos negativos requiere especial cuidado.
Una arista negativa no produce por sí sola una contradicción matemática.
El problema aparece si existe un ciclo cuyo costo total es negativo.
Supongamos que podemos ir de a , recorrer un ciclo de costo y volver al mismo punto del recorrido.
Cada vez que repetimos el ciclo reducimos el costo total en tres.
Entonces no existe un camino de costo mínimo finito:
La pregunta «¿cuál es el camino más corto?» deja de tener la misma clase de respuesta.
Por eso los algoritmos y las definiciones deben adecuarse a la semántica de los pesos.
Si una variable puede ser negativa porque representa correlación, beneficio o cambio de energía, quizá «sumarla como longitud» ni siquiera sea la formulación correcta.
La matemática del camino debe construirse después de decidir qué cantidades son acumulables a lo largo de una ruta.
93.44. Verificación computacional
El paquete reproducible construye el grafo base de seis nodos.
Obtiene la matriz completa de distancias y verifica:
diámetro radio y distancia media
Los centros son y
Una implementación explícita de BFS desde reproduce exactamente las distancias calculadas por NetworkX.
Las potencias
recuperan también la primera longitud para la cual existe un paseo entre cada par.
En el contraste de igual secuencia de grados, el ciclo tiene fracción de pares alcanzables uno, mientras dos triángulos separados alcanzan solo
El digrafo es débilmente conectado pero no fuertemente conectado y contiene tres componentes fuertemente conectadas:
Finalmente, el ejemplo ponderado verifica que usar fuerza como costo elige una ruta indirecta, mientras transformar recupera la arista fuerte directa.
Se ejecutaron 38 comprobaciones automáticas y las 38 resultaron satisfactorias.
93.45. Qué queda establecido
Los caminos convierten conexiones locales en estructura global.
La distancia geodésica es la longitud mínima entre dos nodos alcanzables. En redes desconectadas, algunos pares carecen de distancia finita.
La matriz de adyacencia contiene información sobre paseos a través de sus potencias:
cuenta paseos de longitud .
BFS calcula eficientemente distancias en redes no ponderadas.
La secuencia de grados no determina conectividad ni accesibilidad. Un ciclo y dos triángulos pueden tener idénticos grados y propiedades globales muy distintas.
En redes dirigidas, alcanzabilidad y distancia son asimétricas. En redes ponderadas, un peso solo puede convertirse en distancia después de decidir qué significa.
Por tanto, «estar conectado» puede significar vínculo directo, existencia de algún camino o acceso dentro de un costo determinado. Cada afirmación necesita especificar su nivel.
C94 estudiará el agrupamiento local y los motivos de conexión. Allí preguntaremos, más allá de si los vecinos de un nodo existen, cómo se conectan entre sí y qué patrones pequeños aparecen con frecuencia dentro de la red.
Referencias
- Barabási, A.-L. (2016). Network Science. Cambridge University Press.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.
- Diestel, R. (2017). Graph Theory (5th ed.). Springer.
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271. https://doi.org/10.1007/BF01386390
- Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press.
Recursos reproducibles
Descargar recursos del capítulo (ZIP, 172 kB).
12 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.