基于聚类的超链路预测

齐鹏飞，周丽华，杜国王，黄 皓，黄 通

（云南大学信息学院，昆明650091）

0 引言

现实世界中许多复杂的交互系统都可以自然地被描述为信息网络［1］，比如社会网络、协作网络、引文网络、生物神经网络和蛋白质相互作用网络。链路预测能够利用网络中已经观测到的网络结构或者节点的属性信息来复现网络中缺失的链路，受到了来自生物学、信息学等多学科学者的关注，成为横跨多个学科的核心科学问题［2］。

传统链路预测是对两个节点之间是否存在链接进行预测。但是在现实网络中，链接关系可能存在于多个节点之间，比如DBLP网络中论文的发表包含了作者-论文-期刊/会议等不同类型节点之间的关系［3］。为了便于描述多个节点之间的复杂关系，Zhang 等［4］提出了超链路概念：即一组包含有任意数量的同种或不同类型的节点，这些节点在一起形成一个多路径关系。超链路不再局限于只有两个节点组成链路的限制，允许任意数量的同型或不同类型的节点共同形成超链路，保留了网络中丰富多元的信息。

现有超链路预测算法大多是基于所有超链路观察样本的相似性来进行预测，若某一类超链路样本数量较多或者某类超链路中节点之间的联系较其他类节点之间的关系更加密切，掩盖了其他类超链路的信息，那么训练样本数目较少的超链路可能预测不出来，导致预测结果覆盖面不全。比如在图1 中相同线型的线连接的节点组成一条超链路，实线代表预测出来的超链路。原始网络中B-A-E 和G-H 这两条超链路是缺失的。图1（a）是对整个网络使用超链路预测算法CMM（Coordinated Matrix Minimization）［4］的预测结果，仅仅预测出超链路B-A-E，而超链路G-H 没有被预测出来；图1（b）先对整个网络的超链路进行聚类，得到簇1、簇2，然后分别基于簇1 和簇2 进行预测，从图1（b）中可以看出，超链路B-A-E 和超链路G-H均被预测出来了。

本文提出的基于聚类的超链路预测算法C-CMM（Clusterd-based CMM）首先将观察到的超链路聚类成簇，然后对每个簇分别建立超链路预测模型，这样每个簇中所蕴含的信息能够得到充分利用，保证预测结果覆盖所有类别，能克服预测结果种类不全的缺陷；此外，经过聚类处理后，每个簇包含的超链路数目远远小于整个网络中所包含超链路数目，预测时间将大幅度缩减。

图1 超链路预测Fig.1 Hyperlink prediction

本文主要工作如下：

1）提出了对超链路进行基于非负矩阵分解（Nonnegative Matrix Factorization，NMF）的聚类算法。该算法基于非负矩阵分解学习超链路的表达，然后对超链路进行聚类得到不同的簇，使簇内的超链路尽可能相似，不同簇间的超链路尽可能相异。

2）提出了基于聚类的超链路预测算法C-CMM。C-CMM对聚类获得的每个簇分别建立超链路预测模型，从而充分利用各个簇的观察样本所蕴含的信息，保证预测结果覆盖所有类别，克服预测结果可能种类单一的不足。

3）使用三个真实数据集对所提算法进行了实验验证，从预测的准确性、预测结果覆盖种类的全面性和算法的执行效率三个方面考察了基于聚类的超链路预测算法的效果和效率，并与其他超链路预测算法的结果进行了比较，结果表明C-CMM算法具有较好的性能。

1 相关工作

1.1 链路预测算法

