给定一个网络G(U, O, E)，其中U和O分别表示两种不同类型的节点集合，E表示U与O之间的连边的集合，当边只存在于不同类型的节点之间时，这种网络被称为二分网络。现实生活中存在很多二分网络的例子，如作者与论文之间的发表关系、用户与商品之间的购买关系等都属于二分网络。假设图 1表示的是用户与商品之间的购买关系，如果要对某个用户推荐商品，最容易想到的一种办法就是先看一下该用户曾经购买过什么商品，然后给他推荐与其购买过的商品最相似的物品，由于二分网络只记录了用户与商品之间的关系，而没有记录商品与商品之间的相似关系，因此需要对用户与商品之间的关系进行投影，从而得到商品与商品之间的相似关系。最简单的一种投影方式就是判断两件不同的商品是否有被同一用户购买，如果存在共同的购买者，则说明这两件商品之间存在一定的相似度，在对应的投影网络中这两件商品之间便产生一条连边。例如，对图中所示的二分网络进行投影后便得到商品相似关系网络，如果投影网络中两个商品之间存在连边，则说明这两个商品是相似的。接下来就可以利用商品相似关系网络对用户进行商品推荐。例如，由图 1得知用户u₁购买了商品o₁和o₂，又根据投影网络可知商品o₄同商品o₁、o₂都相似，因此可以把商品o₄推荐给用户u₁。

图  1  二分网络及其投影

前面的投影方法得到的投影网络是一个无权网络，该网络只反映了两用户之间是否存在相似性，却无法刻画相似程度的大小。基于此，文献[16]提出了一个物质扩散算法来改进这种投影存在的缺陷。其方法描述如下：在二分网络中选择一个商品节点β，在该节点上放置1个单位的资源，该资源先从β节点以均分的方式扩散到与其相连的用户节点，然后再以同样的方式从用户节点扩散到商品节点，此时商品节点上资源的数量就代表了其与β节点的相似程度。如图 2所示，如果最初在物品节点o₁上放置1单位的资源，经过两步扩散后，o₁, o₂, o₃, o₄上的资源分别是5/12, 5/12, 0, 1/6。

图  2  二分网络中的物质扩散过程示意图

该扩散过程的资源分配方式可以表示为：

式中， ${{k_\beta }}$ 表示购买了商品 $\beta $ 的用户数； ${{k_i}}$ 表示用户i购买过的商品种数；用矩阵A记录用户与商品之间的购买关系，其元素 ${{k_i}}$ 表示用户i是否购买了商品 $\alpha $ ，如果购买了其值为1，否则其值为0； ${w_{\alpha \beta }}$ 为从 $\beta $ 扩散到 $\alpha $ 的资源数量，表示购买了 $\beta $ 的用户还会购买 $\alpha $ 的概率，值得注意的是${w_{\alpha \beta }} \ne {w_{\beta \alpha }}$，也就是说两个商品之间相互推荐的权重是不一样的。

利用该方法可以计算出任意两个商品之间的相似性，并由此生成一个有向含权投影网络，与该网络对应的是一个扩散转移矩阵W，W中的每一个元素 ${w_{\alpha \beta }}$ 表示资源从β节点扩散到α节点的数量，代表购买了商品β的用户还会购买商品α的概率。将这种方法对图 2所示的二分网络进行投影后，得到图 3所示的有向含权投影网络，该投影网络对应的转移矩阵W为：

图  3  基于物质扩散方法得到的投影网络

如果用向量 ${\mathit{\boldsymbol{f}}_i} = {[{f_{i1}}, {f_{i2}}, \cdots, {f_{in}}]^{\rm{T}}}$ 表示用户i的购买历史，其中${f_{i\alpha }}{\rm{ = }}1$表示用户i购买了商品α，${f_{i\alpha }}{\rm{ = }}0$表示其没购买该商品，可以计算用户购买其他商品的相对概率：

例如，对于图 2所示的二分网络来说，已知用户u₁购买了商品o₁和o₂，则有：

由于用户1已经购买了商品1和商品2，所以不必再推荐这两个商品，因此只要对其它商品按得分降序排列就可以得到推荐列表，这个计算过程反映在投影网络中其实就是资源做一步扩散的过程。对于用户1来说，在图 3中将节点1和节点2分别放置1单位的资源，这些资源根据边的权重和方向进行扩散，扩散一步之后每个节点获得的总资源数就对应着用户1将会购买该商品的相对概率。二分网络中物质扩散推荐算法的步骤。

输入：用户-物品购买关系数据集。

步骤1)：由输入的数据集生成购买关系矩阵A，其元素a_iα的值表示用户i是否购买过物品α。

步骤2)：由矩阵A统计出每个用户购买过的物品数以及每种物品被多少个用户购买过。

步骤3)：由式(1)计算出任意两个物品之间的相似度w，得到扩散转移矩阵W。

步骤4)：利用式(3)计算用户购买每件物品的相对概率。

步骤5)：根据步骤4)中的计算结果对物品进行降序排列，并去除用户已经购买过的物品。

输出：每个用户的物品推荐列表。

物质扩散投影方法克服了简单投影方法的两个缺点：1)该方法考虑了商品之间连边的权重，两个商品拥有的共同用户越多，其相似性就越大；2)从式(1)可以看出，如果 ${k_\alpha } > {k_\beta }$ ，则${w_{\alpha \beta }} > {w_{\beta \alpha }}$，这说明购买了冷门商品的用户再购买热门商品的概率要大于购买了热门商品再购买冷门商品的概率，这一点也是与实际情况一致的。正因如此，物质扩散算法与很多传统算法相比具有明显的优势。

从前面的分析可知，利用物质在二分网络中的两步扩散过程可以实现商品的推荐，既然二分网络中的两步扩散可以用于商品推荐，自然可以把该过程拓展到4步、8步、…、直至2N步扩散，又由于二分网络中的两步扩散等价于其投影网络中的一步扩散，所以二分网络中的2N步扩散就等效于其投影网络中的N步扩散(为方便起见，后面的讨论提到的扩散都只针对投影网络)。本文着重关注的问题是随着扩散步数的增加，网络中的资源分布最终会达到什么状态？而对应的推荐算法有具有什么特点？用向量 $\mathit{\boldsymbol{f}}_i^0$ 表示用户i对所有商品节点配置初始资源的情况(如果用户i购买了某商品α， $f_{i\alpha }^0 = 1$ ，否则 $f_{i\alpha }^0 = 0$ )，经N步扩散后，各商品节点上的资源便为 $\mathit{\boldsymbol{f}}_i^N$ ，显然， $\mathit{\boldsymbol{f}}_i^N = \mathit{\boldsymbol{Wf}}_i^{N - 1} = {\mathit{\boldsymbol{W}}^2}\mathit{\boldsymbol{f}}_i^{N - 2} = \cdots = {\mathit{\boldsymbol{W}}^N}\mathit{\boldsymbol{f}}_i^0$ ，要回答前面的问题就必须对 $\mathit{\boldsymbol{f}}_i^N$ 的特点进行研究，如果多步扩散之后资源的分布会稳定下来，就意味着当 $N \to \infty $ 时 ${\mathit{\boldsymbol{f}}^N}$ 收敛。假设 ${\mathit{\boldsymbol{f}}^N}$ 收敛，不妨令 $\mathop {\lim }\limits_{N \to \infty } {\mathit{\boldsymbol{f}}^N} = {\mathit{\boldsymbol{f}}^*}$ ，则有 ${\mathit{\boldsymbol{f}}^*} = \mathit{\boldsymbol{W}}{\mathit{\boldsymbol{f}}^*}$ ，因此 ${\mathit{\boldsymbol{f}}^*}$ 便为矩阵 $\mathit{\boldsymbol{W}}$ 的特征值1对应的特征向量。又由于 ${\mathit{\boldsymbol{f}}^N} = {\mathit{\boldsymbol{W}}^N}{\mathit{\boldsymbol{f}}^0}$ ，所以只有当 ${\mathit{\boldsymbol{W}}^N}$ 收敛时 ${\mathit{\boldsymbol{f}}^N}$ 才会收敛，因此 ${\mathit{\boldsymbol{f}}^N}$ 是否收敛便成为关键问题，本文接下来利用矩阵分析的方法对 $\mathit{\boldsymbol{W}}$ 的性质进行分析，从而揭示多步物质扩散推荐算法的特点。

