PageRank算法
PageRank算法总的来说就是预先给每个网页一个PR值（下面用PR值指代PageRank值），由于PR值物理意义上为一个网页被访问概率，所以一般是\(\frac{1}{N}\)，其中N为网页总数。另外，一般情况下，所有网页的PR值的总和为1。如果不为1的话也不是不行，最后算出来的不同网页之间PR值的大小关系仍然是正确的，只是不能直接地反映概率了。
所以PageRank算法实际上就是预先给定PR值后，通过每个网页之间的链接关系不断迭代，直至达到平稳分布为止。
各个网页的PR值之间的关系一般情况下表示为如下的式子：
\(PR(p_i)=α\sum_{p_j∈M_{p_i}}\frac{PR(p_j)}{L(p_j)}+\frac{(1-α)}{N}\)
其中\(M_{p_i}\)是所有对\(p_i\)网页有出链的网页集合；\(L(p_j)\)是网页的出链数目；\(N\)是网页总数；\(α\)是阻尼系数，即用户离开当前网页重新输入网址访问的概率，一般取0.85。
根据这一关系不断迭代，当算法收敛的时候，得到的PR值即使每个网页的PR排序值。
算法实现
digraph类
由于一个搜索引擎中的网页数不胜数，使用一个矩阵存储各个网页之间的链接关系是不可能的，这里采用有向图类来优化稀疏矩阵的存储。
| 名字 |
参数 |
说明 |
| init_nodes |
self, nodes |
初始化向图图的节点 |
| init_edges |
self, edges |
初始化向图图的边 |
| add_edge |
self, edge |
增加向图图中的边 |
| neighbors |
self, node |
返回参数节点的所有后继节点 |
| incidents |
self, node |
返回参数节点的所有前驱节点 |
class digraph:
def init_nodes(self, nodes):
self.nodes = nodes
def init_edges(self, edges):
self.edges = edges
def add_edge(self, edge):
self.edges.append(edge)
def neighbors(self, node):
neighbors = []
for edge in self.edges:
if edge[0] == node:
neighbors.append(edge[1])
return neighbors
def incidents(self, node):
incidents = []
for edge in self.edges:
if edge[1] == node:
incidents.append(edge[0])
return incidents
PRIterator类
PRIterator类是用来迭代计算PR值的类，由一个有向图和一个阻尼系数构造，阻尼系数即公式中的α。默认的最大迭代次数是100，确定迭代是否结束，即PR值是否收敛的参数为0.00001，即ϵ。
只有一个方法——page_rank方法，来迭代计算PR值直至收敛。同时如果一个节点没有任何的后继节点，那么相当于所有的节点都是它的后继节点，即一个网页没有出链的情况下，下一秒访问任何网页的概率都是相等的。
class PRIterator:
__doc__ = '''计算一张图中的PR值'''
def __init__(self, dg, damping_factor):
self.damping_factor = damping_factor # 阻尼系数,即α
self.max_iterations = 100 # 最大迭代次数
self.min_delta = 0.00001 # 确定迭代是否结束的参数,即ϵ
self.graph = dg
def page_rank(self):
# 先将图中没有出链的节点改为对所有节点都有出链
for node in self.graph.nodes:
if len(self.graph.neighbors(node)) == 0:
for node2 in self.graph.nodes:
self.graph.add_edge((node, node2))
nodes = self.graph.nodes
graph_size = len(nodes)
if graph_size == 0:
return {}
page_rank = dict.fromkeys(nodes, 1.0 / graph_size) # 给每个节点赋予初始的PR值
damping_value = (1.0 - self.damping_factor) / graph_size # 公式中的(1−α)/N部分
flag = False
for i in range(self.max_iterations):
change = 0
for node in nodes:
rank = 0
for incident_page in self.graph.incidents(node): # 遍历所有"入射"的页面
rank += self.damping_factor * (page_rank[incident_page] / len(self.graph.neighbors(incident_page)))
rank += damping_value
change += abs(page_rank[node] - rank) # 绝对值
page_rank[node] = rank
print("This is NO.%s iteration" % (i + 1))
if change < self.min_delta:
flag = True
break
if flag:
print("finished in %s iterations!" % node)
else:
print("finished out of 100 iterations!")
return page_rank
主函数
主函数的作用就是读取网页的链接数据，初始化有向图，迭代计算PR值直至收敛，最后输出计算结果。
测试的数据为维基百科网站上所有网页的链接数据，由于数据共有103689条，这里不再给出详细数据，文末附有数据集及源码，可执行文件下载链接。这里给出一部分样例的截图如下。数据格式为：网页ID——链接到的网页ID。
在主程序中，需要输入测试数据的路径和阻尼系数。运行结果如下图。
if __name__ == '__main__':
# python NewPageRankDemo.py
# 输入数据和输出结果所在的文件夹位置
directory = input('输入数据和输出结果所在的文件夹位置：\n示例输入：C:\\Users\\37618\\Desktop\\PageRank\\\n')
damping_factor = input('输入阻尼系数α（一般取0.85）：\n')
damping_factor = float(damping_factor)
# 储存训练样本数据
f = open(directory + 'WikiData.txt')
nodes = []
edges = []
for v in f:
tmp = v.split("\t")
tmp[1] = tmp[1].split("\n")[0]
if nodes.count(tmp[0]) == 0:
nodes.append(tmp[0])
if nodes.count(tmp[1]) == 0:
nodes.append(tmp[1])
edges.append((tmp[0], tmp[1]))
# 输出预测结果
import sys
output = sys.stdout
outputfile = open(directory + 'result(' +str(damping_factor)+ ').txt', 'w')
sys.stdout = outputfile
dg = digraph()
dg.init_nodes(nodes)
dg.init_edges(edges)
pr = PRIterator(dg, damping_factor)
page_ranks = pr.page_rank()
print("The final page rank is\n")
for page_rank in page_ranks:
print(page_rank, ' ', page_ranks.get(page_rank))
outputfile.close()
sys.stdout = output
示例输出如下图。
可以看到，程序在31次迭代后在ID为8274的网页处收敛，并输出了所有网页的PR值。
[mdx_warning title=”特别注意”]10万条数据的迭代非常占内存，请配置垃圾的笔记本们慎重尝试！[/mdx_warning]
源代码链接
源代码链接，附带测试数据集及测试输出，源代码及说明，可执行文件
