推荐系统论文阅读 Why Does Collaborative Filtering Work?

这篇是一篇比较早的利用图来研究推荐系统的文章（2005）：Why Does Collaborative Filtering Work? — Recommendation Model Validation and Selection by Analyzing Bipartite Random Graphs

作者利用二元图（bipartite）方法来对一个数据集做一个量化的评价，希望能够通过二元图拓扑结构的评价指标${C}$C来解释为何CF会比传统的算法好或者坏。定义的几种拓扑结构如下图所示，圆圈代表一个用户，方形代表一个物品。

由此可以定义一个4-node bipartite clustering coefficient：

${C_4 = \frac{4 × (number\ of\ 4-node\ cycles\ in\ the\ bipartite\ graph)}{number\ of\ 4-node\ paths}}$C4​=number of 4−node paths4×(number of 4−node cycles in the bipartite graph)​

直观来想，如果${C_4}$C4​太小，说明两个顾客${c_1,\ c_2}$c1​, c2​很少会共同买两个物品${p_1,\ p_2}$p1​, p2​，那么CF算法可能表现不如传统的Top-N流行算法好，因为这种协同的关系太少了。反之，可能CF算法会优于传统算法。

实验用了两个数据集retail和book，具体信息如下图所示：

z-score: indicate how much the observed values deviate from the simulated distribution

Retail相比book来说，observed ${C_4}$C4​偏离simulated更多（Z-score更大），CF算法相比Top-N流行算法表现更好。