利用朴素贝叶斯模型进行多层网络链接预测
时间：2023-06-24 22:50:03 来源：雅意学习网 本文已影响 人 
张亚坤，李龙杰，陈晓云
1.兰州大学信息科学与工程学院，甘肃 兰州 730000
2.甘肃省媒体融合技术与传播重点实验室，甘肃 兰州 730030
20世纪末，在大量研究工作的基础上逐渐形成了一个称为复杂网络的研究方向[1-2]。许多复杂系统可以用复杂网络进行建模，其中节点代表系统的基本单元，节点间的链接代表单元之间的交互关系[3]。然而，这种聚合方式可能会丢失一些重要信息，因为复杂系统的基本单元可能通过不同含义的关系进行连接。生物学家发现细胞间的信息交流可分为电学信号和化学信号[4]，论文作者之间的关系可以分为共同作者和共同引用[5]等，人与人之间的社交关系可分为家人、同事和朋友等。多层网络可以将实体间各种类型的交互关系抽象为相同节点间不同类型的链接，每种类型的链接描述特定的交互关系，能更好地为这类复杂系统建模。
链接预测的目的是评估两个节点之间存在链接的可能性。在网络不断增长的条件下，链接预测也可以对网络的演化机制进行分析，因此不仅在复杂网络研究中占据一席之地，而且在现实生活中得到了广泛应用，如在线营销、电子商务和社交网络中好友推荐等[6-7]。此外，恐怖主义网络中的链接预测还可以帮助国家安全部门找到隐藏的恐怖分子或恐怖组织[8]。
尽管链接预测问题已经得到了深入的研究，但是现有工作关注的对象主要是单层网络，而对多层网络链接预测问题的研究相对较少。已有研究表明多层网络中层与层之间存在一定的结构相关性[9-11]，在进行链接预测时如果忽略层间信息就可能丢失有价值的信息。文献[12]提出了一个基于层间相关性的相似性指标，将节点对在每层的相似性融合进行链接预测。文献[10]提出了一个生成模型和期望最大化算法，在多层网络中实现社团检测和链接预测的目的。文献[11]定义了一个多层网络的层间相似性指标，并设计了一个组合层内信息和层间信息的链接预测框架。文献[13]在每层网络中提取节点对的结构特征，根据有监督的分类算法在目标层进行链接预测。文献[14]使用矩阵分解技术检测社团结构，并基于目标层的社团结构和其他层的社团结构重建目标层网络。文献[15]在多层网络中提取基于节点属性的特征和基于元路径的特征，然后根据机器学习分类算法预测节点对之间是否存在链接。文献[16]采用多层网络社团检测方法得到目标层的社团结构，然后组合链接的强度和多层网络的结构特征得到其他层提供的外部信息，最后和目标层的内部特征结合得到节点对之间存在链接的概率。文献[17]基于层间相关性和节点的度值计算多层网络随机游走的转移概率矩阵，以多层网络随机游走算法捕获本层和其他层的结构信息并计算节点对相似性值。文献[18]将节点对在每层的相似性值当作属性，层间相关性当作权重，使用多属性决策方法综合考虑多层网络中所有层的信息，得到节点对在目标层的相似性值。尽管上述方法在多层网络链接预测中可以获得较好的预测性能，但是在某些方面还存在一些弊端。例如：基于机器学习的方法需要采集大量特征，导致计算复杂度较高；
基于相似性的方法未考虑层间具有负相关性的情况。此外，还有些方法依赖于社团检测，其预测性能在一些社团结构不明显的网络中较低。
为了更好地解决多层网络链接预测问题，本文提出了一个新的链接预测算法。受单层网络中的局部朴素贝叶斯（local naïve Bayes，LNB）模型[19]的启发，本文将LNB 模型扩展到多层网络，通过融合网络中不同层的结构信息进行链接预测。在目标层中，直接使用LNB 模型并根据节点对的邻域信息计算其连接概率。对于其他层，利用朴素贝叶斯模型计算节点对在其他层有边或无边时在目标层存在链接的概率。最后，把不同层得到的概率结合进行链接预测。为了验证所提算法的性能，本文在多个真实网络和合成网络进行实验，结果表明该算法在正相关和负相关的多层网络中都能取得很好的预测性能。
1.1 多层网络
复杂网络表示为G=(V,E)，其中V和E分别为节点集和边集。边使用节点的二元组或e表示，即E={(u,v)|u ∈V,v ∈V}={euv|u ∈V,v ∈V}，并且E ⊆V ×V。一个由N个节点组成的M层网络可用M=(G,E) 表示，其中是网络Gi=(Vi,Ei) 的集合，Gi代表第i层网络，每层网络的节点集相同，即V1=V2=···=VM；
是层间链接集合，第i层与第j层之间的层间链接为Eij={(vi,vj)|vi ∈Vi,vj ∈Vj,vi=vj}。本文主要研究对象是无向的多层网络，因此假设每层网络都是无向的。网络结构使用邻接矩阵A存储，则第i层网络的邻接矩阵Ai为
式中
图1展示了文艺复兴时期佛罗伦萨的一些家族之间的联姻关系和商业关系形成的多层网络[20]。在多层网络中，每层网络的节点集相同。相同节点之间的跨层链接称为层间链接，即图1中的虚线。若某些节点在某层中没有链接，则表示为未激活节点，如图1中商业关系层的0、1、12 号节点。
图1 文艺复兴时期佛罗伦萨家族的多层社交网络Figure 1 Multiplex social network describing Florentine families in the Renaissance
1.2 多层网络链接预测
1.2.1 问题定义
多层网络中的链接预测是指在辅助层的帮助下，预测目标层T ∈{1,2,···,M}上缺失或未来可能出现的链接。首先将目标层中的链接ET划分为训练集EtrainT和测试集EtestT，满足ETtrain∪ETtest=ET，ETtrain∩ETtest=∅。在链接预测任务中将只使用训练集和辅助层的信息，计算目标层中除去训练集的所有节点对U −ETtrain存在链接的概率分数，这里U是包含所有节点对的集合；
然后将这些节点对按照分数从大到小排序，分数越大链接存在的概率越大；
最后根据测试集中节点对的概率分数用评价指标来评估链接预测的性能。
1.2.2 评价指标
1）AUC[21]使用AUC 作为链接预测的评价指标可以评估算法的整体正确性。AUC 表示从测试集ETtest中随机选择节点对的分数高于从不存在链接的集合U −ET中随机选择节点对的分数的概率，其计算公式为
式中：n为比较的次数，且次随机选择的潜在链接的分数高于随机选择的实际不存在的链接的分数，次随机选择的潜在链接的分数和随机选择的实际不存在的链接的分数相等。
2）Ranking-score[22]该指标衡量所有测试集ETtest中链接的分数在预测链接U −ETtrain中的降序排名。如果所有测试集中链接的排名越靠前，那么Ranking-score 的值越小，代表着预测性能越高。Ranking-score 的计算公式为
式中：re为链接e的分数在预测链接中的排名。
3）Precision 将U −ETtrain中的节点对按照概率分数降序排列，则潜在链接数目占所选节点对数目的比值就是Precision。若在前K条链接中，实际存在L条链接，那么Precision可以用公式表示为
在本文实验中，K=|ETtest|，即测试集大小。如果在预测的前K条链接中，实际存在的链接越多，那么Precision 的值就越高，即预测算法的精度越高。
1.3 层间相关性
本文引言指出多层网络的层与层之间存在相关性，并且这种相关性有助于研究多层网络的相关工作，如多层网络社团检测[23]、多层网络信息传播[24]以及链接预测[11-12,18]。本节将介绍3 种常用的层间相关性指标，可以从不同的角度刻画层与层之间的相似性。
1）边重叠率（edge overlap rate,EOR）[25]该指标描述两层网络间重复的边占总边数的比率，重复的边越多，表明两层网络越相似。计算目标层GT与辅助层GA之间EOR 的公式为
式中：eT A表示在目标层GT和辅助层GA同时出现的边，EA表示辅助层中的链接。[0,1]，=0，表示两层网络中没有同时出现的链接；
=1，表示两层网络的边完全相同。
2）皮尔逊相关系数（Pearson correlation coefficient,PCC）[12]PCC 可以衡量两个向量之间的相关程度，其取值范围为[−1,1]，其中负值表示两个向量之间负相关，0 代表不相关，正值表示正相关。文献[12]将GT层、GA层的邻接矩阵AT、AA分别按行拼接成两个长向量gT=(a11T,···,a21T,···,aNNT) 和gA=(a11A,···,a21A,···,aNNA)，再根据式(6) 计算两个层之间的相关性
式中：、分别为目标层向量、辅助层向量的均值，σ(gT)、σ(gA) 分别为目标层向量、辅助层向量的标准差。在多层网络中，=±1，表明GT层与GA层之间强正（负）相关，即在GT层出现的边必然会（不会）在GA层出现。
3）非对称平均邻居相似度（asymmetric average similarity of neighbors,AASN）[11]根据网络密度的思想，文献[11]将节点在两层网络中都存在的链接数与本层存在的链接数相比，得到AASN。这一相关性背后隐藏的直觉是如果两层网络存在足够的相似度，那么一个网络的密度越大，给其他层进行链接预测时提供的信息越多。该指标定义为
式中：kuTA表示节点u在两层网络中同时存在的链接数目；
kuT表示节点u在GT层网络中存在的链接数目，即度值。衡量了GA层对GT层的相似度，描述了对GT层进行链接预测时GA层中可用信息的比例。
1.4 LNB 模型
LNB 模型[19]认为每个共同邻居对节点对形成链接的贡献不同，并基于朴素贝叶斯评估邻居的贡献程度。给定节点x和y，其连接可能性定义为
式中：s=为一个常量，Oxy为节点x和y的公共邻居节点集合，Rw=N∆w和N∧w分别代表节点w和邻居之间形成的三角形数量和三元组数量。将式(8) 两边取对数，忽略常数s−1可得
考虑公共邻居w对形成链接的贡献可以通过其度值kw进行加权，于是得到式(9) 的3个不同版本如下：
在现实世界中，个体之间不同类型的关系存在一定程度的相互影响。在某个社交网络中，若一个人与另外一个人是朋友关系，那么他们将有很大概率存在其他类型的社交关系，如一起休闲、一起吃饭和互相通信等。利用这种影响对于提高目标层链接预测的性能非常重要。为了有效地利用层与层之间的信息进行链接预测，本文提出了一个基于朴素贝叶斯的多层链接预测（multiplex link prediction based on naïve Bayes,MLPNB）方法。为了能利用其他层对目标层的影响，MLPNB 方法将节点对在辅助层是否存在链接当作特征，使用朴素贝叶斯计算基于此特征时目标层节点对有边的概率。目标层节点对间存在链接的概率由基于其他层影响得出的概率与基于目标层自身结构信息计算出的概率组合得到。
MLPNB 方法的计算步骤如下：
步骤1计算目标层GT中节点对存在链接的概率分数。该步骤仅使用目标层的层内拓扑结构信息，概率分数由LNB 模型[19]计算得到，3 个不同的版本如式(10)～(12) 所示。
步骤2根据多层网络层与层之间存在相关性，考虑节点对在其他层是否有边对目标层的影响，将节点对在其他层是否有边当作特征，根据朴素贝叶斯模型可以得出如下两个后验概率：
式中：L1T(x,y) 表示节点对(x,y) 在GT层内有边，L0T(x,y) 表示节点对(x,y) 在GT层内无边。Uxy为特征集合，exyA ∈Uxy，当节点x和y在GA层有边时，exAy=1，否则为0。P(L1T(x,y)|Uxy) 表示节点x与y在GT层内有边的后验概率，P(L0T(x,y)|Uxy) 表示节点x与y在GT层内无边的后验概率。为了便于比较节点对之间存在链接的概率大小，定义rTxy为P(L1T(x,y)|Uxy) 除以P(L0T(x,y)|Uxy)，得到
将式(13) 两侧取对数，并忽略常数s−1可得
式中：P(L1T(x,y)|exyA) 表示节点x和y在辅助层GA有边，并且在GT层也有边的概率。为了计算P(L1T(x,y)|exyA)，定义
式中：A为邻接矩阵，AiTj=1 表示节点i和j在GT层内有边，否则为0。式(15) 表示节点x和y在GT层有边的概率，式(17) 表示节点对(x,y) 在GT和GA层同时有边的联合概率，其余情况的联合概率分布如下：
计算条件概率为
p1、p2、q可根据以下公式近似计算：
式中
因此
步骤3使用最大最小归一化方法将和rTxy分别进行归一化处理。
步骤4将归一化处理后的和rTxy进行结合，根据式(10)～(12) 得到3 个版本的MLPNB 计算公式为
式中：参数α ∈[0,1]控制两部分的权重。
本文所有的实验流程均独立进行20 次，结果取平均值，测试集大小为10%，即|ETtest|/|ET|=10%。
3.1 数据集
本文实验使用9 个公开的多层网络数据集，并简要描述如下：
1）CS-Aarhus[26]该网络是丹麦Aarhus 大学计算机科学系的61 名职工的社交关系网络。
2）Elegans[27]秀丽隐杆线虫的神经元通过各种突触链接类型组成的多层网络。
3）Drosophila[27]果蝇的基因相互作用网络。
4）Physicians[28]美国4 个城市的医生在使用一种新药时的关系网络。
5）Krackhardt[29]该多层网络由一个高科技企业管理团队之间的3 种关系组成。
6）Lazega[30]律师事务所的合伙人和普通律师之间的社交网络，共拥有3 种类型的社交关系。
7）Padgett[20]在文艺复兴时期，佛罗伦萨家族之间的联姻和商业关系构成的两层网络。
8）TF[19]两个线上社交网络服务Twitter 和Foursquare 的共同用户之间的交互关系。
9）Vickers[31]29 名7年级学生之间存在的3 种关系构成的网络。
表1展示了上述数据集的拓扑特征。其中：layer 表示网络层对应的名称；
N、NT、|ET|分别代表多层网络的总节点数目、该层激活的节点数目、该层的链接数目；
〈k〉表示网络的平均度；
〈C〉为网络的平均聚集系数，用来刻画网络中节点之间凝聚成团的平均程度；
ρ为网络密度；
H为网络的度异质性，描述网络中节点的度分布的均衡性；
ϕ为度同配系数，衡量节点是否偏向于连接与自身性质相同的其他节点。
表1 多层网络的拓扑特征Table 1 Topological characteristics of multiplex networks
图2展示了各网络层间相关性，度量指标采用PCC。很显然，不同网络的层间相关性差异很大。
从图2中可以看出：这些网络的层间PCC 均为正数，表明网络的层与层之间都是正相关的。实际中可能存在负相关的网络，而现有方法对层间PCC 为负值的多层网络关注度较低。为了验证本文提出的方法能够适用于负相关性网络，根据ER 模型[32]生成了两个负相关的多层网络Syn1 和Syn2、一个不相关的多层网络Syn3 以及两个正相关的多层网络Syn4 和Syn5，它们的拓扑信息及相关性见表2和3。表3中layer1→layer2 表示layer1 层对layer2 层的AASN 相关性。
表2 合成多层网络的拓扑特征Table 2 Topological characteristics of synthetic multiplex networks
表3 合成多层网络的层间相关性Table 3 Interlayer relevance of synthetic multiplex networks
图2 多层网络基于PCC 的层间相关性Figure 2 Interlayer relevance of multiplex networks based on PCC
3.2 参数分析
本方法有一个参数α，α=0 表示仅使用目标层的结构信息，α=1.0 表示仅使用辅助层提供的信息。图3～5 分别给出了MLPNB-CN、MLPNB-AA 和MLPNB-RA 方法在Elegans、TF 和Vickers 网络上的链接预测结果，误差棒为20 次独立实验结果的标准差。从图3～5 中可以看出：3 种方法的曲线趋势大体一致，但就整体而言，MLPNB-RA 表现略优。在其他网络上的结果与这3 个网络上的结果基本一致，由于空间的限制，文中不再给出。
此外，从图3～5 的结果中还可以看出：MLPNB 方法的性能随着α值的增大迅速到达峰值并在后续趋于稳定，当α=1.0 时的性能迅速下降。这表明通过加入其他层的信息可以提高目标层的链接预测性能，若不使用目标层的结构信息则预测性能会明显降低。当α=0.5时，MLPNB 方法在3 个网络上都取得了较优的预测结果。因此，后续实验将α设定为0.5。
图3 MLPNB 方法在Elegans 网络上的预测性能Figure 3 Prediction performance of MLPNB in Elegans network
图4 MLPNB 方法在TF 网络上的预测性能Figure 4 Prediction performance of MLPNB in TF network
图5 MLPNB 方法在Vickers 网络上的预测性能Figure 5 Prediction performance of MLPNB in Vickers network
3.3 对比实验
为了验证本文方法的性能，将MLPNB 方法与一些代表性的多层网络链接预测方法进行对比，它们分别为LP-TOPSIS[18]、LPIS[11]、LAA[14]、NSILR[12]。这些方法以不同的方式提取并使用了辅助层的信息，且除LAA 方法外其余算法的预测性能远优于仅使用目标层结构信息的传统链接预测算法。LAA 算法因未使用目标层自身的结构信息而导致性能较差，但在一些相关性较高的多层网络中的预测精度较高。LP-TOPSIS、LPIS、NSILR 方法都同时利用了来自辅助层的信息和目标层的结构信息。在本实验中，层间相关性指标使用AASN。
如图6所示，MLPNB 方法在大多数网络上得到的AUC 结果优于其他方法，LAA 方法在Padgett 网络上的预测性能略高于MLPNB 方法。这是因为Padgett 网络的节点和链接较少，基于公共邻居的LNB-RA 方法不能有效地预测目标层中的潜在链接，而仅利用辅助层信息的LAA 方法反而可以取得较优的AUC 值。
图6 MLPNB 方法和对比方法在多层网络上的AUC 结果Figure 6 AUC results of MLPNB and compared methods in multiplex networks
图7展示的Ranking-score 结果与上述AUC 大体相同，MLPNB 方法仍然在大多数网络上优于对比方法。Ranking-score 衡量测试链接在所有预测链接中的整体排名。经过分析发现MLPNB 方法在Drosophila 网络中计算得出的节点对概率分数大部分相同。因为Drosophila网络仅有两层，而由辅助层计算得到的概率分数仅有两个值——节点对在辅助层有边时目标层有边的概率、在辅助层无边时目标层有边的概率，所以根据AUC 指标的计算公式可知：本文方法在AUC 评价指标下略有逊色，但在Ranking-score 评价指标下表现较好。
图8给出了MLPNB 与对比方法的Precision 结果。从图8的Precision 结果中可以看出，MLPNB 方法在除TF 网络外的其余数据集上均优于其他方法。如图6所示，MLPNB 方法在TF 网络的第2 层上且当α=0.1 时的Precision 最大，然后随着α的增大而不断减小。根据表1可以发现TF 网络第2 层的平均聚集系数远大于第1 层，因此仅使用第2 层自身的信息便可以取得较好的预测结果。
图8 MLPNB 方法和对比方法在多层网络上的Precision 结果Figure 8 Precision results of MLPNB and compared methods in multiplex networks
由本节的对比实验结果可知：MLPNB 方法相比于现有的多层网络链接预测方法，不仅有更好的预测性能，还有更高的普适性。
3.4 在合成网络上的实验
为了进一步研究MLPNB 的普适性，本节在合成数据上进行实验。考虑到合成数据中有负相关的多层网络以及它们的EOR 值和AASN 值几乎一样，本节的实验设置在上一节的基础上添加了PCC 相关性。图9给出了MLPNB 与对比方法在合成数据上的AUC 结果。
图9 MLPNB 方法和对比方法在合成多层网络上的AUC 结果Figure 9 AUC results of MLPNB and compared methods in synthetic multiplex networks
LP-TOPSIS、LPIS、NSILR 方法使用PCC 和AASN 层间相关性指标在不同的合成多层网络中得出的预测结果几乎一致。所有方法在不具有相关性的Syn3 网络上得到的AUC 值都接近于0.5，Precision 值接近于0。MLPNB 方法不仅在负相关网络Syn1 和Syn2 上表现最优，在正相关网络Syn4 和Syn5 上也得到了最优的预测结果。因为LPIS 方法也考虑了节点对是否在其他层存在链接的影响，所以在负相关网络获得了较好的预测结果。然而，所有数据都是根据ER 模型生成的，网络结构具有较高的随机性。因此，使用逻辑回归的LPIS 方法在正相关网络上表现最差。LAA 方法仅考虑辅助层的信息，虽然在正相关性的网络上具有较高的预测性能，但是在负相关性的网络上表现最差。
综上所述，MLPNB 方法在正相关网络和负相关网络都具有较高的预测性能，即相比于对比方法具有较高的普适性。
本文提出了一个基于朴素贝叶斯模型的多层网络链接预测算法。该算法将朴素贝叶斯模型扩展到多层网络，通过集成网络不同层的信息进行链接预测；
针对目标层和辅助层，根据不同的结构信息分别计算节点对在目标层存在链接的概率，再将两者结合得到节点在目标层存在链接的可能性。实验结果表明：本文提出的算法不仅在正相关的真实数据上性能优越，而且在合成的负相关网络上也得到了期望的预测结果。
