福州电子网站建设,厦门有做网站建设,wordpress网站关键词设置,中国南昌企业网站制作目录一、简介二、概述三、算法四、PageRank的缺点五、Python实现迭代法参考文献一、简介
PageRank#xff0c;又称网页排名、谷歌左侧排名、PR#xff0c;是Google公司所使用的对其搜索引擎搜索结果中的网页进行排名的一种算法。
佩奇排名本质上是一种以网页之间的超链接个…
目录一、简介二、概述三、算法四、PageRank的缺点五、Python实现迭代法参考文献一、简介
PageRank又称网页排名、谷歌左侧排名、PR是Google公司所使用的对其搜索引擎搜索结果中的网页进行排名的一种算法。
佩奇排名本质上是一种以网页之间的超链接个数和质量作为主要因素粗略地分析网页的重要性的算法。其基本假设是更重要的页面往往更多地被其他页面引用或称其他页面中会更多地加入通向该页面的超链接。 其将从A页面到B页面的链接解释为“A页面给B页面投票”并根据投票来源甚至来源的来源即链接到A页面的页面和投票对象的等级来决定被投票页面的等级。简单的说一个高等级的页面可以提升其他低等级的页面。
二、概述
PageRank是一种链接分析算法它通过对超链接集合中的元素用数字进行权重赋值实现“衡量集合范围内某一元素的相关重要性”的目的。该算法可以应用于任何含有元素之间相互引用的情况的集合实体。
PageRank的结果来源于一种基于图论的数学算法。它将万维网上所有的网页视作节点node而将超链接视作边edge并且考虑到了一些权威的网站类似CNN。每个节点的权重值表示对应的页面的重要度。通向该网页的超链接称做“对该网页的投票a vote of support”。每个网页的权重值大小被递归地定义依托于所有链接该页面的页面的权重值。例如一个被很多页面的链接的页面将会拥有较高的权重值high PageRank。
三、算法
假设一个由4个网页组成的集合ABC和D。同一页面中多个指向相同的链接视为同一个链接并且每个页面初始的PageRank值相同最初的算法将每个网页的初始值设定为1。但是在后来的版本以及下面的示例中为了满足概率值位于0到1之间的需要我们假设这个值是0.25。
在每次迭代中给定页面的PR值PageRank值将均分到该页面所链接的页面上。
如果所有页面都只链接至A那么A的PR值将是BC及D的PR值之和即
PR(A)PR(B)PR(C)PR(D)PR(A)PR(B)PR(C)PR(D)PR(A)PR(B)PR(C)PR(D)
重新假设B链接到A和CC链接到A并且D链接到A,B,C。最初一个页面总共只有一票。所以B给A ,C每个页面半票。以此类推D投出的票只有三分之一加到了A的PR值上
PR(A)PR(B)2PR(C)1PR(D)3PR(A){\frac {PR(B)}{2}}{\frac {PR(C)}{1}}{\frac {PR(D)}{3}}PR(A)2PR(B)1PR(C)3PR(D)
换句话说算法将根据每个页面连出总数L(X)L(X)L(X)平分该页面的PR值并将其加到其所指向的页面
PR(A)PR(B)L(B)PR(C)L(C)PR(D)L(D)PR(A){\frac {PR(B)}{L(B)}}{\frac {PR(C)}{L(C)}}{\frac {PR(D)}{L(D)}}PR(A)L(B)PR(B)L(C)PR(C)L(D)PR(D)
或者
PR(A) 是页面A的PR值PR(Ti)是页面Ti的PR值在这里页面Ti是指向A的所有页面中的某个页面C(Ti)是页面Ti的出度也就是Ti指向其他页面的边的个数d 为阻尼系数其意义是在任意时刻用户到达某页面后并继续向后浏览的概率
该数值是根据上网者使用浏览器书签的平均频率估算而得通常d0.85
最后所有这些PR值被换算成百分比形式再乘上一个修正系数 ddd。由于“没有向外链接的网页”传递出去的PR值会是0而这会递归地导致指向它的页面的PR值的计算结果同样为零所以赋给每个页面一个最小值(1−d)/N(1-d)/N(1−d)/NN为页面的总数
PR(A)(PR(B)L(B)PR(C)L(C)PR(D)L(D)⋯)d1−dNPR(A)\left({\frac {PR(B)}{L(B)}}{\frac {PR(C)}{L(C)}}{\frac {PR(D)}{L(D)}}\,\cdots \right)d{\frac {1-d}{N}}PR(A)(L(B)PR(B)L(C)PR(C)L(D)PR(D)⋯)dN1−d
需要注意的是在Sergey Brin和Lawrence Page的1998年原版论文中给每一个页面设定的最小值是1−d1-d1−d而不是这里的(1−d)/N(1-d)/N(1−d)/N这将导致集合中所有网页的PR值之和为NN为集合中网页的数目而非所期待的1。
因此一个页面的PR值直接取决于指向它的的页面。如果在最初给每个网页一个随机且非零的PR值经过重复计算这些页面的PR值会趋向于某个定值也就是处于收敛的状态即最终结果。这就是搜索引擎使用该算法的原因。
那么什么时候迭代结束哪一般要设置收敛条件比如上次迭代结果与本次迭代结果小于某个误差我们结束程序运行比如还可以设置最大循环次数。
四、PageRank的缺点
PageRank算法的主要缺点在于旧的页面的排名往往会比新页面高。因为即使是质量很高的新页面也往往不会有很多外链除非它是某个已经存在站点的子站点。这也是PageRank需要多项算法结合以保证其结果的准确性的原因。
五、Python实现迭代法
下面仅仅实现迭代法代码如下需要用到Python的numpy库用于矩阵乘法
# 输入为一个*.txt文件例如
# A B
# B C
# B A
# ...表示前者指向后者import numpy as npif __name__ __main__:# 读入有向图存储边f open(input_1.txt, r)edges [line.strip(\n).split( ) for line in f]print(edges)# 根据边获取节点的集合nodes []for edge in edges:if edge[0] not in nodes:nodes.append(edge[0])if edge[1] not in nodes:nodes.append(edge[1])print(nodes)N len(nodes)# 将节点符号字母映射成阿拉伯数字便于后面生成A矩阵/S矩阵i 0node_to_num {}for node in nodes:node_to_num[node] ii 1for edge in edges:edge[0] node_to_num[edge[0]]edge[1] node_to_num[edge[1]]print(edges)# 生成初步的S矩阵S np.zeros([N, N])for edge in edges:S[edge[1], edge[0]] 1print(S)# 计算比例即一个网页对其他网页的PageRank值的贡献即进行列的归一化处理for j in range(N):sum_of_col sum(S[:,j])for i in range(N):S[i, j] / sum_of_colprint(S)# 计算矩阵Aalpha 0.85A alpha*S (1-alpha) / N * np.ones([N, N])print(A)# 生成初始的PageRank值记录在P_n中P_n和P_n1均用于迭代P_n np.ones(N) / NP_n1 np.zeros(N)e 100000 # 误差初始化k 0 # 记录迭代次数print(loop...)while e 0.00000001: # 开始迭代P_n1 np.dot(A, P_n) # 迭代公式e P_n1-P_ne max(map(abs, e)) # 计算误差P_n P_n1k 1print(iteration %s:%str(k), P_n1)print(final result:, P_n)输入的input_1.txt文本内容为
A B
A C
A D
B D
C E
D E
B E
E A结果为 最后的一个数组分别为A, B, C, D, E的PageRank值其中E最高 A第二高 B和C相同均最低。
参考文献
[1] PageRank算法原理与实现
[2] 数据挖掘十大算法六PageRank算法原理与Python实现
[3] PageRank 维基百科自由的百科全书
[4] 斯坦福CS224W图机器学习、图神经网络、知识图谱【同济子豪兄】
