Centralidad de Katz

En teoría de grafos , la centralidad de Katz o centralidad alfa de un nodo es una medida de centralidad en una red . Fue introducida 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 (la geodésica ) 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]

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 en la red que se conectan al nodo en consideración a través de estos vecinos inmediatos. Sin embargo, las conexiones realizadas con vecinos distantes se penalizan con 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 Jose se conecta a John indirectamente a través de Bob, el peso asignado a esta conexión (compuesta por dos vínculos) 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, Jose 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}$

Sea A la matriz de adyacencia de una red en consideración. 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 vínculos entre dos nodos a través de intermediarios. Por ejemplo, en la matriz , si elemento , indica que el nodo 2 y el nodo 12 están conectados a través de algún camino 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}}$

Nótese 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 manera que sea menor que el recíproco del valor absoluto del valor propio más grande 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 la 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 los recorridos 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 los recorridos para contribuir a un efecto acumulativo. La flecha del tiempo se conserva 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,}$

que representa la matriz de adyacencia en cada instante . Por lo tanto: ${\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 de manera uniforme. para lo cual es un recuento ponderado de la cantidad de caminatas dinámicas de longitud de nodo a nodo . La forma para la comunicabilidad dinámica entre 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, la centralidad mide la eficacia con la que un 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}}$.

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] utilizó un vector constante . Hubbell ^[9] introdujo el uso de un . ${\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}}}$

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 tradicionalmente utilizadas, como la centralidad del vector propio, resultan 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 una comparación de la metodología con la de expertos humanos en el campo y cómo los resultados concuerdan con un panel de expertos en redes sociales.

En neurociencia , se ha descubierto que la centralidad de Katz se correlaciona con la tasa 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 fMRI obtenidos de un experimento de aprendizaje musical en ^[14] donde se recogen 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 grupos en línea con el éxito del aprendizaje.

Una forma generalizada de centralidad de Katz se puede utilizar 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 el análisis y visualización de redes. ^[16]