Grafos y redes

Un sistema puede tener muchas conexiones y depender de muy pocas para comunicar sus regiones. Contar enlaces no revela dónde se concentran ni qué lugares quedan separados cuando uno falla. En un transporte, un circuito o una organización, la disposición de las relaciones puede importar tanto como las propiedades de cada elemento.

Un grafo conserva esa disposición mediante entidades y conexiones. Permite preguntar qué puede alcanzarse, por dónde debe pasar un recorrido o cuánto admite una red de circulación. Su utilidad depende de lo que significa cada conexión. Una arista que representa autorización, proximidad o intercambio observado conserva información distinta, aunque el dibujo sea idéntico.

126.1. Nodos, aristas, caminos y conectividad#

Un grafo reúne un conjunto de nodos, también llamados vértices, y un conjunto de conexiones, o aristas. Se escribe $G=(V,E)$, donde $V$ contiene los nodos y $E$ las aristas. En un grafo simple no dirigido, cada arista conecta dos nodos distintos, sin indicar un sentido, y hay como máximo una entre cada par. Dos nodos conectados directamente son adyacentes. (Levin, problemas y definiciones de grafos).

La posición sobre el papel no forma parte de esa definición. Puede dibujarse el mismo grafo con líneas largas, cortas o curvas sin cambiar sus conexiones. Un cruce de líneas tampoco crea un nodo a menos que se marque como tal. Si los nodos representan lugares físicos, sus coordenadas pueden añadirse como atributos, pero la distancia en el dibujo no sustituye a una distancia medida.

Ejemplo construido. Una red simple no dirigida tiene ocho nodos: $a,b,c,u,v,d,e,f$. Los tres primeros forman un triángulo y los tres últimos otro. Entre ellos existe únicamente la cadena $c-u-v-d$. Sus nueve aristas son $ab,bc,ca,cu,uv,vd,de,ef,fd$, donde $ab$ representa el par no ordenado $\{a,b\}$. Todas tienen el mismo significado abstracto: permiten recorrer la conexión en cualquiera de los dos sentidos.

El grado de un nodo es su número de aristas incidentes. Aquí $c$ y $d$ tienen grado tres; los demás, grado dos. La suma de los grados es 18, el doble de las nueve aristas. Cada arista se cuenta en sus dos extremos. En grafos con lazos, donde una conexión vuelve al mismo nodo, la convención usual cuenta ese lazo dos veces en el grado; no hay lazos en el ejemplo.

Un recorrido sigue aristas sucesivas. En este capítulo, camino designa un recorrido que no repite nodos; otras fuentes distinguen esos términos de otra manera. Desde $a$ hasta $f$ existe el camino $a,c,u,v,d,f$, de cinco aristas. La distancia de grafo entre ambos es la longitud del camino más corto, aquí cinco. No representa cinco kilómetros ni cinco minutos si no se han definido pesos con esas unidades.

Una red no dirigida es conexa si todo par de nodos puede unirse mediante un camino. Una componente conexa es una región máxima de nodos que pueden alcanzarse entre sí. El ejemplo tiene una componente. Quitar $uv$ lo divide en dos, cada una con cuatro nodos. $uv$ es un puente: una arista cuya eliminación aumenta el número de componentes. También lo son $cu$ y $vd$. Las aristas de los triángulos no son puentes porque queda una ruta alternativa entre sus extremos.

Eliminar un nodo puede tener otro efecto. Si se elimina $u$ junto con sus aristas, se separa el triángulo izquierdo de la región derecha. Es un nodo de articulación. «Quitar una arista» y «quitar un nodo» son intervenciones diferentes: la segunda elimina todas sus conexiones. Una evaluación de vulnerabilidad debe precisar cuál se considera y qué servicio se pretende conservar.

126.2. Árboles, ciclos, flujos y cortes#

Un ciclo vuelve al nodo inicial sin repetir otros nodos. Los triángulos del ejemplo son ciclos de tres aristas. Tener un ciclo introduce al menos una alternativa de recorrido: se puede llegar entre dos de sus nodos por lados distintos. Esa redundancia local no elimina automáticamente los puentes situados en otra región.

Un árbol es un grafo no dirigido conexo sin ciclos. Entre cada par de nodos hay un único camino: dos caminos distintos crearían un ciclo. Un árbol de $n$ nodos tiene $n-1$ aristas. Puede justificarse quitando sucesivamente una hoja, un nodo de grado uno: se elimina un nodo y una arista, conservando un árbol, hasta llegar a un único nodo sin aristas. (Levin, árboles).

La existencia de una hoja también tiene una razón. En un árbol finito de al menos dos nodos, se elige un camino de longitud máxima. Un extremo no puede tener otro vecino fuera del camino, pues permitiría alargarlo; tampoco puede conectarse con otro nodo anterior del camino, pues crearía un ciclo. Sólo tiene el vecino que sigue en el camino. El razonamiento permite retirar hojas sin suponer de antemano la forma del árbol ni que tenga una raíz especial.

Una red conexa puede conservar sólo algunas aristas y seguir conectando todos sus nodos sin ciclos. El resultado es un árbol generador. En el ejemplo, quitar una arista de cada triángulo conserva los ocho nodos conectados con siete aristas. Es una forma de mantener alcanzabilidad usando el mínimo número de conexiones, pero todas sus aristas se vuelven puentes. Menor costo de enlace puede significar menor redundancia; el grafo por sí solo no fija la compensación deseable.

Las tareas de recorrido también difieren. Visitar todos los nodos una vez no es recorrer todas las aristas una vez. Esta última tarea corresponde a un recorrido euleriano. En una red no dirigida conexa con aristas, se puede recorrer cada arista exactamente una vez y regresar al inicio si todos los grados son pares; se puede hacerlo con extremos distintos si hay exactamente dos nodos de grado impar. Entrar y salir de cada nodo intermedio usa aristas en pares, lo que explica la necesidad de la condición. (Levin, recorridos y circuitos eulerianos).

Un flujo plantea otra pregunta: no busca sólo un camino, sino cuánto puede circular simultáneamente. Se emplea una red dirigida con una fuente $s$, un destino $t$ y una capacidad no negativa por arista. Un flujo factible respeta cada capacidad y conserva lo que entra y sale en los nodos intermedios. El valor del flujo es la salida neta de la fuente, igual a la entrada neta al destino bajo esas condiciones.

Ejemplo construido. Una red ideal de transporte de volumen tiene cuatro nodos, $s,A,B,t$. Las capacidades, en litros por minuto, son $s\to A:4$, $s\to B:3$, $A\to t:2$, $B\to t:4$ y $A\to B:1$. No hay almacenamiento, pérdidas ni otras conexiones. Un flujo de seis litros por minuto se obtiene enviando tres desde $s$ a $A$ y tres desde $s$ a $B$. $A$ entrega dos al destino y uno a $B$; $B$ recibe cuatro en total y los entrega al destino.

Para demostrar que seis es el máximo hay que excluir todos los flujos mayores, no sólo ensayar varios recorridos. Todo lo que llega a $t$ debe cruzar $A\to t$ o $B\to t$, cuyas capacidades suman seis. Es una cota superior alcanzada por el flujo construido.

Un corte que separa fuente y destino divide los nodos en dos grupos, uno con $s$ y otro con $t$. Su capacidad es la suma de capacidades de aristas que pasan del primer grupo al segundo. Ningún flujo puede superar esa capacidad, porque toda entrega neta debe atravesar la separación. El teorema de flujo máximo y corte mínimo establece que, en el modelo habitual de red finita con capacidades no negativas, el mayor flujo factible iguala la menor capacidad de esos cortes. No afirma que una instalación física necesariamente alcance su capacidad nominal. (MIT, flujo de redes y cortes).

126.3. Redes dirigidas, ponderadas y multicapa#

En un grafo dirigido, una arista $a\to b$ permite pasar de $a$ a $b$; no presupone el regreso. Se distinguen grado de entrada y de salida. Una red es fuertemente conexa si cada nodo alcanza a todos los demás siguiendo los sentidos. Es débilmente conexa si queda conexa al ignorar esos sentidos. Una cadena $a\to b\to c$ cumple la segunda condición, pero no la primera.