链路预测［5］是数据挖掘领域的一个研究方向，在网络研究领域已经有多年的研究历史［6-9］。早期的研究主要使用马尔可夫链和机器学习的方法来对链路预测进行研究，近年来研究者主要基于网络拓扑结构进行预测。根据网络拓扑结构的链路预测方法可以分为基于相似性的链路预测、基于似然分析的链路预测和基于元路径的链路预测［10］等。其中基于相似性的链路预测方法中最具代表性的指标是CN（Common Neighbors）［5］指标，即节点之间拥有越多的共同节点则越容易形 成 链 路。Katz［11］提 出 的Katz 指 标 结 合 了CN 指 标 和LP（Local Path）［2］指标，考虑了节点对之间所有的链路，对短路径赋予较小的权重，而长路径则相反。近年来许多研究者尝试基于表达学习进行链路预测［12-16］，这些方法从网络结构或/和节点属性学习每个节点的向量表示，然后实现链路预测。由于学到的节点向量表示揭示了节点非线性的隐特征，因此基于表达学习的链路预测的性能得到了极大提高。

1.2 超链路预测

超链路预测通过给定一个不完整的网络和一个潜在超链路的候选集，来找到候选集中所有最有可能是网络中缺失的超链路或者网络将会形成的超链路［4］。Xu 等［17］提出了一个使用熵评分为特征的监督HPLSF（Hyperlink Prediction using Latent Social Features）框架来预测社交网络中的超链路；Neville 等［18］利用潜在的社会特征来预测网络中超链路的存在；Chen 等［6］提出了利用超链路正则化的半监督超图顶点分类算法，利用节点的超链路关系来提高节点的学习性能；Zhang 等［4］提出了CMM 算法，在网络的顶点邻接空间中交替执行非负矩阵分解和最小二乘匹配，以推断最适合整个观测到的网络的超链路。目前关于超链路预测的研究成果还不多，研究空间还很大。

2 基于聚类的超链路预测算法C-CMM

2.1 超链路聚类

信息网络中存在大量的超链路，且节点数目可变。直接采用传统聚类算法在处理数据量小、维度低的数据时，通常能取得较好的效果，但随着数据量增大、维度升高，聚类性能将逐渐下降。如K-means 聚类算法在低维数据上聚类效果较好，但是受“维度灾难”的影响，在高维数据上不能取得较好的聚类效果。非负矩阵分解（NMF）［19］是一种有效的降维方式，能够获得高维数据样本的低维特征，使用传统的聚类算法对低维表征进行聚类，可以获得更好的效果。

非负矩阵分解算法为关联矩阵S 找到合适的非负基矩阵Wm×k∈ℜ+和非负系数矩阵H k×n ∈ℜ+，使得它们的乘积近似于原始关联矩阵S，即：

其中：k ≪min(m，n)，W 的列向量可以表示为对S 中所有超链路的加权和，而系数矩阵H 可以看作是关联矩阵S 的低维表达。H的第l列表示第l条超链路在W的矢量构成的空间中投影的特征表达。基于该特征表达，通过传统的聚类算法（比如K-means）对矩阵H 进行聚类，可以将n 条超链路聚集成簇。为了找到S ≈WH的近似分解，NMF最小化如下目标函数：

s.t.W ≥0，H ≥0

其中，‖ · ‖F表示矩阵的F 范数。对于式（2）的优化，本文采用乘子更新法进行迭代更新，H 和W 更新规则如式（3）和（4）所示。

获得H 后，可以使用聚类算法完成聚类。聚类算法可以使 用K-means、DBSCAN（Density-Based Spatial Clustering of Applications with Noise）等算法。H 中的每一列对应超链路的低维表达，对这些低维表达的聚类就相当于对超链路的聚类。基于非负矩阵分解的聚类算法如算法1所示。

算法1 超链路聚类（Hyperlink Cluster，HC）。

输入 超链路关联矩阵S，簇个数k，误差阈值ε；

输出 k个簇S1，S2，…，Sk。

1）初始化W，H

2）Repeat

3） 固定W，通过式（3）更新H

4） 固定H，通过式（4）更新W

5）Until||S-WH||2＜ε

6）使用K-means算法对H聚类得到S1，S2，…，Sk

比如，图1（a）所示待预测的信息网络的关联矩阵如下所示，其中行代表了A 到H 这8 个节点，每一列分别代表e1～e6这6条超链路。

