Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Utilice el algoritmo PageRank para clasificar sitios web

En este ejemplo se muestra cómo usar un algoritmo PageRank para clasificar una colección de sitios Web. Aunque el algoritmo PageRank fue diseñado originalmente para clasificar los resultados del motor de búsqueda, también se puede aplicar más ampliamente a los nodos en muchos tipos diferentes de gráficos. La puntuación de PageRank da una idea de la importancia relativa de cada nodo de gráfico en función de cómo se conecta a los otros nodos.

Teóricamente, la puntuación de PageRank es la probabilidad limitante de que alguien haga clic aleatoriamente en los enlaces de cada sitio web llegará a cualquier página en particular. Así que las páginas con una puntuación alta están altamente conectadas y detectables dentro de la red, y es más probable que un surfista web aleatorio visite esa página.

Descripción del algoritmo

En cada paso del algoritmo PageRank, la puntuación de cada página se actualiza según,

r = (1-P)/n + P*(A'*(r./d) + s/n);

  • es un vector de puntuaciones de PageRank.r

  • es un factor de amortiguación escalar (normalmente 0,85), que es la probabilidad de que un surfista aleatorio haga clic en un vínculo de la página actual, en lugar de continuar en otra página aleatoria.P

  • es la transposición de la matriz de adyacencia del gráfico.A'

  • es un vector que contiene el out-Degree de cada nodo en el gráfico. se establece en para los nodos sin aristas salientes.dd1

  • es el número escalar de nodos en el gráfico.n

  • es la suma escalar de las puntuaciones de PageRank para las páginas sin vínculos.s

En otras palabras, el rango de cada página se basa en gran medida en las filas de las páginas que enlazan a ella. El término selecciona las puntuaciones de los nodos de origen que enlazan a cada nodo del gráfico y las puntuaciones se normalizan por el número total de enlaces salientes de esos nodos de origen.A'*(r./d) Esto garantiza que la suma de las puntuaciones del PageRank es siempre.1 Por ejemplo, si el nodo 2 enlaza con los nodos 1, 3 y 4, transfiere su puntuación de PageRank a cada uno de esos nodos durante cada iteración del algoritmo.1/3

Cree un gráfico que ilustre cómo cada nodo confiere su puntuación de PageRank a los otros nodos del gráfico.

s = {'a' 'a' 'a' 'b' 'b' 'c' 'd' 'd' 'd'}; t = {'b' 'c' 'd' 'd' 'a' 'b' 'c' 'a' 'b'}; G = digraph(s,t); labels = {'a/3' 'a/3' 'a/3' 'b/2' 'b/2' 'c' 'd/3' 'd/3' 'd/3'}; p = plot(G,'Layout','layered','EdgeLabel',labels); highlight(p,[1 1 1],[2 3 4],'EdgeColor','g') highlight(p,[2 2],[1 4],'EdgeColor','r') highlight(p,3,2,'EdgeColor','m') title('PageRank Score Transfer Between Nodes')

La función contiene una opción para calcular las puntuaciones del PageRank.centrality

PageRank con 6 nodos

Cree y trace un gráfico dirigido que contenga seis nodos que representen sitios web ficticios.

s = [1 1 2 2 3 3 3 4 5]; t = [2 5 3 4 4 5 6 1 1]; names = {'http://www.example.com/alpha', 'http://www.example.com/beta', ...          'http://www.example.com/gamma', 'http://www.example.com/delta', ...          'http://www.example.com/epsilon', 'http://www.example.com/zeta'}; G = digraph(s,t,[],names)
G =    digraph with properties:      Edges: [9x1 table]     Nodes: [6x1 table]  
plot(G,'Layout','layered', ...     'NodeLabel',{'alpha','beta','gamma','delta','epsilon','zeta'})

Calcule la puntuación de centralidad de PageRank para este gráfico. Utilice una probabilidad de seguimiento (también conocida como factor de amortiguación) de.0.85

pr = centrality(G,'pagerank','FollowProbability',0.85)
pr = 6×1

    0.3210
    0.1706
    0.1066
    0.1368
    0.2008
    0.0643

Vea la información de calificaciones y grados de PageRank para cada página.

G.Nodes.PageRank = pr; G.Nodes.InDegree = indegree(G); G.Nodes.OutDegree = outdegree(G); G.Nodes
ans=6×4 table
                  Name                  PageRank    InDegree    OutDegree
    ________________________________    ________    ________    _________

    'http://www.example.com/alpha'      0.32098        2            2    
    'http://www.example.com/beta'       0.17057        1            2    
    'http://www.example.com/gamma'      0.10657        1            3    
    'http://www.example.com/delta'      0.13678        2            1    
    'http://www.example.com/epsilon'    0.20078        2            1    
    'http://www.example.com/zeta'       0.06432        1            0    

Los resultados muestran que no es sólo el de los enlaces de página que determina la puntuación, sino también el.numberquality Los sitios web y ambos tienen un grado total de 4, sin embargo, enlaces a ambos y, que también son altamente clasificados. solo está vinculada a una página, que se encuentra en el centro de la lista.alphagammaalphaepsilonbetagammabeta Por lo tanto, se anota más alto que el algoritmo.alphagamma

PageRank de sitios web en mathworks.com

Cargue los datos en y visualice la matriz de adyacencia,.mathworks100.matA Estos datos se generaron en 2015 utilizando un rastreador de páginas automático. El rastreador de página comenzó en y seguido enlaces a páginas web subsiguientes hasta que la matriz de adyacencia contenía información sobre las conexiones de 100 páginas web únicas.https://www.mathworks.com

load mathworks100.mat  spy(A)

Cree un grafo dirigido con la matriz de adyacencia dispersa, utilizando las URL contenidas en como nombres de nodo.AU

G = digraph(A,U)
G =    digraph with properties:      Edges: [632x1 table]     Nodes: [100x1 table]  

Trace el gráfico utilizando el diseño de fuerza.

plot(G,'NodeLabel',{},'NodeColor',[0.93 0.78 0],'Layout','force'); title('Websites linked to https://www.mathworks.com')

Calcule las puntuaciones del PageRank para el gráfico, utilizando 200 iteraciones y un factor de amortiguación de.G0.85 Agregue la información de calificaciones y grados a la tabla de nodos del gráfico.

pr = centrality(G,'pagerank','MaxIterations',200,'FollowProbability',0.85); G.Nodes.PageRank = pr; G.Nodes.InDegree = indegree(G); G.Nodes.OutDegree = outdegree(G);

Vea las 25 puntuaciones principales resultantes.

G.Nodes(1:25,:)
ans=25×4 table
                                        Name                                        PageRank    InDegree    OutDegree
    ____________________________________________________________________________    ________    ________    _________

    'https://www.mathworks.com'                                                     0.044342       20          14    
    'https://ch.mathworks.com'                                                      0.043085       20          14    
    'https://cn.mathworks.com'                                                      0.043085       20          14    
    'https://jp.mathworks.com'                                                      0.043085       20          14    
    'https://kr.mathworks.com'                                                      0.043085       20          14    
    'https://uk.mathworks.com'                                                      0.043085       20          14    
    'https://au.mathworks.com'                                                      0.043085       20          14    
    'https://de.mathworks.com'                                                      0.043085       20          14    
    'https://es.mathworks.com'                                                      0.043085       20          14    
    'https://fr.mathworks.com'                                                      0.043085       20          14    
    'https://in.mathworks.com'                                                      0.043085       20          14    
    'https://it.mathworks.com'                                                      0.043085       20          14    
    'https://nl.mathworks.com'                                                      0.043085       20          14    
    'https://se.mathworks.com'                                                      0.043085       20          14    
    'https://www.mathworks.com/index.html%3Fnocookie%3Dtrue'                          0.0015        0           1    
    'https://www.mathworks.com/company/aboutus/policies_statements/patents.html'    0.007714        6           6    
      ⋮

Extraiga y trace un subgráfico que contenga todos los nodos cuya puntuación sea mayor que.0.005 Colorea los nodos del gráfico en función de su puntuación de PageRank.

H = subgraph(G,find(G.Nodes.PageRank > 0.005)); plot(H,'NodeLabel',{},'NodeCData',H.Nodes.PageRank,'Layout','force'); title('Websites linked to https://www.mathworks.com') colorbar

Las puntuaciones de PageRank para los principales sitios web son bastante similares, de manera que un surfista web aleatorio tiene aproximadamente un 4,5% de probabilidades de aterrizar en cada página. Este pequeño grupo de páginas altamente conectadas forma una camarilla en el centro de la trama. Conectados a este clítoris central hay varios cliques más pequeños, que están muy conectados entre sí.

Referencias

Moler, C. . .Experiments with MATLABCapítulo 7: Google PageRank MathWorks, Inc., 2011.

Consulte también

| |