基于分包的混合朴素贝叶斯链路预测模型

曾茜 韩华 李秋晖 李巧丽

摘要：

隐朴素贝叶斯模型（HNB）和树增强朴素贝叶斯模型（TAN）通过挖掘共邻节点之间的内在关联缓解局部朴素贝叶斯模型（LNB）的强独立性假设，却忽略了真实网络中同时存在关联紧密的节点和相对独立的节点。在此基础上设计一种分包准则，将共邻节点划分为关联共邻节点和独立共邻节点，然后分别对HNB和TAN做分包改进，提出基于分包的混合朴素贝叶斯模型。在平均共邻节点数高的FWFW网络上，分包后HNB和TAN模型与原模型相比AUC值分别提升12%和11.6%。实验结果表明，所提方法能有效提升链路预测性能，并且具有良好的鲁棒性。

关键词：

复杂网络；链路预测；分包；混合朴素贝叶斯

中图分类号： TP393 文献标识码：A

收稿日期：2022-02-21；修回日期：2022-03-24

基金项目：

国家自然科学基金（12071364）；国家自然科学基金青年科学基金（11701435）

第一作者：

曾茜（1997-），女，湖北武汉人，硕士研究生，主要研究方向为链路预测、复杂网络分析。

通信作者：

韩华（1975-），女，山东烟台人，博士，教授，主要研究方向为复杂性分析与评价、经济控制与决策。

Package-based Hybrid Naive Bayesian Model

ZENG Xi， HAN Hua， LI Qiuhui， LI Qiaoli

（School of Science， Wuhan University of Technology， Wuhan 430070， China）

Abstract：Hidden Naive Bayesian Model （HNB） and Tree Augmented Naive Bayesian Model （TAN） alleviate the strong independence assumption of Local Naive Bayesian Model （LNB） by mining the intrinsic associations between co-neighboring nodes， but ignore that there are both closely correlated nodes and relatively independent nodes in the real network. On this basis， a package criterion is designed， which divides the co-neighboring nodes into correlated co-neighboring nodes and independent co-neighboring nodes according to the degree of association. Then， packaging HNB and TAN respectively， so that the packaged-based hybrid naive Bayesian models are obtained. On FWFW networks with high average number of co-neighbors， the AUC values of the HNB and TAN models after packaging are increased by 12% and 11.6%， respectively. The experimental results show that the proposed method can effectively improve the link prediction performance and has good robustness.

Key words：

complex network; link prediction; packaged; hybrid naive Bayesian model

0 引言

復杂网络可以很好地描述现今社会中各种信息的复杂交互关系［1］，网络中的节点代表复杂关系中的个体，连边代表个体之间的关系或相互作用［2］。链路预测作为复杂网络研究的一个重要分支，旨在利用已知的网络信息预测和还原网络中的未知链接［3］和未来链接［4］。链路预测在不同领域中具有重要的应用价值，例如，在生物网络中预测网络中的连边关系并关注最有可能存在的链接，以降低生物实验的成本［5］；在线上社交网络和电商网络中搭建推荐系统，向用户推荐可能感兴趣的内容或商品［6］，从而创造商业价值。

目前，学者们针对链路预测中基于网络结构相似性的方法展开了大量研究。基于结构相似性的链路预测方法根据节点对的拓扑结构信息来计算节点对的相似性得分，相似性得分越高，两个节点连边的可能性就越大［7］。已有的相似性方法可大致分为两类：一是基于局部信息的相似性指标，如CN指标［8］、AA 指标［9］、RA指标［10］和CCNC指标［11］等；二是基于全局信息的相似性指标，如基于随机游走的ACT指标［12］、RWR指标［13］、BRWR指标［14］和基于路径的Katz指标［15］等。

CN指标因计算复杂度低、适用于大规模网络等优点被广泛应用，它简单地认为所有共邻节点对待测连边的贡献相同。Liu等［16］考虑到不同共邻节点的局部信息对连边有不同影响，提出局部朴素贝叶斯链路预测模型（LNB）。该方法严格假设每个共邻节点的贡献是独立的，往往与真实网络中节点之间的复杂链接关系不符。针对聚集性高、共邻节点富集的真实网络，伍杰华等［17］提出隐朴素贝叶斯模型（HNB），该模型计算每个共邻节点与其它共邻节点关联关系的贡献，性能优于LNB方法。然而，HNB方法在计算关联贡献时默认任意两共邻节点都是关联的，忽略了相对独立的共邻节点。Wu等［18］提出树增强朴素贝叶斯模型（TAN），该模型根据共邻节点之间的连边情况，分别计算有连边的共邻节点对的关联贡献和无连边孤立共邻节点的独立贡献。但是，共邻节点之间的连边关系不足以量化其关联的程度。

基于上述问题，本文提出一种分包的思想，首先利用条件互信息刻画共邻节点对的关联程度，然后设定将共邻节点划分为关联节点包和独立节点包的分包准则，从而得到同时计算关联节点贡献和独立节点贡献的混合朴素贝叶斯模型。考虑到HNB和TAN模型为计算关联贡献提供了不同的思路，同时在解决独立性问题时各有不足，本文将分包思想应用到HNB和TAN模型上，并进行实验验证，旨在揭示基于分包的混合朴素贝叶斯链路预测模型在高密度和聚集性强的真实网络中表现出的有效性。

3.2 评价指标

为了量化链路预测方法的准确性，将网络边集E随机划分为训练集ET和测试集EP两部分，满足E=ET∪EP，且ET∩EP=。训练集ET作为可观察的已知网络信息用于计算待测节点对的相似性分数。测试集EP作为待预测边的集合用于验证预测的准确性。本文使用AUC指标［25］、精确度［26］来评价模型的有效性和鲁棒性。

AUC指标从整体上衡量模型的准确度。假设n次独立抽取中有n′次测试集中边的分数值更高，n″次抽取的两条边的分数值相等，则AUC指标可定义为

AUC=n′+0.5n″n（44）

精确度衡量排序前L条边中预测的准确度。将预测边按相似性得分降序排序，假设前L的边中有m条测试集中的边，则精确度定义为

Precision=mL（45）

由于实验中所用网络的规模各不相同，这里设置各网络边数的10%作为L的值。

3.3 实验结果分析

本次实验中，采用随机抽样法将实验数据集划分为训练集和测试集，训练集占比为0.9，所有结果均为100次独立重复实验的平均值。为了验证分包准则的有效性，在6个网络上将HNBs指标和TANs指标作为基准指标设置两组对比：HNBs与PHNBs对比、TANs与PTANs对比。

针对HNB和TAN分包后，能得到不同的预测结果。由表2可知，与HNBs指标（HNBCN、HNBAA、HNBRA）相比，分包后的PHNBs指标（PHNBCN、PHNBAA、PHNBRA）在不同网络中均能取到最高的AUC值。PHNBs系列中，PHNBRA在C.elegans网络上略低于原始的HNBRA，PHNBAA在Email网络上略低于原始的HNBAA，相差均不超过1%。除此之外，每个网络中的PHNBs指标均优于其对应的原始指标，这表明共邻节点集合中存在部分共邻节点独立地影响连边的形成，分类计算独立节点贡献和关联节点贡献的方法是可行的。同样将TANs和PTANs作对比，PTANs系列中每个指标（PTANCN、PTANAA、PTANRA）均优于相应未分包的TANs指标（TANCN、TANAA、TANRA），且在每个网络中PTANRA的预测精度最高，这说明分包准则作为共邻节点划分依据应用到TAN模型中是合理有效的。

在FWEW和FWFW網络中，对HNB和TAN模型进行分包改进后AUC值提升较大。以HNBCN为例，PHNBCN的AUC值与之相比在FWEW网络中提升了5.8%，在FWFW网络中提升了12%，在其他网络中提升范围为0.08%～1.2%。PTANCN与TANCN相比AUC值在FWEW和FWFW网络中分别提升了4.9%和11.6%，而在其他网络中提升范围为0.9%～1.4%。从表1中不难发现，FWEW和FWFW网络的平均共邻节点数较大，说明在共邻节点富集的网络上分类讨论共邻节点的贡献能有效提升链路预测的性能。

表3给出了两组对比模型的Precision值。结果表明，无论是HNBs还是TANs中的指标，其分包后相似性指标的Precision值在不同网络中均有提升，这与AUC结果相同。横向对比HNBs和PHNBs的6个指标，不难

发现每个网络中最高的Precision值均在PHNBs中取得。同样将TANs和PTANs的6个指标进行对比，每个网络中最高的Precision值也在PHNBs中取得。从Precision结果可以看出，对HNB和TAN模型应用分包准则能够提升预测的准确度，进一步验证了分包的混合朴素贝叶斯模型的有效性和可行性。

3.4 鲁棒性分析

为了进一步分析PHNB模型和PTAN模型的鲁棒性，本部分测试在不同训练集比例下各指标AUC和Precision结果的变化情况。从图2可以看出，随着训练集比例从0.9开始每次减少0.1直到0.6，每个网络中各指标的AUC值随之降低，这是由于网络的可观测数据随着训练集的变化而减少，导致了网络的预测性能降低。当各网络的可观测数据降低到60%时，6个网络中PHNBs和PTANs指标的AUC值相较于其未分包的原始指标仍有不同程度的提升，这表明PHNB和PTAN模型的鲁棒性较好。

从图3可以看出，随着训练集比例从0.9逐次减少0.1直到0.6，每个网络中各指标的Precision值随之增加，这是因为Precision关注前L条预测边的准确率，训练集比例越小，预测边出现在测试集的可能性就越大，准确率就越大。当各网络可观测数据从90%降低到60%，整体上PHNBs和PTANs指标相较于其未分包的原始指标的预测性能更优，进一步验证了PHNB和PTAN模型具有良好的鲁棒性。

4 结语

本文在HNB和TAN模型的基础上，考虑到独立的共邻节点和关联的共邻节点对待测连边有不同贡献，设计了划分共邻节点的分包准则并融入到HNB和TAN模型中。6个真实网络上的实验结果表明，通过分包改进后PHNB和PTAN模型在AUC和Precision标准下的预测性能优于原始模型，而且具有良好的鲁棒性。本文方法仅针对无权无向网络，将此方法应用到加权有向网络或者多维网络的工作有待进一步开展。此外，在结构特征不同的网络上如何获取预测性能最优以及计算复杂度最优的阈值也是下一步研究的重点。

参考文献：

［1］BATOOL K， NIAZI M A. Modeling the internet of things： a hybrid modeling approach using complex networks and agent-based models［J］. Complex Adaptive Systems Modeling， 2017， 5（1）： 1-19.

［2］HUANG Q J， ZHANG X， WANG X J， et al. The degree-related clustering coefficient and its application to link prediction［J］. Physica A： Statistical Mechanics and Its Applications， 2016， 454： 24-33.

［3］YANG Y， LICHTENWALTER R N， CHAWLA N V. Evaluating link prediction methods［J］. Knowledge and Information Systems， 2015， 45（3）： 751-782.

［4］LI S B， HUANG J W， ZHANG Z G， et al. Similarity-based future common neighbors model for link prediction in complex networks［J］. Scientific Reports， 2018， 8（1）： 1-11.

［5］MLIKA Z， GOONEWARDENA M， AJIB W， et al. User-base-station association in HetSNets： complexity and efficient algorithms［J］. IEEE Trans on Vehicular Technology， 2017， 66（2）： 1484-1495.

［6］ZHANG L L， LI J， ZHANG Q L， et al. Domain knowledge-based link prediction in customer-product bipartite graph for product recommendation［J］. International Journal of Information Technology & Decision Making， 2019， 18（1）： 311-338.

［7］Lu L Y， ZHOU T. Link Prediction in complex networks： a survey［J］. Physica A： Statistical Mechanics and Its Applications，2011， 390（6）： 1150-1170．

［8］LORRAIN F， WHITE H C. Structural equivalence of individuals in social networks［J］. The Journal of Mathematical Sociology， 1971， 1（1）： 49-80.

［9］ADAMIC L A， ADAR E. Friends and neighbors on the Web［J］. Social Networks， 2003， 25（3）： 211-230.

［10］ ZHOU T， Lu L Y， ZHANG Y C. Predicting missing links via local information［J］. The European Physical Journal B， 2009， 71（4）： 623-630.

［11］ 郁湧， 王莹港， 罗正国， 等. 基于聚类系数和节点中心性的链路预测算法［J］. 清华大学学报（自然科学版）， 2022， 62（1）： 98-104.

YU Y， WANG Y G， LUO Z G， et al. Link prediction algorithm based on clustering coefficient and node centrality［J］. Journal of Tsinghua University（Science and Technology）， 2022， 62（1）： 98-104.

［12］ KLEIN D J， RANDI M. Resistance distance［J］. Journal of Mathematical Chemistry， 1993， 12（1）： 81-95.

［13］ BRIN S， PAGE L. The anatomy of a large-scale hypertextual web search engine［J］. Computer Networks and ISDN Systems， 1998， 30（1）： 107-117.

［14］ 呂亚楠， 韩华， 贾承丰， 等. 基于有偏向的重启随机游走链路预测算法［J］. 复杂系统与复杂性科学， 2018， 15（4）： 17-24.

Lu Y N， HAN H， JIA C F， et al. Link prediction algorithm based on biased random walk with restart［J］. Complex Systems and Complexity Science， 2018， 15（4）： 17-24.

［15］ KATZ L. A new status index derived from sociometric analysis［J］. Psychometrika， 1953， 18（1）： 39-43.

［16］ LIU Z， ZHANG Q M， Lü L Y， et al. Link prediction in complex networks： a local naive Bayes model［J］. Europhysics Letters， 2011， 96（4）： 48007.

［17］ 伍杰华， 朱岸青， 蔡雪莲， 等. 基于隐朴素贝叶斯模型的社会关系推荐［J］. 计算机应用研究， 2014， 31（5）： 1381-1384.

WU J H， ZHU A Q， CAI X L， et al. Hidden nave Bayesian model for social relation recommendation［J］. Application Research of Computer， 2014， 31（5）： 1381-1384.

［18］ WU J. A generalized tree augmented naive Bayes link prediction model［J］. Journal of computational science， 2018， 27： 206-217.

［19］ HEYMANS J J， ULANOWIC R E， BONDAVALLI C. Network analysis of the South Florida Everglades graminoid marshes and comparison with nearby cypress ecosystems［J］. Ecological Modelling， 2002， 149（2）： 5-23.

［20］ ALMUNIA J， BASTERRETXEA G， ARISTEGUI J， et al. Benthic-pelagic switching in a coastal subtropical lagoon［J］. Estuarine Coastal and Shelf Science， 1999， 49（3）： 363-384.

［21］ BATAGELJ V， MRVAR A. Pajek-program for large network analysis［J］. Connections， 1998， 21（2）： 47-57.

［22］ WATTS D J， STROGATZ S H. Collective dynamics of ‘small-world networks［J］. Nature， 1998， 393（6684）： 440-442.

［23］ ADAMIC L A， GLANCE N. The political blogosphere and the 2004 US election： divided they blog［C］// Proceedings of the 3rd International Workshop on Link Discovery. New York： ACM Press， 2005： 36-43.

［24］ GUIMERA R， DANOD L， DIAZ-GUILEAR A， et al. Self-similar community structure in a network of human interactions［J］. Physical Review E， 2003， 68（6）： 65-73.

［25］ ZENG G P， ZENG E. On the three-way equivalence of AUC in credit scoring with tied scores［J］. Communications in Statistics-Theory and Methods， 2019， 48（7）： 1635-1650.

［26］ WU Z H， LIN Y F， ZHAO Y J， et al. Improving local clustering based top-L link prediction methods via asymmetric link clustering information［J］. Physica A： Statistical Mechanics and Its Applications， 2018， 492： 1859-1874.

（責任编辑 耿金花）