miércoles, 14 de septiembre de 2016

ARS 101: Centralidad Alfa



Centralidad Alfa
Wikipedia

En la teoría de grafos y análisis de redes sociales, la centralidad Alfa es una medida de centralidad de los nodos de un grafo. Es una adaptación de la centralidad de vector propio con la particularidad de que los nodos están impregnadas de importancia a partir de fuentes externas.

Definición

Dada una gráfica con la matriz de adyacencia A_{i,j} la centralidad alfa se define como sigue:

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

donde e_{j} es la importancia dada al nodo externo j y \alpha  es un parámetro. [1]

Motivación

Para entender la centralidad alfa primero hay que entender Centralidad del Vector Propio. Un proceso intuitivo para calcular vector propio carácter central es dar a cada nodo de una cantidad positiva al azar a partir de influencia. Cada nodo se divide entonces su influencia de manera uniforme y lo divide entre sus vecinos hacia el exterior, recibiendo de sus vecinos hacia el interior en especie. Este proceso se repite hasta que todo el mundo está dando hacia fuera tanto como que están tomando y el sistema ha alcanzado el estado estacionario. La cantidad de influencia que tienen en este estado estacionario es su centralidad del vector propio. Computacionalmente este proceso se llama el método de la potencia. Sabemos que este proceso ha convergido cuando el vector de influencia cambia sólo por una constante de la siguiente manera.

x_{i}={\frac  {1}{\lambda }}A_{{i,j}}^{T}x_{j}

Donde x_{i} es la cantidad de influencia que el nodo i lleva, A_{i,j} es la matriz de adyacencia y \lambda  pasa a ser el valor propio director (aunque esto no es muy importante en este caso).

La centralidad Alfa mejora este proceso al permitir que los nodos que tienen fuentes de influencia. La cantidad de influencia que el nodo i recibe en cada ronda se codifica en e_{i}. El proceso descrito anteriormente ahora debe detenerse cuando

x_{i}=\alpha A_{{i,j}}^{T}x_{j}+e_{i}\,,
Donde \alpha  es una constante que intercambia la importancia de la influencia externa en contra de la importancia de la conexión. Cuando \alpha =0 sólo importa la influencia externa. Cuando \alpha  es muy grande, entonces sólo importa la conectividad, es decir, reducimos al caso centralidad del vector propio.

En lugar de realizar la iteración descrita anteriormente se puede resolver este sistema para x, obteniendo la siguiente ecuación:

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

Aplicaciones

La centralidad Alfa se lleva a cabo en la biblioteca igraph para el análisis y visualización de red. [2]




Ejemplo

FUna epidemia representa otro tipo de flujo en una red. Una epidemia es un proceso dinámico que, a diferencia del paseo aleatorio, transiciona simultáneamente a todos los vecinos de un nodo dado (y con éxito infecta cada nodo, o sobrevive en ese nodo, con una probabilidad a). La película anterior muestra una propagación de la epidemia en el gráfico Club de Karate. Bajo ciertas condiciones, que alcanza un estado estacionario, dada por centralidad Alfa. La centralidad Alfa fue introducido por Bonacich [1987] como una generalización del índice de Katz de un nodo. Cuando la probabilidad de infección está supeditada a sobrepasar un umbral epidémico, la centralidad Alfa del Vector Propio es proporcional a la centralidad. Esta medida, introducido por Bonacich [2001] está dada por el vector propio que corresponde al valor propio más grande de la matriz de adyacencia del grafo [Ghosh y Lerman, 2011]. Por cierto, el umbral de epidemia está dado por la inversa de la mayor valor propio de la matriz de adyacencia [Wang et al., 2003].

Código de Matlab para calcularla


a=0.1; % damping factor has to be smaller than 1/lambda0, where lambda0 is largest eigenvalue of A
s=A*t;
cr=s;
for i=1:20
    cr=s+a*A*cr;
end
cr

Fuente

No hay comentarios:

Publicar un comentario