727 次浏览

PageRank算法

看到许多图神经网络论文都会涉及到Rank算法,所以抽空来看看这个Rank经典算法PageRank,算法的发明人就是两位Google创始人,这个算法最初也是作为网页的排名算法。

PageRank算法是基于有向图的形式进行的,在其上定义一个随机游走模型(一阶马尔科夫链),通过马尔科夫链的n步转移概率,整个有向图的概率转移会趋于稳定,达到收敛值。也就是我们在访问网页时,由一个网页到另一个网页的概率是一个定值,这样通过定值来判断网页的重要度。

PageRank算法描述

将强连通且非周期性的有向图记作\(\)\(G=(V, E)\)\(\),其中V和E分别表示节点和有向边的集合。转移概率矩阵\(\)\(M=[m_{ij}]_{n*n}\)\(\),\(\)\(m_{ij}= 1/k\)\(\)(k为由j连出的k条边,i为其中之一),也就是当前网页j跳转到网页i的概率。

所以有上述定义,在进行状态转移时,假设时刻\(\)\(t\)\(\)的状态分布\(\)\(R_t\)\(\),则在时刻\(\)\(t+1\)\(\)的状态分布为:\(\)\(R_{t+1}=M R_t\)\(\)。

通过迭代得到时刻\(\)\(t\)\(\)的状态分布\(\)\(R_t = M^t R_0\)\(\),并最终收敛,\(\)\(lim_{t \rightarrow \infty}=R\)\(\),最终得到的R的各个分量为每个节点(网页)的最终PageRank值: \(\)\(PR(v_i)=\sum_{v_j \in M(v_i)}\frac{PR(v_j)}{L(v_j)}\)\(\),其中\(\)\(M(v_i)\)\(\)为指向节点\(\)\(v_i\)\(\)的节点集合,\(\)\(L(v_j)\)\(\)为节点\(\)\(v_j\)\(\)连出的节点数

节点之间关系图
概率转移矩阵
假设初始状态分布,R0初始状态设置总和为1,总会收敛到固定值。

使用上述图以及python networkx包来计算pagerank值,很简单的掉包进行工具人操作。

import networkx as nx

# 创建有向图
G = nx.DiGraph()

# 有向图之间边的关系
edges = [("A", "B"), ("A", "C"), ("A", "D"), ("B", "A"), ("B", "D"), ("C", "A"), ("D", "B"), ("D", "C")]

for edge in edges:

    G.add_edge(edge[0], edge[1])

pagerank_list = nx.pagerank(G, alpha=1)

print("pagerank 值是:", pagerank_list)

>>> pagerank 值是: {‘A’: 0.33333396911621094, ‘B’: 0.22222201029459634, ‘C’: 0.22222201029459634, ‘D’: 0.22222201029459634}

上述的过程,因为图是强连通的,最终会收敛与平稳状态,当图不是强连通的,最终PR值将会变成0(reference2,等级泄露、等级沉默)。

为了解决这个问题,PageRank算法定义了一个阻尼系数d(经验系数)。
\(\)\(PR(v_i)=d(\sum_{v_j \in M(v_i)}\frac{PR(v_j)}{L(v_j)})+ \frac{1-d}{n}\)\(\)

import networkx as nx

# 创建有向图
G = nx.DiGraph()

# 有向图之间边的关系
edges = [("A", "B"), ("A", "C"), ("A", "D"), ("B", "A"), ("B", "D"), ("C", "C"), ("D", "B"), ("D", "C")]

for edge in edges:

    G.add_edge(edge[0], edge[1])

pagerank_list = nx.pagerank(G, alpha=1)

print("pagerank 值是:", pagerank_list)

>>> pagerank 值是: {‘A’: 1.1390724191374332e-06, ‘B’: 1.6601150213484846e-06, ‘C’: 0.999995540697538, ‘D’: 1.6601150213484846e-06}

简单的将前面图中的C->A的边去掉,给C点增加一个自环(等级泄露),再进行程序的运行,C的PR值变得很高(这里没有管networkx中PageRank算法的实际实现,使用迭代计算C的PR值升高到一半了)

下面是迭代法进行计算,进行验证。

import numpy as np

# 等级沉默
# M = np.array([
#     [0, 1/2, 1/2, 0],
#     [1/2, 0, 0, 1],
#     [0, 0, 0, 0],
#     [1/2, 1/2, 1/2, 0]
# ])

# 等级泄露
M = np.array([
    [0, 1/2, 0, 0],
    [1/3, 0, 0, 1/2],
    [1/3, 0, 1, 1/2],
    [1/3, 1/2, 0, 0]
])

R = np.array([
    [1/4],
    [1/4],
    [1/4],
    [1/4]
])

I = np.array([
    [1],
    [1],
    [1],
    [1]
])

for i in range(20):
    R = 0.8 * np.dot(M, R) + 0.2/4 * I
    print(i, ':', R)

最后,推荐大家看看reference2的博客,里面有关于使用PageRank进行数据挖掘希拉里邮件门的案例。

reference
1. 李航,《统计学习方法》第二版
2. https://www.cnblogs.com/jpcflyer/p/11180263.html
3. https://networkx.github.io/documentation/stable/tutorial.html#