4  Teoría de Grafos, Cadenas de Markov y PageRank

4.1 Grafos dirigidos y no dirigidos, matrices de adyacencia

La modelación matemática de redes de transporte, sistemas logísticos y flujos de distribución requiere un lenguaje estructural que permita representar de manera abstracta las relaciones de conectividad entre entidades discretas. La teoría de grafos proporciona este marco formal, ofreciendo herramientas para analizar propiedades topológicas, optimizar rutas y caracterizar la dinámica de procesos definidos sobre redes (Bondy y Murty 2008). En el contexto de la logística humanitaria en Chiapas, los grafos constituyen la base sobre la cual se construyen los algoritmos de priorización territorial y evaluación de accesibilidad desarrollados en este capítulo.

4.1.1 Definiciones fundamentales

Definición 1.1 (Grafo no dirigido). Un grafo no dirigido es un par ordenado \(G = (V, E)\), donde:

  • \(V = \{v_1, v_2, \dots, v_n\}\) es un conjunto finito no vacío de vértices o nodos,
  • \(E \subseteq \{\{u,v\} : u, v \in V, u \neq v\}\) es un conjunto de aristas, cada una representada como un par no ordenado de vértices distintos.

Cuando \(\{u,v\} \in E\), se dice que \(u\) y \(v\) son adyacentes o vecinos, y que la arista es incidente en ambos vértices. En aplicaciones de transporte terrestre, los vértices representan municipios, centros de distribución o intersecciones viales, mientras que las aristas modelan conexiones físicas bidireccionales entre ellos. Para más detalles, puede constultarse (Taha 2017).

Definición 1.2 (Grafo dirigido). Un grafo dirigido (o digrafo) es un par ordenado \(D = (V, A)\), donde:

  • \(V\) es un conjunto finito no vacío de vértices,
  • \(A \subseteq V \times V\) es un conjunto de arcos, cada uno representado como un par ordenado \((u,v)\) con \(u, v \in V\) y \(u \neq v\).

El arco \((u,v)\) se interpreta como una conexión unidireccional desde el vértice origen \(u\) hacia el vértice destino \(v\). En redes logísticas, los grafos dirigidos permiten modelar restricciones de sentido único, pendientes pronunciadas que afectan la transitabilidad en una dirección, o flujos asimétricos de recursos (Newman 2018).

4.1.2 Matriz de adyacencia: representación algebraica de la conectividad

La estructura de un grafo finito puede codificarse de manera compacta mediante su matriz de adyacencia, objeto central en el análisis computacional de redes.

Definición 1.3 (Matriz de adyacencia no dirigida). Sea \(G = (V, E)\) un grafo no dirigido con \(|V| = n\). La matriz de adyacencia de \(G\) es la matriz \(A \in \{0,1\}^{n \times n}\) definida por: \[ a_{ij} = \begin{cases} 1, & \text{si } \{v_i, v_j\} \in E, \\ 0, & \text{en caso contrario}. \end{cases} \] Dado que las aristas son no dirigidas, \(A\) es simétrica: \(a_{ij} = a_{ji}\) para todo \(i,j\) (West 2017).

Definición 1.4 (Matriz de adyacencia dirigida). Sea \(D = (V, A)\) un grafo dirigido con \(|V| = n\). La matriz de adyacencia de \(D\) es la matriz \(A \in \{0,1\}^{n \times n}\) definida por: \[ a_{ij} = \begin{cases} 1, & \text{si } (v_i, v_j) \in A, \\ 0, & \text{en caso contrario}. \end{cases} \] En este caso, \(A\) no es necesariamente simétrica, reflejando la asimetría potencial en las conexiones de la red (Taha 2017).

4.1.3 Propiedades algebraicas y su interpretación en redes

La matriz de adyacencia no solo codifica la conectividad inmediata, sino que sus potencias revelan información sobre caminos de longitud mayor.

Proposición 1.1 (Caminos y potencias de la matriz de adyacencia). Sea \(A\) la matriz de adyacencia de un grafo (dirigido o no dirigido) con \(n\) vértices. Para cualquier entero \(k \geq 1\), la entrada \((i,j)\) de la matriz \(A^k\) satisface: \[ (A^k)_{ij} = \text{número de caminos de longitud } k \text{ desde } v_i \text{ hasta } v_j. \] Demostración. Por inducción sobre \(k\). Para \(k=1\) es la definición de adyacencia. Suponiendo válido para \(k\), se tiene: \[ (A^{k+1})_{ij} = \sum_{\ell=1}^n (A^k)_{i\ell} \, a_{\ell j}, \] que cuenta todos los caminos de longitud \(k\) desde \(v_i\) a \(v_\ell\), seguidos de un arco desde \(v_\ell\) a \(v_j\). \(\square\)

