C´omo mejorar el PageRank de un a´ rbol Arratia Quesada, A. (a) * ; Mariju´an, C.(a)** (a) Departamento

de Matem´atica Aplicada Universidad de Valladolid Valladolid 47005, Espa˜na [email protected],

[email protected]

Resumen. Probamos que el PageRank de la ra´ız de un a´ rbol (PR) s´olo depende de la partici´on de sus nodos en niveles (y no de las conexiones entre niveles). Probamos que la supresi´on del u´ ltimo nivel o de todos los nodos posibles (conservando la altura) en la mitad superior del a´ rbol aumenta su PR. Introducimos el concepto de a´ rbol cola como el sub´arbol de igual altura y menor nu´ mero de nodos con PR mayor que en el original. Damos f´ormulas para calcular el PR de varias clases de a´ rboles, los jerarquizamos en funci´on de su altura y de su tama˜no y damos reglas para mejorar su PR.

1. Introducci´on La red WWW puede verse como un grafo dirigido W = (V, E), donde V es el conjunto de nodos (p´aginas) de la red y cada arco (b, a) ∈ E representa la existencia de un v´ınculo en la p´agina b con la p´agina a. Con este punto de vista, Brin y Page proponen en [1] valorar cada p´agina a de la red con el n´umero positivo P(a) (el PageRank de la p´agina a) dado por la f´ormula (en la versi´on refinada de [2]): P(a) =

P(b) (1 − α ) +α ∑ N C(b) (b,a)∈E

(1)

donde C(b) es el n´umero de v´ınculos en la p´agina b (el exgrado de b), α ∈ (0, 1) es una constante (para la que Brin y Page toman el valor 0,85), N es el nu´ mero total de p´aginas en la red. y el sumatorio se extiende a todas las p´aginas b que tienen un v´ınculo con la p´agina a. Seg´un sus autores, la f´ormula (1) modela el comportamiento de un surfista aleatorio que estando en una p´agina b o bien se conecta, con probabilidad α , con alguna de las p´aginas vinculadas en b o bien salta, con * Parcialmente

financiado por los proyectos MOISES (TIN2005-08832-C03-02) y SINGACOM (MTM2004-00958). ** Financiado por el proyecto SINGACOM (MTM2004-00958).

53

54

Arratia,A.; Mariju´an, C.

probabilidad 1 − α , a cualquier p´agina de la red, independientemente de los contenidos de las p´aginas (ver [5]). De modo que P(b)/C(b) es la aportaci´on de b al PageRank de a amortizado por α . El PageRank de a es, entonces, la probabilidad de que un usuario alcance la p´agina a directamente o a trav´es de una sucesi´on de v´ınculos. Los PageRanks de todas las p´aginas suman 1, de modo que constituyen una distribuci´on de probabilidad sobre la red. Se ha observado que el PageRank de una p´agina depende impl´ıcitamente de la topolog´ıa conectiva local y global de la Web y que frecuentemente las web locales presentan estructuras regulares como a´ rboles dirigidos (o bidireccionales) hacia la ra´ız (su p´agina principal). Nos proponemos estudiar c´omo modificar la estructura conectiva de estas web locales con el objetivo de optimizar el PageRank de su p´agina principal.

2. El PageRank de un a´ rbol Por un a´ rbol entenderemos un grafo dirigido ac´ıclico conexo con ra´ız y con exgrados igual a 1 (i.e. arcos dirigidos hacia la ra´ız). La profundidad de un nodo es el n´umero de arcos del camino que lo conecta con la ra´ız. El nivel N k de un a´ rbol es el conjunto de nodos con profundidad k > 0 y N0 solo consta de la ra´ız. La altura de un a´ rbol es la longitud del camino m´as largo. Teorema 1. Si un a´ rbol tiene N nodos y altura h, entonces el PageRank P(r) de su ra´ız r viene dado por la f´ormula P(r) =



1−α N



h

∑ α k nk

(2)

k=0

donde nk es el n´umero de nodos del nivel Nk , k = 0, 1, . . . , h. Demostraci´on. Usaremos la notaci´on b ∈ Nk : b → a para referirnos a los nodos b del nivel Nk que est´an conectados al nodo a (del nivel Nk−1 ). Sean N0 = {r} y N1 = {a1 , . . . , an1 }. Utilizando (1), teniendo en cuenta que el exgrado de cada nodo es 1, que los conjuntos de ´ındices {b ∈ N2 : b → ai }, para cada i = 1, . . . , n1 , son disjuntos dos a dos y procediendo recursivamente se tiene ! " 1−α 1−α 1−α + α ∑ P(a) = +α +α ∑ P(b) + N N N a∈N1 b∈N2 :b→a1  # "  1 − 1 − α α α 1 − ... +  +α n1 + α ∑ P(b) ∑ P(b) = N + α N N b∈N2 :b→an b∈N2 1     h−1 1−α 1−α = (1 + α n1 ) + α 2 ∑ P(b) = ∑ α k nk + α h ∑ P(b) N N k=0 b∈N b∈N

P(r) = 

2

h

C´omo mejorar el PageRank de un a´ rbol

=



1−α N



55

h

∑ α k nk

k=0

Nota 1. Este teorema prueba que el PageRank de la ra´ız de un a´ rbol s´olo depende del n´umero de nodos de cada nivel y no de las conexiones entre los nodos de niveles consecutivos. Estudiamos ahora el PageRank de algunas clases particulares de a´ rboles. ´ 2.1. Arboles m-arios Si Tmh es un a´ rbol m–ario completo de altura h y P m (r) es el PageRank de su ra´ız r se tiene P1 (r) =

1 − α h+1 y para m > 1 h+1

m−1 h α k mk = (1 − α ) Pm (r) = (1 − α ) mh+1 −1 ∑k=0



m−1

mh+1 −1



(α m)h+1 −1 α m−1



´ 2.2. Arboles binomiales Si Tbh es un a´ rbol binomial completo de altura h (definici´on en [3, S9.1], [4]) y Pb (r) es el PageRank de su ra´ız r se tiene Pb (r) =

1−α 2h

h

∑ αk

k=0

  h (1 − α ) (1 + α )h . = 2h k

Nota 2. En hipertextos es frecuente la estructura arb o´ rea bidireccional. El PageRank P 0 m (r) de la ra´ız r de un a´ rbol m–ario no dirigido se obtiene de forma an´aloga a la del teorema 1 0

P m (r) =



1−α N



h

∑

k=0



α m+1

k

nk

(3)

Por tanto, varios de los resultados que siguen pueden aplicarse a esta clase de a´ rboles.

3. Supresi´on de nodos y a´ rboles cola Despu´es del teorema 1, podemos describir un a´ rbol T con niveles N 0 , N1 , . . . , Nh de cardinales respectivos 1, n1 , . . . , nh por la sucesi´on T = 1n1 . . . nh .

56

Arratia,A.; Mariju´an, C.

Teorema 2. Si en un a´ rbol T = 1n1 . . . nh de altura h ≥ 1, se suprime el u´ ltimo nivel Nh , entonces el PageRank PT (r) de la ra´ız r aumenta. Demostraci´on. Al pasar del a´ rbol T = 1n1 . . . nh con N = 1 + n1 + . . . + nh nodos al a´ rbol T 0 = 1n1 . . . nh−1 se tiene PT 0 (r) − PT (r) = = =

nh (1 + n1α + . . . + nh−1α h−1 − (N − nh )α h ) (N − nh)N

nh (1 + n1α + . . . + nh−1α h−1 − (1 + n1 + . . . + nh−1)α h ) (N − nh)N nh ((1 − α h ) + n1(α − α h ) + . . . + nh−1(α h−1 − α h )) > 0 (N − nh)N

ya que α ∈ (0,1) y h ≥ 1. Nota 3. Si se quiere mejorar el PageRank de la ra´ız de un a´ rbol se deben suprimir, de abajo hacia arriba, tantos niveles como permita el contexto (en el que el a´ rbol tenga su significado). Definici´on 1. El a´ rbol cola del a´ rbol T = 1n1 . . . nh es el a´ rbol . . 1} . Tq = 1n1 . . . nb h−1 c |1 .{z 2

b h2 c+1

Teorema 3. El PageRank de la ra´ız de un a´ rbol es menor que el PageRank de la ra´ız de su a´ rbol cola. Demostraci´on. El PageRank de la ra´ız r de T = 1n1 . . . nh−1 nh es menor que el PageRank de la ra´ız r de T 0 = 1n1 . . . nh−1 1 ya que, si N = 1 + n1 + . . . + nh , entonces PT 0 (r) − PT (r) = =

(nh − 1)(1 − α ) (1 + n1 α + . . . + nh−1 α h−1 − (N − nh )α h ) (N − (nh − 1))N

(nh − 1)(1 − α ) ((1 − α h ) + n1 (α − α h ) + . . . + nh−1 (α h−1 − α h )) > 0. (N − (nh − 1))N

Se repite el proceso para T = 1n1 . . . nh−2 nh−1 1 y T 0 = 1n1 . . . nh−2 11, y se procede recursivamente hasta bh/2c. En la u´ ltima etapa se tiene T = 1n1 . . . nb h−1 c nb h+1 c |1 .{z . . 1} 2

2

b h2 c

y se prueba que su PageRank es menor que el del a´ rbol cola . . 1} . T 0 = 1n1 . . . nb h−1 c |1 .{z 2

b 2h c+1

C´omo mejorar el PageRank de un a´ rbol

57

Basta distinguir los casos par e impar. Si h = 2p − 1 entonces T = 1n1 . . . n p−1 n p |1 .{z . . 1}, T 0 = 1n1 . . . n p−1 |1 .{z . . 1} y N = n1 + . . . + n p + p. Sea M =

(n p −1)(1−α ) (N−(n p −1))N .

p

p−1

Entonces

PT 0 (r) − PT (r) = = M(1 + n1 α + . . . + n p−1 α p−1 − (N − n p )α p + α p+1 + . . . + α 2p−1 ) = M((1 − α p ) + (n1 − α p−1 )(α − α p ) + . . . + (n p−1 − α )(α p−1 − α p )) > 0. Si h = 2p entonces T = 1n1 . . . n p−1 n p |1 .{z . . 1}, p

T 0 = 1n1 . . . n p−1 |1 .{z . . 1} p+1

y N = n1 + . . . + n p + p + 1. Se prueba an´alogamente que PT 0 (r) − PT (r) > 0.

Nota 4. El teorema 3 no puede mejorarse, en el sentido de que la supresi o´ n de un nodo hoja (para conservar la altura) en un a´ rbol cola puede mejorar o empeorar el PageRank de su ra´ız. El a´ rbol cola es el mejor posible para valores peque n˜ os de h. A partir de un h determinado (dependiendo de la paridad) se puede seguir suprimiendo nodos mejorando el PageRank de la ra´ız hasta un l´ımite, no indefinidamente. Hemos realizado un estudio sistem a´ tico para varias clases de a´ rboles cola que incluiremos en la versio´ n extendida.

˜ 4. Jerarqu´ıas de a´ rboles por altura y tamano En lo que sigue supondremos que α ∈ (1/2, 1). Los siguientes resultados permiten ordenar a´ rboles m–arios y binomiales respecto de los PageRanks de sus ra´ıces que denotaremos abreviadamente por P m and Pb . Teorema 4. Para valores de la altura h suficientemente grandes se tiene P1 > P b > P 2 > P 3 > . . . > P m . . . Demostraci´on. Se reduce a un c´alculo de l´ımites: 1.

(k − 1)(mα − 1) Pk = > 1 =⇒ Pk > Pm . h→∞ Pm (m − 1)(kα − 1)

Para 1 < k < m, l´ım

58 2.

3.

Arratia,A.; Mariju´an, C.

α + 1 (2α )h+1 − 1 2h+1 h→∞ P2 −→ 0. = Pb 2(2α − 1) (α + 1)h+1 2h+1 − 1   1+α h (1 − α )(h + 1) Pb 2 h→∞ = −→ 0 . h+1 P1 1−α

Teorema 5. Para un n´umero de nodos N suficientemente grande y α ≥ 0,58 se tiene . . . P m > . . . > P 6 > P5 > Pb > P4 > P3 > P2 > P1 Demostraci´on. Es consecuencia de los siguientes resultados: (a) Si k < m y N >> 0 entonces Pm > Pk : Un a´ rbol k–ario de altura h tiene el kh+1 − 1 mismo n´umero de nodos que un a´ rbol m–ario de altura h 0 si, y s´olo si, = k−1 0 mh +1 − 1 . Entonces m−1 (kα )h+1 Pk (mα − 1) =0 = l´ım m−1 h→∞ (k α − 1) (mα )logm ( k−1 kh+1 ) h→∞ Pm l´ım

(b) Si m ≥ 2 y N >> 0 entonces Pm > P1 : 0

P1 = Pm

1−α h +1 h0 +1 (m−1)(1−α ) (mα )h+1 −1 mα −1 mh+1 −1

mh+1 −1

(mα − 1) 1 − α m−1 h→∞ −→ 0 = (1 − α ) (mα )h+1 − 1

(c) Si N >> 0 entoces P5 > Pb > P4 : En este caso probamos que Pm (1 + α )log2 (m−1) l´ım = h→∞ Pb mα − 1

mα (1 + α )log2 m

Donde el limite L es 0 o ∞ dependiendo de que

mα log m (1+α ) 2

!h+1

= L.

sea menor o mayor que

1, respectivamente. Se prueba que L = 0 si m ≤ 4 o m = 5 y α < α 0 , donde α0 es la soluci´on de 5α0 = (1 + α0 )log2 5 , i.e. α0 = 0,57016 . . .. Por otro lado, L = ∞ si m ≥ 6 o m = 5 y α > α0 . q

Para a´ rboles cola se obtiene el mismo orden. Ahora usaremos P h,m (resp. q Ph,b ) para denotar el PageRank de la ra´ız de un a´ rbol cola m–ario (resp. binomial). Estos valores dependen de la paridad de la altura h.

C´omo mejorar el PageRank de un a´ rbol

59

Teorema 6. (i) Para h suficientemente grande se tiene q

q

q

q

q

Ph,1 > Ph,b > Ph,2 > Ph,3 > . . . > Ph,m . . . (ii) Para N suficientemente grande se tiene q

q

q

q

q

q

q

q

. . . Ph,m > . . . > Ph,6 > Ph,5 > Ph,b > Ph,4 > Ph,3 > Ph,2 > Ph,1 La demostraci´on es m´as complicada y la dejamos para la versi´on extendida.

5. Conclusiones Estos resultados son u´ tiles en el dise˜no de web locales con estructura arb´orea para optimizar o mejorar el PageRank de su p´agina principal. Este objetivo se traduce (teorema 1) en el siguiente problema de optimizaci´on. Objectivo principal: Maximizar la funci´on P(h, 1, n1 , . . . , nh ) =



1−α 1 + n1 + . . . + n h



h

∑ α k nk

k=0

con α ∈ (0, 1) fijo y para todos los a´ rboles T = 1n 1 . . . nh con valores h, ni ≥ 1, 1 ≤ i ≤ h, enteros. Si el n´umero total de nodos N est´a acotado entonces podemos asegurar que el m´aximo existe (P es continua en un dominio compacto). La complejidad del problema es equivalente a la de encontrar las particiones enteras positivas de N, y la posibildad de resolverlo depende de la capacidad del ordenador. Si en la pr´actica no se puede alcanzar el objetivo principal nos podemos aproximar a e´ l aplicando la siguiente regla general deducible de los resultados de este art´ıculo. Regla general: Reducir la altura tanto como lo permita el contexto (teorema 2). Tener en cuenta que se pueden reorganizar como se desee las conexiones entre niveles consecutivos (teorema 1). Fijada la altura o´ ptima se pueden suprimir nodos en la mitad superior del a´ rbol (los que permita el contexto) hasta aproximarnos al a´ rbol cola (teorema 3) y los que no se puedan suprimir se deben conectar al nivel m´as bajo posible (teorema 1). El teorema 6 se ha probado usando t´ecnicas de c´alculo continuo y no puede q q aplicarse para valores no suficientemente grandes de h. C´aculando P h,b y Ph,m para valores peque˜nos de m y h se obtienen los siguientes resultados que completan el teorema 6–(i): 1.

q

q

q

Ph,1 > Ph,b > Ph,2 , para h ≥ 17.

60

Arratia,A.; Mariju´an, C. q

q

2.

Ph,b > Ph,1 , para 2 ≤ h ≤ 16.

3.

q q Ph,b > Ph,2 , para todo h > 1.

4.

q q Ph,1 > Ph,2 , para h ≥ 15.

5.

Ph,2 > Ph,1 , para 2 ≤ h ≤ 14.

6.

Ph,2 > Ph,3 > Ph,4 > . . . > Ph,m . . ., para h ≥ 9.

7.

Ph,2 < Ph,3 < Ph,4 < . . . < Ph,m . . ., para h = 3, 4.

8.

El teorema 6–(i) es “casi” cierto para h = 5, 6, 7, 8 (es cierto para todo m salvo para algunos valores comprendidos entre 2 y 6).

q

q

q

q

q

q

q

q

q

q

Observamos que, en general, el a´ rbol binomial modeliza una estructura conectiva regular para webs locales con mayor PageRank de su p´agina principal.

Bibliograf´ıa [1] Sergey Brin & Lawrence Page, The anatomy of a large scale hypertextual web search engine. Computer Networks and ISDN Systems, 33 (1998), 107117. [2] Sergey Brin, R. Motwami, Lawrence Page & Terry Winograd, The PageRank citation ranking: Bringing order to the web. Technical Report, Comp. Sci. Dept., Stanford University, 1998. [3] Thomas Cormen, Charles Leiserson, Ronald Rivest & Clifford Stein. Introduction to Algorithms, The MIT Press, 2nd. Edition, 2001 [4] Donald E. Knuth, The Art of Computer Programming, Addison-Wesley, volumes 1, 2, and 3, 3rd edition, 1998. [5] Amy N. Langville and Carl D. Meyer, Deeper Inside PageRank, Internet Mathematics 1, 3: 335–380, 2004.