Un peso añade una cantidad a una conexión. Puede expresar longitud, duración, costo, intensidad o capacidad; esos significados no son equivalentes. En un problema de recorrido con tiempos aditivos no negativos, el tiempo de una ruta es la suma de sus pesos y puede minimizarse. Una arista de mayor capacidad, en cambio, no es necesariamente más lenta ni más costosa. Usar intensidad como distancia sin justificar una conversión puede invertir la interpretación.

Por ejemplo, una conexión directa de diez minutos es más lenta que dos conexiones sucesivas de tres minutos cada una, si no hay espera ni otros costos. El camino con menos aristas tiene una arista; el más rápido tiene dos. Si existe una espera de cinco minutos entre esas dos conexiones, dejan de ofrecer seis minutos de viaje total. La definición de costo debe incluir lo que se pretende optimizar.

La matriz de adyacencia permite conservar estas relaciones en un arreglo numérico. Para nodos numerados, se puede adoptar $A_{ij}=1$ cuando hay arista de $i$ a $j$ y cero en otro caso. En una red simple no dirigida, la matriz es simétrica. Con pesos, las entradas pueden guardar esos pesos, pero un cero debe distinguir ausencia de arista de una arista de costo cero. La convención sobre filas y columnas se debe declarar, porque no todos los campos usan el mismo sentido.

Si $A$ es la matriz binaria de una red, la entrada $(i,j)$ de $A^2$ cuenta recorridos de dos aristas desde $i$ hasta $j$: la multiplicación suma sobre cada nodo intermedio. Más generalmente, $A^k$ cuenta recorridos de $k$ aristas, permitiendo repeticiones. No cuenta exclusivamente caminos sin nodos repetidos. La conexión con el capítulo 124 permite calcular sobre la estructura sin confundir operaciones matriciales con desplazamientos físicos.

Una red multicapa conserva tipos de conexiones separados. Los mismos lugares pueden conectarse por transporte terrestre, comunicación y suministro eléctrico. Reunir todas las aristas en una sola red puede crear una ruta que cambia de tipo de relación sin que ese cambio sea posible para el proceso estudiado. Las capas necesitan reglas de transferencia: qué nodo de una puede conectarse con cuál de otra, a qué costo y con qué significado. (Kivelä y colaboradores, redes multicapa).

Además, una conexión puede existir sólo en un momento. Ejemplo construido. Entre las horas cero y seis, $B$ y $C$ se encuentran a la hora dos, y $A$ y $B$ a la hora cinco. Un mensaje disponible sólo en $A$ a la hora cero puede llegar a $B$ a las cinco, pero no aprovechar un encuentro con $C$ ocurrido antes. La red agregada $A-B-C$ muestra un camino que no es realizable en ese orden temporal.

Un recorrido temporal debe respetar la secuencia de activación de sus conexiones, junto con tiempos de tránsito y posibles límites de espera. Agregar una jornada completa puede exagerar la alcanzabilidad durante ella. Las redes temporales conservan esa información, aunque exigen datos más detallados. (Holme y Saramäki, redes temporales).

126.4. Centralidad, comunidad y difusión#

La posición relevante depende de cómo opera el proceso. Tener muchos vecinos directos puede facilitar contactos locales; conectar regiones separadas puede importar para intermediación; estar cerca de otros por rutas cortas puede importar para tiempos de acceso. Una medida de centralidad responde a una de esas preguntas, no a una noción universal de importancia.

La centralidad de grado cuenta vecinos. La de intermediación mide cuánto pasa un nodo por los caminos más cortos entre otros nodos, repartiendo la contribución si hay varios caminos igualmente cortos. La cercanía se basa en distancias a otros nodos; requiere decidir cómo tratar los que no se pueden alcanzar. La centralidad por autovector valora conexiones con nodos que también reciben valores altos, bajo las condiciones matemáticas y convenciones de la matriz usada. (Newman, medidas de centralidad).

