Centralidad del vector propio

Medida de la influencia de un nodo en una red

En teoría de grafos , la centralidad del vector propio (también llamada centralidad propia o puntuación de prestigio ^[1] ) es una medida de la influencia de un nodo en una red conectada . Se asignan puntuaciones relativas a todos los nodos de la red basándose en el concepto de que las conexiones a nodos con puntuación alta contribuyen más a la puntuación del nodo en cuestión que las conexiones iguales a nodos con puntuación baja. Una puntuación de vector propio alta significa que un nodo está conectado a muchos nodos que a su vez tienen puntuaciones altas. ^{[2] [3]}

El PageRank de Google y la centralidad de Katz son variantes de la centralidad del vector propio. ^[4]

Usando la matriz de adyacencia para encontrar la centralidad del vector propio

Para un gráfico dado con vértices, sea la matriz de adyacencia , es decir, si el vértice está vinculado al vértice , y en caso contrario. La puntuación de centralidad relativa, , del vértice se puede definir como: ${\displaystyle G:=(V,E)}$ ${\displaystyle |V|}$ ${\displaystyle A=(a_{v,t})}$ ${\displaystyle a_{v,t}=1}$ ${\displaystyle v}$ ${\displaystyle t}$ ${\displaystyle a_{v,t}=0}$ ${\displaystyle x_{v}}$ ${\displaystyle v}$

${\displaystyle x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\sum _{t\in V}a_{v,t}x_{t}}$

donde es el conjunto de vecinos de y es una constante. Con una pequeña reordenación esto se puede reescribir en notación vectorial como la ecuación de vector propio ${\displaystyle M(v)}$ ${\displaystyle v}$ ${\displaystyle \lambda }$

${\displaystyle \mathbf {Ax} =\lambda \mathbf {x} }$

En general, habrá muchos valores propios diferentes para los cuales existe una solución de vector propio distinto de cero. Sin embargo, el supuesto de conectividad y el requisito adicional de que todas las entradas en el vector propio no sean negativas implican (según el teorema de Perron-Frobenius ) que sólo el mayor valor propio da como resultado la medida de centralidad deseada. ^[5] El componente del vector propio relacionado proporciona la puntuación de centralidad relativa del vértice en la red. El vector propio solo está definido hasta un factor común, por lo que solo las razones de las centralidades de los vértices están bien definidas. Para definir una puntuación absoluta, se debe normalizar el vector propio, por ejemplo, de modo que la suma de todos los vértices sea 1 o el número total de vértices  n . La iteración de potencia es uno de los muchos algoritmos de valores propios que pueden usarse para encontrar este vector propio dominante. ^[4] Además, esto se puede generalizar de modo que las entradas en A puedan ser números reales que representen intensidades de conexión, como en una matriz estocástica . ${\displaystyle \lambda }$ ${\displaystyle v^{\text{th}}}$ ${\displaystyle v}$

Puntuación de centralidad de vector propio normalizada

El PageRank de Google se basa en la centralidad del vector propio normalizado, o prestigio normalizado, combinado con una suposición de salto aleatorio. ^[1] El PageRank de un nodo tiene una dependencia recursiva del PageRank de otros nodos que apuntan a él. La matriz de adyacencia normalizada se define como: ${\displaystyle v}$ ${\displaystyle N}$

$${\displaystyle N(u,v)={\begin{cases}{1 \over \operatorname {od} (u)},&{\text{if }}(u,v)\in E\\0,&{\text{if }}(u,v)\not \in E\end{cases}}}$$

grado de salida ${\displaystyle od(u)}$ ${\displaystyle u}$

${\displaystyle \mathbf {N} =\mathbf {diag} (\mathbf {Ae} )^{-1}\mathbf {A} }$,

donde es el vector de unos y es la matriz diagonal del vector . es una matriz estocástica por filas. ${\displaystyle \mathbf {e} }$ ${\displaystyle \mathbf {diag} (\mathbf {x} )}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {N} }$

La puntuación de prestigio del vector propio normalizado se define como:

${\displaystyle p(v)=\sum _{u}{N^{T}(v,u)\cdot p(u)},}$

o en forma vectorial,

${\displaystyle \mathbf {p} =\mathbf {N} ^{T}\mathbf {p} .}$

Aplicaciones

La centralidad del vector propio es una medida de la influencia que tiene un nodo en una red. Si muchos nodos (que también tienen una alta centralidad de vector propio) apuntan a un nodo, entonces ese nodo tendrá una alta centralidad de vector propio. ^[6]

El primer uso de la centralidad del vector propio lo realizó Edmund Landau en un artículo de 1895 sobre la puntuación de torneos de ajedrez. ^{[7] [8]}

Más recientemente, investigadores de muchos campos han analizado aplicaciones, manifestaciones y extensiones de la centralidad del vector propio en una variedad de dominios:

• La centralidad del vector propio es la única medida que satisface ciertos axiomas naturales para un sistema de clasificación. ^{[9] [10]}
• En neurociencia , se ha descubierto que la centralidad del vector propio de una neurona en una red neuronal modelo se correlaciona con su tasa de activación relativa. ^[6]
• La centralidad del vector propio y conceptos relacionados se han utilizado para modelar la influencia de la opinión en sociología y economía, como en el modelo de aprendizaje de DeGroot .
• La definición de centralidad de vector propio se ha extendido a redes multiplex ^[11] y multicapa a través del concepto de versatilidad ^[12].
• En un estudio que utilizó datos de Filipinas, los investigadores mostraron cómo las familias de los candidatos políticos tenían una centralidad de vector propio desproporcionadamente alta en las redes locales de matrimonios mixtos. ^[13]
• La centralidad del vector propio se ha aplicado ampliamente para estudiar resultados económicos, incluida la cooperación en redes sociales. ^[14] En los problemas económicos de bienes públicos , la centralidad del vector propio de una persona puede interpretarse como el grado en que las preferencias de esa persona influyen en un resultado social eficiente. ^[15]

Ver también

• Centralidad

Referencias

1. Zaki, Mohammed J.; Meira, Wagner Jr. (2014). Minería y análisis de datos: conceptos y algoritmos fundamentales . Prensa de la Universidad de Cambridge. ISBN 9780521766333.
2. MEJ Newman. «Las matemáticas de las redes» (PDF) . Consultado el 9 de noviembre de 2006 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
3. Christian FA Negre, Uriel N. Morzan, Heidi P. Hendrickson, Rhitankar Pal, George P. Lisi, J. Patrick Loria, Ivan Rivalta, Junming Ho, Victor S. Batista. (2018). "Centralidad del vector propio para la caracterización de vías alostéricas de proteínas". Procedimientos de la Academia Nacional de Ciencias . 115 (52): E12201–E12208. arXiv : 1706.02327 . Código Bib : 2018PNAS..11512201N. doi : 10.1073/pnas.1810452115 . PMC 6310864 . PMID  30530700. {{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
4. David Austin. "Cómo Google encuentra su aguja en el pajar de la Web". AMS.
5. MEJ Newman. «Las matemáticas de las redes» (PDF) . Consultado el 9 de noviembre de 2006 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
6. Fletcher, Jack McKay y 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.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
7. Edmundo Landau (1895). "Zur relatedn Wertbemessung der Turnierresultate". Deutsches Wochenschach (11): 366–369. doi :10.1007/978-1-4615-4819-5_23.
8. Holmes, Peter (15 de abril de 2019). "Primeros en la ciencia de las redes" . Consultado el 17 de abril de 2019 .
9. Altman, Alon; Tennenholtz, Moshe (2005). "Sistemas de clasificación". Actas de la sexta conferencia ACM sobre comercio electrónico - EC '05 . Nueva York, Nueva York, Estados Unidos: ACM Press. págs. 1–8. doi :10.1145/1064009.1064010. ISBN 1-59593-049-3.
10. Palacios-Huerta, Ignacio; Volij, Óscar (2004). "La medición de la influencia intelectual" (PDF) . Econométrica . 72 (3). La sociedad econométrica: 963–977. doi :10.1111/j.1468-0262.2004.00519.x. hdl : 10419/80143 . ISSN  0012-9682.
11. Solá, Luis; Romántico, Miguel; Criado, Regino; Flores, Julio; García del Amo, Alejandro; Boccaletti, Stefano (2013). "Centralidad del vector propio de nodos en redes multiplex". Caos: una revista interdisciplinaria de ciencia no lineal . 23 (3): 033131. arXiv : 1305.7445 . Código Bib :2013Caos..23c3131S. doi : 10.1063/1.4818544. ISSN  1054-1500. PMID  24089967. S2CID  14556381.
12. De Domenico, Manlio; Solè-Ribalta, ALbert; Omodei, Elisa; Gómez, Sergio; Arenas, Álex (2015). "La clasificación en redes multicapa interconectadas revela nodos versátiles". Comunicaciones de la naturaleza . 6 : 6868. arXiv : 1305.7445 . doi : 10.1063/1.4818544. ISSN  2041-1723. PMID  25904405. S2CID  14556381.
13. Cruz, Cesi; Labonne, Julien; Querubin, Pablo (2017). "Redes de familias políticas y resultados electorales: evidencia de Filipinas". Revista económica estadounidense . 107 (10). Prensa de la Universidad de Chicago: 3006–37. doi : 10.1257/aer.20150343 .
14. Jackson, Matthew O. (1 de noviembre de 2010). Redes Sociales y Económicas. Prensa de la Universidad de Princeton. doi :10.2307/j.ctvcm4gh1. ISBN 978-1-4008-3399-3. JSTOR  j.ctvcm4gh1.
15. Elliott, Mateo; Golub, Benjamín (2019). "Un enfoque de red para los bienes públicos". Revista de Economía Política . 127 (2). Prensa de la Universidad de Chicago: 730–776. doi :10.1086/701032. ISSN  0022-3808. S2CID  158834906.