Rango Chei

Nodos con enlaces en el plano de PageRank y CheiRank

El CheiRank es un vector propio con un valor propio real máximo de la matriz de Google construida para una red dirigida con las direcciones invertidas de los enlaces. Es similar al vector PageRank , que clasifica los nodos de la red en promedio proporcionalmente a un número de enlaces entrantes que es el vector propio máximo de la matriz de Google con una dirección inicial dada de enlaces. Debido a la inversión de las direcciones de los enlaces, el CheiRank clasifica los nodos de la red en promedio proporcionalmente a un número de enlaces salientes. Dado que cada nodo pertenece tanto a los vectores CheiRank como a los de PageRank, la clasificación del flujo de información en una red dirigida se vuelve bidimensional . ${\displaystyle G^{*}}$ ${\displaystyle G}$

Definición

Fig. 1. Distribución de las llamadas a procedimientos de la red del kernel de Linux en el plano de probabilidad de PageRank y probabilidad de CheiRank para la versión 2.6.32 de Linux con un tamaño de matriz de , el color muestra la densidad de nodos con blanco para el máximo y azul para el mínimo, el espacio negro no tiene nodos (de Chepelianskii) ${\displaystyle x=\log _{10}P_{i}}$ ${\displaystyle y=\log _{10}{P}_{i}^{*}}$ ${\displaystyle N=285509}$ ${\displaystyle \alpha =0.85}$

Para una red dirigida dada, la matriz de Google se construye de la manera descrita en el artículo Matriz de Google . El vector PageRank es el vector propio con el valor propio real máximo . Se introdujo en ^[1] y se analiza en el artículo PageRank . De manera similar, el CheiRank es el vector propio con el valor propio real máximo de la matriz construida de la misma manera que pero utilizando la dirección invertida de los enlaces en la matriz de adyacencia dada inicialmente . Ambas matrices y pertenecen a la clase de operadores de Perron-Frobenius y, según el teorema de Perron-Frobenius, los vectores propios CheiRank y PageRank tienen componentes no negativos que pueden interpretarse como probabilidades. ^{[2] [3]} Por lo tanto, todos los nodos de la red se pueden ordenar en un orden de probabilidad decreciente con rangos para CheiRank y PageRank respectivamente. En promedio, la probabilidad de PageRank es proporcional al número de enlaces entrantes con . ^{[4] [5] [6]} Para la red World Wide Web (WWW), el exponente donde es el exponente de la distribución de enlaces entrantes. ^{[4] [5]} De manera similar, la probabilidad de CheiRank es en promedio proporcional al número de enlaces salientes con donde es el exponente de la distribución de enlaces salientes de la WWW. ^{[4] [5]} El CheiRank se introdujo para la red de llamadas a procedimientos del software del kernel de Linux en, ^[7] el término en sí se utilizó en Zhirov. ^[8] Mientras que el PageRank resalta los nodos muy conocidos y populares, el CheiRank resalta los nodos muy comunicativos. Los nodos superiores de PageRank y CheiRank tienen cierta analogía con las autoridades y los centros que aparecen en el algoritmo HITS ^[9] pero el HITS depende de la consulta mientras que las probabilidades de rango clasifican todos los nodos de la red. Dado que cada nodo pertenece tanto a CheiRank como a PageRank, obtenemos una clasificación bidimensional de los nodos de la red. Se habían realizado estudios preliminares sobre PageRank en redes con dirección invertida de enlaces ^{[10] [11],} pero las propiedades del ranking bidimensional no se habían analizado en detalle. ${\displaystyle \lambda =1}$ ${\displaystyle G^{*}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G^{*}}$ ${\displaystyle P_{i}^{*}}$ ${\displaystyle P_{i}}$ ${\displaystyle N}$ ${\displaystyle i}$ ${\displaystyle K_{i}^{*},K_{i}}$ ${\displaystyle P_{i}^{*},P_{i}}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{i}\propto 1/{K_{i}}^{\beta }}$ ${\displaystyle \beta =1/(\nu -1)\approx 0.9}$ ${\displaystyle \nu \approx 2.1}$ ${\displaystyle P_{i}^{*}\propto 1/{K_{i}^{*}}^{\beta ^{*}}}$ ${\displaystyle \beta ^{*}=1/(\nu ^{*}-1)\approx 0.6}$ ${\displaystyle \nu ^{*}\approx 2.7}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{i}^{*}}$

Fig. 2. Dependencia de la probabilidad de PageRank (curva roja) y CheiRank (curva azul) en los índices de rango correspondientes y . Las líneas discontinuas rectas muestran la dependencia de la ley de potencia con la pendiente respectivamente, correspondiente a (de Zhirov) ${\displaystyle P}$ ${\displaystyle P^{*}}$ ${\displaystyle K}$ ${\displaystyle K^{*}}$ ${\displaystyle \beta =0.92;0.57}$ ${\displaystyle \beta =1/(\nu -1)}$

Ejemplos

En la figura 1 se muestra un ejemplo de distribución de nodos en el plano de PageRank y CheiRank para la red de llamadas a procedimientos del software del kernel de Linux. ^[7]

Fig. 3. Distribución de la densidad de los artículos de Wikipedia en inglés (2009) en el plano de los índices PageRank y CheiRank, mostrados por colores, con azul para el mínimo y blanco para el máximo (negro para cero); los puntos verdes/rojos muestran las 100 personalidades principales de PageRank/CheiRank, los signos más amarillos muestran las 100 personalidades principales del libro de Hart, número de artículos (de Zhirov) ${\displaystyle 0<\ln K,\ln K^{*}<\ln N}$ ${\displaystyle N=3282257}$

La dependencia de la red de hipervínculos de los artículos de Wikipedia en inglés se muestra en la Fig. 2 de Zhirov. La distribución de estos artículos en el plano de PageRank y CheiRank se muestra en la Fig. 3 de Zhirov. La diferencia entre PageRank y CheiRank se ve claramente en los nombres de los artículos de Wikipedia (2009) con el rango más alto. En la parte superior de PageRank tenemos 1. Estados Unidos, 2. Reino Unido, 3. Francia mientras que para CheiRank encontramos 1. Portal: Contenidos/Esquema de conocimiento/Geografía y lugares, 2. Lista de líderes estatales por año, 3. Portal: Contenidos/Índice/Geografía y lugares. Claramente PageRank selecciona primero los artículos sobre un tema ampliamente conocido con una gran cantidad de enlaces entrantes mientras que CheiRank selecciona primero los artículos altamente comunicativos con muchos enlaces salientes. Dado que los artículos se distribuyen en 2D, se pueden clasificar de varias maneras correspondientes a la proyección del conjunto 2D en una línea. Las líneas horizontales y verticales corresponden a PageRank y CheiRank, 2DRank combina propiedades de CheiRank y PageRank como se analiza en Zhirov. ^[8] Muestra los principales artículos de Wikipedia: 1.India, 2.Singapur, 3.Pakistán. ${\displaystyle P,P^{*}}$ ${\displaystyle K,K^{*}}$

El ranking 2D destaca las propiedades de los artículos de Wikipedia de una manera nueva, rica y fructífera. Según el PageRank, las 100 personalidades principales descritas en los artículos de Wikipedia tienen actividades en 5 categorías principales: 58 (política), 10 (religión), 17 (arte), 15 (ciencia), 0 (deporte), y por lo tanto la importancia de los políticos está fuertemente sobreestimada. El CheiRank da respectivamente 15, 1, 52, 16, 16 mientras que para el 2DRank se encuentran 24, 5, 62, 7, 2. Este tipo de ranking 2D puede encontrar aplicaciones útiles para varias redes dirigidas complejas, incluida la WWW.

CheiRank y PageRank aparecen naturalmente para la red de comercio mundial, o comercio internacional , donde están vinculados con los flujos de exportación e importación de un país determinado respectivamente. ^[12]

Se consideran las posibilidades de desarrollo de motores de búsqueda bidimensionales basados ​​en PageRank y CheiRank. ^[13] Las redes dirigidas se pueden caracterizar por el correlador entre los vectores PageRank y CheiRank: en ciertas redes este correlador es cercano a cero (por ejemplo, la red del kernel de Linux), mientras que otras redes tienen valores de correlador grandes (por ejemplo, Wikipedia o redes universitarias). ^{[7] [13]}

Ejemplo de red sencilla

Fig. 4. Ejemplo de red dirigida

Fig. 5. Matriz relacionada ${\displaystyle S}$

Fig. 6. Matriz relacionada ${\displaystyle S^{*}}$

A continuación se muestra un ejemplo simple de la construcción de las matrices de Google y , utilizadas para la determinación de los vectores PageRank y CheiRank relacionados. El ejemplo de red dirigida con 7 nodos se muestra en la Fig.4. La matriz , construida con las reglas descritas en el artículo Matriz de Google , se muestra en la Fig.5; la matriz de Google relacionada es y el vector PageRank es el vector propio derecho de con el valor propio unitario ( ). De manera similar, para determinar el vector propio CheiRank se invierten todas las direcciones de los enlaces en la Fig.4, luego se construye la matriz, de acuerdo con las mismas reglas aplicadas para la red con direcciones de enlace invertidas, como se muestra en la Fig.6. La matriz de Google relacionada es y el vector CheiRank es el vector propio derecho de con el valor propio unitario ( ). Aquí está el factor de amortiguamiento tomado en su valor habitual. ${\displaystyle G}$ ${\displaystyle G^{*}}$ ${\displaystyle S}$ ${\displaystyle G=\alpha S+(1-\alpha )ee^{T}/N}$ ${\displaystyle G}$ ${\displaystyle GP=P}$ ${\displaystyle S^{*}}$ ${\displaystyle G^{*}=\alpha S^{*}+(1-\alpha )ee^{T}/N}$ ${\displaystyle G^{*}}$ ${\displaystyle G^{*}P^{*}=P^{*}}$ ${\displaystyle \alpha \approx 0.85}$

Véase también

• PageRank , algoritmo HITS , matriz de Google
• Cadenas de Markov , Operador de transferencia , Teorema de Perron-Frobenius
• Recuperación de información
• Motores de búsqueda web

Referencias

1. Brin S.; Page L. (1998), "La anatomía de un motor de búsqueda web hipertextual a gran escala", Computer Networks and ISDN Systems , 30 (1–7): 107, doi :10.1016/S0169-7552(98)00110-X, S2CID  7587743
2. Langville, Amy N .; Carl Meyer (2006). PageRank de Google y más allá . Princeton University Press . ISBN 0-691-12202-4.
3. Austin, David (2008). "Cómo Google encuentra su aguja en el pajar de la Web". Columnas destacadas de AMS.
4. Donato D.; Laura L.; Leonardi S.; Millozzi S. (2004), "Propiedades a gran escala del Webgraph", European Physical Journal B , 38 (2): 239, Bibcode :2004EPJB...38..239D, doi :10.1140/epjb/e2004-00056-6, S2CID  10640375
5. Pandurangan G.; Ranghavan P.; Upfal E. (2005), "Uso de PageRank para caracterizar la estructura web", Internet Math. , 3 : 1, doi : 10.1080/15427951.2006.10129114
6. Litvak, N .; Scheinhardt, WRW; Volkovich, Y. (2008), Relación probabilística entre el grado de entrada y el PageRank , Lecture Notes in Computer Science, vol. 4936, pág. 72
7. Chepelianskii, Alexei D. (2010). "Hacia leyes físicas para la arquitectura de software". arXiv : 1003.5455 [cs.SE].
8. Zhirov AO; Zhirov OV; Shepelyansky DL (2010), "Clasificación bidimensional de artículos de Wikipedia", European Physical Journal B , 77 (4): 523, arXiv : 1006.4270 , Bibcode :2010EPJB...77..523Z, doi :10.1140/epjb/e2010 -10500-7, S2CID  18014470
9. Kleinberg, Jon (1999). "Fuentes autorizadas en un entorno hipervinculado". Revista de la ACM . 46 (5): 604–632. doi : 10.1145/324133.324140 . S2CID  221584113.
10. Fogaras, D. (2003), ¿Por dónde empezar a navegar por la web?, Lecture Notes in Computer Science, vol. 2877, pág. 65
11. Hrisitidis V.; Hwang H.; Papakonstantinou Y. (2008), "Búsqueda de palabras clave basada en autoridad en bases de datos", ACM Trans. Database Syst. , 33 : 1, doi :10.1145/1331904.1331905, S2CID  11978441
12. Ermann L.; Shepelyansky DL (2011). "Matriz de Google de la red de comercio mundial". Acta Physica Polonica A . 120 (6A): A. arXiv : 1103.5027 . Código Bibliográfico :2011AcPPA.120..158E. doi :10.12693/APhysPolA.120.A-158. S2CID  18315654.
13. Ermann L.; Chepelianskii AD; Shepelyansky DL (2011). "Hacia motores de búsqueda bidimensionales". Journal of Physics A: Mathematical and Theoretical . 45 (27): 275101. arXiv : 1106.6215 . Bibcode :2012JPhA...45A5101E. doi :10.1088/1751-8113/45/27/275101. S2CID  14827486.

Enlaces externos

• Clasificación bidimensional de los artículos de Wikipedia
• Comercio mundial: CheiRank versus PageRank
• Hacia motores de búsqueda bidimensionales
• Personajes destacados de Wikipedia