Centralidad de cercanía

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

El número al lado de cada nodo es la distancia desde ese nodo hasta el nodo cuadrado rojo medida por la longitud del camino más corto. Los bordes verdes ilustran uno de los dos caminos más cortos entre el nodo cuadrado rojo y el nodo círculo rojo. La cercanía del nodo cuadrado rojo es, por tanto, 5/(1+1+1+2+2) = 5/7.

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 está la distancia (longitud del camino más corto) entre los vértices y ? Esta versión no normalizada de cercanía a veces se conoce 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 viene dado por la fórmula anterior multiplicada por , donde es el número de nodos en el gráfico dando como resultado: ${\displaystyle d(y,x)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle N-1}$ ${\displaystyle N}$

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

La normalización de cercanía simplifica la comparación de nodos en gráficos de diferentes tamaños. Para gráficos grandes, el menos uno en la normalización se vuelve intrascendente y, a menudo, se elimina.

Como una de las medidas de centralidad más antiguas, la cercanía a menudo se da en discusiones generales sobre medidas de centralidad de red 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 que la cercanía y el grado ^[12] 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 }$

donde es el grado del vértice, mientras que y β son parámetros que se encuentran 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 nodos (excluyendo el nodo raíz y las hojas) de los árboles de ruta más corta utilizados para aproximar redes al demostrar esta relación. ^[12] Esta nunca es una relación exacta, pero captura una tendencia que se observa en muchas redes del mundo real. ${\textstyle k_{x}}$ ${\displaystyle x}$ ${\displaystyle z}$

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 , la distancia promedio entre vértices en una red, es simplemente el promedio de los valores de cercanía inversos. ${\textstyle \langle \ell \rangle }$

${\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)}$.

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

Aplicaciones

La cercanía se utiliza en muchos contextos diferentes. En bibliometría, la cercanía se ha utilizado para observar la forma en que 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 posibles clientes potenciales en los datos de los clientes, se ha visto 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 a 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 las redes biológicas ^[5] donde, por ejemplo, se utilizó para identificar a más del 50% de los reguladores globales dentro del 2% superior de los genes clasificados ^[18] o se encontró que genes esenciales tienen una mayor cercanía que los genes no esenciales en las 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]

En gráficos desconectados

Cuando un gráfico no es fuertemente conexo , Beauchamp introdujo en 1965 la idea de utilizar la suma de recíprocos de distancias, ^[21] en lugar del recíproco de la suma de 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 gráficas 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 distancias, mientras que la centralidad de Beauchamp es el recíproco de la media armónica de distancias.

Esta idea ha resurgido varias veces en la literatura, a menudo sin el factor de normalización : para gráficos no dirigidos bajo el nombre de centralidad valorada por Dekker (2005) ^[23] y bajo el nombre ${\displaystyle n-1}$centralidad armónica de Rochat (2009); ^[24] fue axiomatizado por Garg (2009) ^[25] y propuesto una vez más posteriormente por Opsahl (2010). ^[26] Boldi y Vigna (2014) lo estudiaron en gráficos generales dirigidos. ^[27] Esta idea también es bastante similar al potencial de mercado propuesto en Harris (1954) ^[28], que ahora suele denominarse acceso al mercado. ^[29]

Variantes

Dangalchev (2006), ^[30] en un trabajo sobre vulnerabilidad de redes propone para gráficos 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 gráficos desconectados y permite crear fórmulas convenientes para operaciones gráficas. Por ejemplo:

Si el gráfico se crea vinculando un nodo del gráfico con un nodo del gráfico , entonces la cercanía combinada es: ${\displaystyle G_{1}+G_{2}}$ ${\displaystyle p}$ ${\displaystyle G_{1}}$ ${\displaystyle q}$ ${\displaystyle G_{2}}$

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

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

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

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

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

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

${\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)}},}$

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

La centralidad de la 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 difusión de información se modela mediante el uso de caminos más cortos. Es posible que este modelo no sea 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 del paseo aleatorio introducida por Noh y Rieger (2004). Mide la velocidad con la que los mensajes que caminan aleatoriamente llegan a un vértice desde cualquier otra parte del gráfico. ^[36] La cercanía jerárquica de Tran y Kwon (2014) ^[37] es una centralidad de cercanía extendida para abordar aún de otra manera la limitación de la cercanía en gráficos 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.

Ver también

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

Referencias

