martes, 10 de noviembre de 2015

ARS 101: Centralidad de autovector

Centralidad de autovector

Información general

La centralidad de vector propio o autovector es uno de varios indicadores de nodo que caracterizan la prominencia "global" (en lugar de "local") de un vértice o nodo en un grafo. Otros incluyen la centralidad poder de Katz, Bonacich, y Page Rank.

La esencia de la centralidad del vector propio es calcular la centralidad de un nodo como una función de las centralidades de sus vecinos.

¿Qué es un vector propio?

Considere el siguiente gráfico y su matriz de adyacencia 5x5, A.


Y luego considere, x, un vector 5x1 de valores, uno para cada vértice o nodo en el grafo. En este caso, hemos utilizado la centralidad grado de cada vértice.

Ahora echemos un vistazo a lo que sucede cuando se multiplica el vector x de la matriz A. El resultado, por supuesto, es otro vector 5x1.


Si nos fijamos bien en el primer elemento del vector resultante vemos que los 1s en la matriz A "recogen" los valores de cada vértice al que está conectado el primer vértice (en este caso, el segundo, tercero y cuarto) y el valor resultante es la suma de los valores de cada uno de estos vértices tenido.

En otras palabras, lo que la multiplicación por la matriz de adyacencia hace, es reasignar a cada vértice la suma de los valores de sus vértices vecinos.


Esto, en efecto, "difunde" la centralidad de grado. Esto se está moviendo en la dirección de una métrica razonable para centralidad se puede ver mejor si reordenamos el grafo un poco:


Supongamos que multiplicamos el vector resultante de A de nuevo, ¿cómo podemos interpretar lo que eso significa? En efecto, estaríamos permitiendo que este valor de centralidad de una vez se "extendiera" a través de los enlaces del grafo. Y nos dimos cuenta de que la propagación es en ambas direcciones (los vértices tanto dan como reciben de sus vecinos). Podríamos especular que este proceso podría finalmente llegar a un equilibrio cuando la cantidad que entra en un vértice dado estaría en equilibrio con la cantidad de salir a sus vecinos. Ya que estamos simplemente añadiendo cosas, los números seguirían cada vez más grande, pero podría llegar a un punto en que la participación en el total en cada nodo se mantendría estable.

En ese momento nos podríamos imaginar que toda la "centralidad" del grafo habían equilibrada y el valor de cada nodo capturado por completo el carácter central de todos sus vecinos, todo el camino hasta los enlaces del grafo.

Ahora imagine un vector más genérico de valores para nuestros vértices - sólo (v, w, x, y, z) donde las letras representan valores desconocidos. Vamos a escribir lo que multiplicando este vector por la matriz A se vería


Una nota aparte

Cuando multiplicamos un vector o matriz con sólo un número - lo llamamos un "escalar" - ¿cómo funciona? Lo que por ejemplo, podría ser el doble del vector (1,3)? La respuesta es simple: usted multiplica cada elemento por el escalar. Así, el resultado sería (2,6). Lo mismo es cierto para una matriz:

 (1)

Y, en general, se escribe esta "multiplicación escalar" con una variable no negrita delante del vector o matriz. Por lo tanto, la bM significaría la matriz M multiplicado por el escalar b.

Volviendo al grafo y la centralidad

Así, podemos escribir esta última ecuación como Mx = y. Pero nuestro punto era que podría haber algún conjunto de valores en nuestros vértices, (es decir, algunos {\ bf x}), para el que la multiplicación por A no iba a cambiar los tamaños relativos de los valores de los componentes del vector - el número haría hacen más grandes, pero todos por el mismo factor. Podemos expresar esto así:


Un vector con esta propiedad - que puede ser multiplicado por la matriz de adyacencia de un grafo y retorna a sí multiplicado por un escalar - es una característica de esta matriz de adyacencia particular. En otras palabras, hay algo en el patrón particular de conexiones en este gráfico que conduce a un conjunto específico de valores de vértices que tendrán la propiedad de equilibrio descrito anteriormente.

Este vector se denomina un vector propio de la matriz A.

Los elementos de este vector son las centralidades de vector propio de los vértices del grafo.

Referencias y Exploración

Borgatti, Stephen. Centrality for MGMT 780 at UK School of Business.
Wikidot

No hay comentarios:

Publicar un comentario