对上述关联矩阵S进行非负矩阵分解得到H如下：

使用K-means 算法对矩阵H 进行聚类，得到两个簇：e1、e2、e3、e4为一个簇，e5、e6为一个簇。

2.2 C-CMM超链路预测算法

CMM 算法［4］是一种优秀的超链路预测方法，它在网路的邻接空间中交替执行非负矩阵分解和最小二乘匹配，以推断与观测到的超链路最吻合的超链路。本文将聚类信息融入CMM 模型，提出基于聚类的超链路预测算法C-CMM。假定U是一个超链路的候选集，其中包含了网络Hyper中缺失的超链路，超链路预测C-CMM 的目标就是找到集合U 中最有可能是网络Hyper 中缺失的超链路。在2.1 节中，已经对关联矩阵S进行了聚类，即将一个网络Hyper划分成簇S1，S2，…，Sk。这k个簇相当于网络Hyper 的k 个子网络，由于网络Hyper 是不完整的，所以每个子网络也可能是不完整的。本文随机生成k个网络，模拟不存在的超链路，将它们分别与簇S1，S2，…，Sk结合，构造出候选集Ui(i=1，2，…，k)，并假定该簇缺失的超链路均包含在U i 中。因此，基于聚类的超链路预测算法C-CMM 将分别从各自的候选集U i 中找到最有可能是该簇缺失的超链路。基于聚类的超链路预测算法如算法2所示。

算法2 基于聚类的超链路预测算法C-CMM。

输入 观测到的超链路矩阵S；

输出 预测到的超链路矩阵ΔS。

1）ΔS起始为空

2）对S 调用超链路聚类算法HC 进行聚类，得到k 个簇S1，S2，…，Sk，并将其与随机生成的网络结合起来分别构造出各自的超链路候选集U1，U2，…，U k

3）For i=1 to k

5）End for

6）ΔS=ΔSi∪…∪ΔSk

2.3 计算复杂性分析

设k 是簇的数目。对邻接矩阵Sm×n的分解，每进行一次迭代要进行4kmn+k2m+k2n+km+kn次乘法计算，km+kn次除法计算和4kmn+k2m+k2n 次加法计算。因为乘子更新法能在I次迭代内得到H以及k ≪min(m，n)，所以矩阵分解的时间复杂度为O(Imnk)。从文献［5］可知，CMM 算法的时间复杂度为O(n3)。对于每一个簇，都需要使用CMM 进行一次预测，因此C-CMM算法的时间复杂度为O(Imnk+kn3)。

3 实验与分析

3.1 实验数据集与评价指标

本文使用了鸡尾酒、传统中国菜食谱和DBLP 三个真实数据集进行实验。鸡尾酒是一种混合饮品，由两种或两种以上的酒或饮料、水果等其他辅助材料混合而成。根据基酒的不同，鸡尾酒可以分为不同的类别。鸡尾酒数据集从drink8.cn上下载，收集到了朗姆、白兰地、龙舌兰、伏特加和利口5种类型的鸡尾酒。例如“波本鸡尾酒”包含“威士忌、橙汁、薄荷”三种配料；“苹果白兰地鸡尾酒”包含“苹果汁、白兰地”两种配料。这5种类型中，每种类型均包含40种不同的鸡尾酒配方，共200条鸡尾酒配方，其中配料一共有82种，故鸡尾酒配方转化为82×200 的0-1 矩阵（矩阵中值为0 的元素表示列配方不包含行配料，值为1 表示包含）。传统中国菜食谱数据集来自meishi.net。该数据集有882种食谱，包含439种不同的食材，构成439×882 的0-1 矩阵。DBLP 数据集选择了数据挖掘领域的20 个会议、8 000 篇文章、3 910 个作者，以及6 917 个期刊。以每篇论文的发表事件作为一个超链路，这条超链路包括了发表这篇论文的全部作者和收录论文的会议和期刊，最终整理为10 847×8 000的0-1矩阵。

