​基于图的随机游走推荐算法概述

基于图的推荐算法，被称为personalRank,它脱胎于PageRank，用概率游走方式，计算用户对商品的关注程度，最终形成推荐。

如图，是用户A B C，对商品a b c d 的浏览情况。我们可以看到，就A而言，浏览过a c,那么，我们的目的就是计算A对b d的关注程度，怎么计算呢，

我们要看的是，用户-商品所创建的图中，A到达 b d，所经历的路径。如图，A如果要到d,那么，可以是A-a-B-d ，或A-c-C-d；用类似这种路径概率，我们就可以知道，A可能对哪个更感兴趣。

其实，这就是一个特殊的PageRank，所以我们可以先看一下PageRank。pageRank是用出链入链来计算每一个网页的重要程度。

用PR代表页面的重要程度。

对于页面A，有B C D三个页面指向A，那么，A的PR(A)就是B C D三个页面的PR之和，及

但是，假设B的出链除了A，还有C，D的出链除了A还有两个，那么，B到A的概率就只有1/2 ,D到A的概率只有1/3,那么

更加通用的写法：

其中，L(x),是页面x的出链数。

对页面求PR值的完整公式是：

，其中 q是阻尼系数 0.85，为了防止无链页面对结果产生的影响。

我们要求的就是一系列的PR值，如果我们设这个系列为R

那么，我们由上面的公式得到一个关于矩阵的等式，稍等懂点矩阵知识就有，

那么，最后变成了对这么矩阵等式求解。得到R的最终结果。

而，personalRank和PageRank唯一的不同，就是1-q/N ,变成了 1-q 。因为我们不是对所有图中的元素求结果，而是固定一个点，来做迭代。

特别感谢“guisu，程序人生。 逆水行舟，不进则退。”博客主 ，部分公式来自博客

想解释一句，为毛我又写Java 又写算法，因为现在是算法团队的一名研发，准备让自己成为懂算法的Java研发O(∩_∩)O，是不是很扯