Question

1. 过去几年大量研究致力于理解复杂的网络。一类特殊的网络是二部网络 bipartite network，其中节点被分为两组 $ \mathcal X,\mathcal Y $ ，并且只允许不同组中的节点之间存在连接，如下图 (a) 所示。许多系统自然地建模为二部网络，例如人类性别网络 human sexual network 由男性和女性组成、代谢网络 metabolic network 由化学物质和化学反应组成。有两种二部网络很重要，因为它们在社会、经济、以及信息系统中有特殊意义。

   • 一种是所谓的协同网络 collaboration network。这种网络的例子很多，包括共同撰写同一篇科学论文而联系起来的科学家、共同主演同一部电影而联系起来的演员等等。此外，协同网络的概念不一定局限于社会系统。

     尽管协同网络通常通过对参与者的 one-mode 投影来展示，但是它的完整表示是一个二部网络。

   • 另一种是所谓的意见网络 opinion network，其中用户集合user-set 中的节点和对象集合object set 中的节点相连。例如，听众和他们在音乐共享库收集的音乐建立联系、互联网用户和他们在书签网站中收集的 web url 建立联系、顾客和他们购买的书籍建立联系。

   最近，人们对分析和建模二部网络给予了很多关注。但是，为了方便直接表示一组特定节点之间的关系，通常采用 one-mode 投影来压缩二部网络。 $ \mathcal X $ 上的 one-mode 投影（简称 $ \mathcal X $ 投影） 是指仅包含 $ \mathcal X $ 节点的网络，当两个 $ \mathcal X $ 节点至少存在一个共同的 $ \mathcal Y $ 邻居节点时这两个 $ \mathcal X $ 节点相连。下图 (b) 展示了 $ \mathcal X $ 投影的结果网络、(c) 展示了 $ \mathcal Y $ 投影的结果网络。

   

   最简单的方法是将二部网络投影到一个未加权的网络上，而不考虑协同collaboration 重复的频次。虽然可以从这个未加权的版本中定性地获得一些拓扑特性，但是信息的损失是显而易见的。例如，如果两位听众各自收集了 100 首以上的音乐，并且这两位听众仅共享了一首音乐，那么可以得出结论：这两位听众可能具有不同的音乐偏好。相反，如果这两位听众共享了接近 100 首音乐，那么这两位听众很可能具有非常相似的习惯。然而，在未加权的听众投影中，这两种情况具有完全相同的 graph representation 。

   由于 one-mode 投影总是比原始二部网络提供的信息更少，为了更好地反映网络的结构，必须使用二部图来量化投影图中的权重。一种直接的方法是直接通过相应 partnership 重复的次数来对边进行加权。如图 (b),(c) 所示，这个简单的规则可以获得 $ \mathcal X $ 投影和 $ \mathcal Y $ 投影的权重。这个加权网络比未加权网络提供更多信息，并且可以通过未加权图的标准技术进行分析，因为它的权重都是整数。然而，这种方法在定量上也是有偏的quantitatively biased 。

   Li 等人对科学协同网络进行了实证研究，并指出额外一篇合作论文的影响应该取决于两位作者之间的原始权重。例如，如果两位作者之间之前仅合作一篇论文，那么多一篇合作论文将比两位作者之前合作 100 篇论文的影响更大。通过将双曲正切函数引入简单的协同次数计数，可以考虑这种饱和效应saturation effect 。

   Newman 指出，与许多其他合作者一起出现在同一篇论文的两位作者，他们的平均相互了解程度低于作为论文唯二作者的两位作者。为了考虑这种影响，他引入了因子 $ 1/(n-1) $ 来削弱涉及多个参与者的合作的贡献，其中 $ n $ 是参与者的数量。

   如何对边进行加权是 one-mode 投影及其使用的关键问题。然而，我们缺乏对这个问题的系统探索，迄今为止都还没有任何加权方法的坚实理论基础。

   • 例如，人们可能会问为什么使用双曲正切函数来解决饱和效应而不是其它大量潜在的候选函数的理论依据。
   • 此外，为了简单起见，加权邻接矩阵 $ \mathbf W $ 总是设置为对称的，即 $ w_{i,j} = w_{j,i} $ 。然而，在科学协同网络中，同一篇合作论文中不同的作者可能会分配不同的权重，可能是发表论文较少的作者给予更高的权重，亦或反之。因此，更自然的加权方法可能是非对称的。

   现有方法的另一个缺陷是：在 $ \mathcal X $ 投影图中，如果 $ \mathcal Y $ 顶点只有一个相连的 $ \mathcal X $ 顶点，则这个连接关系会在投影过程中丢失。 $ \mathcal Y $ 投影图也有类似的问题，如 $ x_8 $ 仅仅和 $ y_5 $ 关联，这使得在 $ \mathcal Y $ 的投影图中完全丢失了 $ x_8 $ 的信息。即二部网络中 degree 为 1 的边所包含的信息将在 one-mode 投影中丢失。 这种信息丢失在一些真实的意见网络中可能会很严重。例如在 user-web 网络 delicious 中，有相当一部分的 web 仅被收集一次，而相当一部分 user 仅收集了一个 web。因此，无论是用户投影还是 web 投影，都将浪费大量信息。

   与意见网络密切相关的一个核心问题是：如何抽取隐藏信息 hidden information 并进行个性化推荐。互联网和 World Wide Web 的指数级增长使得人们面临信息过载：用户面临太多数据和来源，无法找到与用户最相关的信息。信息过滤的一个里程碑是使用搜索引擎，然而它无法解决这个过载问题，因为它没有考虑个性化，因此对于习惯截然不同的用户返回了相同的结果。因此，如果用户的习惯和主流不同，那么用户很难在无数的搜索结果中找到自己喜欢的东西。迄今为止，有效过滤信息过载的最有潜力的方法是个性化推荐。也就是说，使用用户的个人信息（即该用户活动的历史轨迹）来揭示其习惯并在推荐中加以考虑。例如，Amazon.com 使用用户的购买历史来提供个性化推荐。如果你购买了统计物理学教科书，那么亚马逊可能会向你推荐一些其它统计物理学书籍。基于成熟的 WEB 2.0 技术，推荐系统经常用于 web-based 的电影共享（音乐共享、书籍共享等）系统、web-based 的销售系统、书签网站等。最近，受经济和社会意义的推动，高效推荐算法的设计成为从营销实践到数学分析、从工程科学到物理学界的共同焦点。

   在论文 《Bipartite network projection and personal recommendation》 中，作者提出了一种非对称（即 $ w_{i,j}\ne w_{j,i} $ ）、允许自连接（即 $ w_{i,i}\gt 0 $ ）的加权方法。此外，作者提出的方法是沟通二部网络投影、个性化推荐双方的桥梁。数值模拟表明：论文的方法作为个性化推荐算法，其性能显著优于广泛使用的全局排序方法global ranking method: GBM 和协同过滤 collaborative filtering: CF 。

6.1 模型

6.1.1 加权投影图

1. 不失一般性，我们首先确定 $ \mathcal X $ 加权投影图中边的权重。定义 $ w_{i,j} $ 为：从顶点 $ x_j $ 的角度看，顶点 $ x_i $ 的重要性。 我们假设每个 $ \mathcal X $ 类型的顶点都有一定数量的资源（如推荐强度 power ），因此 $ w_{i,j} $ 表示顶点 $ x_j $ 的资源需要分配给顶点 $ x_i $ 的比例。通常 $ w_{i,j} \ne w_{j,i} $ 。

   为得到 $ w_{i,j} $ 的解析表达式，我们回归二部图。由于二部图本身是无权的，因此任意 $ \mathcal X $ 类型顶点的资源应该平均分配给它的 $ \mathcal Y $ 类型的邻居；同理，任意 $ \mathcal Y $ 类型顶点的资源应该平均分配给它的 $ \mathcal X $ 类型的邻居。如下图所示，我们最初为三个 $ \mathcal X $ 类型的顶点初始分配了资源 $ x,y,z $ 。则资源重新分配过程包含两个步骤：

   • 资源先从 $ \mathcal X $ 类型的顶点流动到 $ \mathcal Y $ 类型的顶点。
   • 然后资源从 $ \mathcal Y $ 类型的顶点流回 $ \mathcal X $ 类型的顶点。

   假设最后三个 $ \mathcal X $ 类型的顶点最终分配到资源 $ x^\prime,y^\prime,z^\prime $ ，则有：

   $ \begin{bmatrix} x^\prime\\ y^\prime\\ z^\prime \end{bmatrix} = \begin{bmatrix} \frac {11}{18} & \frac{1}{6}&\frac{5}{18}\\ \frac {1}{9} & \frac{5}{12}&\frac{5}{18}\\ \frac {5}{18} & \frac{5}{12}&\frac{4}{9}\\ \end{bmatrix}\begin{bmatrix} x \\ y\\ z \end{bmatrix} $

   这个 3x3 的矩阵是按列归一化的，记作 $ \mathbf W=\{w_{i,j}\}_{3\times 3} $ ，则第 $ i $ 行第 $ j $ 列元素 $ w_{i,j} $ 表示 $ x_j $ 的初始资源转移到 $ x_i $ 的比例（占 $ x_j $ 初始资源的比例）。根据前面的描述，这个矩阵就是我们需要的权重矩阵。

   

2. 现在考虑更通用的二部图 $ G(X,Y,E) $ ，其中 $ X=\{x_1,\cdots,x_n\} $ 为 $ \mathcal X $ 类型的顶点， $ Y=\{y_1,\cdots,y_m\} $ 为 $ \mathcal Y $ 类型的顶点， $ E $ 为二部图的边。我们定义二部图的邻接矩阵为：

   $ \mathbf A = \begin{bmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,m}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,m}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,m} \end{bmatrix} $

   其中 $ a_{i,l} $ 表示 $ (x_i,y_l) $ 之间的邻接关系：

   $ a_{i,l} = \begin{cases} 1,& (x_i,y_l)\in E\\ 0,& (x_i,y_l)\notin E \end{cases} $

   定义 $ d_{x_i} $ 为顶点 $ x_i $ 的度degree： $ d_{x_i} = \sum_{l=1}^m a_{i,l} $ 。定义 $ d_{y_l} $ 为顶点 $ y_l $ 的度degree ： $ d_{y_l} = \sum_{i=1}^n a_{i,l} $ 。

   假设 $ \mathcal X $ 类型的顶点 $ x_i $ 具有初始的资源 $ f(x_i) \gt 0 $ 。

   • 第一步：所有 $ \mathcal X $ 的资源流入 $ \mathcal Y $ 中，则 $ y_l $ 的资源为：

     $ f(y_l) = \sum_{i=1}^n \frac{a_{i,l}}{d_{x_i}}\times f(x_i) $

   • 第二步：所有 $ \mathcal Y $ 的资源流入 $ \mathcal X $ 中，则 $ x_i $ 的资源为：

     $ f^\prime(x_i) = \sum_{l=1}^m \frac{a_{i,l}}{d_{y_l}}\times f(y_l) = \sum_{l=1}^m \frac{a_{i,l}}{d_{y_l}}\sum_{j=1}^n \frac{a_{j,l}}{d_{x_j}}\times f(x_j)\\ = \sum_{j=1}^n\left(\frac{1}{d_{x_j}}\sum_{l=1}^m\frac{a_{i,l} a_{j,l}}{d_{y_l}}\right)\times f(x_j) $

   如果重写为：

   $ f^\prime(x_i) = \sum_{j=1}^n w_{i,j}f(x_j) $

   则有：

   $ w_{i,j} = \frac{1}{d_{x_j}} \sum_{l=1}^m \frac{a_{i,l}a_{j,l}}{d_{y_l}} $

   因此矩阵 $ \mathbf W = \{w_{i,j}\}_{n\times n} $ 就是我们希望得到的 $ \mathcal X $ 投影图的权重矩阵。因此 $ \mathcal X $ 的资源重新分配过程可以重写为：

   $ \mathbf{\vec f}^\prime = \mathbf W \mathbf{\vec f} $

   该算法可以看作是 PageRank 算法的推广，而这些算法本质上是基于消息传递机制。

3. 可以发现权重矩阵 $ \mathbf W $ 的几个特点：

   • 权重矩阵是非对称的，且满足：

     $ \frac{w_{i,j}}{d_{x_i}} = \frac{w_{j,i}}{d_{x_j}} $

     这符合我们的经验，如果某个科学家发表了很多论文，即他的 degree 很大，则单篇合作论文的权重相对较小。 $ w_{i,j} $ 代表 $ x_j $ 资源转移到 $ x_i $ 的比例，如果 $ x_j $ 的degree 比较大，则它转移到 $ x_i $ 的比例也会较低。

   • 权重矩阵对角线元素非零。这意味着：如果 $ \mathcal Y $ 顶点只有一个相连的 $ \mathcal X $ 顶点，则这个连接关系会在投影过程中得到保留。假设该顶点为 $ y_s $ ，唯一与它相连的顶点为 $ x_i $ ，则有：

     $ d_{y_s} = 1,\quad a_{j,s} = \begin{cases} 1,& j=i\\ 0,& j\ne i \end{cases} $

     因此有：

     $ w_{i,i} = \frac{1}{d_{x_i}} \left(\frac{a^2_{i,1} }{d_{y_1}} + \cdots + \frac{a^2_{i,s} }{d_{y_s}} + \cdots \right) $

     可以看到 $ (x_i,y_s) $ 的连接关系被保留在 $ w_{i,i} $ 中。

     事实上可以证明：权重矩阵对角线元素是每一列的最大元素，即 $ w_{i,i}\ge w_{j,i} $ 。当且仅当 $ x_i $ 的所有 $ \mathcal Y $ 邻居都是 $ x_j $ 的 $ \mathcal Y $ 邻居的子集时，等式成立。这在论文协作网络上可以发现。如：学生的论文都是和他们的导师共同发表的，因此如果 $ x_i $ 为学生、 $ x_j $ 为他/她的导师，则有 $ \frac{w_{j,i}}{w_{i,i}}\le 1 $ 。

     因此比例系数 $ \frac{w_{j,i}}{w_{i,i}} $ 可以视为 $ x_i $ 的研究相对于 $ x_j $ 的独立性，这个比例越低则独立性越高。最终 $ x_i $ 的独立性可以刻画为：

     $ I_i = \sum_{j=1}^n\left(\frac{w_{j,i}}{w_{i,i}}\right)^2 $

     注意：度量 $ I_i $ 仅仅只是一个示例，它用于说明如何使用 $ w_{i,i} $ 中包含的信息，并不能说明独立是好还是不好。

6.1.2 NetworkBased 推荐

1. 一个推荐系统包含用户集合 $ \mathbb U = \{u_1,\cdots,u_m\} $ ，推荐对象object 集合 $ \mathbb O=\{o_1,\cdots,o_n\} $ 。

   假设只存在用户到object 的边，则推荐系统可以描述为一个 $ m\times n $ 的邻接矩阵 $ \mathbf A=\{a_{i,j}\} $ 。

   我们假设意见网络是无权重的，即：如果 $ u_i $ 收藏了 $ o_j $ ，则 $ a_{i,j}=1 $ 。 $ a_{i,j} = 0 $ 表示用户 $ u_i $ 对 $ o_j $ 尚未收藏。我们认为用户收藏了对象表明用户喜欢该对象。

   一个更复杂的情况是，用户不仅表示了喜欢的意向，还给出了喜欢的程度（以评分表示）。这两种情况密切相关，但是本文我们重点讨论前一种情况。

2. 定义 $ d_{o_i} $ 为 object $ o_i $ 的度 degree ， $ d_{u_i} $ 为用户 $ u_i $ 的度 degree 。

   • Global Ranking Method:GRM：将所有 object 按照 degree 降序排列，并推荐 degree 最高的top 对象，即推荐热门对象。

     尽管GRM 缺乏个性化导致推荐效果不尽人意，但是它简单直接并且节省资源，因此被广泛使用。如 “畅销新书“ 这类推荐都可以视为 GRM 。

   • MemoryBased CF：基于用户之间相似度的个性化推荐。

     给定用户 $ u_i $ 和 $ u_j $ ，他们的相似度定义为：

     $ \text{sim}_{i,j} = \frac{\mathbf{\vec u}_i\cdot \mathbf{\vec u}_j}{||\mathbf{\vec u}_i||\times ||\mathbf{\vec u}_j||} $

     其中 $ \mathbf{\vec u}_i = (a_{i,1},a_{i,2},\cdots,a_{i,n})^T $ 为以object 表示的用户向量，且 $ a_{i,l}\in \{0,1 \} $ （因为是无权图）。则有：

     $ \text{sim}_{i,j} = \frac{\sum_{l=1}^na_{i,l}\times a_{j,l}}{\sqrt{d_{u_i}\times d_{u_j}}} $

     用户 $ u_i $ 在object $ o_l $ 上预测的得分为：

     $ p_{i,l} = \sum_{j=1,j\ne i}^m s_{i,j}\times a_{j,l}\\ s_{i,j} = \frac{\text{sim}_{i,j}}{\sum_{j^\prime=1,j^\prime\ne i}^m \text{sim}_{i,j^\prime}} $

     有两个因素会影响 $ p_{i,l} $ ：

     • 如果 $ o_l $ 的 degree 很大，即非零的 $ a_{j,l } $ 越多，则 $ p_{i,l} $ 累加的项越多，结果越大。
     • 如果 $ o_l $ 被更多的、与 $ u_i $ 相似的用户喜欢，则对应的权重 $ s_{i,j} $ 越大，则 $ p_{i,l} $ 越大。

     前者重视全局信息（对象 $ o_l $ 的度，对每个用户都是无差别的）、后者重视个性化信息（每个用户都不同）。

     对于任意用户 $ u_i $ ，我们将所有非零 $ p_{i,l} $ 且 $ a_{i,l} = 0 $ （ $ a_{i,l} = 0 $ 表示用户尚未收藏的）的对象根据 $ p_{i,l} $ 降序排列，然后推荐其中的 top K 对象。

3. 这里我们基于加权投影图提出了一种推荐算法，该算法是对二部图的加权方法的直接应用。

   • 首先对二部图进行 object 映射，得到的加权图定义为 $ G_{\mathcal O} $ 。

   • 然后给定用户 $ u_i $ ，我们获取用户已经收藏的object 集合为 $ \mathbb O_{u_i} $ ，并在该集合的每个object 上放置一些资源。

     为简单起见，我们在 $ G_{\mathcal O} $ 的每个顶点上初始化资源为：

     $ f(o_l) = a_{i,l} $

     即：如果 $ u_i $ 喜欢 $ o_j $ ，则它初始化资源为单位1；否则初始化资源为 0 。

     注意：对于不同用户， $ G_{\mathcal O} $ 的初始化配置是不同的，这是个性化的初始化。

   • 最终我们得到 $ G_{\mathcal O} $ 中顶点的资源为：

     $ \mathbf{\vec f}^\prime = \mathbf W\mathbf{\vec f} $

     因此有：

     $ f^\prime(o_l) = \sum_{k=1}^n w_{l,k}f(o_k) =\sum_{k=1}^n w_{l,k}\times a_{i,k} $

     其中 $ w_{l,k} $ 表示 $ o_k $ 的资源分配到 $ o_l $ 的比例。

     对于每个用户 $ u_i $ ，我们将所有非零资源 $ f^\prime(o_l) $ 、且 $ a_{i,l} = 0 $ （ $ a_{i,l} = 0 $ 表示用户尚未收藏）的对象按照资源 $ f^\prime(o_l) $ 降序排列，然后推荐其中的 top K 对象。

   由于不同用户的初始化配置不同，因此该分配方程需要重复执行 $ m $ 次。写成矩阵的形式为：

   $ \mathbf F^\prime = \mathbf W \mathbf A^\top\in \mathbb R^{n\times m} $

   其中 $ \mathbf F^\prime $ 第 $ i $ 列为用户 $ u_i $ 在各 object 上的最终分配资源。

   这种方法我们称作基于网络的推断 NetworkBased Inference: NBI，因为它是基于加权映射网络 $ G_{\mathcal O} $ 的。

   该方法是标签传播算法的推广，有两个区别：该方法仅传播两次，相比之下标签传播算法不停传播直到收敛；该方法除了邻接矩阵还有权重矩阵，相比之下标签传播算法仅使用邻接矩阵。

4. NBI 方法仅仅考虑用户喜欢的商品，而完全不考虑用户不喜欢的商品，这可能会丢失一些信息。NBI 方法的一个重要优点是：它不依赖于任何控制参数，因此不需要调参。

   另外，这里提出的 NBI 推荐算法只是一个粗糙的框架，很多细节尚未详细的探索。例如，顶点的初始配置可以采取更复杂的形式：

   $ f(o_l) = a_{i,l}\times d_{o_l}^\beta $

   即它给不同degree 的顶点 $ o_l $ 分配不同的资源，这可能会比原始的分配产生更好的推荐效果。

   也可以考虑动态的资源分配过程，这会导致类似于标签传播算法的迭代式推荐算法。虽然这样的算法需要更长的 CPU 时间，但是可以提供更准确的预测。

5. 定义 $ \bar d_u $ 为用户的平均degree， $ \bar d_o $ 为object 的平均 degree，则有：

   • MemoryBased CF 的平均计算复杂度为： $ O(m^2\bar d_u + mn\bar d_o) $ 。

     • 第一项来自于用户之间的相似度计算： $ m\times m $ 对用户、每对用户平均 $ \bar d_u $ 个object。
     • 第二项来自于预测得分：每个用户平均需要使用 $ \bar d_o $ 个相似用户（必须在目标object 上有收藏行为）根据相似度（计算复杂度为 $ n $ ）的加权和，一共 $ m $ 个用户。

     假设 $ n\bar d_o = m\bar d_u $ （它就是二部图中边的数量），则整体计算复杂度为 $ O(m^2 \bar d_u) $ 。

   • NBI 的计算复杂度为： $ O(m\bar d_{u^2} + mn\bar d_u) $ ，其中 $ \bar d_{u^2} $ 为用户 degree 分布的二阶矩（二阶矩为随机变量平方的期望）。第一项为权重矩阵的计算，第二项为最终资源分布的计算。很明显有 $ \bar d_{u^2} \lt n\bar d_u $ ，因此计算复杂度为 $ O(mn\bar d_u) $ 。

   在很多推荐系统中，用户数通常比object 数大得多，因此 NBI 运行速度比 MemoryBased CF 快得多。另外 NBI 存储权重矩阵需要 $ O(n^2) $ 的空间，而 MemoryBased CF 存储相似度矩阵需要 $ O(m^2) $ 的空间。因此 NBI 能够在准确性、时间复杂度、空间复杂度上超越 MemoryBased CF 。

但是在某些推荐系统中（如书签共享网络），object 数（书签数量）远远大于用户数量，因此 MemoryBased CF 可能更加适用。

6.2 实验

1. 数据集：Movielens 数据集，包含 1682 部电影和 943 个用户，通过评分构成了带权二部图。评分从1 到 5 分同五个等级。

   我们预处理数据集：如果评分大于等于3 分，我们认为用户喜欢该电影。原始数据集包含 $ 10^5 $ 个评分，有 85.25% 的评分大于等于3 分，因此我们预处理后的无权二部图包含 85250 条无权边。

   注意：这种预处理方式仅保留用户评分较高的边，会丢失大量信息。

   我们将所有的边拆分为训练集和测试集，其中训练集包含 90% 的边、测试集包含 10% 的边。注意：训练集和测试集都包含全部的顶点。

2. 评估方式：对于任意一个用户 $ u_i $ ：

   • 我们首先获取他/她尚未收藏的电影集合 $ \mathbb P_{u_i} = \mathbb O - \mathbb O_{u_i} $ ，然后根据 NBI 计算到的资源对这些电影降序排列。

   • 然后对于测试集中的每条边 $ (u_i,o_l) $ ，我们评估 $ o_l $ 位于有序的、未收藏列表中的位置。

     如：假设 $ u_i $ 有 1500 个未收藏的电影，假设测试集存在边 $ (u_i,o_l) $ 且电影 $ o_l $ 在 $ \mathbb P_{u_i} $ 中的排名是第 30 名（从1 开始计数），则我们说 $ o_l $ 的位置为 top 30/1500，记作：

     $ r_{i,l} = \frac{30}{1500} = 0.02 $

     由于测试集中的边实际上都是用户收藏的，因此一个好的算法应该产生一个很小的 $ r $ 值。

   我们在预处理的 MovieLens 数据集上比较了 GRM、CF（即 MemoryBasedCF）、NBI 算法，

   所有测试样本的 $ r $ 结果的平均值为：GRM = 0.139, CF =0.120, NBI=0.106 。可以看到 NBI 是其中表现最好的。

3. 假设用户 $ u_i $ 的推荐列表长度为 $ L $ ，它给出了算法得到的 top L 个未收藏的电影。对于测试集中的每条边 $ (u_i,o_l) $ ，如果 $ o_l $ 在该列表中，则我们就说算法命中了。

   定义命中的测试样本占所有测试样本的比例为命中率。对于给定的 $ L $ ，命中率越高越好。如果 $ L $ 大于用户所有未收藏的电影数，则推荐列表就是这些全量未收藏的电影。显然，命中率随着 $ L $ 的增加单调增加，上限为 1 。下图给出了不同算法的命中率：

   

   一些典型长度的命中率如下表：

   

   可以看到：命中率表现为 NBI > CF > GRM。因此实验表明 NBI 的性能显著优于 GRM 和 CF，有力地证明了我们方法的有效性。