Esta propiedad fundamenta algoritmos de alcanzabilidad, detección de componentes conexas y cálculo de centralidad, todos ellos relevantes para la planificación logística territorial (Bondy y Murty 2008).

4.1.4 Grafos ponderados y aplicación a redes de transporte

En aplicaciones reales, las conexiones entre nodos poseen atributos cuantitativos (distancia, tiempo, costo, capacidad) que deben incorporarse al modelo.

Definición 1.5 (Grafo ponderado). Un grafo ponderado es una terna \(G = (V, E, w)\), donde \((V,E)\) es un grafo y \(w: E \to \mathbb{R}^+\) es una función de pesos que asigna a cada arista un valor positivo. La matriz de pesos \(W \in \mathbb{R}^{n \times n}\) se define como: \[ w_{ij} = \begin{cases} w(\{v_i,v_j\}), & \text{si } \{v_i,v_j\} \in E, \\ 0, & \text{en caso contrario}. \end{cases} \]

En la red territorial de Chiapas, el peso \(w_{ij}\) representa la distancia tridimensional \(d_{ij}^{(3D)}\) entre municipios, incorporando explícitamente las variaciones topográficas del terreno. Esta métrica es fundamental para estimar con precisión los costos logísticos y los tiempos de respuesta en escenarios de emergencia.

4.1.5 Conexión con la optimización de rutas

La representación matricial de grafos ponderados permite formular problemas de optimización de rutas como programas lineales o algoritmos de búsqueda en grafos. Por ejemplo, el problema de encontrar la ruta de menor costo entre un origen \(s\) y un destino \(t\) se expresa como: \[ \min_{\mathbf{x}} \sum_{(i,j) \in E} w_{ij} x_{ij}, \quad \text{sujeto a restricciones de flujo}, \] donde \(x_{ij} \in \{0,1\}\) indica si el arco \((i,j)\) pertenece a la ruta óptima. Algoritmos clásicos como Dijkstra o Bellman-Ford operan directamente sobre la estructura de adyacencia ponderada para resolver este problema en tiempo polinomial (Taha 2017; Cormen et al. 2022).

En el contexto de esta tesis, la matriz de pesos derivada de distancias 3D constituye el insumo principal para la construcción de la matriz de transición estocástica utilizada en el algoritmo PageRank, cerrando así el vínculo entre la teoría de grafos, la modelación geométrica del terreno y la priorización logística territorial.

4.2 Redes ponderadas y aplicaciones a redes de transporte

La representación binaria de la conectividad mediante grafos no ponderados resulta insuficiente para modelar sistemas logísticos reales, donde las conexiones entre nodos poseen atributos cuantitativos que determinan la intensidad del flujo, la accesibilidad y la vulnerabilidad estructural. Las redes ponderadas extienden el marco de la teoría de grafos al incorporar funciones de peso que codifican distancias, tiempos de tránsito, costos operativos o dificultades de acceso, permitiendo así un análisis más realista de la topología territorial (Newman 2018). En el contexto de la distribución de ayuda humanitaria en Chiapas, la ponderación adecuada de la red es fundamental para priorizar municipios estratégicos y evaluar patrones de conectividad bajo restricciones topográficas.

4.2.1 Definición formal de redes ponderadas

Definición 1.6 (Red ponderada dirigida). Una red ponderada dirigida es una cuaterna \(G = (V, A, w, \mathcal{W})\), donde:

  • \((V, A)\) es un grafo dirigido con \(|V| = n\) vértices y \(|A| = m\) arcos,
  • \(\mathcal{W} \subseteq \mathbb{R}^+\) es un conjunto de valores de peso admisibles,
  • \(w: A \to \mathcal{W}\) es una función de peso que asigna a cada arco \((v_i, v_j) \in A\) un valor \(w_{ij} \in \mathcal{W}\).

Cuando la red modela un sistema de transporte terrestre, el peso \(w_{ij}\) puede interpretarse como:

  • Distancia física: \(w_{ij} = d_{ij}^{(3D)}\) (kilómetros), incorporando variaciones topográficas,
  • Tiempo de tránsito: \(w_{ij} = t_{ij}\) (minutos), estimado a partir de velocidades promedio por tipo de vía,
  • Dificultad de acceso: \(w_{ij} = \delta_{ij}\) (índice adimensional), derivado de pendientes, estado de la vía o exposición a riesgos naturales (Taha 2017).

La elección de la métrica de peso determina el tipo de análisis estructural que puede realizarse sobre la red, y debe alinearse con los objetivos operativos del sistema logístico.

4.2.2 Representación matricial y transformación a probabilidades de transición

La estructura de una red ponderada puede codificarse mediante su matriz de pesos \(W \in \mathbb{R}^{n \times n}\), definida como: \[ w_{ij} = \begin{cases} w(v_i, v_j), & \text{si } (v_i, v_j) \in A, \\ 0, & \text{en caso contrario}. \end{cases} \] A diferencia de la matriz de adyacencia binaria, \(W\) contiene información cuantitativa que habilita el análisis de flujos potenciales, centralidad y resiliencia estructural (Bondy y Murty 2008).