1. Bavelas, Álex (1950). "Patrones de comunicación en grupos orientados a tareas". La Revista de la Sociedad de Acústica de América . 22 (6): 725–730. Código bibliográfico : 1950ASAJ...22..725B. doi :10.1121/1.1906679.
2. Sabidussi, G (1966). "El índice de centralidad de un gráfico". Psicometrika . 31 (4): 581–603. doi :10.1007/bf02289527. hdl : 10338.dmlcz/101401 . PMID  5232444. S2CID  119981743.
3. Harary, Frank (1959). "Estado y Contrastatus". Sociometría . 22 (1): 23–43. doi :10.2307/2785610. JSTOR  2785610.
4. Hage, por; Harary, Frank (1995). "Excentricidad y centralidad en las redes". Redes sociales . 17 (1): 57–63. doi :10.1016/0378-8733(94)00248-9.
5. Wuchty, Stefan; Stadler, Peter F. (2003). "Centros de redes complejas". Revista de Biología Teórica . 223 (1): 45–53. Código Bib : 2003JThBi.223...45W. doi :10.1016/S0022-5193(03)00071-7. PMID  12782116.
6. Newman, MEJ (2010). Redes: una introducción. Oxford: Prensa de la Universidad de Oxford. ISBN 978-0-19-920665-0. OCLC  456837194.
7. Latora, Vito (2017). Redes complejas: principios, métodos y aplicaciones. Vincenzo Nicosia, Giovanni Russo. Cambridge, Reino Unido. ISBN 978-1-316-21600-2. OCLC  1004620089.{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )
8. Cosia, Michele (2021). El Atlas para el aspirante a científico de redes . arXiv : 2101.00863 . ISBN 9788797282403.
9. Bolland, John M (1988). "Clasificación de la centralidad: un análisis del rendimiento de cuatro modelos de centralidad en redes reales y simuladas". Redes sociales . 10 (3): 233–253. doi :10.1016/0378-8733(88)90014-7.
10. Brandes, Ulrik; Hildenbrand, enero (2014). "Gráficos más pequeños con distintos centros singleton". Ciencia de redes . 2 (3): 416–418. doi :10.1017/nws.2014.25. ISSN  2050-1242. S2CID  3841410.
11. Schoch, David; Valente, Thomas W.; Brandes, Ulrik (2017). "Correlaciones entre índices de centralidad y una clase de gráficos con clasificación única". Redes sociales . 50 : 46–54. doi :10.1016/j.socnet.2017.03.010. S2CID  10932381.
12. Evans, Tim S.; Chen, Bingsheng (2022). "Vincular la centralidad de la red mide cercanía y grado". Física de las Comunicaciones . 5 (1): 172. arXiv : 2108.01149 . Código Bib : 2022CmPhy...5..172E. doi :10.1038/s42005-022-00949-5. ISSN  2399-3650. S2CID  236881169.
13. Valente, Thomas W.; Coronges, Kathryn; Lakon, Cynthia; Costenbader, Elizabeth (1 de enero de 2008). "¿Cuán correlacionadas están las medidas de centralidad de la red?". Conexiones (Toronto, Ontario) . 28 (1): 16–26. ISSN  0226-1766. PMC 2875682 . PMID  20505784. 
14. Ni, Chaoqun; Sugimoto, Cassidy ; Jiang, Jiepu (2011). Noyons, ED; Ngulube, Patricio; Leta, Jacqueline (eds.). "Grado, cercanía e intermediación: aplicación de medidas de centralidad grupal para explorar diacrónicamente la evolución macrodisciplinaria" (PDF) : 605. {{cite journal}}: Citar diario requiere |journal=( ayuda )
15. Yan, Erjia; Ding, Ying (2009). "Aplicación de medidas de centralidad al análisis de impacto: un análisis de red de coautoría". Revista de la Sociedad Estadounidense de Ciencia y Tecnología de la Información . 60 (10): 2107–2118. arXiv : 1012.4862 . doi :10.1002/asi.21128. S2CID  261294843.
16. Beso, Christine; Bichler, Martín (2008). "Identificación de personas influyentes - Medición de la influencia en las redes de clientes". Sistemas de Soporte a la Decisión . 46 (1): 233–253. doi :10.1016/j.dss.2008.06.007. S2CID  9783337.
17. Wang, Jiaoe; Mo, Huihui; Wang, Fahui; Jin, Fengjun (2011). "Explorando la estructura de la red y la centralidad nodal de la red de transporte aéreo de China: un enfoque de red complejo". Revista de Geografía del Transporte . 19 (4): 712–721. doi :10.1016/j.jtrangeo.2010.08.012.
18. Koschützki, Dirk; Schreiber, Falk (2008). "Métodos de análisis de centralidad para redes biológicas y su aplicación a redes reguladoras de genes". Regulación genética y biología de sistemas . 2 : 193-201. doi :10.4137/GRSB.S702. ISSN  1177-6250. PMC 2733090 . PMID  19787083. 
19. Hahn, Mateo W.; Kern, Andrew D. (2005). "Genómica comparada de centralidad y esencialidad en tres redes de interacción de proteínas eucarióticas". Biología Molecular y Evolución . 22 (4): 803–806. doi : 10.1093/molbev/msi072 . ISSN  1537-1719. PMID  15616139.
20. Mamá, H.-W.; Zeng, A.-P. (22 de julio de 2003). "La estructura de conectividad, componente fuerte gigante y centralidad de las redes metabólicas". Bioinformática . 19 (11): 1423-1430. doi : 10.1093/bioinformática/btg177 . ISSN  1367-4803. PMID  12874056.
21. Beauchamp, Murray (1965). "Un índice de centralidad mejorado". Ciencia del comportamiento . 10 (2): 161–163. doi :10.1002/bs.3830100205. PMID  14284290.
22. Marchiori, Massimo; Latora, Vito (2000), "Armonía en el mundo pequeño", Physica A , 285 (3–4): 539–546, arXiv : cond-mat/0008357 , Bibcode :2000PhyA..285..539M, doi : 10.1016/s0378-4371(00)00311-3, S2CID  10523345
23. Dekker, Anthony (2005). "Distancia conceptual en el análisis de redes sociales". Revista de Estructura Social . 6 (3).
24. Yannick Rochat. Centralidad de cercanía extendida a gráficos desconectados: el índice de centralidad armónica (PDF) . Aplicaciones del análisis de redes sociales, ASNA 2009.
25. Manuj Garg (2009), Fundamentos axiomáticos de la centralidad en las redes , doi :10.2139/ssrn.1372441, S2CID  117717919
26. Tore Opsahl (20 de marzo de 2010). "Centralidad de cercanía en redes con componentes desconectados".
27. Boldi, Paolo; Vigna, Sebastiano (2014), "Axiomas de centralidad", Internet Mathematics , 10 (3–4): 222–262, doi : 10.1080/15427951.2013.865686
28. Harris, Chauncy D. (1954). "El mercado como factor de localización de la industria en Estados Unidos". Anales de la Asociación de Geógrafos Americanos . 44 (4): 315–348. doi :10.2307/2561395. JSTOR  2561395.
29. Gutberlet, Teresa. Carbón barato versus acceso al mercado: el papel de los recursos naturales y la demanda en la industrialización de Alemania. Hoja de trabajo. 2014.
30. Ch, Dangalchev (2006). "Cercanía residual en redes". Física A. 365 (2): 556. Código bibliográfico : 2006PhyA..365..556D. doi :10.1016/j.physa.2005.12.020.
31. Ch, Dangalchev (2020). "Crecimiento adicional de cercanía y redes". Fundamentos de la informática . 176 (1): 1–15. doi :10.3233/FI-2020-1960. S2CID  226300861.
32. Dangalchev, Chavdar (2023). "Cercanía de algunas operaciones gráficas". arXiv : 2308.14491 [cs.DM].
33. Ch, Dangalchev (2018). "Cercanía residual de gráficos de espinas generalizados". Fundamentos de la informática . 162 (1): 1–15. doi :10.3233/FI-2018-1710. S2CID  52073138.
34. Ch, Dangalchev (2011). "Cercanía residual y cercanía generalizada". Revista Internacional de Fundamentos de la Informática . 22 (8): 1939-1948. doi :10.1142/s0129054111009136.
35. Stephenson, KA; Zelen, M. (1989). "Repensar la centralidad: métodos y ejemplos". Redes sociales . 11 : 1–37. doi :10.1016/0378-8733(89)90016-6.
36. No, JD; Rieger, H. (2004). "Paseos aleatorios en redes complejas". Física. Rev. Lett . 92 (11): 118701. arXiv : cond-mat/0307719 . Código bibliográfico : 2004PhRvL..92k8701N. doi :10.1103/physrevlett.92.118701. PMID  15089179. S2CID  14767557.
37. Tran, Tien-Dzung; Kwon, Yung-Keun (2014). "La cercanía jerárquica predice eficazmente genes de enfermedades en una red de señalización dirigida". Biología y Química Computacional . 53 : 191-197. doi :10.1016/j.compbiolchem.2014.08.023. PMID  25462327.