Centralidad de Katz

Medida de centralidad en una red basada en influencia nodal.

En teoría de grafos , la centralidad de Katz o centralidad alfa de un nodo es una medida de centralidad en una red . Fue introducido por Leo Katz en 1953 y se utiliza para medir el grado relativo de influencia de un actor (o nodo) dentro de una red social . ^[1] A diferencia de las medidas de centralidad típicas que consideran solo el camino más corto (el geodésico ) entre un par de actores, la centralidad de Katz mide la influencia teniendo en cuenta el número total de caminatas entre un par de actores. ^[2]

Es similar al PageRank de Google y a la centralidad del vector propio . ^[3]

Medición

Una red social simple: los nodos representan personas o actores y los bordes entre nodos representan alguna relación entre actores.

La centralidad de Katz calcula la influencia relativa de un nodo dentro de una red midiendo el número de vecinos inmediatos (nodos de primer grado) y también todos los demás nodos de la red que se conectan al nodo considerado a través de estos vecinos inmediatos. Sin embargo, las conexiones realizadas con vecinos lejanos se ven penalizadas por un factor de atenuación . ^[4] A cada ruta o conexión entre un par de nodos se le asigna un peso determinado por y la distancia entre nodos como . ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{d}}$

Por ejemplo, en la figura de la derecha, supongamos que se está midiendo la centralidad de John y que . El peso asignado a cada vínculo que conecta a John con sus vecinos inmediatos Jane y Bob será . Dado que José se conecta con John indirectamente a través de Bob, el peso asignado a esta conexión (compuesta por dos enlaces) será . De manera similar, el peso asignado a la conexión entre Agneta y John a través de Aziz y Jane será y el peso asignado a la conexión entre Agneta y John a través de Diego, José y Bob será . ${\displaystyle \alpha =0.5}$ ${\displaystyle (0.5)^{1}=0.5}$ ${\displaystyle (0.5)^{2}=0.25}$ ${\displaystyle (0.5)^{3}=0.125}$ ${\displaystyle (0.5)^{4}=0.0625}$

formulación matemática

Sea A la matriz de adyacencia de una red considerada. Los elementos de A son variables que toman un valor 1 si un nodo i está conectado al nodo j y 0 en caso contrario. Las potencias de A indican la presencia (o ausencia) de enlaces entre dos nodos a través de intermediarios. Por ejemplo, en la matriz , si es elemento , indica que el nodo 2 y el nodo 12 están conectados a través de un recorrido de longitud 3. Si denota la centralidad de Katz de un nodo  i , entonces, dado un valor , matemáticamente: ${\displaystyle (a_{ij})}$ ${\displaystyle A^{3}}$ ${\displaystyle (a_{2,12})=1}$ ${\displaystyle C_{\mathrm {Katz} }(i)}$ ${\displaystyle \alpha \in (0,1)}$

${\displaystyle C_{\mathrm {Katz} }(i)=\sum _{k=1}^{\infty }\sum _{j=1}^{n}\alpha ^{k}(A^{k})_{ji}}$

Tenga en cuenta que la definición anterior utiliza el hecho de que el elemento en la ubicación de refleja el número total de conexiones de grado entre nodos y . El valor del factor de atenuación debe elegirse de modo que sea menor que el recíproco del valor absoluto del mayor valor propio de A. ^[5] En este caso se puede utilizar la siguiente expresión para calcular la centralidad de Katz: ${\displaystyle (i,j)}$ ${\displaystyle A^{k}}$ ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \alpha }$

${\displaystyle {\overrightarrow {C}}_{\mathrm {Katz} }=((I-\alpha A^{T})^{-1}-I){\overrightarrow {I}}}$

Aquí está la matriz identidad, es un vector de tamaño n ( n es el número de nodos) que consta de unos. denota la matriz transpuesta de A y denota inversión matricial del término . ^[5] ${\displaystyle I}$ ${\displaystyle {\overrightarrow {I}}}$ ${\displaystyle A^{T}}$ ${\displaystyle (I-\alpha A^{T})^{-1}}$ ${\displaystyle (I-\alpha A^{T})}$

Una extensión de este marco permite calcular las caminatas en un entorno dinámico. ^{[6] [7]} Al tomar una serie dependiente del tiempo de instantáneas de adyacencia de red de los bordes transitorios, se presenta la dependencia de las caminatas para contribuir a un efecto acumulativo. La flecha del tiempo se preserva de modo que la contribución de la actividad sea asimétrica en la dirección de propagación de la información.

Red que produce datos de la forma:

${\displaystyle \left\{A^{[k]}\in \mathbb {R} ^{N\times N}\right\}\qquad {\text{for}}\quad k=0,1,2,\ldots ,M,}$

representando la matriz de adyacencia en cada momento . Por eso: ${\displaystyle t_{k}}$

${\displaystyle \left(A^{[k]}\right)_{ij}={\begin{cases}1&{\text{there is an edge from node }}i{\text{ to node }}j{\text{ at time }}t_{k}\\0&{\text{otherwise}}\end{cases}}}$

Los puntos de tiempo están ordenados pero no necesariamente espaciados por igual. para lo cual es un recuento ponderado del número de caminatas dinámicas de longitud de un nodo a otro . La forma para la comunicabilidad dinámica entre los nodos participantes es: ${\displaystyle t_{0}<t_{1}<\cdots <t_{M}}$ ${\displaystyle Q\in \mathbb {R} ^{N\times N}}$ ${\displaystyle (Q)_{ij}}$ ${\displaystyle w}$ ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle {\mathcal {Q}}=\left(I-\alpha A^{[0]}\right)^{-1}\cdots \left(I-\alpha A^{[M]}\right)^{-1}.}$

Esto se puede normalizar mediante:

${\displaystyle {\hat {\mathcal {Q}}}^{[k]}={\frac {{\hat {\mathcal {Q}}}^{[k-1]}\left(I-\alpha A^{[k]}\right)^{-1}}{\left\|{\hat {\mathcal {Q}}}^{[k-1]}\left(I-\alpha A^{[k]}\right)^{-1}\right\|}}.}$

Por lo tanto, medidas de centralidad que cuantifican la eficacia con la que el nodo puede "transmitir" y "recibir" mensajes dinámicos a través de la red: ${\displaystyle n}$

${\displaystyle C_{n}^{\mathrm {broadcast} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{nk}\quad \mathrm {and} \quad C_{n}^{\mathrm {receive} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{kn}}$.

Centralidad alfa

Dado un gráfico con matriz de adyacencia , la centralidad de Katz se define de la siguiente manera: ${\displaystyle A_{i,j}}$

${\displaystyle {\vec {x}}=(I-\alpha A^{T})^{-1}{\vec {e}}-{\vec {e}}\,}$

donde es la importancia externa dada al nodo , y es un factor de atenuación no negativo que debe ser menor que el inverso del radio espectral de . La definición original de Katz ^[8] utilizaba un vector constante . Hubbell ^[9] introdujo el uso de un general . ${\displaystyle e_{j}}$ ${\displaystyle j}$ ${\displaystyle \alpha }$ ${\displaystyle A}$ ${\displaystyle {\vec {e}}}$ ${\displaystyle {\vec {e}}}$

Medio siglo después, Bonacich y Lloyd ^[10] definieron la centralidad alfa como:

${\displaystyle {\vec {x}}=(I-\alpha A^{T})^{-1}{\vec {e}}\,}$

que es esencialmente idéntica a la centralidad de Katz. Más precisamente, la puntuación de un nodo difiere exactamente en , por lo que si es constante el orden inducido en los nodos es idéntico. ${\displaystyle j}$ ${\displaystyle e_{j}}$ ${\displaystyle {\vec {e}}}$

Aplicaciones

La centralidad de Katz se puede utilizar para calcular la centralidad en redes dirigidas, como las redes de citas y la World Wide Web. ^[11]

La centralidad de Katz es más adecuada en el análisis de gráficos acíclicos dirigidos donde las medidas utilizadas tradicionalmente como la centralidad de vectores propios se vuelven inútiles. ^[11]

La centralidad de Katz también se puede utilizar para estimar el estatus relativo o la influencia de los actores en una red social. El trabajo presentado en ^[12] muestra el estudio de caso de la aplicación de una versión dinámica de la centralidad de Katz a los datos de Twitter y se centra en marcas particulares que tienen líderes de discusión estables. La aplicación permite comparar la metodología con la de expertos humanos en el campo y cómo los resultados coinciden con un panel de expertos en redes sociales.

En neurociencia , se encuentra que la centralidad de Katz se correlaciona con la velocidad relativa de activación de las neuronas en una red neuronal. ^[13] La extensión temporal de la centralidad de Katz se aplica a los datos de resonancia magnética funcional obtenidos de un experimento de aprendizaje musical en ^[14] donde se recopilan datos de los sujetos antes y después del proceso de aprendizaje. Los resultados muestran que los cambios en la estructura de la red a lo largo de la exposición musical crearon en cada sesión una cuantificación de la comunicabilidad cruzada que produjo clusters en línea con el éxito del aprendizaje.

Se puede utilizar una forma generalizada de centralidad de Katz como un sistema de clasificación intuitivo para equipos deportivos, como en el fútbol universitario . ^[15]

La centralidad alfa se implementa en la biblioteca igraph para análisis y visualización de redes. ^[dieciséis]

Referencias

1. Katz, L. (1953). Un nuevo índice de estatus derivado del análisis sociométrico. Psicometrika, 39–43.
2. Hanneman, RA y Riddle, M. (2005). Introducción a los métodos de redes sociales. Obtenido de http://faculty.ucr.edu/~hanneman/nettext/
3. Vigna, S. (2016). "Ranking espectral". Ciencia de redes . 4 (4): 433–445. doi : 10.1017/nws.2016.21 . hdl : 2434/527942 .
4. Aggarwal, CC (2011). Análisis de datos de redes sociales. Nueva York, Nueva York: Springer.
5. Junker, BH y Schreiber, F. (2008). Análisis de Redes Biológicas. Hoboken, Nueva Jersey: John Wiley & Sons.
6. Grindrod, Peter; Parsons, Mark C; Higham, Desmond J; Estrada, Ernesto (2011). "Comunicabilidad a través de redes en evolución" (PDF) . Revisión física E. 83 (4). APS: 046120. Código bibliográfico : 2011PhRvE..83d6120G. doi : 10.1103/PhysRevE.83.046120. PMID  21599253.
7. Peter Grindrod; Desmond J. Higham. (2010). "Gráficos en evolución: modelos dinámicos, problemas inversos y propagación". Proc. R. Soc. A . 466 (2115): 753–770. Código Bib : 2010RSPSA.466..753G. doi : 10.1098/rspa.2009.0456 .
8. Leo Katz (1953). "Un nuevo índice de estatus derivado del análisis sociométrico". Psicometrika . 18 (1): 39–43. doi :10.1007/BF02289026. S2CID  121768822.
9. Charles H. Hubbell (1965). "Un enfoque insumo-producto para la identificación de camarillas". Sociometría . 28 (4): 377–399. doi :10.2307/2785990. JSTOR  2785990.
10. P. Bonacich, P. Lloyd (2001). "Medidas de centralidad similares a vectores propios para relaciones asimétricas". Redes sociales . 23 (3): 191–201. CiteSeerX 10.1.1.226.2113 . doi :10.1016/S0378-8733(01)00038-7. 
11. Newman, ME (2010). Redes: una introducción. Nueva York, Nueva York: Oxford University Press.
12. Laflin, Peter; Mantzaris, Alejandro V; Ainley, Fiona; Otley, Amanda; Grindrod, Peter; Higham, Desmond J (2013). "Descubrir y validar la influencia en una red social online dinámica". Análisis y Minería de Redes Sociales . 3 (4). Saltador: 1311-1323. doi :10.1007/s13278-013-0143-7. S2CID  7125694.
13. Fletcher, Jack McKay; Wennekers, Thomas (2017). "De la estructura a la actividad: uso de medidas de centralidad para predecir la actividad neuronal". Revista internacional de sistemas neuronales . 28 (2): 1750013. doi : 10.1142/S0129065717500137 . hdl : 10026.1/9713 . PMID  28076982.
14. Mantzaris, Alejandro V.; Danielle S. Bassett; Nicolás F. Wymbs; Ernesto Estrada; Mason A. Portero; Pedro J. Mucha; Scott T. Grafton; Desmond J. Higham (2013). "La centralidad de la red dinámica resume el aprendizaje en el cerebro humano". Revista de redes complejas . 1 (1): 83–92. arXiv : 1207.5047 . doi : 10.1093/comnet/cnt001.
15. Parque, Juyong; Newman, MEJ (31 de octubre de 2005). "Un sistema de clasificación basado en red para el fútbol universitario americano". Revista de Mecánica Estadística: Teoría y Experimento . 2005 (10): P10014. arXiv : física/0505169 . doi :10.1088/1742-5468/2005/10/P10014. ISSN  1742-5468. S2CID  15120571.
16. "Bienvenido al nuevo hogar de igraph".