推荐系统之SimRank算法

SimRank算法

一般而言，我们可以将用户和物品看作一张二部图，用户在一侧，物品在另一侧。有一个很简单的策略，如果两个用户连接的物品越相似，则这两个用户越相似。同样的，如果两个物品连接的用户越相似，则这两个物品就越相似。也就是说相似性是可以传递的。所以可以列出式子如下：

$$s(a,b)=\begin{cases} 1,a=b\\0,I(a)=\emptyset\ or\ I(b)=\emptyset\\\frac{C}{|I(a)||I(b)|}\sum_{i\in I(a)}\sum_{j\in I(b)}w_{a,i}s(i,j)w_{b,j} \end{cases}$$

其中，$I(a)$表示与$a$相连的二部图另一侧的节点的边权集合，$I(b)$表示与$b$相连的二部图另一侧的节点的边权集合，$|I(a)|$或$|I(b)|$表示集合边权和，$a$和$b$是在二部图同一侧的，$w_{a,i}$表示$a$和$i$的边权，$w_{b,j}$表示$b$和$j$的边权。对于第三种情况，假设二部图的边权都归一化了，有以下式子：

$$s(a,b)=Cw_a^T\{\sum_{i}\sum_{j}s(i,j)\}w_b=Cw_a^TSw_b$$

假设$S$表示相似度矩阵，则有以下递推式：

$$S_0=I$$ $$S_k=\max\{CW^TS_{k-1}W,I\}$$

有一个求max的步骤，这么做是为了维护对角元素相似度为1的性质。可以证明，当$W$和$S$所有数都大于等于0小于等于1，$W$每列元素和小于等于1时，$W^TSW$的所有元素均大于等于0小于等于1，所以取和单位矩阵的最大值可以维护对角元素值为1的性质。