Centralidad de la cercanía

En un grafo conectado , la centralidad de cercanía (o proximidad ) de un nodo es una medida de centralidad en la red , calculada como el recíproco de la suma de las longitudes de los caminos más cortos entre el nodo y todos los demás nodos del grafo. Por lo tanto, cuanto más central es un nodo, más cerca está de los demás.

La cercanía fue definida por Bavelas (1950) como el recíproco de la lejanía , ^{[ 1 ] [ 2 ]} es decir:

${\displaystyle C_{B}(x)={\frac {1}{\sum _{y}d(y,x)}},}$

dónde${\displaystyle d(y,x)}$es la distancia (longitud del camino más corto) entre vértices${\displaystyle x}$y${\displaystyle y}$Esta versión no normalizada de cercanía se conoce a veces como estatus. ^{[ 3 ] [ 4 ] [ 5 ]} Cuando se habla de centralidad de cercanía, la gente suele referirse a su forma normalizada, que representa la longitud promedio de los caminos más cortos en lugar de su suma. Generalmente se da mediante la fórmula anterior multiplicada por${\displaystyle N-1}$, dónde${\displaystyle N}$es el número de nodos en el grafo que resulta en:

${\displaystyle C(x)={\frac {N-1}{\sum _{y}d(y,x)}}.}$

La normalización de la cercanía simplifica la comparación de nodos en grafos de diferentes tamaños. Para grafos grandes, el restar uno en la normalización resulta irrelevante y suele omitirse.

Como una de las medidas de centralidad más antiguas, la cercanía se suele mencionar en discusiones generales sobre medidas de centralidad de redes en textos introductorios ^{[ 6 ] [ 7 ] [ 8 ]} o en artículos que comparan diferentes medidas de centralidad. ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ]} Los valores producidos por muchas medidas de centralidad pueden estar altamente correlacionados. ^{[ 9 ] [ 13 ] [ 11 ]} En particular, se ha demostrado ^{[ 12 ]} que la cercanía y el grado están relacionados en muchas redes a través de una relación aproximada.

${\displaystyle {\frac {1}{C(x)}}\approx {\frac {-1}{\ln(z-1)}}\ln(k_{x})+\beta }$

dónde${\textstyle k_{x}}$es el grado del vértice${\displaystyle x}$mientras${\displaystyle z}$y β son parámetros que se obtienen ajustando la cercanía y el grado a esta fórmula. El parámetro z representa el factor de ramificación , el grado promedio de los nodos (excluyendo el nodo raíz y las hojas) de los árboles de ruta más corta que se utilizan para aproximar las redes al demostrar esta relación. ^{[ 12 ]} Esta nunca es una relación exacta, pero captura una tendencia observada en muchas redes del mundo real.

La cercanía está relacionada con otras escalas de longitud utilizadas en la ciencia de redes. Por ejemplo, la longitud promedio del camino más corto.${\textstyle \langle \ell \rangle }$La distancia promedio entre vértices en una red es simplemente el promedio de los valores de cercanía inversos.

${\displaystyle \langle \ell \rangle ={\frac {1}{N}}\sum _{x}{\frac {1}{C(x)}}={\frac {1}{N(N-1)}}\sum _{x}\sum _{y}d(y,x)}$.

Calcular las distancias desde o hacia todos los demás nodos es irrelevante en los grafos no dirigidos, mientras que puede producir resultados totalmente diferentes en los grafos dirigidos (por ejemplo, un sitio web puede tener una alta centralidad de cercanía a partir de los enlaces salientes, pero una baja centralidad de cercanía a partir de los enlaces entrantes).

La cercanía se utiliza en muchos contextos diferentes. En bibliometría, se ha utilizado para analizar cómo los académicos eligen sus revistas y bibliografías en diferentes campos ^{[ 14 ]} o para medir el impacto de un autor en un campo y su capital social ^{[ 15 ]} . Cuando se utiliza para seleccionar clientes potenciales en datos de clientes, se ha observado que la cercanía conduce a una ganancia significativa en la tasa de éxito ^{[ 16 ]} . Se ha demostrado que la cercanía de una ciudad en una red de transporte aéreo está altamente correlacionada con indicadores socioeconómicos como el producto interno bruto regional ^{[ 17 ]} . La cercanía también se ha aplicado a redes biológicas ^{[ 5 ]} donde, por ejemplo, se utilizó para identificar más del 50% de los reguladores globales dentro del 2% superior de los genes clasificados ^{[ 18 ]} o se encontró que los genes esenciales tenían mayor cercanía que los genes no esenciales en redes de interacción de proteínas ^{[ 19 ]} . En una red metabólica, la cercanía de los nodos puede identificar los metabolitos más importantes ^{[ 20 ] .}

Cuando un grafo no está fuertemente conectado , Beauchamp introdujo en 1965 la idea de usar la suma de los recíprocos de las distancias, ^{[ 21 ]} en lugar del recíproco de la suma de las distancias, con la convención${\displaystyle 1/\infty =0}$:

