Centralidad de Grado
La centralidad de grado es una medida en teoría de grafos que evalúa la importancia de un vértice dentro de un grafo basado en el número de conexiones directas que tiene. En otras palabras, mide cuántas aristas están conectadas a un vértice dado. Es una de las medidas más simples y directas para determinar la prominencia de un vértice en un grafo.
Definición Matemática
En un grafo no dirigido \( G = (V, E) \), la centralidad de grado de un vértice \( v \in V \) se define como el número de aristas incidentes a \( v \). Se puede expresar matemáticamente como:
\[
C_D(v) = \deg(v)
\]
donde \( \deg(v) \) es el grado del vértice \( v \), es decir, el número de aristas que están conectadas al vértice \( v \).
En un grafo dirigido, la centralidad de grado se puede calcular en dos formas diferentes:
1. Grado de Entrada (In-Degree): El número de aristas que entran al vértice \( v \). Se denota como:
\[
\text{In-Degree}(v) = \text{deg}_{\text{in}}(v)
\]
2. Grado de Salida (Out-Degree): El número de aristas que salen del vértice \( v \). Se denota como:
\[
\text{Out-Degree}(v) = \text{deg}_{\text{out}}(v)
\]
La centralidad de grado en un grafo dirigido se puede definir entonces como:
\[
C_D(v) = \text{In-Degree}(v) + \text{Out-Degree}(v)
\]
Propiedades Matemáticas
1. Rango de Valores:
- En un grafo no dirigido, el valor de centralidad de grado varía entre 0 (para vértices sin aristas) y \( |V| - 1 \) (para vértices conectados a todos los demás vértices).
- En un grafo dirigido, el rango puede ser desde 0 hasta \( |V| - 1 \), dependiendo de la estructura del grafo y las conexiones dirigidas.
2. Simetría en Grafos No Dirigidos:
La centralidad de grado es simétrica en grafos no dirigidos, ya que el número de aristas incidentes a un vértice es igual sin importar la dirección de las aristas.
3. Impacto en Grafos Dirigidos:
En grafos dirigidos, la centralidad de grado considera tanto el grado de entrada como el de salida, reflejando el número total de conexiones que un vértice tiene, ya sea recibiendo o enviando aristas.
Aplicaciones
- Análisis de Redes Sociales: Identificar los individuos más influyentes en una red social basada en el número de conexiones directas que tienen.
- Redes de Comunicación: Determinar los nodos más centrales en una red de comunicación, que pueden ser cruciales para la difusión de información.
- Biología Computacional: Identificar genes o proteínas centrales en redes biológicas según su número de interacciones.
La centralidad de grado proporciona una visión básica pero importante sobre la prominencia de un vértice en un grafo, permitiendo identificar los vértices más conectados y, por lo tanto, los más influyentes en la red.
Centralidad de Cercanía
La centralidad de cercanía es una medida en teoría de grafos que evalúa la importancia de un vértice en un grafo en función de la distancia promedio desde ese vértice a todos los demás vértices. La idea es que un vértice que puede alcanzar a otros vértices con menos pasos (o aristas) tiene una mayor centralidad de cercanía, indicando su capacidad para llegar rápidamente a otros nodos en la red.
Definición Matemática
Dado un grafo \( G = (V, E) \), donde \( V \) es el conjunto de vértices y \( E \) es el conjunto de aristas, la centralidad de cercanía de un vértice \( v \in V \) se define como el inverso de la suma de las distancias desde \( v \) a todos los demás vértices en el grafo. Matemáticamente, la centralidad de cercanía se expresa como:
\[
C_C(v) = \frac{1}{\sum_{u \in V} d(v, u)}
\]
donde \( d(v, u) \) es la distancia entre los vértices \( v \) y \( u \), definida como el número mínimo de aristas en el camino más corto que conecta \( v \) y \( u \).
En un grafo no conexo, la suma de distancias puede incluir distancias infinitas (o valores grandes), lo que puede llevar a una centralidad de cercanía indefinida para esos vértices. En tales casos, se pueden usar fórmulas modificadas o normalizar los valores de acuerdo con la estructura del grafo.
Propiedades Matemáticas
1. Rango de Valores:
- La centralidad de cercanía está relacionada inversamente con la distancia total desde un vértice a todos los demás. Vértices con menor suma de distancias tienen mayor centralidad de cercanía.
- El rango de valores depende de la estructura del grafo y la conectividad. En un grafo completo, todos los vértices tienen la misma centralidad de cercanía máxima, mientras que en un grafo no conexo, algunos vértices pueden tener una centralidad indefinida.
2. Escalabilidad:
- La centralidad de cercanía se ve afectada por el tamaño del grafo, ya que la suma de distancias aumenta con el número de vértices y puede ser computacionalmente costosa para grafos grandes.
3. Sensibilidad a la Estructura del Grafo:
- La centralidad de cercanía puede cambiar drásticamente con cambios en la estructura del grafo. La adición o eliminación de aristas puede afectar las distancias entre vértices y, por lo tanto, la centralidad de cercanía.
4. Aplicaciones:
- Redes de Comunicación: Identificar los nodos que tienen la capacidad de alcanzar rápidamente a todos los otros nodos, lo que puede ser crucial para optimizar la eficiencia de la red.
- Análisis de Redes Sociales: Determinar qué individuos tienen una posición central en términos de accesibilidad a otros miembros de la red.
- Optimización de Rutas: Encontrar puntos estratégicos para la ubicación de recursos o centros en redes de transporte y distribución.
La centralidad de cercanía proporciona una medida de qué tan bien posicionado está un vértice para acceder a otros vértices en el grafo, reflejando su capacidad para actuar como un intermediario eficiente o influir en la comunicación en la red.
Centralidad de Intermediación (Betweenness)
La centralidad de intermediación, también conocida como centralidad de betweenness, es una medida en teoría de grafos que cuantifica el grado en que un vértice actúa como intermediario en los caminos más cortos entre otros vértices. En otras palabras, mide cuántas veces un vértice se encuentra en el camino más corto entre pares de otros vértices.
Definición Matemática
Para un grafo \( G = (V, E) \), donde \( V \) es el conjunto de vértices y \( E \) es el conjunto de aristas, la centralidad de intermediación de un vértice \( v \in V \) se define mediante el conteo de caminos más cortos que pasan a través de \( v \). Matemáticamente, la centralidad de intermediación de un vértice \( v \) se expresa como:
\[
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}
\]
donde:
- \( \sigma_{st} \) es el número total de caminos más cortos entre los vértices \( s \) y \( t \).
- \( \sigma_{st}(v) \) es el número de estos caminos que pasan a través del vértice \( v \).
La suma se realiza sobre todos los pares de vértices \( s \) y \( t \) en el grafo, excluyendo \( v \). La centralidad de intermediación de un vértice mide cuán frecuentemente actúa como intermediario en los caminos más cortos entre otros pares de vértices.
Propiedades Matemáticas
1. Rango de Valores:
- La centralidad de intermediación puede variar de 0 (para vértices que no están en ningún camino más corto entre otros pares de vértices) hasta un valor máximo que depende de la estructura del grafo y la conectividad entre sus vértices.
2. Sensibilidad a la Estructura del Grafo:
- La centralidad de intermediación es sensible a la estructura global del grafo. La adición o eliminación de aristas puede cambiar significativamente la centralidad de intermediación de un vértice, especialmente en redes densamente conectadas.
3. Relación con la Comunicación y el Control:
- Los vértices con alta centralidad de intermediación suelen tener un papel clave en la comunicación dentro de la red, ya que actúan como puentes entre diferentes partes del grafo. En redes sociales, por ejemplo, estos vértices pueden ser cruciales para la difusión de información.
4. Cálculo y Complejidad:
- El cálculo de la centralidad de intermediación puede ser computacionalmente costoso, especialmente en grafos grandes, ya que requiere encontrar todos los caminos más cortos entre pares de vértices y contar cuántos de estos pasan a través de un vértice dado.
Aplicaciones
- Redes Sociales: Identificar individuos que tienen un papel clave en la difusión de información o que tienen una posición estratégica en la red social.
- Redes de Transporte: Determinar los puntos críticos que conectan diferentes partes de una red de transporte, como carreteras o líneas de ferrocarril.
- Biología Computacional: Identificar proteínas o genes que actúan como intermediarios cruciales en redes de interacciones biológicas.
La centralidad de intermediación proporciona una medida importante sobre el papel de un vértice en la conexión de diferentes partes de un grafo, revelando su influencia en la comunicación y la transmisión de información dentro de la red.