实验目的及要求
实验目的
1.了解网页排序在搜索引擎的重要性
2.掌握网页排序算法PageRank和HITS的原理及过程
3.理解PageRank和HITS各自优缺点及异同
实验要求
1.实现基本PageRank网页排序算法和PageRank随机浏览模型的编码、调试和运行
2.实现HITS网页排序算法的编码、调试和运行。
实验提交内容
1.实验工程文件和可执行文件
2.实验报告
实验原理
1.PageRank：通过链接分析来衡量一个网站好坏，是一种在搜索引擎中根据网页之间相互的链接关系计算网络排名的技术。
2. HITS算法的目的即是通过一定的技术手段，在海量网页中找到与用户查询主题相关的高质量权威页面和枢纽页面，尤其是权威页面，因为这些页面代表了能够满足用户查询的高质量内容，搜索引擎以此作为搜索结果返回给用户。
实验环境（使用的软件）
Python 3.8
实验过程（实验步骤、记录、数据、分析）
一、基本PageRank网页排序算法
import numpy as np
from fractions import Fraction
np.set_printoptions(formatter={'all':lambda x: str(Fraction(x).limit_denominator())}) #格式化 保留分数，不至于精度丢失
H = np.array([[0,1/2,1,0],[1/3,0,0,1/2],[1/3,0,0,1/2],[1/3,1/2,0,0]])? #根据有向图得出的转移矩阵
PR_0 = np.array([1/4,1/4,1/4,1/4]).reshape(4,1)? #初始PR
def PageRank(H,PR_0):? ? #定义一个迭代函数，直至MR=R时，输出R
? ? while(True):
? ? ? ? PR_1 = np.dot(H,PR_0)
? ? ? ? if((PR_1 == PR_0).any()):? #判断两个数组是否相等
? ? ? ? ? ? print(PR_1)
? ? ? ? ? ? break
? ? ? ? else:
? ? ? ? ? ? PR_0 = np.copy(PR_1)
PageRank(H,PR_0)
二、PageRank随机浏览模型
#PageRank随机浏览模型
class Graph():
? ? def __init__(self):
? ? ? ? self.node_map = {}#各个网络顶点的链接关系
? ? ? ? self.node_PR ={}#各个网络顶点的PR值
? ? ? ? self.node_num ={}#各个网络顶点的链接数
? ? #添加网页顶点
? ? def add_node(self, node_id):
? ? ? ? if node_id not in self.node_map:
? ? ? ? ? ? self.node_map[node_id] = set([])
? ? ? ? ? ? self.node_PR[node_id] = 0
? ? ? ? ? ? self.node_num[node_id] = 0
? ? ? ? else:
? ? ? ? ? ? print("这个顶点已经存在")
? ? #增加一个从node1指向node2的边。允许添加新顶点
? ? def add_link(self, node1, node2):
? ? ? ? if node1 not in self.node_map:
? ? ? ? ? ? self.add_node(node1)
? ? ? ? if node2 not in self.node_map:
? ? ? ? ? ? self.add_node(node2)
? ? ? ? self.node_map[node1].add(node2)#为node1添加一个出链，表示ndoe2引用了node1
? ? #计算各个网络顶点的链接数
? ? def get_num(self):
? ? ? ? for node in self.node_num:
? ? ? ? ? ? self.node_num[node] = len(self.node_map[node])
? ? #计算PR值
? ? def get_PR(self,d=0.85,iteration_num=10):
? ? ? ? self.get_num()
? ? ? ? for node in self.node_PR:#计算初始PR值
? ? ? ? ? ? self.node_PR[node]=1/len(self.node_map)
? ? ? ? for i in range(iteration_num):
? ? ? ? ? ? for node in self.node_PR:
? ? ? ? ? ? ? ? self.node_PR[node]=(1-d)+d*sum([self.node_PR[temp_node]/self.node_num[temp_node] for temp_node in self.node_map[node]])
? ? ? ? print(self.node_PR)
edges = [[1,2], [1,3], [1,4], [2,1], [2,4], [3,3], [4,3],[4,2]]#模拟的一个网页链接网络? ? ?
if __name__ == '__main__':
? ? graph = Graph()
? ? for edge in edges:
? ? ? ? graph.add_link(edge[0], edge[1])
graph.get_PR()
三、HITS算法
from math import sqrt
from pygraph.classes.digraph import digraph
import cmath
class HITSIterator:
? ? def __init__(self, dg):
? ? ? ? self.max_iterators = 100? # 最大迭代次数
? ? ? ? self.min_delta = 0.0001? # 判断是否迭代结束
? ? ? ? self.graph = dg
? ? ? ? self.hub = {}
? ? ? ? self.authority = {}
? ? ? ? for node in self.graph.nodes():
? ? ? ? ? ? self.hub[node] = 1
? ? ? ? ? ? self.authority[node] = 1
? ? def hits(self):
? ? ? ? """
? ? ? ? 计算每个页面的Hub,Authority值
? ? ? ? """
? ? ? ? if not self.graph:
? ? ? ? ? ? return
? ? ? ? flag = False
? ? ? ? for i in range(self.max_iterators):
? ? ? ? ? ? change = 0.0? # 变化量
? ? ? ? ? ? norm = 0
? ? ? ? ? ? tmp = {}
? ? ? ? ? ? tmp = self.authority.copy()
? ? ? ? ? ? # 计算每个页面的authority值
? ? ? ? ? ? for node in self.graph.nodes():
? ? ? ? ? ? ? ? self.authority[node] = 0
? ? ? ? ? ? ? ? for incident_page in self.graph.incidents(node):? # 入射边
? ? ? ? ? ? ? ? ? ? self.authority[node] += self.hub[incident_page]
? ? ? ? ? ? ? ? norm += pow(self.authority[node], 2)
? ? ? ? ? ? # 标准化
? ? ? ? ? ? norm = sqrt(norm)
? ? ? ? ? ? for node in self.graph.nodes():
? ? ? ? ? ? ? ? self.authority[node] /= norm
? ? ? ? ? ? ? ? change += abs(tmp[node] - self.authority[node])
? ? ? ? ? ? # 计算每个页面的Hub值
? ? ? ? ? ? norm = 0
? ? ? ? ? ? tmp = self.hub.copy()
? ? ? ? ? ? for node in self.graph.nodes():
? ? ? ? ? ? ? ? self.hub[node] = 0
? ? ? ? ? ? ? ? for neighbor_page in self.graph.neighbors(node):? # 出射边
? ? ? ? ? ? ? ? ? ? self.hub[node] += self.authority[neighbor_page]
? ? ? ? ? ? ? ? norm += pow(self.hub[node], 2)
? ? ? ? ? ? # 标准化
? ? ? ? ? ? norm = sqrt(norm)
? ? ? ? ? ? for node in self.graph.nodes():
? ? ? ? ? ? ? ? self.hub[node] /= norm
? ? ? ? ? ? ? ? change += abs(tmp[node] - self.hub[node])
? ? ? ? ? ? if(change < self.min_delta):
? ? ? ? ? ? ? ? flag = True
? ? ? ? ? ? ? ? break
? ? ? ? if flag:
? ? ? ? ? ? print("总共进行了%s次迭代" % (i+1))
? ? ? ? else:
? ? ? ? ? ? print("总共进行了超过100次迭代")
? ? ? ? print("最好的Authority页面", max(self.authority.items(),key=lambda x: x[1]))
? ? ? ? print("最好的Hub页面", max(self.hub.items(),key=lambda x: x[1]))
if __name__ == '__main__':
? ? dg = digraph()
? ? dg.add_nodes(["A", "B", "C", "D", "E","F"])
? ? dg.add_edge(("A", "B"))
? ? dg.add_edge(("F", "D"))
? ? dg.add_edge(("C", "A"))
? ? dg.add_edge(("D", "A"))
? ? dg.add_edge(("F", "C"))
? ? dg.add_edge(("E", "C"))
? ? dg.add_edge(("E", "D"))
? ? dg.add_edge(("E", "F"))
? ? hits = HITSIterator(dg)
? ? hits.hits()
小结
通过本次学习，我还学习到了NumPy包的相关操作，学会了如何进行线性代数的运算。
我还学习到了python-graph-core包中digraph有向图的相关定义
另外我复习了python3中max函数的用法
————————————————
版权声明：本文为CSDN博主「PawnTz」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_45791919/article/details/133281199