algorithm - 如何用MapReduce/Hadoop实现特征值计算？

Question

这是可能的，因为 PageRank 是特征值的一种形式，这就是引入 MapReduce 的原因。但是在实际实现中似乎存在问题，比如每台从机都要维护一份矩阵？

Answer 1

PageRank 通过迭代寻找网络的稳态离散流条件来解决主导特征向量问题。

如果NxM矩阵A描述了从节点n到节点m的链路权重(流量)，则

p_{n+1} = A . p_{n} 

在 p 收敛到稳态 (p_n+1 = p_n) 的极限下，这是一个特征值为 1 的特征向量问题。

PageRank 算法不需要将矩阵保存在内存中，但在密集(非稀疏)矩阵上效率低下。对于密集矩阵，MapReduce 是错误的解决方案——您需要局部性和节点之间的广泛交换——您应该改为查看 LaPACK 和 MPI 以及其他 friend 。

您可以在 wukong library 中看到有效的 pagerank 实现(用于 ruby​​ 的 hadoop 流)或在 Heretrix pagerank submodule 中. (heretrix代码独立于Heretrix运行)

(免责声明:我是悟空的作者。)