看到许多图神经网络论文都会涉及到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#