曾茜 韓華 李秋暉 李巧麗

摘要：

隱樸素貝葉斯模型（HNB）和樹增強(qiáng)樸素貝葉斯模型（TAN）通過挖掘共鄰節(jié)點(diǎn)之間的內(nèi)在關(guān)聯(lián)緩解局部樸素貝葉斯模型（LNB）的強(qiáng)獨(dú)立性假設(shè)，卻忽略了真實(shí)網(wǎng)絡(luò)中同時(shí)存在關(guān)聯(lián)緊密的節(jié)點(diǎn)和相對(duì)獨(dú)立的節(jié)點(diǎn)。在此基礎(chǔ)上設(shè)計(jì)一種分包準(zhǔn)則，將共鄰節(jié)點(diǎn)劃分為關(guān)聯(lián)共鄰節(jié)點(diǎn)和獨(dú)立共鄰節(jié)點(diǎn)，然后分別對(duì)HNB和TAN做分包改進(jìn)，提出基于分包的混合樸素貝葉斯模型。在平均共鄰節(jié)點(diǎn)數(shù)高的FWFW網(wǎng)絡(luò)上，分包后HNB和TAN模型與原模型相比AUC值分別提升12%和11.6%。實(shí)驗(yàn)結(jié)果表明，所提方法能有效提升鏈路預(yù)測(cè)性能，并且具有良好的魯棒性。

關(guān)鍵詞：

復(fù)雜網(wǎng)絡(luò)；鏈路預(yù)測(cè)；分包；混合樸素貝葉斯

中圖分類號(hào)： TP393 文獻(xiàn)標(biāo)識(shí)碼：A

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

基金項(xiàng)目：

國家自然科學(xué)基金（12071364）；國家自然科學(xué)基金青年科學(xué)基金（11701435）

第一作者：

曾茜（1997-），女，湖北武漢人，碩士研究生，主要研究方向?yàn)殒溌奉A(yù)測(cè)、復(fù)雜網(wǎng)絡(luò)分析。

通信作者：

韓華（1975-），女，山東煙臺(tái)人，博士，教授，主要研究方向?yàn)閺?fù)雜性分析與評(píng)價(jià)、經(jīng)濟(jì)控制與決策。

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 引言

復(fù)雜網(wǎng)絡(luò)可以很好地描述現(xiàn)今社會(huì)中各種信息的復(fù)雜交互關(guān)系［1］，網(wǎng)絡(luò)中的節(jié)點(diǎn)代表復(fù)雜關(guān)系中的個(gè)體，連邊代表個(gè)體之間的關(guān)系或相互作用［2］。鏈路預(yù)測(cè)作為復(fù)雜網(wǎng)絡(luò)研究的一個(gè)重要分支，旨在利用已知的網(wǎng)絡(luò)信息預(yù)測(cè)和還原網(wǎng)絡(luò)中的未知鏈接［3］和未來鏈接［4］。鏈路預(yù)測(cè)在不同領(lǐng)域中具有重要的應(yīng)用價(jià)值，例如，在生物網(wǎng)絡(luò)中預(yù)測(cè)網(wǎng)絡(luò)中的連邊關(guān)系并關(guān)注最有可能存在的鏈接，以降低生物實(shí)驗(yàn)的成本［5］；在線上社交網(wǎng)絡(luò)和電商網(wǎng)絡(luò)中搭建推薦系統(tǒng)，向用戶推薦可能感興趣的內(nèi)容或商品［6］，從而創(chuàng)造商業(yè)價(jià)值。

目前，學(xué)者們針對(duì)鏈路預(yù)測(cè)中基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的方法展開了大量研究。基于結(jié)構(gòu)相似性的鏈路預(yù)測(cè)方法根據(jù)節(jié)點(diǎn)對(duì)的拓?fù)浣Y(jié)構(gòu)信息來計(jì)算節(jié)點(diǎn)對(duì)的相似性得分，相似性得分越高，兩個(gè)節(jié)點(diǎn)連邊的可能性就越大［7］。已有的相似性方法可大致分為兩類：一是基于局部信息的相似性指標(biāo)，如CN指標(biāo)［8］、AA 指標(biāo)［9］、RA指標(biāo)［10］和CCNC指標(biāo)［11］等；二是基于全局信息的相似性指標(biāo)，如基于隨機(jī)游走的ACT指標(biāo)［12］、RWR指標(biāo)［13］、BRWR指標(biāo)［14］和基于路徑的Katz指標(biāo)［15］等。

