python实现的pagerank算法

Python实现pagerank算法

Pagerank算法是谷歌的网页排序算法，通过对不同的网页赋予一定的权重，权重大的靠前。最原始的算法逻辑上并不难，主要是对网页赋初值，并进一步对迭代。

原始公式如下：

这里的Ru是网页U的打分，d是阻尼系数，B(u)是节点U的入邻居集合，Lv是点V的出读，Rv是点V的分数，N是总顶点个数。当图比较大的时候，我们会面临R值过小的情况，因此，两边同时乘N，并且另Ru = NRu， Rv = NRv，这样就得到了下面的公式：

通常情况下，我们对图中的每个点初始赋值为1，然后利用公式迭代。迭代的终止条件有两种，一种是直接迭代固定的次数，第二种是两次迭代点之间差值的平均值小于一个数时停止。

这里给出一种python实现方法，选择固定迭代次数，对输入图数据进行迭代。

# 用于存储图
class Graph():
    def __init__(self):
        self.linked_node_map = {}  # 邻接表
        self.PR_map = {}  # 存储不同的节点的PR值

    # 添加节点
    def add_node(self, node_id):
        if node_id not in self.linked_node_map:
            self.linked_node_map[node_id] = set({})
            self.PR_map[node_id] = 0
        else:
            print("这个节点已经存在")

    # 增加一条边
    def add_link(self, node1, node2):
        if node1 not in self.linked_node_map:
            self.add_node(node1)
        if node2 not in self.linked_node_map:
            self.add_node(node2)
        self.linked_node_map[node1].add(node2)  # 为node1添加一个邻接节点，表示ndoe2引用了node1

    # 计算pr
    def get_PR(self, path, epoch_num, d):  # 路径，迭代轮数，系数
        lines = open(path, "w+")
        for node in self.PR_map:
            self.PR_map[node] = 1
        for i in range(epoch_num):
            for node in self.PR_map:  # 遍历每一个节点
                num = sum([self.PR_map[temp_node]/(len(self.linked_node_map[temp_node])+1) for temp_node in self.linked_node_map[node]])
                self.PR_map[node] = (1 - d) + d * num
            if(i == epoch_num - 1):
                lines.write(str(self.PR_map))
            print("执行完第" +str(i) + "次迭代")

# 输入文件path每行一条边，边的两个点用空格分割，如更改，修正split，结果存储在res_path
if __name__ == '__main__':
    path = "graph.txt" # 这个是图的文件
    res_path = "res.txt" # 这个是结果文件
    lines = open(path, "r")
    graph = Graph()
    for line in lines:
        # print(line)
        points = line.split(' ')
        point1 = int(points[0])
        point2 = int(points[1])
        graph.add_link(point1, point2) //增加一条边
    graph.get_PR(res_path, 100, 0.85)
           

这里的图的构建参考了知乎上大佬的例子。这里的输入文件是类似这样的：

3837632 484095
3837632 86546
3837632 86546
6745739 733864
6745739 246090
6745739 153461
           

每一行代表一条边。