python - 页面排名转换矩阵的高效实现

Question

我正在尝试实现 PageRank。我正在阅读这里的描述:http://nlp.stanford.edu/IR-book/html/htmledition/markov-chains-1.html

一切对我来说都非常清楚，但是我担心矩阵 $P$ 的构造。我发现以天真的方式构造 $P$ 会非常昂贵。例如:要实现步骤 1，需要检查 $A$ 的每一行，然后检查该行的每个元素以查看所有元素是否为零。对于第 2 步，需要计算每一行的个数。我可以想象我的代码有讨厌的慢循环。我想知道是否有可以有效构造 $P$ 的智能线性代数技术。我将使用 python numpy 进行编码。

编辑:我现在想解决这个问题的一种方法是对 $A$ 的列明智地进行求和元素。这样我就有了一个列向量。现在我将遍历该向量的每个元素以检查哪些元素为零。因此，我现在可以知道哪些行没有 1，并且我可以将这些行与 $1/N$ 相乘。

Answer 1

您的担心是正确的。由于网页(表示图中的顶点)数量巨大，因此不可能实际生成这样的 A 并对其进行处理。

使用 sparse matrix 可以更有效地计算页面排名的矩阵计算实现，因为矩阵非常稀疏。大多数网页实际上并没有相互连接，因此矩阵中的大多数条目都是 0。

稀疏矩阵构建如下:

• 如 A_ij = 1 所述构建矩阵 A 如果 (i,j) 是一条边，否则 A_ij = 0
• 通常不会执行第 1 步，而是迭代地删除“汇”。这样做是为了防止矩阵变得密集，一些替代方案还将“汇”链接回链接到它们的节点，或者将汇自身链接起来。
• 按照 (2) 中的描述将 A 中的每一个除以 1

让我们将结果矩阵表示为 M，这是我们将处理的结果矩阵，以便获得列向量 p(用 1 初始化/n 用于每个条目)。

x = [1/n, 1/n, ... , 1/n]^T //a column vector
p = [1/n, 1/n, ... , 1/n]^T //a column vector with the initial ranks
M = genSparseMatrix() //as described above
do until p converge:
    p = (1-\alpha)* M*p + (\alpha) * x
return p

最后，这会产生 p，即保存每个节点的页面排名值的列向量。