CN指標(biāo)因計(jì)算復(fù)雜度低、適用于大規(guī)模網(wǎng)絡(luò)等優(yōu)點(diǎn)被廣泛應(yīng)用，它簡(jiǎn)單地認(rèn)為所有共鄰節(jié)點(diǎn)對(duì)待測(cè)連邊的貢獻(xiàn)相同。Liu等［16］考慮到不同共鄰節(jié)點(diǎn)的局部信息對(duì)連邊有不同影響，提出局部樸素貝葉斯鏈路預(yù)測(cè)模型（LNB）。該方法嚴(yán)格假設(shè)每個(gè)共鄰節(jié)點(diǎn)的貢獻(xiàn)是獨(dú)立的，往往與真實(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)之間的復(fù)雜鏈接關(guān)系不符。針對(duì)聚集性高、共鄰節(jié)點(diǎn)富集的真實(shí)網(wǎng)絡(luò)，伍杰華等［17］提出隱樸素貝葉斯模型（HNB），該模型計(jì)算每個(gè)共鄰節(jié)點(diǎn)與其它共鄰節(jié)點(diǎn)關(guān)聯(lián)關(guān)系的貢獻(xiàn)，性能優(yōu)于LNB方法。然而，HNB方法在計(jì)算關(guān)聯(lián)貢獻(xiàn)時(shí)默認(rèn)任意兩共鄰節(jié)點(diǎn)都是關(guān)聯(lián)的，忽略了相對(duì)獨(dú)立的共鄰節(jié)點(diǎn)。Wu等［18］提出樹增強(qiáng)樸素貝葉斯模型（TAN），該模型根據(jù)共鄰節(jié)點(diǎn)之間的連邊情況，分別計(jì)算有連邊的共鄰節(jié)點(diǎn)對(duì)的關(guān)聯(lián)貢獻(xiàn)和無連邊孤立共鄰節(jié)點(diǎn)的獨(dú)立貢獻(xiàn)。但是，共鄰節(jié)點(diǎn)之間的連邊關(guān)系不足以量化其關(guān)聯(lián)的程度。

基于上述問題，本文提出一種分包的思想，首先利用條件互信息刻畫共鄰節(jié)點(diǎn)對(duì)的關(guān)聯(lián)程度，然后設(shè)定將共鄰節(jié)點(diǎn)劃分為關(guān)聯(lián)節(jié)點(diǎn)包和獨(dú)立節(jié)點(diǎn)包的分包準(zhǔn)則，從而得到同時(shí)計(jì)算關(guān)聯(lián)節(jié)點(diǎn)貢獻(xiàn)和獨(dú)立節(jié)點(diǎn)貢獻(xiàn)的混合樸素貝葉斯模型。考慮到HNB和TAN模型為計(jì)算關(guān)聯(lián)貢獻(xiàn)提供了不同的思路，同時(shí)在解決獨(dú)立性問題時(shí)各有不足，本文將分包思想應(yīng)用到HNB和TAN模型上，并進(jìn)行實(shí)驗(yàn)驗(yàn)證，旨在揭示基于分包的混合樸素貝葉斯鏈路預(yù)測(cè)模型在高密度和聚集性強(qiáng)的真實(shí)網(wǎng)絡(luò)中表現(xiàn)出的有效性。

3.2 評(píng)價(jià)指標(biāo)

為了量化鏈路預(yù)測(cè)方法的準(zhǔn)確性，將網(wǎng)絡(luò)邊集E隨機(jī)劃分為訓(xùn)練集ET和測(cè)試集EP兩部分，滿足E=ET∪EP，且ET∩EP=。訓(xùn)練集ET作為可觀察的已知網(wǎng)絡(luò)信息用于計(jì)算待測(cè)節(jié)點(diǎn)對(duì)的相似性分?jǐn)?shù)。測(cè)試集EP作為待預(yù)測(cè)邊的集合用于驗(yàn)證預(yù)測(cè)的準(zhǔn)確性。本文使用AUC指標(biāo)［25］、精確度［26］來評(píng)價(jià)模型的有效性和魯棒性。

AUC指標(biāo)從整體上衡量模型的準(zhǔn)確度。假設(shè)n次獨(dú)立抽取中有n′次測(cè)試集中邊的分?jǐn)?shù)值更高，n″次抽取的兩條邊的分?jǐn)?shù)值相等，則AUC指標(biāo)可定義為

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

精確度衡量排序前L條邊中預(yù)測(cè)的準(zhǔn)確度。將預(yù)測(cè)邊按相似性得分降序排序，假設(shè)前L的邊中有m條測(cè)試集中的邊，則精確度定義為

Precision=mL（45）

由于實(shí)驗(yàn)中所用網(wǎng)絡(luò)的規(guī)模各不相同，這里設(shè)置各網(wǎng)絡(luò)邊數(shù)的10%作為L的值。

3.3 實(shí)驗(yàn)結(jié)果分析

本次實(shí)驗(yàn)中，采用隨機(jī)抽樣法將實(shí)驗(yàn)數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集，訓(xùn)練集占比為0.9，所有結(jié)果均為100次獨(dú)立重復(fù)實(shí)驗(yàn)的平均值。為了驗(yàn)證分包準(zhǔn)則的有效性，在6個(gè)網(wǎng)絡(luò)上將HNBs指標(biāo)和TANs指標(biāo)作為基準(zhǔn)指標(biāo)設(shè)置兩組對(duì)比：HNBs與PHNBs對(duì)比、TANs與PTANs對(duì)比。

針對(duì)HNB和TAN分包后，能得到不同的預(yù)測(cè)結(jié)果。由表2可知，與HNBs指標(biāo)（HNBCN、HNBAA、HNBRA）相比，分包后的PHNBs指標(biāo)（PHNBCN、PHNBAA、PHNBRA）在不同網(wǎng)絡(luò)中均能取到最高的AUC值。PHNBs系列中，PHNBRA在C.elegans網(wǎng)絡(luò)上略低于原始的HNBRA，PHNBAA在Email網(wǎng)絡(luò)上略低于原始的HNBAA，相差均不超過1%。除此之外，每個(gè)網(wǎng)絡(luò)中的PHNBs指標(biāo)均優(yōu)于其對(duì)應(yīng)的原始指標(biāo)，這表明共鄰節(jié)點(diǎn)集合中存在部分共鄰節(jié)點(diǎn)獨(dú)立地影響連邊的形成，分類計(jì)算獨(dú)立節(jié)點(diǎn)貢獻(xiàn)和關(guān)聯(lián)節(jié)點(diǎn)貢獻(xiàn)的方法是可行的。同樣將TANs和PTANs作對(duì)比，PTANs系列中每個(gè)指標(biāo)（PTANCN、PTANAA、PTANRA）均優(yōu)于相應(yīng)未分包的TANs指標(biāo)（TANCN、TANAA、TANRA），且在每個(gè)網(wǎng)絡(luò)中PTANRA的預(yù)測(cè)精度最高，這說明分包準(zhǔn)則作為共鄰節(jié)點(diǎn)劃分依據(jù)應(yīng)用到TAN模型中是合理有效的。

在FWEW和FWFW網(wǎng)絡(luò)中，對(duì)HNB和TAN模型進(jìn)行分包改進(jìn)后AUC值提升較大。以HNBCN為例，PHNBCN的AUC值與之相比在FWEW網(wǎng)絡(luò)中提升了5.8%，在FWFW網(wǎng)絡(luò)中提升了12%，在其他網(wǎng)絡(luò)中提升范圍為0.08%～1.2%。PTANCN與TANCN相比AUC值在FWEW和FWFW網(wǎng)絡(luò)中分別提升了4.9%和11.6%，而在其他網(wǎng)絡(luò)中提升范圍為0.9%～1.4%。從表1中不難發(fā)現(xiàn)，F(xiàn)WEW和FWFW網(wǎng)絡(luò)的平均共鄰節(jié)點(diǎn)數(shù)較大，說明在共鄰節(jié)點(diǎn)富集的網(wǎng)絡(luò)上分類討論共鄰節(jié)點(diǎn)的貢獻(xiàn)能有效提升鏈路預(yù)測(cè)的性能。

表3給出了兩組對(duì)比模型的Precision值。結(jié)果表明，無論是HNBs還是TANs中的指標(biāo)，其分包后相似性指標(biāo)的Precision值在不同網(wǎng)絡(luò)中均有提升，這與AUC結(jié)果相同。橫向?qū)Ρ菻NBs和PHNBs的6個(gè)指標(biāo)，不難

發(fā)現(xiàn)每個(gè)網(wǎng)絡(luò)中最高的Precision值均在PHNBs中取得。同樣將TANs和PTANs的6個(gè)指標(biāo)進(jìn)行對(duì)比，每個(gè)網(wǎng)絡(luò)中最高的Precision值也在PHNBs中取得。從Precision結(jié)果可以看出，對(duì)HNB和TAN模型應(yīng)用分包準(zhǔn)則能夠提升預(yù)測(cè)的準(zhǔn)確度，進(jìn)一步驗(yàn)證了分包的混合樸素貝葉斯模型的有效性和可行性。

3.4 魯棒性分析

為了進(jìn)一步分析PHNB模型和PTAN模型的魯棒性，本部分測(cè)試在不同訓(xùn)練集比例下各指標(biāo)AUC和Precision結(jié)果的變化情況。從圖2可以看出，隨著訓(xùn)練集比例從0.9開始每次減少0.1直到0.6，每個(gè)網(wǎng)絡(luò)中各指標(biāo)的AUC值隨之降低，這是由于網(wǎng)絡(luò)的可觀測(cè)數(shù)據(jù)隨著訓(xùn)練集的變化而減少，導(dǎo)致了網(wǎng)絡(luò)的預(yù)測(cè)性能降低。當(dāng)各網(wǎng)絡(luò)的可觀測(cè)數(shù)據(jù)降低到60%時(shí)，6個(gè)網(wǎng)絡(luò)中PHNBs和PTANs指標(biāo)的AUC值相較于其未分包的原始指標(biāo)仍有不同程度的提升，這表明PHNB和PTAN模型的魯棒性較好。

從圖3可以看出，隨著訓(xùn)練集比例從0.9逐次減少0.1直到0.6，每個(gè)網(wǎng)絡(luò)中各指標(biāo)的Precision值隨之增加，這是因?yàn)镻recision關(guān)注前L條預(yù)測(cè)邊的準(zhǔn)確率，訓(xùn)練集比例越小，預(yù)測(cè)邊出現(xiàn)在測(cè)試集的可能性就越大，準(zhǔn)確率就越大。當(dāng)各網(wǎng)絡(luò)可觀測(cè)數(shù)據(jù)從90%降低到60%，整體上PHNBs和PTANs指標(biāo)相較于其未分包的原始指標(biāo)的預(yù)測(cè)性能更優(yōu)，進(jìn)一步驗(yàn)證了PHNB和PTAN模型具有良好的魯棒性。

4 結(jié)語

本文在HNB和TAN模型的基礎(chǔ)上，考慮到獨(dú)立的共鄰節(jié)點(diǎn)和關(guān)聯(lián)的共鄰節(jié)點(diǎn)對(duì)待測(cè)連邊有不同貢獻(xiàn)，設(shè)計(jì)了劃分共鄰節(jié)點(diǎn)的分包準(zhǔn)則并融入到HNB和TAN模型中。6個(gè)真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明，通過分包改進(jìn)后PHNB和PTAN模型在AUC和Precision標(biāo)準(zhǔn)下的預(yù)測(cè)性能優(yōu)于原始模型，而且具有良好的魯棒性。本文方法僅針對(duì)無權(quán)無向網(wǎng)絡(luò)，將此方法應(yīng)用到加權(quán)有向網(wǎng)絡(luò)或者多維網(wǎng)絡(luò)的工作有待進(jìn)一步開展。此外，在結(jié)構(gòu)特征不同的網(wǎng)絡(luò)上如何獲取預(yù)測(cè)性能最優(yōu)以及計(jì)算復(fù)雜度最優(yōu)的閾值也是下一步研究的重點(diǎn)。

參考文獻(xiàn)：

［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］ 郁湧， 王瑩港， 羅正國， 等. 基于聚類系數(shù)和節(jié)點(diǎn)中心性的鏈路預(yù)測(cè)算法［J］. 清華大學(xué)學(xué)報(bào)（自然科學(xué)版）， 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ī)游走鏈路預(yù)測(cè)算法［J］. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 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］ 伍杰華， 朱岸青， 蔡雪蓮， 等. 基于隱樸素貝葉斯模型的社會(huì)關(guān)系推薦［J］. 計(jì)算機(jī)應(yīng)用研究， 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.

（責(zé)任編輯 耿金花）