Centralidad de nodo en redes ponderadas
Tore Opsahl
La centralidad de los nodos, o la identificación de qué nodos son más "centrales" que otros, ha sido un tema clave en el análisis de redes (Freeman, 1978; Bonacich, 1987; Borgatti, 2005; Borgatti et al., 2006). Freeman (1978) argumentó que los nodos centrales eran aquellos "en el meollo de las cosas" o puntos focales. Para ejemplificar su idea, utilizó una red que consta de 5 nodos. El nodo medio tiene tres ventajas sobre los otros nodos: tiene más vínculos, puede alcanzar a todos los demás más rápidamente y controla el flujo entre los demás. Con base en estas tres características, Freeman (1978) formalizó tres medidas diferentes de la centralidad del nodo: grado, cercanía e interdependencia. Grado es la cantidad de nodos a los que está conectado un nodo focal y mide la participación del nodo en la red. Su simplicidad es una ventaja: solo debe conocerse la estructura local alrededor de un nodo para que se calcule (p. Ej., Cuando se utilizan datos de la Encuesta social general, McPherson et al., 2001). Sin embargo, existen limitaciones: la medida no toma en consideración la estructura global de la red. Por ejemplo, aunque un nodo podría estar conectado a muchos otros, podría no estar en condiciones de alcanzar a otros rápidamente para acceder a los recursos, como la información o el conocimiento (Borgatti, 2005; Brass, 1984). Para capturar esta característica, la centralidad de cercanía se definió como la suma inversa de las distancias más cortas a todos los demás nodos desde un nodo focal. Una de las principales limitaciones de la cercanía es la falta de aplicabilidad a las redes con componentes desconectados (consulte Centralidad de proximidad en redes con componentes desconectados). La última de las tres medidas, betweenness, evalúa el grado en que un nodo se encuentra en la ruta más corta entre otros dos nodos y puede canalizar el flujo en la red. Al hacerlo, un nodo puede ejercer control sobre el flujo. Si bien esta medida tiene en cuenta la estructura de red global y puede aplicarse a redes con componentes desconectados, no deja de tener sus limitaciones. Por ejemplo, una gran proporción de nodos en una red generalmente no se encuentra en la ruta más corta entre ninguno de los otros dos nodos, y por lo tanto recibe la misma puntuación de 0.
Las tres medidas se han generalizado a redes ponderadas. En un primer conjunto de generalizaciones, Barrat et al. (2004) grado generalizado tomando la suma de pesos en lugar de los nudos, mientras que Newman (2001) y Brandes (2001) utilizaron el algoritmo de Dijkstra (1959) de caminos más cortos para generalizar la cercanía y la interdependencia a redes ponderadas, respetuosamente (ver Rutas más cortas en Weighted Networks para más detalles). Estas generalizaciones se centraron únicamente en los pesos vinculados e ignoraron la característica original de las medidas: el número de vínculos. Como tal, un segundo conjunto de generalización fue propuesto por Opsahl et al. (2010) que incorpora tanto el número de vínculos como los pesos de enlace utilizando un parámetro de ajuste.
Grado
El grado es la más simple de las medidas de centralidad del nodo al usar la estructura local solo alrededor de los nodos. En una red binaria, el grado es el número de vínculos que tiene un nodo. En una red dirigida, un nodo puede tener un número diferente de enlaces salientes y entrantes, y por lo tanto, el grado se divide en grado y grado, respectivamente.Por lo general, el grado se ha extendido a la suma de ponderaciones cuando se analizan las redes ponderadas (Barrat et al., 2004; Newman, 2004; Opsahl et al., 2008) y la resistencia del nodo etiquetada. Es igual a la definición tradicional de grado si la red es binaria (es decir, cada vínculo tiene un peso de 1). Por el contrario, en las redes ponderadas, los resultados de estas dos medidas son diferentes. Como la fuerza del nodo toma en consideración el peso de los enlaces, esta ha sido la medida preferida para analizar las redes ponderadas (por ejemplo, Barrat et al., 2004; Opsahl et al., 2008). Sin embargo, la fortaleza del nodo es una medida contundente, ya que solo toma en consideración el nivel total de participación de un nodo en la red, y no toma en cuenta la característica principal de las medidas originales formalizadas por Freeman (1978): el número de vínculos. Esta limitación se destaca por la centralidad de grado de las tres redes de ego de la tercera red EIES de Freeman. Los tres nodos han enviado aproximadamente la misma cantidad de mensajes; sin embargo, a un número bastante diferente de otros. Si se aplicó la medida original de Freeman (1978), el puntaje de centralidad del nodo en el panel A es casi cinco veces más alto que el nodo en el panel C. Sin embargo, al usar la generalización de Barrat et al., Obtienen aproximadamente el mismo puntaje.
Redes Ego de Phipps Arabie (A), John Boyd (B) y Maureen Hallinan (C) de la tercera red EIES de Freeman. El ancho de un enlace corresponde a la cantidad de mensajes enviados desde el nodo focal a sus contactos. Adoptado de Opsahl et al. (2010).
En un intento de combinar el grado y la fuerza, Opsahl et al. (2010) utilizó un parámetro de ajuste para establecer la importancia relativa de la cantidad de vínculos en comparación con los pesos de enlace. Específicamente, la medida de centralidad de grado propuesta fue el producto de la cantidad de nodos a los que está conectado un nodo focal y el peso promedio de estos nodos ajustado por el parámetro de ajuste. Hay dos valores de referencia para el parámetro de ajuste (0 y 1), y si el parámetro se establece en cualquiera de estos valores, se reproducen las medidas existentes (Barrat et al., 2004; Freeman, 1978). Si el parámetro se establece en el valor de referencia de 0, los resultados de las medidas se basan únicamente en el número de vínculos, y son iguales a la encontrada al aplicar la medida de Freeman (1978) a una versión binaria de una red donde todas las los lazos con un peso mayor a 0 se configuran como presentes. Al hacerlo, los pesos vinculados son completamente ignorados. Por el contrario, si el valor del parámetro es 1, la medida se basa solamente en los pesos de empate y es idéntica a la generalización ya propuesta (Barrat et al., 2004). Esto implica que no se tiene en cuenta el número de vínculos. La siguiente tabla destaca las diferencias entre las medidas de grado.
.
| Nodo | Grado medido por | |||
|---|---|---|---|---|
| Freeman (1978) | Barrat et al. (2004) | Opsahl et al. (2010; alpha=0.5) | Opsahl et al. (2010; alpha=1.5) | |
| Phipps Arabie (A) | 28 | 155 | 66 | 365 |
| John Boyd (B) | 11 | 188 | 45 | 777 |
| Maureen Hallinan (C) | 6 | 227 | 37 | 1396 |
Para calcular las puntuaciones de grado de los nodos, a continuación se muestra un código de muestra para calcular los puntajes de grado de las neuronas del gusano c.elegans (Watts y Strogatz, 1998) utilizando el R-package tnet.
1
2
3
4
5
6
7
8
9
10
11
| # Load tnetlibrary(tnet)# Load the neural network of the c.elegans networkdata(tnet)# Calculate the out-degree of neurons and the generalised measures (alpha=0.5)degree_w(net=celegans.n306.net, measure=c("degree","output","alpha"), alpha=0.5)# Calculate the in-degree of neurons and the generalised measures (alpha=0.5)degree_w(net=celegans.n306.net, measure=c("degree","output","alpha"), alpha=0.5, type="in") |
Cercanía
La cercanía se define como la inversa de la lejanía, que a su vez es la suma de las distancias a todos los demás nodos (Freeman, 1978). La intención detrás de esta medida fue identificar los nodos que podrían llegar a otros rápidamente. Una limitación principal de la cercanía es la falta de aplicabilidad a redes con componentes desconectados: dos nodos que pertenecen a diferentes componentes no tienen una distancia finita entre ellos. Por lo tanto, la cercanía generalmente está restringida a los nodos dentro del componente más grande de una red. La publicación de blog Closeness Centrality in Networks with Disconnected Components sugiere un método para superar esta limitación,
La cercanía se ha generalizado a las redes ponderadas por Newman (2001), que utilizó el algoritmo de Dijkstra (1959) (para obtener más detalles, consulte Trayectos más cortos en Redes ponderadas). Para reiterar rápidamente el trabajo de Dijkstra (1959) y de Newman (2001) aquí:
- Dijkstra (1959) propuso un algoritmo para encontrar las rutas más cortas en una red donde los pesos podrían considerarse costos. La ruta menos costosa que conecta dos nodos fue la ruta más corta entre ellos (por ejemplo, una red de carreteras donde cada tramo de carretera tiene un costo de tiempo asignado).
- Newman (2001) transformó los pesos positivos en una red de colaboración en costos invirtiéndolos (dividiendo 1 por el peso).
- Sobre la base de los pesos invertidos, Newman (2001) aplicó el algoritmo de Dijkstra y encontró los caminos menos costosos entre todos los nodos.
- El costo total de las rutas de un nodo a todos los demás fue una medida de lejanía: cuanto mayor es el número, más cuesta que un nodo llegue a todos los otros nodos. Para crear una medida de proximidad, Newman (2001) siguió a Freeman (1978) e invirtió los números (1 dividido por la lejanía). Por lo tanto, una alta lejanía se transformó en una baja cercanía, y una baja lentitud se transformó en una gran cercanía.
De forma similar a la generalización de grado de Barrat et al. (2004), el algoritmo generalizado de Newman (2001) se centra únicamente en la suma de ponderaciones de relación y no tiene en cuenta la cantidad de vínculos en las rutas. Opsahl et al. (2010) la generalización de las rutas más cortas se puede aplicar para determinar la longitud de ellas.
Para calcular las puntuaciones de cercanía de los nodos, a continuación se muestra un código de muestra para calcular los puntajes de cercanía de las neuronas del gusano c.elegans (Watts y Strogatz, 1998) utilizando el paquete de R tnet.
.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| # Load tnetlibrary(tnet)# Load the neural network of the c.elegans networkdata(tnet)# Calculate the binary closeness scorescloseness_w(net=celegans.n306.net, alpha=0)# Calculate the first generation weighted closeness scorescloseness_w(net=celegans.n306.net, alpha=1)# Calculate the second generation weighted closeness scores (alpha=0.5)closeness_w(net=celegans.n306.net, alpha=0.5) |
Intermediación
La medida en que un nodo forma parte de las transacciones entre otros nodos se puede estudiar utilizando la medida de interdependencia de Freeman (1978). En la red de muestra de la derecha, si los enlaces no tenían un peso asignado, las líneas grises intermitentes representan las 9 rutas más cortas de la red que pasan por nodos intermedios. El nodo resaltado es un intermedio en 8 de estas rutas. Esto le dará a este nodo una puntuación de interinidad de 8.Brandes (2001) propuso un nuevo algoritmo para calcular la interrelación más rápido. Además de reducir el tiempo, este algoritmo también relajó la suposición de que los vínculos debían estar presentes o ausentes (es decir, una red binaria) y permitió que se calculase la interdependencia en redes ponderadas (tenga en cuenta que esta generalización es independiente de la medida de flujo propuesta por Freeman et al., 1991, que podría ser más apropiado en ciertos entornos). Esta generalización tiene en cuenta que, en las redes ponderadas, la transacción entre dos nodos podría ser más rápida a lo largo de las rutas con más nodos intermedios que están fuertemente conectados que las rutas con menos nodos intermedios débilmente conectados. Esto se debe al hecho de que los nodos intermedios fuertemente conectados tienen, por ejemplo, un contacto más frecuente que los conectados débilmente. Por ejemplo, el vínculo entre el nodo superior izquierdo y el nodo focal en la red de muestra anterior tiene cuatro veces la fuerza del enlace entre el nodo inferior izquierdo y el nodo focal. Esto podría significar que el nodo superior izquierdo tiene contacto más frecuente con el nodo focal que el nodo inferior izquierdo. A su vez, esto podría implicar que el nodo superior izquierdo podría dar al nodo focal una información (o una enfermedad) cuatro veces más rápido que el nodo inferior izquierdo. Si estamos estudiando los nodos que con mayor probabilidad canalizan información o enfermedades en una red, entonces la velocidad a la que viaja y las rutas que lleva se ven claramente afectadas por los pesos. La identificación de las rutas más cortas en redes ponderadas también se puede utilizar al identificar los nodos que canalizan transacciones entre otros nodos en redes ponderadas. Si suponemos que las transacciones en una red ponderada siguen las rutas más cortas identificadas por el algoritmo de Dijkstra en lugar de la que tiene el menor número de nodos intermedios, entonces el número de rutas más cortas que pasan por un nodo podría cambiar.
.
| Nodo | Medida de intermediación de | ||
|---|---|---|---|
| Freeman (1978) | Brandes (2001) | Opsahl et al. (2010; alpha=0.5) | |
| 1 | 0 | 4 | 0 |
| 2 | 8 | 8 | 8 |
| 3 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 |
| 5 | 4 | 4 | 4 |
| 6 | 0 | 0 | 0 |
Ahora, el nodo 1 (A) también obtuvo una puntuación de interdependencia de 4. Esto se debe a que se usa la ruta indirecta desde el nodo B al nodo C hasta A en lugar de la conexión directa.
De forma similar a la generalización de proximidad de Newman (2001), el algoritmo generalizado de Brandes (2001) se centra únicamente en la suma de ponderaciones de relación y no tiene en cuenta la cantidad de vínculos en las rutas. Opsahl et al. (2010) la generalización de las rutas más cortas también puede aplicarse para identificarlas.
Para calcular las puntuaciones de interdete de los nodos, a continuación se muestra un código de muestra para producir las tres tablas anteriores utilizando el paquete de R de tnet.
.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| # Manually enter the example networknet <- cbind(i=c(1,1,2,2,2,2,3,3,4,5,5,6),j=c(2,3,1,3,4,5,1,2,2,2,6,5),w=c(4,2,4,1,4,2,2,1,4,2,1,1))# Calculate the binary betweenness measurebetweenness_w(net, alpha=0)# Calculate the first generation weighted betweenness measurebetweenness_w(net, alpha=1)# Calculate the first generation weighted betweenness measurebetweenness_w(net, alpha=0.5) |
Nota: La implementación del algoritmo de Brandes (2001) encuentra múltiples rutas si tienen exactamente la misma distancia. Por ejemplo, si se encuentra un camino sobre el empate directo con un peso de 1 (distancia = 1/1 = 1) y un segundo camino es a través de un nodo intermediario con dos empates con pesos de 2 (distancia = 1/2 + 1 / 2 = 1), las dos rutas tienen exactamente la misma distancia. Sin embargo, si hay un tercer camino a través de dos intermediarios con tres vínculos con pesos de 3 (distancia = 1/3 + 1/3 + 1/3), no es exactamente igual a 1 ya que las computadoras leen estos valores como 0.3333333 y la suma de estos valores es 0.9999999. Por lo tanto, esta ruta se considera más corta que las otras dos rutas (distancia = 1).
Referencias
Barrat, A., Barthelemy, M., Pastor-Satorras, R., Vespignani, A., 2004. The architecture of complex weighted networks. Proceedings of the National Academy of Sciences 101 (11), 3747-3752. arXiv:cond-mat/0311416Brandes, U., 2001. A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25, 163-177.
Dijkstra, E. W., 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271.
Freeman, L. C., 1978. Centrality in social networks: Conceptual clarification. Social Networks 1, 215-239.
Freeman, L. C., Borgatti, S. P., White, D. R., 1991. Centrality in valued graphs: A measure of betweenness based on network flow. Social Networks 13 (2), 141-154.
Newman, M. E. J., 2001. Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. Physical Review E 64, 016132.
Opsahl, T., Agneessens, F., Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks 32, 245-251.
.png)
![\mbox{closeness}(i) = \sum_j \left[ d_{ij} \right]^{-1} = \frac{1}{\sum_j d_{ij}}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_t15fBIvphJnZl9F4KL8ZCyMWbI3N2h0rfuvqaaV3I2j358yb4jJiKEL52LfGZcvZuRpzVPXXch6-D01d3WikIPg_Jmzjl6hakFhIhwkqt9ogEKSOl3hxz2BFKDWZ9wMYONX20YX-TWGCIIHN5EMBPWCnKEqmAXyEG0-rd1x-tbCE2LyeXFw3TtlLpuTekkaHZfy0hRvKpXyZ28gdSUDIhYO1NE3TzGkk2PRLFJrnXipGBQwJdXg5YgPM_kAQ8GVyblK2QL-KNzWZYo0bkYgnhQCrLsSZ8k4nDHG0HY=s0-d "\mbox{closeness}(i) = \sum_j \left[ d_{ij} \right]^{-1} = \frac{1}{\sum_j d_{ij}}")
es el nodo focal, 
es otro nodo en la red, y 
es la distancia mas corta entre estos dos nodos. En esta ecuación, las distancias están invertidas después de que se han sumado, y cuando la suma de un número infinito, el resultado es infinito. Para superar este problema durante su estancia en consonancia con la medida existente de cercanía, me aproveché del hecho de que el límite de un número dividido por infinito es cero. A pesar de que el infinito no es un número exacto, el inverso de un número muy alto es muy cercano a 0. De hecho, se devuelve 0 si introduce 1 / Inf en el programa estadístico R. Al tomar ventaja de esta característica, es posible reescribir la ecuación cercanía como la suma de las distancias La Inversa a todos los demás nodos en lugar de la inversa de la suma de las distancias a todos los demás nodos. La ecuación sería entonces: