PageRank (PR) es un algoritmo utilizado por Google Search para clasificar sitios web en los resultados de su motor de búsqueda. PageRank lleva el nombre de Larry Page, uno de los fundadores de Google. PageRank es una forma de medir la importancia de las páginas de un sitio web. Según Google:
PageRank funciona contando el número y la calidad de los enlaces a una página para determinar una estimación aproximada de la importancia del sitio web. La suposición subyacente es que es probable que los sitios web más importantes reciban más enlaces de otros sitios web.
No es el único algoritmo utilizado por Google para ordenar los resultados del motor de búsqueda, pero es el primer algoritmo que utilizó la empresa, y es el más conocido.
La medida de centralidad anterior no se implementa para gráficos múltiples.
Algoritmo
El algoritmo PageRank genera una distribución de probabilidad que se utiliza para representar la posibilidad de que una persona que hace clic aleatoriamente en los enlaces llegue a una página en particular. PageRank se puede calcular para colecciones de documentos de cualquier tamaño. Se supone en varios trabajos de investigación que la distribución se divide uniformemente entre todos los documentos de la colección al comienzo del proceso computacional. Los cálculos de PageRank requieren varias pasadas, llamadas «iteraciones», a través de la colección para ajustar los valores de PageRank aproximados para reflejar más fielmente el valor real teórico.
Algoritmo simplificado
Suponga un pequeño universo de cuatro páginas web: A, B, C y D. Se ignoran los enlaces de una página a sí misma, o múltiples enlaces salientes de una sola página a otra única página. PageRank se inicializa con el mismo valor para todas las páginas. En la forma original de PageRank, la suma de PageRank en todas las páginas era el número total de páginas en la web en ese momento, por lo que cada página en este ejemplo tendría un valor inicial de 1. Sin embargo, las versiones posteriores de PageRank y el resto de esta sección, suponga una distribución de probabilidad entre 0 y 1. Por lo tanto, el valor inicial para cada página en este ejemplo es 0,25.
El PageRank transferido desde una página determinada a los objetivos de sus enlaces salientes en la siguiente iteración se divide por igual entre todos los enlaces salientes.
Si los únicos enlaces en el sistema fueran de las páginas B, C y D a A, cada enlace transferiría 0,25 PageRank a A en la siguiente iteración, para un total de 0,75. 
Supongamos, en cambio, que la página B tiene un enlace a las páginas C y A, la página C tiene un enlace a la página A y la página D tiene enlaces a las tres páginas. Por lo tanto, en la primera iteración, la página B transferiría la mitad de su valor existente, o 0,125, a la página A y la otra mitad, o 0,125, a la página C. La página C transferiría todo su valor existente, 0,25, al único página a la que enlaza, A. Dado que D tenía tres enlaces salientes, transferiría un tercio de su valor existente, o aproximadamente 0,083, a A. Al finalizar esta iteración, la página A tendrá un PageRank de aproximadamente 0,458. 
En otras palabras, el PageRank conferido por un enlace saliente es igual a la puntuación de PageRank del propio documento dividida por el número de enlaces salientes L( ). 
En el caso general, el valor de PageRank para cualquier página u se puede expresar como: 
,
es decir, el valor de PageRank para una página u depende de los valores de PageRank para cada página v contenida en el conjunto Bu (el conjunto que contiene todas las páginas que enlazan con la página). u), dividido por el número L(v) de enlaces de la página v. El algoritmo implica un factor de amortiguamiento para el cálculo del PageRank. Es como el impuesto sobre la renta que el gobierno extrae de uno a pesar de pagarlo él mismo.
A continuación se muestra el código para el cálculo del ranking de la página.
Python
def pagerank(G, alpha=0.85, personalization=None,
max_iter=100, tol=1.0e-6, nstart=None, weight='weight',
dangling=None):
"""Return the PageRank of the nodes in the graph.
PageRank computes a ranking of the nodes in the graph G based on
the structure of the incoming links. It was originally designed as
an algorithm to rank web pages.
Parameters
----------
G : graph
A NetworkX graph. Undirected graphs will be converted to a directed
graph with two directed edges for each undirected edge.
alpha : float, optional
Damping parameter for PageRank, default=0.85.
personalization: dict, optional
The "personalization vector" consisting of a dictionary with a
key for every graph node and nonzero personalization value for each node.
By default, a uniform distribution is used.
max_iter : integer, optional
Maximum number of iterations in power method eigenvalue solver.
tol : float, optional
Error tolerance used to check convergence in power method solver.
nstart : dictionary, optional
Starting value of PageRank iteration for each node.
weight : key, optional
Edge data key to use as weight. If None weights are set to 1.
dangling: dict, optional
The outedges to be assigned to any "dangling" nodes, i.e., nodes without
any outedges. The dict key is the node the outedge points to and the dict
value is the weight of that outedge. By default, dangling nodes are given
outedges according to the personalization vector (uniform if not
specified). This must be selected to result in an irreducible transition
matrix (see notes under google_matrix). It may be common to have the
dangling dict to be the same as the personalization dict.
Returns
-------
pagerank : dictionary
Dictionary of nodes with PageRank as value
Notes
-----
The eigenvector calculation is done by the power iteration method
and has no guarantee of convergence. The iteration will stop
after max_iter iterations or an error tolerance of
number_of_nodes(G)*tol has been reached.
The PageRank algorithm was designed for directed graphs but this
algorithm does not check if the input graph is directed and will
execute on undirected graphs by converting each edge in the
directed graph to two edges.
"""
if len(G) == 0:
return {}
if not G.is_directed():
D = G.to_directed()
else:
D = G
# Create a copy in (right) stochastic form
W = nx.stochastic_graph(D, weight=weight)
N = W.number_of_nodes()
# Choose fixed starting vector if not given
if nstart is None:
x = dict.fromkeys(W, 1.0 / N)
else:
# Normalized nstart vector
s = float(sum(nstart.values()))
x = dict((k, v / s) for k, v in nstart.items())
if personalization is None:
# Assign uniform personalization vector if not given
p = dict.fromkeys(W, 1.0 / N)
else:
missing = set(G) - set(personalization)
if missing:
raise NetworkXError('Personalization dictionary '
'must have a value for every node. '
'Missing nodes %s' % missing)
s = float(sum(personalization.values()))
p = dict((k, v / s) for k, v in personalization.items())
if dangling is None:
# Use personalization vector if dangling vector not specified
dangling_weights = p
else:
missing = set(G) - set(dangling)
if missing:
raise NetworkXError('Dangling node dictionary '
'must have a value for every node. '
'Missing nodes %s' % missing)
s = float(sum(dangling.values()))
dangling_weights = dict((k, v/s) for k, v in dangling.items())
dangling_nodes = [n for n in W if W.out_degree(n, weight=weight) == 0.0]
# power iteration: make up to max_iter iterations
for _ in range(max_iter):
xlast = x
x = dict.fromkeys(xlast.keys(), 0)
danglesum = alpha * sum(xlast[n] for n in dangling_nodes)
for n in x:
# this matrix multiply looks odd because it is
# doing a left multiply x^T=xlast^T*W
for nbr in W[n]:
x[nbr] += alpha * xlast[n] * W[n][nbr][weight]
x[n] += danglesum * dangling_weights[n] + (1.0 - alpha) * p[n]
# check convergence, l1 norm
err = sum([abs(x[n] - xlast[n]) for n in x])
if err < N*tol:
return x
raise NetworkXError('pagerank: power iteration failed to converge '
'in %d iterations.' % max_iter)
El código anterior es la función que se ha implementado en la biblioteca networkx.
Para implementar lo anterior en networkx, tendrás que hacer lo siguiente:
Python
>>> import networkx as nx >>> G=nx.barabasi_albert_graph(60,41) >>> pr=nx.pagerank(G,0.4) >>> pr
A continuación se muestra el resultado que obtendría en IDLE después de las instalaciones requeridas.
Python
{0: 0.012774147598875784, 1: 0.013359655345577266, 2: 0.013157355731377924,
3: 0.012142198569313045, 4: 0.013160014506830858, 5: 0.012973342862730735,
6: 0.012166706783753325, 7: 0.011985935451513014, 8: 0.012973502696061718,
9: 0.013374146193499381, 10: 0.01296354505412387, 11: 0.013163220326063332,
12: 0.013368514624403237, 13: 0.013169335617283102, 14: 0.012752071800520563,
15: 0.012951601882210992, 16: 0.013776032065400283, 17: 0.012356820581336275,
18: 0.013151652554311779, 19: 0.012551059531065245, 20: 0.012583415756427995,
21: 0.013574117265891684, 22: 0.013167552803671937, 23: 0.013165528583400423,
24: 0.012584981049854336, 25: 0.013372989228254582, 26: 0.012569416076848989,
27: 0.013165322299539031, 28: 0.012954300960607157, 29: 0.012776091973397076,
30: 0.012771016515779594, 31: 0.012953404860268598, 32: 0.013364947854005844,
33: 0.012370004022947507, 34: 0.012977539153099526, 35: 0.013170376268827118,
36: 0.012959579020039328, 37: 0.013155319659777197, 38: 0.013567147133137161,
39: 0.012171548109779459, 40: 0.01296692767996657, 41: 0.028089802328702826,
42: 0.027646981396639115, 43: 0.027300188191869485, 44: 0.02689771667021551,
45: 0.02650459107960327, 46: 0.025971186884778535, 47: 0.02585262571331937,
48: 0.02565482923824489, 49: 0.024939722913691394, 50: 0.02458271197701402,
51: 0.024263128557312528, 52: 0.023505217517258568, 53: 0.023724311872578157,
54: 0.02312908947188023, 55: 0.02298716954828392, 56: 0.02270220663300396,
57: 0.022060403216132875, 58: 0.021932442105075004, 59: 0.021643288632623502}
El código anterior se ejecutó en IDLE (Python IDE de Windows). Deberá descargar la biblioteca networkx antes de ejecutar este código. La parte dentro de las llaves representa la salida. Es casi similar a Ipython (para usuarios de Ubuntu).
Referencias
- https://en.wikipedia.org/wiki/PageRank
- http://networkx.readthedocs.io/en/networkx-1.10/index.html
- https://www.geeksforgeeks.org/ranking-google-search-works/
- https://www.geeksforgeeks.org/google-search-works/
Por lo tanto, de esta manera se calcula la medida de centralidad de Page Rank para el gráfico dado. De esta manera hemos cubierto 2 medidas de centralidad. Me gustaría escribir más sobre las diversas medidas de centralidad utilizadas para el análisis de red.
Este artículo es una contribución de Jayant Bisht . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA