Centralidad de cercanía

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).

En análisis de redes sociales, la centralidad de cercanía, o simplemente cercanía (en inglés, closeness), es una medida de centralidad basada en las ideas de Plantilla:Harvtxt, definida formalmente por Plantilla:Harvtxt y Plantilla:Harvtxt, con aplicaciones en redes de comunicación, y luego popularizada porPlantilla:Harvtxt. Es la más conocida y utilizada de las medidas radiales de longitud. Se basa en calcular la suma o bien el promedio de las distancias geodésicas (o longitudes de los caminos más cortos) desde un nodo hacia todos los demás. Note que mientras mayor sea la «distancia» entre dos vértices, menor será la «cercanía» entre estos. Por lo tanto, la cercanía se define como el inverso multiplicativo de la «lejanía» entre dos vértices.

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, para un grafo (dirigido o no dirigido), sea $d(u,v)$ la distancia geodésica entre los nodos $u$ y $v$, la cercanía $C_C(u)$ de un nodo $u\in V$ se define como:

$C_C(u)=\frac{1}{\sum _{v\in V}d(u,v)}$

Note que en algunas referencias $d(u,v)$ puede cambiar por $d(v,u)$.

Sea $S$ la matriz de distancias de la red, es decir, aquella matriz cuyos elementos $(i,j)$ corresponden a la distancia geodésica desde el nodo $i$ hasta el nodo $j$, entonces una definición alternativa es la siguiente:

$C_C(i)=\frac{1}{\sum _{j=1}^n(S{)}_{ij}}$

Para normalizar esta medida, se considera el mayor valor posible que podría asumir la medida para un nodo. Si el grafo no admite bucles, entonces un nodo a lo más puede conectarse directamente a los $n-1$ nodos restantes; si admite bucles (y asumimos que no es un multigrafo), entonces podrá conectarse directamente con los $n$ nodos de la red. Por lo tanto, la medida normalizada queda definida formalmente, para ambos casos, respectivamente:

$C_C(u)=\frac{n-1}{\sum _{v\in V}d(u,v)}$ o bien $C_C(u)=\frac{n}{\sum _{v\in V}d(u,v)}$

En una red de flujo esta medida se puede interpretar como el tiempo de llegada a destino de algo que fluye a través de la red. También puede interpretarse como la rapidez que tomará la propagación de la información desde un nodo a todos los demás. La cercanía mide de alguna forma la accesibilidad de un nodo en la red. Este concepto es utilizado también de manera similar en topología, donde se define como un espacio métrico.

Note que en un grafo disconexo, la cercanía de todos los vértices será siempre igual a 0, dado que siempre existirá algún otro nodo para el cual la distancia geodésica con él resulta infinita. Por lo tanto, la centralidad de cercanía tiene la desventaja de que solo se puede aplicar, en el caso de redes no dirigidas, sobre grafos conexos o componentes conexos, y para redes dirigidas, sobre componentes fuertemente conexos.

Variantes de la cercanía

En lugar de considerar la suma de las distancias geodésicas de un nodo hacia todos los demás, existe una variante que se enfoca únicamente en hallar la menor de estas distancias geodésicas. La excentricidad de un nodo es la mayor distancia entre ese nodo y cualquier otro del grafo. El centro de Jordan refiere al subconjunto de nodos con menor excentricidad dentro del grafo. Este centro puede encontrarse fácilmente a partir de la matriz de distancias del grafo, seleccionando aquellos nodos que comparten el menor valor máximo de sus respectivas filas en la matriz. Un concepto relacionado muy antiguo, al menos desdePlantilla:Harvtxt, es el de centroide, más apropiado específicamente para árboles. La idea es que para cada nodo del árbol, se considera el peso de cada una de sus ramas o caminos que parten desde dicho nodo, donde el peso de una rama es su número de aristas. El nodo se queda con el mayor de los pesos resultantes de entre todas sus ramas. El centroide corresponde así al subconjunto de nodos que comparten el peso final más pequeño.

La medida tradicional de cercanía asume que la propagación de información siempre se da en la red a través del camino más corto. Este modelo puede no ser el más realista para algunos tipos de escenarios de comunicación. Por ello han surgido algunas variantes de esta medida como la denominada cercanía por camino aleatorio (en inglés, random-walk closeness centrality), introducida por Plantilla:Harvtxt y que considera caminos aleatorios para acceder de un nodo a los demás, en lugar de escoger siempre el camino más corto.

En grafos disconexos