Para aplicar métodos basados en cadenas de Markov, como el algoritmo PageRank, es necesario transformar los pesos de distancia en probabilidades de transición. Una estrategia común consiste en utilizar el inverso de la distancia como medida de influencia o accesibilidad: \[ \tilde{w}_{ij} = \begin{cases} \displaystyle \frac{1}{w_{ij}}, & \text{si } (v_i, v_j) \in A, \\ 0, & \text{en caso contrario}. \end{cases} \] La matriz de transición estocástica \(Q\) se obtiene normalizando por columnas: \[ q_{ij} = \frac{\tilde{w}_{ij}}{\sum_{k=1}^n \tilde{w}_{kj}}, \quad \text{si } \sum_{k} \tilde{w}_{kj} > 0. \] Esta transformación garantiza que \(Q\) sea una matriz estocástica por columnas (\(\sum_i q_{ij} = 1\)), condición necesaria para interpretarla como el núcleo de un proceso de Markov discreto (Brin y Page 1998).

4.2.3 Aplicaciones a redes de transporte terrestre

En logística humanitaria, las redes ponderadas permiten cuantificar propiedades estructurales que son críticas para la planificación estratégica:

4.2.3.1 1. Medición de centralidad e influencia estructural

El peso de las aristas no solo refleja distancia física, sino también la intensidad de la interacción entre nodos. Municipios con múltiples conexiones de bajo peso (corta distancia, alta accesibilidad) tienden a acumular mayor flujo potencial, convirtiéndose en centros naturales de distribución. Esta propiedad se cuantifica mediante medidas de centralidad espectral, como el vector PageRank, que asigna a cada nodo una puntuación proporcional a su importancia relativa en la red (Borgatti 2005).

4.2.3.2 2. Evaluación de vulnerabilidad y robustez

La sensibilidad de la red ante la interrupción de arcos o nodos puede analizarse mediante variaciones en la distribución estacionaria. Sea \(\pi\) el vector de centralidad original y \(\pi^{(e)}\) el vector tras eliminar el arco \(e\). El impacto relativo se mide como: \[ \Delta^{(e)} = \|\pi - \pi^{(e)}\|_1 = \sum_{i=1}^n |\pi_i - \pi_i^{(e)}|. \] Valores elevados de \(\Delta^{(e)}\) identifican enlaces críticos cuya falla redistribuye significativamente la importancia estructural de los municipios, guiando así prioridades de mantenimiento o rutas de contingencia (Barabási 2016).

4.2.3.3 3. Accesibilidad ponderada y equidad territorial

La distribución de pesos en la red refleja desigualdades geográficas en el acceso a servicios. Un análisis de los pesos de arista salientes por municipio permite identificar regiones con conectividad sistémicamente deficiente, incluso cuando la red es topológicamente conexa. Esta información es esencial para diseñar políticas de inclusión logística y localizar centros de almacenamiento intermedios.

4.2.4 Conexión con el algoritmo PageRank: centralidad estructural

El algoritmo PageRank opera exclusivamente como un medidor de centralidad estructural. Su propósito es cuantificar la importancia relativa de cada municipio dentro de la red territorial, basándose en su posición topológica y en la calidad de sus conexiones ponderadas.

Matemáticamente, PageRank resuelve el sistema de ecuaciones en diferencias: \[ \pi = P\pi, \quad \sum_{i=1}^n \pi_i = 1, \quad \pi_i > 0, \] donde \(P\) es la matriz de transición modificada con factor de amortiguamiento \(p \in (0,1)\). La componente \(\pi_i\) representa la probabilidad estacionaria de que un “navegante aleatorio” se encuentre en el municipio \(i\) en el largo plazo. Valores altos de \(\pi_i\) indican nodos que actúan como concentradores naturales de flujo, independientemente de que no sean necesariamente puntos de origen o destino en una misión específica.

La transformación de pesos de distancia a probabilidades inversas (\(w_{ij}^{-1}\)) asegura que la proximidad geográfica y la facilidad de tránsito se traduzcan directamente en mayor influencia dentro del proceso estocástico. Municipios bien conectados a otros municipios igualmente bien conectados acumulan iterativamente mayor probabilidad estacionaria, revelando así la jerarquía implícita de la red territorial.

En el estudio de caso de Chiapas, los pesos \(w_{ij}\) se definen como las distancias tridimensionales \(d_{ij}^{(3D)}\) calculadas en la Sección 6.3, garantizando que la priorización de municipios mediante PageRank incorpore explícitamente las barreras topográficas que caracterizan la región. Esta integración entre modelación geométrica, teoría de grafos ponderados y procesos estocásticos constituye el núcleo analítico sobre el cual se construye la estrategia logística territorial.