En la red de dos triángulos unidos por $c-u-v-d$, $u$ tiene sólo dos vecinos. Sin embargo, todos los caminos entre los tres nodos de su lado izquierdo y los cuatro de su lado derecho pasan por él. Son $3\cdot 4=12$ pares de otros nodos. $c$, con grado tres, intermedia entre $a,b$ y los cinco nodos al otro lado: diez pares. En el conteo no normalizado de este ejemplo, $u$ tiene más intermediación que $c$ pese a menor grado. Un nodo dentro de un triángulo puede tener igual grado que $u$ y ninguna intermediación.

Esos números sólo describen caminos más cortos del grafo observado. Si la circulación usa rutas alternativas, si el nodo puede ser sustituido o si las conexiones omiten relaciones informales, no miden directamente control o poder. Una centralidad alta tampoco prueba que intervenir ese nodo produzca el mayor efecto: tal conclusión exige un modelo del proceso y de la intervención.

Una comunidad suele designar un grupo con conexiones internas relativamente abundantes respecto de sus conexiones externas o de un modelo de referencia. «Relativamente» es decisivo: contar aristas internas sin considerar tamaño y grado puede favorecer grupos grandes. Hay varias definiciones, escalas y métodos de detección; algunos admiten pertenencias superpuestas y otros exigen una partición. Un resultado algorítmico debe contrastarse con la pregunta y los datos, no tomarse como división natural incuestionable. (Fortunato y Hric, detección de comunidades).

La difusión requiere añadir una regla de cambio a la estructura. Ejemplo construido. En la red de ocho nodos, se activa una señal inicialmente en $a$. Cada paso activa a cualquier nodo con al menos un vecino ya activo en el paso anterior, y la señal no se pierde. Con esa regla todos terminan activados porque la red es conexa. El tiempo mínimo de activación de cada nodo es su distancia desde $a$.

Si la regla exige dos vecinos activos, el resultado cambia. Activar inicialmente $a$ y $b$ permite que $c$ se active en el siguiente paso, pero $u$ sigue viendo sólo un vecino activo y la expansión se detiene. La misma red conexa no garantiza propagación bajo todas las dinámicas. Este ejercicio no describe por sí solo una epidemia ni una decisión humana; aísla cómo una exigencia local de exposición puede impedir atravesar una conexión escasa.

La observación de personas similares conectadas tampoco identifica difusión causal. Pueden haberse elegido por semejanza, compartir un entorno o responder a una misma fuente externa. Para atribuir un cambio a la influencia de la red se necesita distinguir esas alternativas. Un diagrama de contactos especifica oportunidades de interacción; no demuestra cuáles se realizaron ni qué efecto tuvieron. (Shalizi y Thomas, confusión entre semejanza e influencia).

126.5. Lo que una representación de red omite#

La primera decisión de una red observada es su frontera. Incluir sólo nodos de una institución puede hacer parecer desconectadas regiones comunicadas mediante personas externas. Medir únicamente relaciones declaradas o registradas puede omitir otras. Una conexión ausente puede significar ausencia comprobada o falta de observación; el mismo cero en una matriz no permite distinguir ambas situaciones.

El umbral de inclusión también modifica la estructura. Si se dibuja una arista sólo cuando hay al menos cinco intercambios durante un mes, bajar el umbral a uno puede unir componentes y cambiar centralidades. El umbral no es una propiedad matemática universal. Debe vincularse al significado de la relación y comprobarse cuánto dependen las conclusiones de decisiones plausibles de registro.

Algunas interacciones reúnen varios participantes simultáneamente. Una reunión con cuatro personas puede representarse como seis aristas entre pares, pero esa proyección crea un triángulo entre cualquier terna sin demostrar contactos separados. Puede convenir una red bipartita, con nodos de personas y de reuniones, o un hipergrafo, cuyas conexiones reúnen más de dos nodos. La representación se elige según qué información debe conservar, no según qué dibujo resulta más familiar. (Battiston y colaboradores, interacciones de varios participantes).