Existen algunas variantes de la cercanía que permiten trabajar con grafos disconexos. Si la red no es un componente fuertemente conexo,Plantilla:Harvtxt propuso usar la suma del recíproco de las distancias en lugar del recíproco de la suma de las distancias, con la convención de que $1/\mathrm{\infty }=0$, esto es, que las distancias entre actores inaccesibles sea cero, en lugar de infinito:

$H(u)=\sum _{u\ne v}\frac{n-1}{d(u,v)}$

A esta medida actualmente se le conoce como centralidad armónica (harmonic centrality, en inglés). Esta medida respeta el principio general propuesto por Plantilla:Harvtxt, que dice que en grafos con distancias infinitas la media armónica se comporta mejor que la media aritmética, utilizada por la medida de cercanía tradicional. Esta idea es similar al factor de potencial de mercado propuesto por Plantilla:Harvtxt, que actualmente se conoce como «acceso al mercado» (market access, en inglés).

Esta idea ha reaparecido varias veces en la literatura, usualmente sin el factor de normalización $n-1$, por ejemplo por Plantilla:Harvtxt para grafos no dirigidos, bajo el nombre de centralidad valorada (valued centrality, en inglés). Fue axiomatizada por Plantilla:Harvtxt y propuesta nuevamente por Plantilla:Harvtxt como solución para redes con componentes disconexos. Sus axiomas también fueron estudiados por Plantilla:Harvtxt.

Otra alternativa natural, siguiendo las ideas de Plantilla:Harvtxt, es considerar únicamente los nodos accesibles desde o hacia el nodo cuya centralidad se está midiendo. Sea $J_u$ el número de actores dentro del rango de influencia de $u$ (o accesibles desde o hacia $u$, dependiendo de si se desea trabajar con aristas de salida o de llegada en un grafo dirigido, respectivamente), se puede definir la siguiente variante de la centralidad de cercanía:

$C_C^{*}(u)=\frac{J_u/(n-1)}{\sum _{v\in V}d(u,v)/J_u}$

donde $J_u/(n-1)$ es la proporción de nodos accesibles en el componente conexo, y $\sum _{v\in V}d(u,v)/J_u$ es la distancia media de los nodos a $v$.

Una alternativa más distinta es la de Plantilla:Harvtxt, quien propone la siguiente medida de vulnerabilidad en las redes:

$C_{DC}(i)=\sum _{j=1}^n{2}^{-(S{)}_{ij}}$

donde $S$ es nuevamente la matriz de distancias.

Índices de prestigio

Para redes dirigidas, la cercanía y sus variantes se suelen centrar en caminos desde un nodo dado. Sin embargo, también puede ser útil considerar los caminos hacia dicho nodo. A las medidas de centralidad que consideran este último tipo de caminos se les suele también llamar medidas o índices de prestigio.

A partir de ideas de Plantilla:Harvtxt, el prestigio de proximidad $P_P(u)$ de un nodo $u\in V$ se define como:

$P_P(u)=\frac{I_u/(n-1)}{\sum _{v\in D(u)}d(v,u)/I_u}=\frac{I_u^2}{(n-1)\sum _{v\in D(u)}d(v,u)}$

donde $D(u)$ es el dominio de influencia del nodo $u$, es decir, el conjunto de actores que pueden acceder a dicho actor, $I_u=|D(u)|$ es la cardinalidad del dominio de influencia de $u$, $I_u/(n-1)$ es la proporción de nodos de la red que están en el dominio de influencia de $u$, y $\sum _{v\in D(u)}d(v,u)/I_i$ es la distancia media a la que los nodos del dominio de influencia están de $u$.

Note que el prestigio de proximidad se puede aplicar sobre redes disconexas.Plantilla:Harvtxt y Plantilla:Harvtxt también propusieron medidas similares.

Por otra parte,Plantilla:Harvtxt define el estatus neto de un actor $u\in V$, que definiremos $P_E(u)$, como:

$P_E(u)=\sum _{v\in V}d(u,v)-\sum _{v\in V}d(v,u)$

donde la primera sumatoria es el estatus de $v$, y la segunda sumatoria el contraestatus de $v$.

Otro índice de prestigio conocido es la centralidad de vector propio, la que para cada actor considera no solo su propio prestigio, sino también el de los actores que apuntan a este. Bajo este criterio, un actor es más prestigioso en la medida que los actores relacionados con él son también más prestigiosos.

Véase también

• Centralidad
• Centralidad de vector propio

Bibliografía

• Plantilla:Cita libro