看到许多图神经网络论文都会涉及到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\)\(\)连出的节点数



使用上述图以及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#