本文算法包含聚类和预测两个步骤，聚类结果使用轮廓系数［20］作为评价指标，超链路预测使用受试者工作特征曲线下面积（Area Under the receiver operating characteristic Curve，AUC）和召回率作为评价指标。

轮廓系数（Silhouette Coefficient）是评价聚类效果好坏的度量指标，它结合内聚度和分离度两种因素。使用轮廓系数评价聚类结果时不用知道数据的类别，而且还能评价划分后的簇是否在内部尽可能相似，簇之间是否尽可能不相似。它主要分为个体轮廓系数和全局轮廓系数。个体轮廓系数的定义如式（5）所示。

其中：ai表示超链路i与同簇内其他超链路之间的平均距离；bi表示超链路i 与其他簇中超链路平均距离的最小值，即bi=min{bi1，bi2，…，bik}，bik是超链路i 与第k 簇中超链路间的平均距离。ai称为超链路i 的簇内不相似度，bi为超链路i 的簇间不相似度。si∈[-1，1]，si接近1，说明超链路i的聚类合理；若si接近-1，说明超链路i的聚类不合理，应当划分到其他簇内。对所有超链路的个体轮廓系数计算平均值，得到全局轮廓系数，如式（6）所示：

AUC 是一种常用的评价模型分类/预测效果好坏的度量指标，AUC=1 表示分类/预测效果完美；0.5 ＜AUC ＜1 表示分类/预测效果优于随机猜测；AUC=0.5 表示分类/预测效果与随机猜测一样。假设模型的输出结果是一个分数值，表示一条超链路真实存在的概率，则随机选取一对（存在，不存在）的超链路，利用模型对两条超链路进行预测，AUC的值表示模型对存在超链路的输出值大于对不存在超链路的输出的概率。随机抽取n 对（存在，不存在）的超链路进行预测，假设有n'次预测中存在超链路的分数值大于不存在超链路的分数值，有n″次预测中两个的分数值相等，则AUC的定义如（7）所示。

召回率（Recall）主要用于评价模型预测的覆盖范围，即真正存在的超链路有多少被预测出来。假设有N条真实存在但未观察到的超链路，模型预测的top-N 条超链路中有n 条是真实存在的，则n 称为召回条数，召回条数与N 的比值称为召回率，其定义如式（8）所示。

召回率越高，模型预测的覆盖面越广。与AUC 相比，召回率侧重于预测结果中排名靠前的超链路。

3.2 基准算法

为了验证基于聚类的超链路预测算法的有效性，本文选择了如下6种算法作为基准算法，分别为Katz［11］、CN［5］、BS［21］、HPLSF［12］、Random（随机）和CMM［4］以及它们的变种。每种算法都将在超链路聚类后的簇上运行，得到的预测结果将与算法直接在整个超网络上预测的结果进行比较。为了便于区分，用“C-算法名”表示该算法在聚类后的簇上预测的版本，如C-Katz。

本文基于鸡尾酒数据、食谱数据和DBLP 数据进行鸡尾酒配方预测、食谱预测和论文发表事件预测。

1）鸡尾酒配方预测。给定一系列鸡尾酒配料和配方，预测给定的配料是否还能搭配出哪些给定配方外的其他配方。

2）食谱预测。给定一系列的食材和菜谱，预测给定的食材是否还能搭配出哪些给定菜谱外的其他菜谱。

3）论文发表事件预测。由给定的论文发表事件和作者、期刊和会议，预测还会有哪些作者会合作，以及这些作者合著的论文会被哪些期刊/会议录用。

3.3 预测结果

本实验在使用矩阵分解获取低维表达时，鸡尾酒、食谱和DBLP 数据集的基矩阵的秩分别设定为r=4，15，50，在使用K-means 算法对鸡尾酒、食谱和DBLP 数据聚类时簇的数目分别设定为k=5，11，37（此时，聚类结果的轮廓系数最大，见3.4节），在每个簇中随机选取50%的超链路作为训练集，剩余50%的超链路作为测试集。随机生成的超链路数目与测试集中的超链路数目相等。测试集中的超链路与随机生成的超链路合并构成候选集。每种算法分别在原始数据和聚类获得的簇上进行预测，计算各种算法的召回率和AUC。使用CMM 算法对三个数据集的原始数据进行矩阵分解时，鸡尾酒、食谱和DBLP 数据集的基矩阵的秩分别设置为10、30、80；使用C-CMM 算法对三个数据集的各个簇进行矩阵分解时，各个簇的矩阵的秩分别设为5、10、30。表1 展示了所有算法对于三种数据集的预测结果，最好的实验结果用粗体进行表示。

表1 三个数据集上的召回率和AUCTab.1 Recall and AUC on three datasets

从表1 可以看出，基于聚类的链路预测算法在召回条数和AUC 上普遍优于基准算法，这表明超链路预测时提前对超链路聚类能够获得更好的性能。此外，在所有的超链路预测算法中，C-CMM 算法得到的预测性能最好，比基准算法CMM性能有大幅度提升，说明基于聚类的超链路预测算法C-CMM是有效的。

3.4 结果可视化

本节将可视化预测到的真实存在的top-5 个鸡尾酒配方和top-10 个食谱配方及非真实存在的top-3 个鸡尾酒配方和食谱配方。DBLP 数据集上的预测结果与鸡尾酒和食谱数据集的预测结果类似，限于篇幅不再展示。

3.4.1 真实存在的top-k个鸡尾酒配方和菜谱

图2 和图3 展示了用C-CMM 和CMM 算法预测得到的top-5个真实存在的鸡尾酒配方和top-10个真实存在的菜谱。

从图2 可以看出，CMM 算法得到的结果仅仅只有3 种类型，而C-CMM算法得到的结果包含了5种类型。

从图3 可以看出，CMM 预测到的10 种菜口味偏重、偏辣，而且菜式重复，如水煮千张、水煮牛肉、麻辣豆腐鱼的做法基本一致，这些菜虽然真实存在，但是种类太少，口味单一。而C-CMM 预测到的菜谱有六种和CMM 一致，是真实存在的，而且菜品的种类增多了，如酸甜口味的菠萝咕咾肉、苦味的苦瓜鸡片、甜品木瓜炖奶酪，还有清爽的火龙果虾球；做法类似的菜品也减少，水煮千张、水煮牛肉和麻辣豆腐鱼这三种菜只剩下水煮牛肉，这是因为聚类后，每一种类别与其他类别都有较大的差异。这表明基于聚类的超链路预测模型能够更好地利用每个簇中的信息，使预测结果更加全面。

3.4.2 非真实存在的top-k个鸡尾酒方和菜谱

图4和图5展示了用C-CMM 和CMM 算法预测得到的top-3个非真实存在的鸡尾酒和菜谱。

由图4 可见，C-CMM 算法预测出来的鸡尾酒只包含一种基酒，可以进行调酒，但是CMM 算法预测出来一种鸡尾酒，包含了三种不同类型的酒，这种组合不能进行调酒；此外，CMM算法预测的鸡尾酒比C-CMM算法预测的类型少。

由图5可以看出，CMM算法预测的菜谱用料较单一重复，甚至有的食材不适于做成菜，比如牛肉和鸡肉一般不会放在一起做菜；而C-CMM预测的菜谱用料丰富，而且食材之间的组合也更加合理一些，均可以做出可口的菜，比如南瓜羹、麻辣土豆鱼和菠菜肚丝汤，与CMM算法相比没有出现奇怪的组合。

图2 C-CMM和CMM预测到的top-5个真实存在的鸡尾酒Fig.2 Top-5 real cocktails predicted by C-CMM and CMM

图3 C-CMM和CMM预测到的top-10个真实存在的菜谱Fig.3 Top-10 real menus predicted by C-CMM and CMM

图4 C-CMM和CMM预测到的top-3个非真实存在的鸡尾酒Fig.4 Top-3 non-real cocktails predicted by C-CMM and CMM

3.5 参数影响

本节考察了簇数目、基矩阵的秩和训练样本数目这三个参数对预测结果的影响。

3.5.1 真实存在的top-k个鸡尾酒配方和菜谱

图6 展示了设定不同簇数目时K-means 算法聚类结果的轮廓系数，其中横坐标表示簇数，纵坐标表示轮廓系数。从图6可以看出，K-means算法对鸡尾酒数据、食谱数据和DBLP 数据在k=5，11，37时有较高的轮廓系数。

3.5.2 不同秩对预测结果的影响

C-CMM 算法在进行矩阵分解时，需要设定基矩阵的秩r（超链路低维表达的维度）。图7展示了设定不同秩时C-CMM算法预测结果的召回条数，其中横坐标表示秩，纵坐标表示召回条数。从图7可见，C-CMM算法对鸡尾酒数据、食谱数据和DBLP数据在r=4，15，50时有较高的召回率。

3.5.3 不同训练样本数目对预测结果的影响

为了验证不同训练样本数目对预测结果的影响，对鸡尾酒、食谱、DBLP 数据集分别随机删除10 到80，50 到400，500到4 000 条超链路，然后使用删除的超链路作为测试集，剩下的数据集作为训练集。图8～10 分别展示了三个数据集在不同训练样本数目下，所有算法的召回条数，其中横坐标表示删除条数，纵坐标表示召回条数。召回条数越多，说明预测效果越好。从图8～10 中可以看出，在不同训练样本数目下，基于聚类的超链路预测算法的召回条数普遍高于未使用聚类的超链路预测算法的召回条数，表明基于聚类的超链路预测模型拥有更好的鲁棒性。

图7 C-CMM算法设定不同秩时的召回条数Fig.7 Recalls under different number of ranks of C-CMM algorithm

图8 六种算法分别随机删除10～80条超链路后的召回条数对比Fig.8 Comparison of the number of recalls after randomly deleteing 10 to 80 hyperlinks by six algorithms

图9 六种算法分别随机删除50～400条超链路后的召回条数对比Fig.9 Comparison of the number of recalls after randomly deleteing 50 to 400 hyperlinks by six algorithms

3.6 算法效率

C-CMM 算法与基准算法在鸡尾酒和食谱数据集上运行时间的比较如表2 所示，可见，C-CMM 算法的效率比BS、HPLSF、Random、Katz、CN 高，但是比CMM 低。这是因为BS、HPLSF、Random、Katz、CN 是非迭代算法，程序只需运行一次即可得出结果；虽然C-CMM 调用了CMM 算法，但是聚类后每个簇的关联矩阵要比原始矩阵小，矩阵分解的时间少于对原始矩阵的分解时间，并且各个簇的分解可以并行处理，所以C-CMM的效率比CMM高。

图10 六种算法分别随机删除500～4 000条超链路后的召回条数对比Fig.10 Comparison of the number of recalls after randomly deleteing 500 to 4 000 hyperlinks by six algorithms

表2 运行时间比较 单位：sTab.2 Comparison of running time unit：s

4 结语

信息网络中的超链路预测问题的研究十分重要并且有实际应用价值，但是如何利用观察样本数量不足的超链路蕴含的信息，使预测出来的超链路覆盖的种类全面、有效体现出网络的全貌是人们需要解决的问题。本文针对现有超链路预测算法的不足，提出了基于聚类的超链路预测算法。该算法首先对观察到的超链路进行聚类，然后对每一个簇分别建立超链路预测模型。实验结果表明基于聚类的超链路预测算法在预测的准确度和预测到的种类上均优于未聚类的超链路预测算法，因此，将聚类算法应用到超链路预测当中是有效的。