Centralidad de proximidad

Concepto en la teoría de grafos

En un grafo conexo , la centralidad de cercanía (o proximidad ) de un nodo es una medida de la centralidad en una 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 sea un nodo, más cerca estará de todos los demás nodos.

El número que aparece junto a 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 circular rojo. Por lo tanto, la proximidad del nodo cuadrado rojo es 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)}},}$

donde es la distancia (longitud del camino más corto) entre los vértices y . Esta versión no normalizada de la cercanía a veces se conoce como estado. ^{[3] [4] [5]} Cuando se habla de centralidad de cercanía, la gente suele referirse a su forma normalizada que representa la longitud media de los caminos más cortos en lugar de su suma. Generalmente se da mediante la fórmula anterior multiplicada por , donde es el número de nodos en el gráfico, lo que da 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 la proximidad simplifica la comparación de nodos en gráficos de distintos tamaños. En el caso de gráficos grandes, el menos uno en la normalización resulta irrelevante y suele omitirse.

Como una de las medidas de centralidad más antiguas, la cercanía se da a menudo 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 ^{[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 }$

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 los 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 observada 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 de la ruta más corta , la distancia promedio entre los vértices de una red, es simplemente el promedio de los valores de cercanía inversa. ${\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 alta centralidad de cercanía a partir de enlaces salientes, pero una baja centralidad de cercanía a partir de 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 clientes potenciales en datos de 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 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 una cercanía mayor 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]} .

En gráficos desconectados

Cuando un grafo no está fuertemente conexo , Beauchamp introdujo en 1965 la idea de utilizar la suma del recíproco 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 propuesto (mucho más tarde en el tiempo) 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 : 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 axiomatizada por Garg (2009) ^[25] y propuesta nuevamente más tarde por Opsahl (2010). ^[26] Fue estudiada en grafos generales dirigidos 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 con el término acceso al mercado. ^[29]

Variantes

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

Si el gráfico se crea vinculando un nodo del gráfico con otro 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 un nodo del gráfico y un nodo del gráfico en un solo nodo, entonces la proximidad 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 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 de espinas 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 la centralidad de cercanía, la propagación de la información se modela mediante el uso de caminos más cortos. Este modelo podría 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 caminata aleatoria introducida por Noh y Rieger (2004). Mide la velocidad con la que los mensajes que caminan aleatoriamente llegan a un vértice desde otra parte del grafo. ^[36] La cercanía jerárquica de Tran y Kwon (2014) ^[37] es una centralidad de cercanía extendida para tratar 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.

Véase también

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

Referencias

1. Bavelas, Alex (1950). "Patrones de comunicación en grupos orientados a tareas". Revista de la Sociedad Acústica de América . 22 (6): 725–730. Bibcode :1950ASAJ...22..725B. doi :10.1121/1.1906679.
2. Sabidussi, G (1966). "El índice de centralidad de un grafo". Psychometrika . 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, Per; Harary, Frank (1995). "Excentricidad y centralidad en 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. Bibcode :2003JThBi.223...45W. doi :10.1016/S0022-5193(03)00071-7. PMID  12782116.
6. Newman, MEJ (2010). Redes: una introducción. Oxford: Oxford University Press. 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 de CS1: falta la ubicación del editor ( enlace )
8. Cosia, Michele (2021). 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, Jan (2014). "Gráficos más pequeños con centros singleton distintos". Network Science . 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 rango único". 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 la cercanía y el grado". Física de las comunicaciones . 5 (1): 172. arXiv : 2108.01149 . Código Bibliográfico :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). "¿Qué tan correlacionadas están las medidas de centralidad de red?". Connections (Toronto, Ontario) . 28 (1): 16–26. ISSN  0226-1766. PMC 2875682. PMID 20505784  . 
14. Ni, Chaoqun; Sugimoto, Cassidy ; Jiang, Jiepu (2011). Noyons, ED; Ngulube, Patrick; Leta, Jacqueline (eds.). "Grado, cercanía e intermediación: aplicación de mediciones de centralidad de grupo para explorar la evolución macrodisciplinaria diacrónicamente" (PDF) : 605. {{cite journal}}: Requiere citar revista |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 Ciencias de la Información y Tecnología . 60 (10): 2107–2118. arXiv : 1012.4862 . doi :10.1002/asi.21128. S2CID  261294843.
16. Kiss, Christine; Bichler, Martin (2008). "Identificación de influenciadores: medición de la influencia en redes de clientes". Sistemas de soporte de decisiones . 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 red y la centralidad nodal de la red de transporte aéreo de China: un enfoque de red complejo". Journal of Transport Geography . 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 de regulación génica". Regulación génica y biología de sistemas . 2 : 193–201. doi :10.4137/GRSB.S702. ISSN  1177-6250. PMC 2733090. PMID 19787083  . 
19. Hahn, Matthew W.; Kern, Andrew D. (2005). "Genómica comparativa de la centralidad y la esencialidad en tres redes de interacción de proteínas eucariotas". Biología molecular y evolución . 22 (4): 803–806. doi : 10.1093/molbev/msi072 . ISSN  1537-1719. PMID  15616139.
20. Ma, 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/bioinformatics/btg177 . ISSN  1367-4803. PMID  12874056.
21. Beauchamp, Murray (1965). "Un índice mejorado de centralidad". Ciencias 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 grafos no conexos: 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 redes , doi :10.2139/ssrn.1372441, S2CID  117717919
26. Tore Opsahl (20 de marzo de 2010). "Centralidad de proximidad 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 en la localización de la industria en los Estados Unidos". Anales de la Asociación de Geógrafos Estadounidenses . 44 (4): 315–348. doi :10.2307/2561395. JSTOR  2561395.
29. Gutberlet, Theresa. Carbón barato versus acceso al mercado: el papel de los recursos naturales y la demanda en la industrialización de Alemania. Documento de trabajo. 2014.
30. Ch, Dangalchev (2006). "Cercanía residual en redes". Physica A . 365 (2): 556. Bibcode :2006PhyA..365..556D. doi :10.1016/j.physa.2005.12.020.
31. Ch, Dangalchev (2020). "Cercanía adicional y crecimiento de redes". Fundamenta Informaticae . 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 grafos de Thorn generalizados". Fundamenta Informaticae . 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 ciencia informática . 22 (8): 1939–1948. doi :10.1142/s0129054111009136.
35. Stephenson, KA; Zelen, M. (1989). "Replanteando la centralidad: métodos y ejemplos". Redes sociales . 11 : 1–37. doi :10.1016/0378-8733(89)90016-6.
36. Noh, JD; Rieger, H. (2004). "Paseos aleatorios en redes complejas". Phys. 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 de manera eficiente los genes de enfermedades en una red de señalización dirigida". Computational Biology and Chemistry . 53 : 191–197. doi :10.1016/j.compbiolchem.2014.08.023. PMID  25462327.