${\displaystyle H(x)=\sum _{y\neq x}{\frac {n-1}{d(y,x)}}.}$

La modificación de Beauchamp sigue el principio general (mucho más tarde) propuesto por Marchiori y Latora (2000) ^{[ 22 ]} de que en grafos con distancias infinitas la media armónica se comporta mejor que la media aritmética. De hecho, la cercanía de Bavelas puede describirse como el recíproco desnormalizado de la media aritmética de las distancias, mientras que la centralidad de Beauchamp es el recíproco de la media armónica de las distancias.

Esta idea ha resurgido varias veces en la literatura, a menudo sin el factor de normalización.${\displaystyle n-1}$: para grafos no dirigidos bajo el nombre de centralidad valorada por Dekker (2005) ^{[ 23 ]} y bajo el nombrecentralidad armónica por Rochat (2009); ^{[ 24 ]} fue axiomatizada por Garg (2009) ^{[ 25 ]} y propuesta nuevamente más tarde por Opsahl (2010). ^{[ 26 ]} Fue estudiada en grafos dirigidos generales por Boldi y Vigna (2014). ^{[ 27 ]} Esta idea también es bastante similar al potencial de mercado propuesto en Harris (1954) ^{[ 28 ]} que ahora a menudo se conoce como acceso al mercado . ^{[ 29 ]}

Dangalchev (2006), ^{[ 30 ]} en un trabajo sobre vulnerabilidad de redes propone para grafos no dirigidos una definición diferente:

${\displaystyle D(x)=\sum _{y\neq x}{\frac {1}{2^{d(y,x)}}}.}$

Esta definición se utiliza eficazmente para grafos desconectados y permite crear fórmulas convenientes para operaciones con grafos . Por ejemplo:

Si el gráfico${\displaystyle G_{1}+G_{2}}$se crea mediante la vinculación de nodos${\displaystyle p}$del gráfico${\displaystyle G_{1}}$al nodo${\displaystyle q}$del gráfico${\displaystyle G_{2}}$Entonces, la cercanía combinada es:

${\displaystyle D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+(1+D(p))(1+D(q));}$

si el gráfico${\displaystyle G_{1}+G_{2}}$se crea colapsando el nodo${\displaystyle p}$del gráfico${\displaystyle G_{1}}$y nodo${\displaystyle q}$del gráfico${\displaystyle G_{2}}$en un nodo entonces la cercanía es: ^{[ 31 ]}

${\displaystyle D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+2D(p)D(q).}$

Si el gráfico${\displaystyle S(G)}$es el gráfico de sombra del gráfico${\displaystyle G}$, que tiene${\displaystyle n}$nodos, entonces${\displaystyle S(G)}$La cercanía es: ^{[ 32 ]}

${\displaystyle D(S(G))=4D(G)+{\frac {n}{2}}.}$

Si el gráfico${\displaystyle T(G)}$es el gráfico de espinas del gráfico${\displaystyle G}$, que tiene${\displaystyle n}$nodos, entonces${\displaystyle T(G)}$La cercanía es: ^{[ 33 ]}

${\displaystyle D(T(G))={\frac {9}{4}}D(G)+n.}$

La generalización natural de esta definición es: ^{[ 34 ]}

${\displaystyle D(x)=\sum _{y\neq x}\ {\alpha ^{d(y,x)}},}$

dónde${\displaystyle \alpha }$pertenece a (0,1). Como${\displaystyle \alpha }$A medida que aumenta de 0 a 1, la cercanía generalizada cambia de una característica local (grado) a una global (número de nodos conectados).

La centralidad de información de Stephenson y Zelen (1989) es otra medida de cercanía, que calcula la media armónica de las distancias de resistencia hacia un vértice x , que es menor si x tiene muchos caminos de pequeña resistencia que lo conectan con otros vértices. ^{[ 35 ]}

En la definición clásica de centralidad de cercanía, la propagación de información se modela mediante el uso de caminos más cortos. Este modelo puede no ser el más realista para todos los tipos de escenarios de comunicación. Por lo tanto, se han discutido definiciones relacionadas para medir la cercanía, como la centralidad de cercanía de paseo aleatorio introducida por Noh y Rieger (2004). Esta mide la velocidad con la que los mensajes de paseo aleatorio llegan a un vértice desde cualquier otro lugar del grafo. ^{[ 36 ]} La cercanía jerárquica de Tran y Kwon (2014) ^{[ 37 ]} es una centralidad de cercanía extendida para abordar de otra manera la limitación de la cercanía en grafos que no están fuertemente conectados. La cercanía jerárquica incluye explícitamente información sobre el rango de otros nodos que pueden verse afectados por el nodo dado.

• Centralidad
• centro de cercanía de paseo aleatorio
• Centralidad de intermediación