这是可能的,因为 PageRank 是特征值的一种形式,这就是引入 MapReduce 的原因。但是在实际实现中似乎存在问题,比如每台从机都要维护一份矩阵?
最佳答案
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运行)
(免责声明:我是悟空的作者。)
关于algorithm - 如何用MapReduce/Hadoop实现特征值计算?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/388302/