El tamaño y la disposición visual pueden producir impresiones que no pertenecen a los datos. Un algoritmo de dibujo puede separar grupos o colocar un nodo en el centro de la página sin que exista una distancia física o una centralidad calculada que lo justifique. En una figura deben distinguirse el código de conexión, los atributos medidos y las decisiones de diseño.

Una interpretación defendible especifica los nodos, la relación, su sentido, las unidades de peso, la ventana temporal y lo que no se observó. Después aplica la medida adecuada y compara representaciones alternativas cuando las omisiones puedan cambiar el resultado. La incertidumbre de una red no reside sólo en valores numéricos: también puede estar en qué conexiones existen y en qué proceso autorizan a modelar. El siguiente capítulo formaliza el razonamiento sobre resultados inciertos sin convertir esa incertidumbre en una propiedad misteriosa del dibujo.

Preguntas de transferencia#

¿Tres vecinos hacen más importante un nodo que dos?#

En la red construida, $c$ tiene grado tres y $u$ grado dos. ¿El grado decide cuál importa más para comunicar las regiones?

¿Más capacidad de entrada aumenta siempre la entrega?#

Ejemplo construido. En la red de flujo del capítulo se aumenta la capacidad $s\to A$ de cuatro a diez litros por minuto y se mantienen todas las demás. ¿Puede superarse la entrega de seis?

¿Un camino agregado garantiza una transmisión?#

Ejemplo construido. $A$ y $B$ se comunican después de que $B$ y $C$ tuvieron su único contacto. Un mensaje empieza en $A$. ¿El camino $A-B-C$ demuestra que llega a $C$?

¿Una matriz al cuadrado cuenta caminos simples?#

Una red tiene sólo dos nodos unidos por una arista no dirigida. Su matriz de adyacencia es $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$. ¿Qué representa $A^2=I$?

Fuentes y lecturas del capítulo#

Oscar Levin. Discrete Mathematics: An Open Introduction, cuarta edición. Se consultaron Problems and Definitions, Trees y Euler Trails and Circuits para las convenciones de grafo simple, caminos, árboles y recorridos que cubren aristas. (Definiciones; árboles; recorridos eulerianos).

MIT OpenCourseWare. Design and Analysis of Algorithms, lección 13, Network Flow (2015). Notas consultadas sobre restricciones de capacidad, conservación, cortes y el teorema de flujo máximo y corte mínimo. (Documento).

M. E. J. Newman. The mathematics of networks. Texto del autor alojado por la Universidad de Michigan, consultado para centralidades y distancias de red. Las medidas describen preguntas diferentes y dependen de convenciones explícitas. (Documento).

Mikko Kivelä, Alexandre Arenas, Marc Barthelemy, James P. Gleeson, Yamir Moreno y Mason A. Porter. Multilayer Networks, versión de autor en arXiv. Marco consultado para conservar tipos de relación y distinguir capas y conexiones entre capas. (Documento).

Petter Holme y Jari Saramäki. Temporal Networks (2012), versión de autor en arXiv. Se consultó la discusión de recorridos que respetan los tiempos de contacto y de la información perdida por agregación. (Documento).

Santo Fortunato y Darko Hric. Community detection in networks: A user guide, Physics Reports 659, 1–44 (2016). Se consultó la ficha de autor y su resumen sobre definiciones y validación de comunidades; no se atribuyen a esa lectura detalles de algoritmos no examinados. (Registro y resumen).

Cosma Rohilla Shalizi y Andrew C. Thomas. Homophily and Contagion Are Generically Confounded in Observational Social Network Studies, Sociological Methods and Research 40, 211–239 (2011). Registro y resumen consultados sobre los supuestos necesarios para distinguir selección por semejanza e influencia causal. (Registro y resumen).

Federico Battiston y colaboradores. Networks beyond pairwise interactions: structure and dynamics (2020). Registro y resumen consultados para la diferencia entre interacciones de grupo y representaciones basadas exclusivamente en pares. (Registro y resumen).

Bibliografía de la parte XII · Bibliografía general

Última revisión editorial

29 de septiembre de 2026

Cierre de contenidos

29 de septiembre de 2026