4.3 Cadenas de Markov de tiempo discreto

Las cadenas de Markov de tiempo discreto constituyen uno de los pilares fundamentales de la teoría de procesos estocásticos, proporcionando un marco matemático riguroso para modelar sistemas que evolucionan en pasos temporales discretos con la propiedad de falta de memoria. En el contexto de la priorización territorial y el análisis de redes de transporte, estas cadenas permiten representar el movimiento de un agente aleatorio a través de los nodos de una red, donde la probabilidad de transición entre municipios depende exclusivamente del estado actual y de la estructura de conectividad ponderada. Para más detalles, (Blanco Castañeda 2013; Rincón 2012).

4.3.1 Definición formal y propiedad de Markov

Definición 1.7 (Cadena de Markov de tiempo discreto). Sea \(\{X_n\}_{n \geq 0}\) una sucesión de variables aleatorias definidas sobre un espacio de probabilidad \((\Omega, \mathcal{F}, \mathbb{P})\), que toman valores en un espacio de estados finito \(\mathcal{S} = \{1, 2, \dots, N\}\). Se dice que \(\{X_n\}\) es una cadena de Markov de tiempo discreto si satisface la propiedad de Markov: \[ \mathbb{P}(X_{n+1} = j \mid X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = \mathbb{P}(X_{n+1} = j \mid X_n = i), \] para todo \(n \geq 0\) y toda secuencia de estados \(i_0, \dots, i_{n-1}, i, j \in \mathcal{S}\). Esta propiedad establece que la distribución condicional del estado futuro depende únicamente del estado presente, siendo condicionalmente independiente de la trayectoria pasada (Rincón 2012).

Cuando las probabilidades de transición no dependen del instante \(n\), la cadena se denomina homogénea. En este caso, se definen las probabilidades de transición en un paso como: \[ p_{ij} = \mathbb{P}(X_{n+1} = j \mid X_n = i), \quad i,j \in \mathcal{S}. \]

4.3.2 Matriz de transición y ecuaciones de Chapman-Kolmogorov

Las probabilidades \(p_{ij}\) se organizan en la matriz de transición \(P = [p_{ij}]_{i,j \in \mathcal{S}} \in \mathbb{R}^{N \times N}\), la cual satisface:

  1. \(p_{ij} \geq 0\) para todo \(i,j\),
  2. \(\sum_{j=1}^{N} p_{ij} = 1\) para todo \(i\) (matriz estocástica por filas).

La probabilidad de transición en \(n\) pasos, denotada \(p_{ij}^{(n)} = \mathbb{P}(X_n = j \mid X_0 = i)\), satisface las ecuaciones de Chapman-Kolmogorov: \[ p_{ij}^{(m+n)} = \sum_{k=1}^{N} p_{ik}^{(m)} p_{kj}^{(n)}, \quad \forall m,n \geq 0. \] En notación matricial, esto implica que \(P^{(m+n)} = P^{(m)} P^{(n)}\), y en particular \(P^{(n)} = P^n\). Esta propiedad algebraica es fundamental para el cálculo de distribuciones a múltiples pasos y constituye la base teórica de los algoritmos iterativos de cálculo de centralidad en redes (Grinstead y Snell 2009).

4.3.3 Clasificación de estados y propiedades estructurales

La topología de la matriz de transición determina el comportamiento asintótico de la cadena. Se introducen las siguientes nociones estructurales:

  • Accesibilidad y comunicación: Un estado \(j\) es accesible desde \(i\) (denotado \(i \to j\)) si existe \(n \geq 0\) tal que \(p_{ij}^{(n)} > 0\). Dos estados \(i\) y \(j\) comunican (\(i \leftrightarrow j\)) si \(i \to j\) y \(j \to i\). Esta relación es de equivalencia y particiona \(\mathcal{S}\) en clases de comunicación.
  • Irreducibilidad: La cadena es irreducible si todos sus estados comunican entre sí, es decir, existe una única clase de comunicación igual a \(\mathcal{S}\).
  • Periodicidad: El período de un estado \(i\) se define como \(d(i) = \gcd\{n \geq 1 : p_{ii}^{(n)} > 0\}\). Si \(d(i) = 1\), el estado es aperiódico. En cadenas irreducibles, todos los estados comparten el mismo período (Norris 1998).
  • Recurrencia y transitoriedad: Un estado \(i\) es recurrente si \(\sum_{n=1}^\infty p_{ii}^{(n)} = \infty\), y transiente en caso contrario. En espacios de estados finitos, la irreducibilidad implica que todos los estados son recurrentes positivos.

4.3.4 Distribución estacionaria y convergencia ergódica

El comportamiento a largo plazo de una cadena irreducible y aperiódica se caracteriza por la existencia de una distribución estacionaria \(\pi = (\pi_1, \dots, \pi_N)\), que satisface el sistema lineal: \[ \pi = \pi P, \quad \sum_{i=1}^{N} \pi_i = 1, \quad \pi_i > 0 \; \forall i. \] El teorema ergódico para cadenas de Markov finitas establece que, bajo irreducibilidad y aperiodicidad, la distribución del estado converge a \(\pi\) independientemente de la distribución inicial \(\pi^{(0)}\): \[ \lim_{n \to \infty} \pi^{(0)} P^n = \pi. \] Además, \(\pi_i\) posee una interpretación frecuencia robusta: representa la fracción de tiempo que la cadena ocupa el estado \(i\) en el límite \(n \to \infty\) (Durrett 2019).

4.3.5 Conexión con el algoritmo PageRank

La estructura matemática desarrollada en esta sección es exactamente la que sustenta el algoritmo PageRank. En la red territorial de Chiapas, los municipios se interpretan como estados de una cadena de Markov discreta finita, y la matriz de transición \(P\) se construye a partir de los pesos de conectividad vial transformados mediante el inverso de la distancia tridimensional y normalizados por columnas (convención computacional equivalente a la transposición de la formulación teórica por filas).

La introducción del factor de amortiguamiento \(p \in (0,1)\) garantiza que la matriz resultante sea estrictamente positiva, asegurando así irreducibilidad y aperiodicidad. Bajo estas condiciones, el teorema ergódico valida la convergencia del método de potencias \(\pi^{(k+1)} = P \pi^{(k)}\) hacia un único vector estacionario \(\pi\), el cual cuantifica la importancia relativa de cada municipio dentro de la red. Esta conexión formal entre teoría de cadenas de Markov y centralidad espectral proporciona el sustento matemático riguroso para la priorización logística desarrollada en los capítulos siguientes.

4.4 Teorema de Perron-Frobenius y su aplicación al PageRank

El análisis espectral de matrices no negativas constituye el fundamento algebraico que garantiza la existencia, unicidad y convergencia numérica del vector de centralidad en redes complejas. El teorema de Perron-Frobenius, originalmente formulado para matrices con entradas estrictamente positivas y extendido posteriormente a matrices irreducibles, proporciona las condiciones necesarias y suficientes para asegurar que una matriz de transición estocástica posea un único vector propio dominante con componentes estrictamente positivas. Esta propiedad es la piedra angular matemática que valida el algoritmo PageRank y justifica el uso del método de potencias para su cálculo computacional (Meyer 2000).

4.4.1 Notación y clases de matrices no negativas

Sea \(A \in \mathbb{R}^{n \times n}\) una matriz con entradas reales. Se establecen las siguientes definiciones estructurales:

  • Matriz no negativa: \(A \geq 0\) si \(a_{ij} \geq 0\) para todo \(i,j \in \{1,\dots,n\}\).
  • Matriz positiva: \(A > 0\) si \(a_{ij} > 0\) para todo \(i,j\).
  • Matriz irreducible: \(A\) es irreducible si para cada par \((i,j)\) existe un entero \(k \geq 1\) tal que \((A^k)_{ij} > 0\). Esta condición equivale a que el grafo dirigido asociado sea fuertemente conexo.
  • Matriz primitiva: \(A\) es primitiva si existe \(m \in \mathbb{N}\) tal que \(A^m > 0\). En el contexto de cadenas de Markov, la primitividad garantiza aperiodicidad y convergencia geométrica de las potencias de la matriz (Horn y Johnson 2012).

4.4.2 Enunciado del teorema

Teorema 1.1 (Perron-Frobenius para matrices estocásticas primitivas). Sea \(P \in \mathbb{R}^{n \times n}\) una matriz estocástica por columnas (\(P \geq 0\), \(\sum_{i=1}^n p_{ij} = 1\)) que es primitiva. Entonces se cumplen las siguientes propiedades:

  1. El radio espectral es \(\rho(P) = 1\).
  2. El valor propio \(\lambda = 1\) es algebraicamente simple y domina estrictamente al resto del espectro: \(|\lambda_i| < 1\) para todo \(\lambda_i \in \sigma(P) \setminus \{1\}\).
  3. Existe un único vector propio derecho \(\pi \in \mathbb{R}^n\) asociado a \(\lambda = 1\), con componentes estrictamente positivas \(\pi_i > 0\) y normalizado tal que \(\sum_{i=1}^n \pi_i = 1\).
  4. Para cualquier vector inicial \(\pi^{(0)} \in \mathbb{R}^n\) con \(\sum \pi_i^{(0)} = 1\), se verifica la convergencia: \[ \lim_{k \to \infty} P^k \pi^{(0)} = \pi. \]

Esbozo de demostración. La igualdad \(\rho(P)=1\) se deduce de la conservación de la norma \(\ell_1\) bajo multiplicación por matrices estocásticas. La positividad estricta de \(P^m\) implica, por el lema de Gelfand y propiedades de conos invariantes, que el subespacio propio asociado a \(\lambda=1\) es unidimensional y que ningún otro valor propio puede alcanzar módulo 1. La convergencia de \(P^k\) sigue de la descomposición de Jordan, donde el bloque asociado a \(\lambda=1\) domina asintóticamente a los bloques contractivos correspondientes a \(|\lambda_i| < 1\) (Meyer 2000). \(\square\)

4.4.3 Aplicación directa al algoritmo PageRank

En el algoritmo PageRank, la matriz de transición modificada (conocida como matriz de Google) se construye a partir de la matriz de conectividad normalizada \(Q\) mediante: \[ G = pQ + (1-p)\mathbf{1}\mathbf{v}^\top, \] donde:

  • \(p \in (0,1)\) es el factor de amortiguamiento (típicamente \(p=0.85\)),
  • \(\mathbf{1} \in \mathbb{R}^n\) es el vector columna de unos,
  • \(\mathbf{v} \in \mathbb{R}^n\) es un vector de probabilidad personalización (\(\mathbf{v} > 0\), \(\sum v_i = 1\); usualmente \(\mathbf{v} = \frac{1}{n}\mathbf{1}\)).

Dado que \(Q \geq 0\), \(p \in (0,1)\) y \(\mathbf{v} > 0\), toda entrada de \(G\) satisface: \[ g_{ij} = p q_{ij} + (1-p) v_j \geq (1-p)v_j > 0. \] Por tanto, \(G\) es una matriz estrictamente positiva y, en consecuencia, primitiva. La aplicación directa del Teorema 2.1 garantiza que:

  1. Existe un único vector estacionario \(\pi > 0\) tal que \(G\pi = \pi\).
  2. El método de potencias \(\pi^{(k+1)} = G\pi^{(k)}\) converge linealmente a \(\pi\) con tasa de convergencia acotada por \(|\lambda_2(G)| \leq p\).
  3. La distribución inicial \(\pi^{(0)}\) es irrelevante para el límite, lo que confiere robustez numérica al algoritmo frente a perturbaciones en la inicialización (Langville y Meyer 2006).

4.4.4 Interpretación en la red territorial de Chiapas

La estructura algebraica de \(G\) no solo valida matemáticamente la existencia del PageRank, sino que explica por qué el factor \(p=0.85\) es óptimo en la práctica: equilibra la fidelidad a la topología de la red vial (\(p\) alto) con una brecha espectral suficientemente amplia (\(1-p\)) para garantizar convergencia rápida en redes de escala municipal. La brecha espectral \(\sigma = 1 - |\lambda_2(G)| \geq 1-p\) determina directamente el número de iteraciones requeridas para alcanzar una tolerancia \(\varepsilon\): \[ \|\pi^{(k)} - \pi\|_1 \leq C \, p^k, \] lo que explica la convergencia observada en menos de 50 iteraciones para la red de 124 municipios.

Este resultado cierra el círculo entre la teoría espectral de matrices no negativas, la ergodicidad de cadenas de Markov y la implementación práctica de algoritmos de centralidad. En el contexto de la logística humanitaria, garantiza que la priorización de municipios sea única, estable y computacionalmente alcanzable, proporcionando una base matemáticamente irreprochable para la toma de decisiones estratégicas en la distribución territorial de ayuda.

4.5 Problemas en redes: nodos colgantes y subgrafos absorbentes

La aplicación de cadenas de Markov y algoritmos de centralidad sobre redes reales enfrenta obstáculos estructurales que, de no tratarse adecuadamente, comprometen la existencia de una distribución estacionaria única y la convergencia numérica del método de potencias. Dos patologías topológicas recurrentes son los nodos colgantes y los subgrafos absorbentes, los cuales violan las hipótesis de irreducibilidad y estocasticidad estricta requeridas para la aplicación del teorema de Perron-Frobenius (Langville y Meyer 2006).

Definición (Nodo colgante). Sea \(G = (V, A)\) un grafo dirigido con \(|V| = n\) y matriz de transición \(Q \in \mathbb{R}^{n \times n}\). Un vértice \(v_j \in V\) se denomina nodo colgante (o dangling node) si su grado de salida es cero, es decir, no existe ningún arco \((v_j, v_k) \in A\). Equivalentemente, la columna \(j\)-ésima de la matriz de adyacencia es idénticamente nula.

En la construcción de la matriz de transición estocástica por columnas, la normalización \(q_{ij} = w_{ij} / \sum_k w_{kj}\) queda indefinida cuando \(\sum_k w_{kj} = 0\). Si se asigna arbitrariamente \(q_{ij} = 0\) para todo \(i\), la matriz deja de ser estocástica: \(\sum_{i=1}^n q_{ij} = 0 < 1\). Esto implica que cada vez que el caminante aleatorio visita \(v_j\), una fracción de probabilidad se “pierde” del sistema, y la norma \(\ell_1\) del vector de estado decae geométricamente: \[ \|\pi^{(k+1)}\|_1 = \sum_{i=1}^n \left| \sum_{j=1}^n q_{ij} \pi_j^{(k)} \right| < \|\pi^{(k)}\|_1. \] La consecuencia teórica es que el radio espectral satisfará \(\rho(Q) < 1\), y el límite \(\lim_{k \to \infty} Q^k \pi^{(0)} = \mathbf{0}\), destruyendo la interpretación probabilística de largo plazo. La corrección estándar en el contexto de PageRank consiste en reemplazar cada columna nula por un vector uniforme \(\mathbf{1}/n\), redistribuyendo equitativamente la probabilidad atrapada hacia todos los nodos de la red (Brin y Page 1998).

Definición (Subgrafo absorbente). Un subconjunto propio no vacío \(S \subset V\) se denomina subgrafo absorbente (o clase cerrada) si para todo \(v_i \in S\) y \(v_k \in V \setminus S\) se cumple \(q_{ki} = 0\). Es decir, no existen arcos salientes de \(S\) hacia el complemento \(V \setminus S\).

Esta estructura implica que la cadena de Markov es reducible. Una vez que el proceso ingresa a \(S\), la probabilidad queda confinada indefinidamente en dicho subconjunto. Desde el punto de vista espectral, la matriz de transición puede permutarse a forma de bloque triangular superior: \[ P = \begin{pmatrix} P_{SS} & P_{S\bar{S}} \\ \mathbf{0} & P_{\bar{S}\bar{S}} \end{pmatrix}, \] donde \(P_{SS}\) es estocástica y \(\mathbf{0}\) refleja la ausencia de flujos hacia el exterior. El teorema de Perron-Frobenius aplicado a \(P\) ya no garantiza un vector estacionario estrictamente positivo sobre \(V\); en su lugar, existen infinitas distribuciones estacionarias soportadas exclusivamente en \(S\), y la convergencia del método de potencias depende críticamente de la distribución inicial \(\pi^{(0)}\) (Meyer 2000). En logística territorial, esto se traduce en que municipios fuera del subgrafo absorbente recibirían puntuación de centralidad nula, distorsionando la priorización operativa.

4.5.1 Corrección unificada mediante el factor de amortiguamiento

Para garantizar convergencia global y unicidad del vector de centralidad, se introduce un mecanismo de teleportación controlado por un parámetro \(p \in (0,1)\). La matriz de Google se define formalmente como: \[ G = pQ' + (1-p)\mathbf{1}\mathbf{v}^\top, \] donde:

  • \(Q'\) es la matriz de transición corregida (columnas nulas reemplazadas por \(\mathbf{1}/n\)),
  • \(\mathbf{v} \in \mathbb{R}^n\) es un vector de probabilidad estrictamente positivo (\(\mathbf{v} > 0\), \(\sum v_i = 1\)),
  • \(\mathbf{1}\mathbf{v}^\top\) es la matriz de rango uno con columnas idénticas a \(\mathbf{v}\).

El término \((1-p)\mathbf{1}\mathbf{v}^\top\) actúa como un operador de perturbación positiva que rompe simultáneamente nodos colgantes y subgrafos absorbentes, asegurando \(g_{ij} \geq (1-p)v_j > 0\) para todo \(i,j\). Por tanto, \(G\) es una matriz estrictamente positiva y, en consecuencia, primitiva. Las hipótesis del teorema de Perron-Frobenius se restauran completamente: existe un único \(\pi > 0\) tal que \(G\pi = \pi\), y la convergencia es lineal con tasa acotada por \(p\) (Langville y Meyer 2006).

4.5.2 Implicaciones para la red territorial de Chiapas

En el análisis empírico de la red vial de los 124 municipios de Chiapas, se verificó la ausencia de nodos colgantes y subgrafos absorbentes, coherente con la conectividad histórica y la estructura radial de la infraestructura estatal. Sin embargo, la incorporación formal del factor de amortiguamiento \(p = 0.85\) en el algoritmo PageRank no es redundante: proporciona robustez estructural frente a escenarios dinámicos como cierres viales por desastres naturales, expansión de la malla municipal o restricciones operativas temporales. Bajo cualquier perturbación que modifique la matriz de adyacencia, la matriz \(G\) mantiene sus propiedades ergódicas, garantizando que la priorización de municipios permanezca matemáticamente consistente y computacionalmente estable.

Esta sección sienta las bases teóricas para el análisis explícito del parámetro \(p\), su impacto en la tasa de convergencia y su interpretación como compromiso entre fidelidad topológica y exploración aleatoria, desarrollado en la siguiente sección.

4.6 Factor de amortiguamiento y matriz de transición modificada

La matriz de transición estocástica derivada directamente de la topología de una red real presenta limitaciones teóricas y numéricas que impiden garantizar la convergencia hacia un único vector de centralidad. Para superar estas deficiencias, el algoritmo PageRank introduce el factor de amortiguamiento \(p \in (0,1)\), un parámetro escalar que modifica la dinámica del proceso estocástico mediante un mecanismo de mezcla entre la estructura de conectividad observada y un salto aleatorio uniforme. Esta sección formaliza la construcción algebraica de la matriz modificada, analiza su impacto en el espectro de valores propios y justifica la selección del valor estándar desde la perspectiva del análisis numérico y la teoría de grafos.

Sea \(Q \in \mathbb{R}^{n \times n}\) la matriz de transición normalizada por columnas, obtenida a partir de la matriz de pesos inversos de la red territorial. La matriz de transición modificada (conocida en la literatura como matriz de Google) se define como: \[ P = pQ + (1-p)E, \] donde \(E = \mathbf{1}\mathbf{v}^\top\) es una matriz de rango uno con columnas idénticas al vector de personalización \(\mathbf{v} \in \mathbb{R}^n\), tal que \(\mathbf{v} > 0\) y \(\sum_{i=1}^n v_i = 1\). En la formulación original de Brin y Page, se adopta la distribución uniforme \(\mathbf{v} = \frac{1}{n}\mathbf{1}\), lo que refleja la hipótesis de un navegante aleatorio que, con probabilidad \(1-p\), reinicia su trayectoria seleccionando cualquier nodo de la red con igual probabilidad (Brin y Page 1998).

La perturbación aditiva \((1-p)E\) transforma radicalmente las propiedades espectrales de \(Q\). Mientras que \(Q\) puede presentar valores propios de módulo unitario, ser reducible o contener nodos colgantes, la matriz \(P\) satisface estrictamente \(P > 0\) para cualquier \(p \in (0,1)\). Por el teorema de Perron-Frobenius, esto garantiza que \(\lambda_1 = 1\) es un valor propio simple, dominante y asociado a un vector propio estrictamente positivo. El resto del espectro se contrae hacia el origen, cumpliendo la cota: \[ |\lambda_k(P)| \leq p, \quad k = 2, \dots, n. \] Esta desigualdad es fundamental para la eficiencia computacional, ya que determina la tasa de convergencia del método de potencias. El error en la iteración \(k\) decae geométricamente como \(\|\pi^{(k)} - \pi\|_1 \leq C \, p^k\), donde \(C\) depende únicamente de la distribución inicial y de la norma del subespacio invariante asociado a los valores propios no dominantes. Por tanto, el parámetro \(p\) controla directamente el compromiso entre velocidad de convergencia y fidelidad a la topología original de la red (Langville y Meyer 2006).

La elección del valor \(p = 0.85\) responde a un equilibrio empírico y teórico ampliamente validado. Valores de \(p\) cercanos a \(1\) preservan con mayor precisión la estructura de conectividad real, pero reducen la brecha espectral \(1 - |\lambda_2(P)|\), incrementando el número de iteraciones requeridas y volviendo el algoritmo sensible a perturbaciones en los pesos de las aristas. Por el contrario, valores pequeños de \(p\) aceleran la convergencia pero diluyen la influencia de la red, haciendo que el vector estacionario se aproxime asintóticamente a \(\mathbf{v}\) y pierda capacidad discriminante entre nodos. El valor \(0.85\) proporciona una brecha espectral de \(0.15\), suficiente para garantizar convergencia en menos de 50 iteraciones en redes de escala municipal, manteniendo simultáneamente una alta correlación con la centralidad estructural real del grafo (Gleich 2015).

En el contexto de la red de transporte de Chiapas, la matriz \(P\) modela un proceso híbrido: en el \(85\%\) de los pasos, el flujo logístico sigue las rutas viales ponderadas por distancia tridimensional; en el \(15\%\) restante, se considera una reasignación probabilística que simula la posibilidad de redirigir recursos hacia cualquier municipio independientemente de la conectividad inmediata. Esta interpretación justifica el uso de PageRank no como un simulador de tráfico determinista, sino como un indicador de robustez estructural, capaz de identificar municipios estratégicos incluso ante fallos parciales de la infraestructura vial o variaciones estacionales en la transitabilidad.

La formalización de la matriz de transición modificada cierra el marco teórico del Capítulo 2, integrando teoría de grafos, álgebra lineal matricial y procesos estocásticos en un modelo coherente y computacionalmente viable. Los conceptos desarrollados en estas secciones se aplican directamente en el Capítulo 4, donde se construye la red territorial de los 124 municipios de Chiapas, se calcula el vector de priorización estructural y se identifican los nodos críticos que guiarán la planificación logística de ayuda humanitaria en escenarios de emergencia.