PageRank算法以及Python实现（简洁版）

古城微笑少年丶 2021-12-22 10:34 464阅读 0赞

## 简述 ##

PageRank有点被神化了，其实公式很简单。

### 文章目录 ###

*   *  简述
     *  算法
     *   *  模型定义
         *  Flow版本
         *  Google Formula
     *  实现

## 算法 ##

主要是分为两种：

*  The ‘Flow’ formula
 *  The Google formula

### 模型定义 ###

很多个网页，直接存在链路关系，设为G，N\*N的矩阵

这里先只考虑有向无权无环图，即边有方向，且权重都一样，且没有自己到自己的边（环）。

*  N为节点数或者是网页数
 *  G\[i\]\[j\] = 1表示，i->j有条边

### Flow版本 ###

r i = ∑ ( j = 1 ) a n d ( j − > i ) N r j d j r\_i = \\sum\_\{(j=1) and (j -> i)\}^N\{\\frac\{r\_j\}\{d\_j\}\} ri=(j=1)and(j−>i)∑Ndjrj

一个很好是数学写法就是：

r = M ∗ r r = M \* r r=M∗r

*  如果有`i->j`, M\[j\]\[i\] = 1/dj，否者为0

**算法流程：**

*  也就是，随机初始化每个点的分数
 *  然后，迭代：
    
     *  每个点的分数，由所有 **指向他的节点的分数** 除以 **这个节点的出度数** 求和所替代
 *  Flow版本会出现两个重要的问题;
    
     *  Dead End：例如只有两个点，然后边为`A->B`，B就是一个Dead END。即到这时候的分数就出不去了。
     *  Spider Traps：循环指向，例如`A->B->A`。那么这个分数就会这之间打转

### Google Formula ###

刚刚说的两个问题在Google Formula上得到很好的改进：

*  提出了一个叫做Teleport的概念，也称之为意念转移。

**很简单，就是说，每个节点有一定的概率发生随机跳转到任意一个点的情况。再结合MapReduce的概念，Google就这样发家了emmmm**

r i = β ∗ ∑ ( j = 1 ) a n d ( j − > i ) N r j d j + ( 1 − β ) ∗ 1 N r\_i = \\beta \* \\sum\_\{(j=1) and (j -> i)\}^N\{\\frac\{r\_j\}\{d\_j\}\} + (1 - \\beta) \* \\frac\{1\}\{N\} ri=β∗(j=1)and(j−>i)∑Ndjrj\+(1−β)∗N1

直接的数学表达：

r = A ∗ r A = β ∗ M + ( 1 − β ) ∗ \[ 1 N \] N ∗ N r = A \* r \\\\ A = \\beta \* M + (1-\\beta) \* \[\\frac\{1\}\{N\}\]\_\{N\*N\} r=A∗rA=β∗M\+(1−β)∗\[N1\]N∗N

Google简化后的数学表达：

r = β ∗ M ∗ r + \[ 1 N \] N r = \\beta \* M \* r + \[\\frac\{1\}\{N\}\]\_N r=β∗M∗r\+\[N1\]N

*  如果有`i->j`, M\[j\]\[i\] = 1/dj，否者为0

**存在的问题：**

*  虽然直接的数学表达会更简洁，但是多出来的A一定会是稠密矩阵使得空间消耗为O(N^2)了，这样的在网站达到数亿的情况下，这个东西就不太现实了。
 *  而Google简化的版本中就只需要记录同样稀疏的M即可，1/N是一个数，只需要让r这个向量的每个元素都加上即可（简单的数学变形，在工业上的产生的价值就很大的不一样了。真的佩服研究数学的哥们）

## 实现 ##

实现同样做两个不同的版本的：

但有些共同的模型：

**导入包：**

import numpy as np
    import random

**创造数据：**

def create_data(N, alpha=0.5): # random > alpha, then here is a edge.
        G = np.zeros((N, N))
        for i in range(N):
            for j in range(N):
                if i == j:
                    continue
                if random.random() < alpha:
                    G[i][j] = 1
        return G
    G = create_data(10)

**GtoM：**

def GtoM(G, N):
        M = np.zeros((N, N))
        for i in range(N):
            D_i = sum(G[i])
            if D_i == 0:
                continue
            for j in range(N):
                M[j][i] = G[i][j] / D_i # watch out! M_j_i instead of M_i_j
        return M
    M = GtoM(G, 10)

*  Flow版本的PageRank

def PageRank(M, N, T=300, eps=1e-6):
        R = np.ones(N) / N
        for time in range(T):
            R_new = np.dot(M, R)
            if np.linalg.norm(R_new - R) < eps:
                break
            R = R_new.copy()
        return R_new

测试下：

values = PageRank(M, 10, T=2000)
    values

输出：

array([0.09972576, 0.09193927, 0.07843151, 0.09125886, 0.08925602,
           0.10407245, 0.09623654, 0.13851257, 0.13086464, 0.07970237])

*  Google Formula

def PageRank(M, N, T=300, eps=1e-6, beta=0.8):
        R = np.ones(N) / N
        teleport = np.ones(N) / N
        for time in range(T):
            R_new = beta * np.dot(M, R) + (1-beta)*teleport
            if np.linalg.norm(R_new - R) < eps:
                break
            R = R_new.copy()
        return R_new

同样的数据测试下：

测试下：

values = PageRank(M, 10, T=2000)
    values

输出：

array([0.09815807, 0.09250429, 0.08376235, 0.09300133, 0.09324628,
           0.10108776, 0.09855127, 0.13019363, 0.12458992, 0.0849051 ])