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 las rutas más cortas 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.
La cercanía fue definida por Bavelas (1950) como el recíproco de la lejanía , [1] [2] es decir:
dónde es la distancia entre vértices y . 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 viene dado por la fórmula anterior multiplicada por, dónde es el número de nodos del gráfico. Para gráficos grandes, esta diferencia se vuelve intrascendente, por lo que la se cae dando como resultado:
La normalización permite comparaciones entre nodos de gráficos de diferentes tamaños.
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 desde el enlace saliente, pero una centralidad de proximidad baja desde los enlaces entrantes).
En gráficos desconectados
Cuando una gráfica no está fuertemente conectada , una idea generalizada es la de usar la suma del recíproco de distancias, en lugar del recíproco de la suma de distancias, con la convención:
La modificación más natural de la definición de cercanía de Bavelas es seguir el principio general propuesto por Marchiori y Latora (2000) [3] de que en gráficos 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 armónica es el recíproco desnormalizado de la media armónica de distancias.
Esta idea fue expresada explícitamente para grafos no dirigidos bajo el nombre de centralidad valorada por Dekker (2005) [4] y bajo el nombrecentralidad armónica de Rochat (2009), [5] axiomatizada por Garg (2009) [6] y propuesta nuevamente más tarde por Opsahl (2010). [7] Fue estudiado en gráficos generales dirigidos por Boldi y Vigna (2014). [8] Esta idea también es bastante similar al potencial de mercado propuesto en Harris (1954) [9], que ahora se conoce con el término acceso al mercado. [10]
Variantes
Dangalchev (2006), [11] en un trabajo sobre la vulnerabilidad de la red propone una definición diferente para los gráficos no dirigidos:
Esta definición se usa de manera efectiva para gráficos desconectados y permite crear fórmulas convenientes para operaciones de gráficos. Por ejemplo:
Si un gráfico se crea al vincular el nodo de gráfico al nodo de gráfico entonces la cercanía combinada es:
si un grafico se crea al colapsar el nodo de gráfico y nodo de gráfico en un nodo, la cercanía es: [12]
Si gráfico es el gráfico de espinas del gráfico , que tiene nodos, entonces la cercanía es: [13]
La generalización natural de esta definición es: [14]
dónde pertenece a (0,1). Como aumenta de 0 a 1, la cercanía generalizada cambia de característica local (grado) a global (número de nodos conectados).
La centralidad de la información de Stephenson y Zelen (1989) es otra medida de proximidad, 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. [15]
En la definición clásica de la centralidad de la cercanía, la difusión de la información se modela mediante el uso de los 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 la cercanía al caminar aleatoriamente introducida por Noh y Rieger (2004). Mide la velocidad con la que los mensajes que caminan aleatoriamente alcanzan un vértice desde otra parte del gráfico, una especie de versión de caminata aleatoria de la centralidad de la cercanía. [16] La cercanía jerárquica de Tran y Kwon (2014) [17] es una centralidad de cercanía extendida para tratar aún de otra manera con 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
Referencias
- ^ Bavelas, Alex (1950). "Patrones de comunicación en grupos orientados a tareas". La Revista de la Sociedad Estadounidense de Acústica . 22 (6): 725–730. Código bibliográfico : 1950ASAJ ... 22..725B . doi : 10.1121 / 1.1906679 .
- ^ Sabidussi, G (1966). "El índice de centralidad de un gráfico". Psychometrika . 31 (4): 581–603. doi : 10.1007 / bf02289527 . hdl : 10338.dmlcz / 101401 . PMID 5232444 . S2CID 119981743 .
- ^ Marchiori, Massimo; Latora, Vito (2000), "Harmony in the small-world", 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
- ^ Dekker, Anthony (2005). "Distancia conceptual en el análisis de redes sociales" . Revista de Estructura Social . 6 (3).
- ^ Yannick Rochat. Centralidad de cercanía extendida a gráficos inconexos: el índice de centralidad armónica (PDF) . Aplicaciones del análisis de redes sociales, ASNA 2009.
- ^ Manuj Garg (2009), Fundamentos axiomáticos de centralidad en redes , doi : 10.2139 / ssrn.1372441 , S2CID 117717919
- ^ Tore Opsahl (20 de marzo de 2010). "Centralidad de cercanía en redes con componentes desconectados" .
- ^ Boldi, Paolo; Vigna, Sebastiano (2014), "Axiomas de centralidad", Matemáticas de Internet , 10 (3–4): 222–262, doi : 10.1080 / 15427951.2013.865686
- ^ 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 Estadounidenses . 44 (4): 315–348. JSTOR 2561395 .
- ↑ Gutberlet, Theresa. 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.
- ^ Ch, Dangalchev (2006). "Cercanía residual en redes". Un Physica . 365 (2): 556. Bibcode : 2006PhyA..365..556D . doi : 10.1016 / j.physa.2005.12.020 .
- ^ Ch, Dangalchev (2020). "Mayor cercanía y crecimiento de las redes". Fundamenta Informaticae . 176 (1): 1-15. doi : 10.3233 / FI-2020-1960 .
- ^ Ch, Dangalchev (2018). "Cercanía residual de gráficos Thorn generalizados". Fundamenta Informaticae . 162 (1): 1-15. doi : 10.3233 / FI-2018-1710 .
- ^ Ch, Dangalchev (2011). "Cercanía residual y cercanía generalizada". Revista Internacional de Fundamentos de la Ciencia de la Computación . 22 (8): 1939-1948. doi : 10.1142 / s0129054111009136 .
- ^ 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 .
- ^ 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 .
- ^ Tran, Tien-Dzung; Kwon, Yung-Keun (2014). "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 .