稀疏矩阵和PageRank算法

节点数据比较稀疏，比如200个节点，完全连接的情况下有40000行，其中每行代表一个连接，但一般只有3000多行的连接，其余均是零。在这种情况下，使用稀疏矩阵来表示点与点之间的关系更为适合——每个数字4个字节，256个数字1k,40000个数字0.16Mb,但wiki节点数在1千万以上，即完全矩阵显示的话存储需要360多个TB,但边只有192万，即低于8MB，由此可见使用稀疏矩阵的必要性。

导入安装包

import numpy as np
from scipy.sparse import csr_matrix

导入数据

当读入的数据量较大时，一般使用上下文管理器with语句，进行单行读取操作。测试数据集可以是任意有向网络数据集，只不过需要将后面的890换为你数据集节点数加1——Python是以0开始计位。另外，需要提前将数据集进行清洗，分析的数据集从第一行开始即为边数据，而不是统计或者描述性信息。

file_name = ""
network_file = f'./{file_name}.txt'
​
row_l = list()
col_l = list()
with open(network_file, "r", encoding="utf-8") as file1:
    while 1:
        networki = file1.readline()
        _temp_value = [int(i) for i in networki.strip().split()]
        if len(_temp_value) >= 2:
            row_l.append(_temp_value[0])
            col_l.append(_temp_value[1])
        else:
            break

数据处理

利用Scipy.sparse的csr_matrix方法将原始数据转化为稀疏矩阵。csr是指CompressedSparseRow矩阵。之所以选用csr而不是csc，是因为csr更便于后期的数据行向加总和矩阵乘法。代码中sparse_m.sum(axis=1)是对每行数据进行求和，原理同np.sum(axis=1)。另外我们可以通过tolist()方法，将scipy的矩阵数据格式转化为list数据格式——后者便于转化为np.ndarray数据格式进行结构变换。

values = [1 for _ in row_l]
sparse_m = csr_matrix((values,(row_l, col_l)), shape=(890, 890))
_axis_1_sum = np.array(sparse_m.sum(axis=1).tolist()).reshape((-1,))
values = list()
for i, j in zip(row_l, col_l):
    values.append(sparse_m[i,j] / _axis_1_sum[i])
sparse_m = csr_matrix((values,(row_l, col_l)), shape=(890, 890)).T

循环求解

PageRank求解方式很多，通过不断拟合数据，达到解稳定是其中一个。具体代码如下，d表示从当前节点以d的概率选择以转移矩阵的形式移到下一个节点，以1-d的概率以完全随机的方式或者以其它特定概率的方式移到下一个节点。如何选出影响力最大的k=20个节点？可以用np.argsort()方法。

d = 0.85
r = (_axis_1_sum / sum(_axis_1_sum)).reshape((-1, 1))
r_bool = _axis_1_sum.reshape((-1, 1)).astype(bool)
a = d * sparse_m
b = (np.ones((890, 1)) - d * r_bool) * r
# b = (1-d) * np.ones((890,1)) / 890
while 1:
    r0 =  a @ r + b
    r0 /= np.sum(r0)
    if np.transpose(r - r0) @ (r-r0) < 10**(-9):
        r = r0.copy()
        break
    else:
        r = r0.copy()
r = np.array(r).reshape((-1, ))
np.argsort(-r)[:20]

逆矩阵求解器

更简单的解决方案是根据逆矩阵求解。

ab = np.linalg.inv(np.eye(890, 890) - d * sparse_m) @ ((1-d) * np.ones((890, 1))/ 890)
ab = np.array(ab.tolist()).reshape((-1,))
np.argsort(-ab)[:20]