【社区检测】PageRank算法及其改进算法LeaderRank介绍

发表于 更新于 分类于 阅读次数：
本文字数： 6.9k 阅读时长 ≈ 6 分钟

PageRank 算法，网页排名，又称网页级别或佩奇排名，是一种根据网页间相互超链接进行网页排名的技术，以Google公司创办人拉里·佩奇（Larry Page）之姓来命名。

LeaderRank 算法，PageRank 的改进版本。

简要介绍

由于网上有很多关于这个算法的原理描述，这里就简单地说下，不多做介绍了，想了解地更详细的话，可以参考下面的链接。

Fig.PageRank
Fig.PageRank
  • PageRank
    • 每个网页可以当做一个节点，节点与节点之间有向图连接（即形成关系）；
    • 初始情况下，用户在所有网页上浏览的概率可以是 \(P=\frac{1}{n}\)，和为1；
    • 随着时间（迭代次数）的更进，页面的值会通过（投票）算法不断迭代，直至达到平稳分布为止。
      • 这种（投票）算法和不同节点的出度数目有关，会形成一个出度的概率转移矩阵。
Fig.LeaderRank
Fig.LeaderRank
  • LeaderRank
    • 在基本的 Pagerank 算法基础上，LeaderRank 增加一个背景节点与所有节点进行双向连接。这个新的网络成了一个强连通网络，修复了基本的 Pagerank 算法的一些问题。

重要公式

PageRank

\[ PR\left(p_{i}\right)=\alpha \sum_{p_{j} \in M_{p_{i}}} \frac{PR\left(p_{j}\right)}{L\left(p_{j}\right)}+\frac{(1-\alpha)}{N} \]

  • PR-PageRank
  • 式子是 PageRank 的修正版计算方式
    • \(PR(p_j)\)：网页 \(p_j\) 的 LeaderRank 值
    • \(\alpha\)：阻尼系数，一般取 0.85，解决某个节点-环的问题
    • \(M_{p_i}\)：指向 \(p_i\) 网页的网页集合
    • \(L(p_j)\)：网页 \(p_j\) 的出度
    • 注意，\(\alpha\) 和 \(\frac{(1-\alpha)}{N}\) 的引入主要是为了解决节点带环的问题
    • \(N\)：节点个数

不带加权的 LeaderRank （PageRank的改进版）

\[ LR\left(p_{i}\right)=\alpha \sum_{p_{j} \in M_{p_{i}}} \frac{LR\left(p_{j}\right)}{L\left(p_{j}\right)}+\frac{(1-\alpha)}{N} \]

\[ LR(p_i) = LR(p_i) + \frac{\hat{LR}(p_g)}{N} \]

  • LR-LeaderRank
  • 第一个式子是 PageRank 的修正版计算方式（这里因为是 LeaderRank，用 LR 标记）
    • \(LR(p_j)\)：网页 \(p_j\) 的 LeaderRank 值
    • \(\alpha\)：阻尼系数，一般取 0.85，解决某个节点-环的问题
    • \(M_{p_i}\)：指向 \(p_i\) 网页的网页集合
    • \(L(p_j)\)：网页 \(p_j\) 的出度
    • 注意，\(\alpha\) 和 \(\frac{(1-\alpha)}{N}\) 的引入主要是为了解决节点带环的问题
    • \(N\)：节点个数
  • 第二个式子是 LeaderRank 的计算方式
    • \(p_g\)：增加的一个 g 节点
    • \(\hat{LR}(p_g)\)：稳定状态下节点 g 节点的 LR 值

带加权的 LeaderRank（LeaderRank的改进版）

\[ LR\left(p_{i}\right)=\alpha \sum_{p_{j} \in M_{p_{i}}} LR(p_{j})w_{p_{j}}+\frac{(1-\alpha)}{N} \]

\[ LR(p_i) = LR(p_i) + \frac{\hat{LR}(p_g)}{N} \]

  • 这里不同的地方主要是 \(w_{p_{j}}=\frac{w_j}{\sum w}\)，表示权值的占比
    • 即：当前 \(p_j\) 与 \(p_i\) 的权值 / 当前 \(p_j\) 连接所有网页节点的权值

数据格式

  • 文件命名为 “demo_data.xlsx”，保存在当前目录下
Fig.demo_data.xlsx
Fig.demo_data.xlsx

代码参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
# LeaderRank 的带权和不带权实现。
import pandas as pd
import networkx as nx

def read_excel2data(path):
    """
    读取 Excel 数据
    """
    return pd.read_excel(path)

def build_data(data):
    """
    构建关系图
    """
    # 构建图
    dg = nx.MultiDiGraph()#.adjacency()#.predecessors(node)
    # 构建图节点，将所有不重复节点找出，假设每个节点都存在关系
    node_ = data.iloc[:,1].drop_duplicates().values.tolist()
    dg.add_nodes_from(node_)
    # 构建关系
    data = data.iloc[:,1:]
    for i in range(data.shape[0]):
        tmp = data.iloc[i,:].values.tolist()
        dg.add_edge(tmp[0],tmp[1],weight=tmp[2])
    return dg

class LRModel:
    """
    计算图的 leader rank
    """
    def __init__(self, dg):
        self.damping_factor = 0.85  # 阻尼系数,即α
        self.max_iterations = 100  # 最大迭代次数
        self.min_delta = 0.00001  # 确定迭代是否结束的参数,即ϵ
        self.graph = dg

    def leader_rank(self, mode=0):
        #  先将图中没有出链的节点改为对所有节点都有出链
        # print(dict(self.graph._adj.items())['A'])
        for n, nbrsdict in self.graph.adjacency():
            # print(n,nbrsdict)
            if len(nbrsdict) == 0:
                for n2 in self.graph.nodes():
                    self.graph.add_edge(n, n2)
            
        ############################ LeaderRank，与 PageRank 不同部分 ###############################
        # 增加 g 节点，并且与所有节点进行连接
        self.graph.add_node('g')
        for node in self.graph.nodes():
            if node != 'g': # 增加了除g以外所有点的双向边
                self.graph.add_edge('g', node, weight=1) # 这里权值是可以改变的
                self.graph.add_edge(node, 'g', weight=1)
        ############################ LeaderRank，删去即为 PageRank ##################################

        # 所有节点
        nodes = self.graph.nodes()
        # 节点个数
        graph_size = len(nodes)
        #print(graph_size)

        if graph_size == 0:
            return {}
        leader_rank = dict.fromkeys(nodes, 1.0 / graph_size)  # 给每个节点赋予初始的PR值
        ############################ LeaderRank，与 PageRank 不同部分 ###############################
        leader_rank['g'] = 0.0 # 除了 g 节点
        ############################ LeaderRank，删去即为 PageRank ##################################
        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 predecessor in list(self.graph.predecessors(node)):  # 遍历所有node的前继节点
                    if mode == 0:
                        rank += self.damping_factor * (leader_rank[predecessor] / len(list(self.graph.successors(predecessor))))
        ############################ LeaderRank，与 PageRank 不同部分 ###############################
                    if mode == 1:
                        n_weight = self.graph.edges[predecessor, node, 0]['weight']
                        #print(n_weight)
                        weights = 0
                        for (nn, items) in dict(self.graph._adj.items())[predecessor].items():
                            # print(predecessor)
                            # print(nn, items)
                            weights += items[0]['weight']
                        # print(n_weight)
                        # print(weights)
                        rank += self.damping_factor * (leader_rank[predecessor] * (n_weight/weights))
        ############################ LeaderRank，删去即为 PageRank ##################################
                rank += damping_value
                change += abs(leader_rank[node] - rank)  # 绝对值
                leader_rank[node] = rank

            #print(f"第{(i + 1)}次迭代，各个节点的 LeaderRank 值：")
            #print(leader_rank)
            #print()

            if change < self.min_delta:
                flag = True
                print(f"共迭代了{i+1}次。")
                break
            
        ############################ LeaderRank，与 PageRank 不同部分 ###############################
        # 节点 g 的 LR 值平均分给其它的N个节点并且删除节点
        avg = leader_rank['g'] / graph_size
        leader_rank.pop('g')
        for k in leader_rank.keys():
            leader_rank[k] += avg
        ############################ LeaderRank，删去即为 PageRank ##################################

        if flag:
            print(f"在最高迭代次数{self.max_iterations}内，迭代结束！")
        else:
            print("超过了最高迭代次数！")
        return leader_rank   

if __name__ == "__main__":
    # demo 中5个节点，8条边
    excel_path = './demo_data.xlsx'
    all_data = read_excel2data(excel_path)

    ############################################################################################
    #不加权重
    print("【不考虑边的权重】")
    demo_dg = build_data(all_data)
    # print(demo_dg2.edges(data="weight")) # 查看权重
    # print(demo_dg2.edges) # 不查看权重
    print("图矩阵已构建！")
    print("...")

    lr = LRModel(demo_dg)
    leader_ranks2 = lr.leader_rank(mode=0)
    
    sorted_leader_ranks2 = sorted(leader_ranks2.items(), key=lambda item: item[1],reverse=True)
    print("最终的排序结果：")
    for n,v in sorted_leader_ranks2:
        print(f"{n}:{v}")
    ############################################################################################
    # 加权重
    print("【考虑边的权重】")
    demo_dg2 = build_data(all_data)
    print("图矩阵已构建！")
    print("...")

    lr2 = LRModel(demo_dg2)
    leader_ranks2 = lr2.leader_rank(mode=1)
    
    sorted_leader_ranks2 = sorted(leader_ranks2.items(), key=lambda item: item[1],reverse=True)
    print("最终的排序结果：")
    for n,v in sorted_leader_ranks2:
        print(f"{n}:{v}")
    ############################################################################################
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# output
【不考虑边的权重】
图矩阵已构建！
...
共迭代了27次。
在最高迭代次数100内，迭代结束！
最终的排序结果：
E:0.2537605095192026
A:0.20759481007355385
D:0.18412396715496265
B:0.15381976553691573
C:0.15381976553691573
【考虑边的权重】
图矩阵已构建！
...
共迭代了28次。
在最高迭代次数100内，迭代结束！
最终的排序结果：
E:0.24384387300099586
A:0.18288925002569967
D:0.17555678233142222
B:0.17282762965862306
C:0.16650192308383807

参考