性质1：矩阵 $\mathit{\boldsymbol{W}}$ 每一列元素之和为1，即 $\sum\limits_{\alpha = 1}^n {{w_{\alpha \beta }}} = 1$ 。

证明：从物质扩散的过程可知，每一步扩散都遵守物质守恒定律，系统中物质的总量没有因为扩散过程发生变化，从任何一个商品节点出发的资源经过两步扩散后又都回到了商品端(所有商品节点构成的集合)，反映在扩散转移矩阵上就是每一列元素之和为1。该性质也可以由式(1)出发进行证明：

性质2：若矩阵W不可约(对应的投影网络是强连通的)，则W的主特征值 ${\lambda _1} = 1$ ，且有 $1 = \left| {{\lambda _1}} \right| > \left| {{\lambda _2}} \right| \ge \left| {{\lambda _3}} \right| \ge \cdot \cdot \cdot \ge \left| {{\lambda _n}} \right|$ 。

证明：由于W与 ${\mathit{\boldsymbol{W}}^T}$ 的特征值相同，所以只要证明 ${\mathit{\boldsymbol{W}}^T}$ 满足性质2即可。由Gerschgorin圆盘定理可知，对于矩阵 ${\mathit{\boldsymbol{W}}^T}$ ，一定存在某行元素 $({w_{\alpha 1}}, {w_{\alpha 2}}, \cdot \cdot \cdot, {w_{\alpha n}})$ ，使得 $\left| {\lambda - {w_{\alpha \alpha }}} \right| \le \sum\limits_{\beta = 1, \beta \ne \alpha }^n {\left| {{w_{\alpha \beta }}} \right|} $ ，又由于 $\left| \lambda \right| - \left| {{w_{\alpha \alpha }}} \right| \le \left| {\lambda - {w_{\alpha \alpha }}} \right|$ ，所以 $\left| \lambda \right| - \left| {{w_{\alpha \alpha }}} \right| \le \sum\limits_{\beta = 1, \beta \ne \alpha }^n {\left| {{w_{\alpha \beta }}} \right|} $ ，因此 $\left| \lambda \right| \le \sum\limits_{\beta = 1, \beta \ne \alpha }^n {\left| {{w_{\alpha \beta }}} \right|} + \left| {{w_{\alpha \alpha }}} \right| = \sum\limits_{\beta = 1}^n {\left| {{w_{\alpha \beta }}} \right|} = 1$ 成立。

根据性质1，W的每一列之和为1，所以 ${\mathit{\boldsymbol{W}}^T}$ 的每一行之和为1，因此 $(1, 1, \cdot \cdot \cdot, 1)_{1 \times n}^{\rm{T}}$ 为 ${\mathit{\boldsymbol{W}}^T}$ 的特征值1对应的右特征向量，因此，1是 ${\mathit{\boldsymbol{W}}^T}$ 的最大特征值，即主特征值。由Perron-Frobenius定理可知，对于一个不可约非负矩阵，其谱半径对应的主特征值一定是大于0的单重特征值，因此 ${\lambda _1} = 1$ 是 ${\mathit{\boldsymbol{W}}^T}$ 的单重特征值，所以 $1 = \left| {{\lambda _1}} \right| > \left| {{\lambda _2}} \right| \ge \left| {{\lambda _3}} \right| \ge \cdot \cdot \cdot \ge \left| {{\lambda _n}} \right|$ 成立，证毕。

性质3： ${(k({o_1}), k({o_2}), \cdot \cdot \cdot, k({o_n}))^{\rm{T}}}$ 是矩阵W的主特征值1对应的右特征向量。

证明：设 ${\mathit{\boldsymbol{A}}_{m \times n}}$ 为二分网络对应的邻接矩阵，m为用户数，n为商品数，其任意元素 ${a_{i\alpha }}$ 的值为1或0，表示用户i是否购买过商品α。

令 $\mathit{\boldsymbol{U}} = {\rm{diag}}\left\{ {k({u_1}), k({u_2}), \cdot \cdot \cdot, k({u_m})} \right\}$ ， $\mathit{\boldsymbol{O}} = {\rm{diag}}\left\{ {k({o_1}), k({o_2}), \cdot \cdot \cdot, k({o_n})} \right\}$ ，其中 $k(u)$ 和 $k(o)$ 分别为二分网络中用户节点和商品节点对应的度，则投影网络对应的矩阵W为：

于是有：

因此，性质3成立。

性质4：当 $N \to \infty $ 时，矩阵 ${\mathit{\boldsymbol{W}}^N}$ 收敛，且 ${\mathit{\boldsymbol{W}}^N}$ 中任意元素 ${w_{\alpha \beta }}$ 的值为 ${{{k}_{\alpha }}}/{\sum\limits_{\alpha =1}^{n}{{{k}_{\alpha }}}}\; $ 。

证明：根据Jordan标准型定理，对任意矩阵W，一定存在矩阵J，使得 $\mathit{\boldsymbol{W}} = \mathit{\boldsymbol{PJ}}{\mathit{\boldsymbol{P}}^{ - 1}}$ ，其中J为矩阵W的Jordan标准型，根据Jordan标准型定义，J满足式(5)所示的分块对角矩阵形式，矩阵J的每一项元素 ${\mathit{\boldsymbol{J}}_i}$ 都是一个Jordan块， ${\mathit{\boldsymbol{J}}_i}$ 的形式如式(6)所示，其中 ${\lambda _i}$ 为矩阵W的第i大特征值，根据性质2， ${\lambda _i} = 1$ 为W的单重主特征值，所以 ${\mathit{\boldsymbol{J}}_1} = 1$ 。

由于当 $i \ge 2$ 时， ${\lambda _i} < 1$ ，所以有 $\mathop {\lim }\limits_{N \to \infty } J_i^N = 0$ ，于是：

因此：

设向量p为矩阵P的第一列， ${\mathit{\boldsymbol{p}}^ * }$ 为 ${\mathit{\boldsymbol{P}}^{ - 1}}$ 的第一行，则上式便化为：

对 $\mathit{\boldsymbol{W}} = \mathit{\boldsymbol{PJ}}{\mathit{\boldsymbol{P}}^{ - 1}}$ 两边同时右乘P，得到 $\mathit{\boldsymbol{WP}} = \mathit{\boldsymbol{PJ}}$ ，由式(7)所示的对角形式可知， $\mathit{\boldsymbol{p}}$ 其实就是 $\mathit{\boldsymbol{PJ}}$ 的第一列，又由于 $\mathit{\boldsymbol{WP}}$ 的第一列为 $\mathit{\boldsymbol{Wp}}$ ，所以有 $\mathit{\boldsymbol{Wp}} = \mathit{\boldsymbol{p}}$ ，因此， $\mathit{\boldsymbol{p}}$ 为矩阵W的右主特征向量，根据性质3， $\mathit{\boldsymbol{p}} = {\varepsilon _1}{[k({o_1}), k({o_2}), \cdots \mathit{\boldsymbol{, }}k({o_\mathit{\boldsymbol{n}}})]^{\rm{T}}}$ ， ${\varepsilon _1}$ 为任意常数。同理，对 $\mathit{\boldsymbol{W}} = \mathit{\boldsymbol{PJ}}{\mathit{\boldsymbol{P}}^{ - 1}}$ 两边同时左乘 ${\mathit{\boldsymbol{P}}^{ - 1}}$ ，得到 ${\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{W}} = \mathit{\boldsymbol{J}}{\mathit{\boldsymbol{P}}^{ - 1}}$ ，显然， $\mathit{\boldsymbol{J}}{\mathit{\boldsymbol{P}}^{ - 1}}$ 的第一行为 ${\mathit{\boldsymbol{p}}^ * }$ ，又由于 ${\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{W}}$ 的第一行为 ${\mathit{\boldsymbol{p}}^ * }\mathit{\boldsymbol{W}}$ ，所以 ${\mathit{\boldsymbol{p}}^ * }\mathit{\boldsymbol{W = }}{\mathit{\boldsymbol{p}}^ * }$ 。因此， ${\mathit{\boldsymbol{p}}^ * }$ 为W的左主特征向量，又由于W每一列元素之和为1，所以 ${\mathit{\boldsymbol{p}}^{\bf{*}}} = {\varepsilon _2}{[1, 1, \cdots, 1]_{1 \times n}}$ ， ${\mathit{\boldsymbol{p}}^{\bf{*}}} = {\varepsilon _2}{[1, 1, \cdots, 1]_{1 \times n}}$ 也为任意常数。 $\mathit{\boldsymbol{Q}}{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{P}} = \mathit{\boldsymbol{I}}$ ， $\mathit{\boldsymbol{Q}}{\mathit{\boldsymbol{p}}^{\bf{*}}}\mathit{\boldsymbol{p}} = 1$ ，即：

令 $\varepsilon = {\varepsilon _1}{\varepsilon _2}$ ，则 $\varepsilon = \frac{1}{{\sum\limits_{\alpha = 1}^n {k({o_\alpha })} }}$ 。

若 $\mathit{\boldsymbol{p}} = {[k{\rm{(}}{o_{\rm{1}}}{\rm{), }}k{\rm{(}}{o_{\rm{2}}}{\rm{), }} \cdots {\rm{, }}k{\rm{(}}{o_n}{\rm{)}}]^{\rm{T}}}$ ，则 ${\mathit{\boldsymbol{p}}^ * } = {[\varepsilon, \varepsilon, \cdots, \varepsilon ]_{1 \times n}}$ 。

因此，根据式(9)可以计算得到收敛结果：

证毕。

下面用一个实例对这个结论进行验证，以图 2所示的用户-商品二分网络为例，其对应的扩散转移矩阵如式(2)所示，下面给出扩散转移矩阵各次幂运算的计算过程：

从上述计算过程可以看出，矩阵W在经过多次幂运算之后最终收敛到了一个稳定状态，该结果与用式(11)计算的结果一致，计算过程为：

在前面的验证过程中，系统总共迭代了21步才使收敛结果精确到小数点后第四位。由此可以提出另一个重要问题——系统的收敛速度由什么因素决定？该问题需要进一步分析收敛速度与扩散转移矩阵之间的关系。由于 ${\mathit{\boldsymbol{W}}^N} = \mathit{\boldsymbol{P}}{\mathit{\boldsymbol{J}}^N}{\mathit{\boldsymbol{P}}^{ - 1}}$ ，而 $\mathit{\boldsymbol{P}}$ 和 ${\mathit{\boldsymbol{P}}^{ - 1}}$ 与迭代步数无关，因此 ${\mathit{\boldsymbol{W}}^N}$ 的收敛速度只由 $J$ 决定，只有当 $J$ 能快速收敛到式(8)所示的形式，系统才能快速达到稳定状态，由式(7)可知，要使 $J$ 快速收敛到式(8)，就得使 ${J_i}^N\left({i \ge 2} \right)$ 尽快收敛至0，又由 $1 = \left| {{\lambda _1}} \right| > \left| {{\lambda _2}} \right| \ge \left| {{\lambda _3}} \right| \ge \cdot \cdot \cdot \ge \left| {{\lambda _n}} \right|$ 及式(6)可知，当 ${\lambda _2}$ 的值越接近0时系统收敛越快，因此多步扩散算法的收敛速度由扩散转移矩阵的第二大特征值决定，该特征值越小，系统收敛越快。

根据上一节的分析，已经证明了 $N \to \infty $ 时 ${\mathit{\boldsymbol{W}}^N}$ 会收敛于一个稳定状态，又根据 ${\mathit{\boldsymbol{f}}^N} = {\mathit{\boldsymbol{W}}^N}{\mathit{\boldsymbol{f}}^0}$ ，可推断 ${\mathit{\boldsymbol{f}}^N}$ 最终也会达到一个稳定状态，这意味着在经过多轮扩散之后，资源的分布最终会稳定下来，对于推荐算法来说，最终的推荐列表会稳定下来，而不再随扩散次数的增加而变化。显然，这个稳定的推荐列表具有什么样的特点便成为我们最关心的问题。假设对于某个用户i，给其购买过的商品节点分别设置1单位的资源，则资源分布情况可以用向量 $\mathit{\boldsymbol{f}}_i^0 = {[{a_{i1}}, {a_{i2}}, \cdot \cdot \cdot, {a_{in}}]^{\rm{T}}}$ 表示，元素a的值为1或0，分别代表该用户是否购买过该相应的商品。假设用户i总共购买了 ${k_i}$ 件物品，则：

根据物质扩散推荐算法，在进行N步扩散之后其资源分布为 $\mathit{\boldsymbol{f}}_i^N = {\mathit{\boldsymbol{W}}^N}\mathit{\boldsymbol{f}}_i^0$ ，当 $N \to \infty $ 时，其值为：

式(14)给出了最终的资源分布结果，从式中可以看出，在经过多轮扩散之后，资源在各商品节点上的分布比例完全由该节点的度决定，由于推荐列表是根据各节点最终获得的资源数从大到小进行排列，所以推荐算法最终将会根据商品节点的度从大到小生成推荐列表。进一步分析可以发现，该推荐列表的排序不仅与扩散前初始资源的分布无关，而且与用户也无关，不论是对哪个用户，不管他之前购买过什么样的商品，该算法始终只根据商品的热门程度给出推荐列表，此时的算法已经不会再根据用户之前的购买历史来推荐与其偏好相似的商品，而是不论针对什么用户一律只推荐热门商品，因此，此时的推荐系统表现得更像一个搜索引擎，不再具有个性化特点。事实上，算法逐渐失去个性化的过程是伴随着扩散步数的增加而发生的，当扩散步数为0时， $\mathit{\boldsymbol{f}} = {\mathit{\boldsymbol{f}}^{\rm{0}}}$ ，此时，算法推荐的是用户购买过的商品，虽然没什么意义，但从个性化角度来看肯定是最好的，随着扩散步数的增加，算法的个性化特点不断失去，最终只推荐热门商品。在实际应用中，可以根据个性化要求的程度选择合适的扩散步数。

本文通过对物质扩散推荐算法中的扩散转移矩阵 ${\mathit{\boldsymbol{W}}}$ 的几个重要性质的研究，深入分析了多步物质扩散推荐算法的逼近行为，证明了 ${\mathit{\boldsymbol{W}}}$ 的主特征值为1，并发现其对应的主特征向量与二分网络中物品节点的度相关，证明了当扩散步数趋于无穷时，转移矩阵 ${\mathit{\boldsymbol{W}}^N}$ 会收敛，并且发现算法随着扩散步数增加不断失去个性化，最终当扩散达到稳定状态时，算法的推荐结果只与商品的热门程度有关。本文的研究揭示了物质扩散算法的扩散步数与个性化特点之间的关系，对物质扩散算法的实际应用具有一定的指导意义。