Centralidad de intermediación

Ejemplo de un mismo grafo donde se visualizan distintas medidas de centralidad:
A) intermediación
B) cercanía
C) vector propio
D) grado
E) centralidad armónica
F) centralidad de Katz
Las tonalidades van del rojo (más centrales) al azul (más periféricos).

Las tonalidades que van desde el rojo (valor 0) hasta el azul (valor máximo) indican la intermediación de los nodos en el grafo.

En análisis de redes sociales, la centralidad de intermediación, o simplemente intermediación (en inglés, betweenness) es una medida de centralidad que cuantifica la frecuencia o el número de veces que un nodo se encuentra entre las geodésicas o caminos más cortos de otros actores. Un actor tendrá una alta intermediación si es un vértice de corte para muchas geodésicas entre actores.

Para Plantilla:Harvtxt, esta medida permite cuantificar el control de un humano en la comunicación existente con otros humanos en una red social. La idea intuitiva es que si se eligen dos nodos al azar, y luego también al azar uno de los eventuales posibles caminos más cortos entre ellos, entonces los nodos con mayor intermediación serán aquellos que aparezcan con mayor probabilidad dentro de este camino.

Historia

En los años 1940,Plantilla:Harvtxt sugirió que los actores ubicados entre muchas geodésicas eran centrales en una red.Plantilla:Harvtxt sugirió que esto podría representar una medida del «estrés» que podían experimentar los actores durante la actividad en la red, mientras que para Plantilla:Harvtxt, estos actores también actuaban como «intermediadores», que podrían negarse a transmitir mensajes, dificultando la comunicación en la red.Plantilla:Harvtxt, por su parte, también destacaron la importancia estructural de este tipo de actores. No obstante lo anterior, la medida fue formalizada más tarde, con Plantilla:Harvtxt y Plantilla:Harvtxt.

Si bien la medida fue inicialmente definida para grafos no dirigidos, una década más tarde,Plantilla:Harvtxt demostró que también funcionaba para grafos dirigidos (o redes sociales asimétricas).

Definición formal

En lo que sigue, se define formalmente un grafo como un par ordenado $G=(V,E)$, donde $V$ es su conjunto de nodos o vértices y $E$ su conjunto de aristas. El número de vértices se denota como $n=|V|$.

Formalmente, la intermediación $C_B(i)$ de un nodo $i$ en una red o grafo se define como:

$C_B(i)=\sum _{j\ne k\in V}\frac{b_{jik}}{b_{jk}}$

donde $b_{jk}$ es el número de caminos más cortos desde el nodo $j$ hasta el nodo $k$, y $b_{jik}$ el número de caminos más cortos desde $j$ hasta $k$ que pasan a través del nodo $i$.

Para normalizar esta medida, y asumiendo que el grafo no tiene bucles o que estos no se consideran, se puede dividir por el mayor número posible de pares de actores, excluyendo el nodo que se está midiendo. Así, por lo tanto, para grafos no dirigidos y dirigidos se obtiene, respectivamente:

$C{\text{'}}_B(i)=\frac{C_B(i)}{(n-1)(n-2)/2}=\frac{2}{(n-1)(n-2)}\cdot \sum _{j\ne k\in V}\frac{b_{jik}}{b_{jk}}$ o bien $C{\text{'}}_B(i)=\frac{C_B(i)}{(n-1)(n-2)}=\frac{1}{(n-1)(n-2)}\cdot \sum _{j\ne k\in V}\frac{b_{jik}}{b_{jk}}$

En su versión normalizada, los valores de la medida siempre varían entre 0 y 1. Por ejemplo, para un grafo estrella, el nodo central tiene intermediación 1 y los nodos periféricos, intermediación 0. Note también que, a diferencia de la medida de cercanía clásica, la intermediación sí se puede calcular sobre grafos disconexos. Los nodos con una alta intermediación suelen jugar un rol crítico en la estructura de la red, especialmente cuando hay grandes flujos de información que son transportados por nodos pertenecientes a grupos compactos. En una red social, este tipo de actores están relacionados con los agujeros estructurales (en inglés, structural holes), es decir, con aquellos nodos de los que depende la integración de algunas componentes de la red. Los nodos que poseen una posición de intermediarios de alguna manera son también controladores o reguladores del flujo de información. Así, en un proceso de difusión, los nodos con una alta intermediación pueden actuar como brókers o «porteros» (en inglés, gatekeepers). Adicionalmente, los actores con una alta intermediación también se pueden considerar como con una alta «influencia interpersonal».

En complejidad computacional, determinar el camino más corto para cada par de nodos de un grafo puede calcularse en tiempo $\mathrm{\Theta }(V^3)$ (por ejemplo, usando el algoritmo de Floyd-Warshall) y utilizando un espacio $\mathrm{\Theta }(V^2)$. En un grafo disperso, el algoritmo de Johnson puede lograr lo mismo en tiempo $O(V^2\log V+VE)$, y si el grafo es sin pesos, se puede lograr en tiempo $O(VE)$ y espacio $O(|V|+|E|)$ utilizando el algoritmo de Brandes.

Variantes de la intermediación

La centralidad de intermediación tiene algunas restricciones. Si bien supone que todas las geodésicas tienen la misma probabilidad de ser elegidas, los actores con un alto grado podrían tener mayor probabilidades de ser elegidos para conectar otros actores, al pertenecer a más geodésicas entre actores. Bajo este razonamiento, solo en las redes regulares todos los actores tendrían la misma probabilidad de ser elegidos. Por otra parte, esta medida solo se centra en las geodésicas, pero en varios contextos (por ejemplo, en redes de telecomunicaciones) es razonable pensar en elegir caminos más largos que las geodésicas.

Plantilla:Harvtxt propuso una versión alternativa de la medida de intermediación, basada en considerar caminos aleatorios del grafo, y no exclusivamente los más cortos. La idea es tomar en cuenta todos los caminos posibles, y calcular la medida de acuerdo a los elegidos aleatoriamente. Formalmente se define como:

$C_{NB}(i)=\sum _{j\ne i\ne k}{R}_{jk}^{(i)}$

donde $R^{(i)}$ es la matriz cuyos elementos $(j,k)$ contienen la probabilidad de ocurrencia de un camino al azar desde $j$ hasta $k$ y que contiene al nodo $i$ como nodo intermediario.

Centralidad de información

La centralidad de información nace de la idea de aplicar la teoría de la información en la definición de medidas de centralidad. Los primeros acercamientos, bastante matemáticos, se deben a Plantilla:Harvtxt y su índice de participación total. Más tarde,Plantilla:Harvtxt definió el índice de flujo continuo, que como el anterior, considera todos los caminos posibles de la red, pero sin considerar el recuento de la intermediación.

La centralidad de información de Plantilla:Harvtxt es una variante de la centralidad de intermediación que, como sus antecesores, no se restringe solo a las geodésicas sino a todos los caminos posibles de la red. Esta medida está además motivada por la teoría de estimación estadística. Los pesos de los caminos se definen como las inversas de sus varianzas y representan la cantidad de información que circula a través de los respectivos actores. Dado que el flujo de información se asume independiente entre las aristas, entonces estas varianzas equivalen a las longitudes de los caminos. Las geodésicas normalmente asumen valores 1, mientras que los caminos más largos, valores inferiores, lo que representa una disminución de información. Esta medida determina la longitud media armónica de los caminos que acaban en un nodo $i$, la que será pequeña si $i$ se conecta con muchos otros nodos a través de caminos cortos.

Véase también

• Centralidad

Bibliografía

• Plantilla:Cita libro