Prerrequisito: Algoritmo de rango de página e implementación , recorrido aleatorio
En las Redes Sociales el page rank es un tema muy importante. Básicamente, el rango de página no es más que cómo se clasifican las páginas web según su importancia y relevancia de búsqueda. Todos los motores de búsqueda utilizan el ranking de páginas. Google es el mejor ejemplo que utiliza el rango de página utilizando el gráfico web.
Método de caminata aleatoria : en el método de caminata aleatoria, elegiremos 1 Node del gráfico de manera uniforme al azar. Después de elegir el Node, miraremos a sus vecinos y elegiremos un vecino uniformemente al azar y continuaremos estas iteraciones hasta que se alcance la convergencia. Después de N iteraciones, llegará un punto después del cual no habrá cambios en los puntos de cada Node. Esta situación se llama convergencia.
Algoritmo: a continuación se muestran los pasos para implementar el método Random Walk.
- Cree un gráfico dirigido con N Nodes.
- Ahora realiza una caminata aleatoria.
- Ahora obtenga Nodes ordenados según los puntos durante la caminata aleatoria.
- Por último, compárelo con el método incorporado de PageRank.
A continuación se muestra el código Python para la implementación del algoritmo de distribución de puntos.
Python3
import networkx as nx
import random
import numpy as np
# Add directed edges in graph
def add_edges(g, pr):
for each in g.nodes():
for each1 in g.nodes():
if (each != each1):
ra = random.random()
if (ra < pr):
g.add_edge(each, each1)
else:
continue
return g
# Sort the nodes
def nodes_sorted(g, points):
t = np.array(points)
t = np.argsort(-t)
return t
# Distribute points randomly in a graph
def random_Walk(g):
rwp = [0 for i in range(g.number_of_nodes())]
nodes = list(g.nodes())
r = random.choice(nodes)
rwp[r] += 1
neigh = list(g.out_edges(r))
z = 0
while (z != 10000):
if (len(neigh) == 0):
focus = random.choice(nodes)
else:
r1 = random.choice(neigh)
focus = r1[1]
rwp[focus] += 1
neigh = list(g.out_edges(focus))
z += 1
return rwp
# Main
# 1. Create a directed graph with N nodes
g = nx.DiGraph()
N = 15
g.add_nodes_from(range(N))
# 2. Add directed edges in graph
g = add_edges(g, 0.4)
# 3. perform a random walk
points = random_Walk(g)
# 4. Get nodes rank according to their random walk points
sorted_by_points = nodes_sorted(g, points)
print("PageRank using Random Walk Method")
print(sorted_by_points)
# p_dict is dictionary of tuples
p_dict = nx.pagerank(g)
p_sort = sorted(p_dict.items(), key=lambda x: x[1], reverse=True)
print("PageRank using inbuilt pagerank method")
for i in p_sort:
print(i[0], end=", ")
Producción:
PageRank using Random Walk Method [ 9 10 4 6 3 8 13 14 0 7 1 2 5 12 11] PageRank using inbuilt pagerank method 9, 10, 6, 3, 4, 8, 13, 0, 14, 7, 1, 2, 5, 12, 11,
Publicación traducida automáticamente
Artículo escrito por sankalpsharma424 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA