曾茜 韓華 李秋暉 李巧麗

摘要：

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

關(guān)鍵詞：

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

中圖分類號： TP393 文獻標(biāo)識碼：A

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

基金項目：

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

第一作者：

曾茜（1997-），女，湖北武漢人，碩士研究生，主要研究方向為鏈路預(yù)測、復(fù)雜網(wǎng)絡(luò)分析。

通信作者：

韓華（1975-），女，山東煙臺人，博士，教授，主要研究方向為復(fù)雜性分析與評價、經(jīng)濟控制與決策。

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

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

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

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

3.2 評價指標(biāo)

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

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

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

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

Precision=mL（45）

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

3.3 實驗結(jié)果分析

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

針對HNB和TAN分包后，能得到不同的預(yù)測結(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%。除此之外，每個網(wǎng)絡(luò)中的PHNBs指標(biāo)均優(yōu)于其對應(yīng)的原始指標(biāo)，這表明共鄰節(jié)點集合中存在部分共鄰節(jié)點獨立地影響連邊的形成，分類計算獨立節(jié)點貢獻和關(guān)聯(lián)節(jié)點貢獻的方法是可行的。同樣將TANs和PTANs作對比，PTANs系列中每個指標(biāo)（PTANCN、PTANAA、PTANRA）均優(yōu)于相應(yīng)未分包的TANs指標(biāo)（TANCN、TANAA、TANRA），且在每個網(wǎng)絡(luò)中PTANRA的預(yù)測精度最高，這說明分包準(zhǔn)則作為共鄰節(jié)點劃分依據(jù)應(yīng)用到TAN模型中是合理有效的。

在FWEW和FWFW網(wǎng)絡(luò)中，對HNB和TAN模型進行分包改進后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é)點數(shù)較大，說明在共鄰節(jié)點富集的網(wǎng)絡(luò)上分類討論共鄰節(jié)點的貢獻能有效提升鏈路預(yù)測的性能。

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

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

3.4 魯棒性分析

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

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

4 結(jié)語

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

參考文獻：

［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é)點中心性的鏈路預(yù)測算法［J］. 清華大學(xué)學(xué)報（自然科學(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］ 呂亞楠， 韓華， 賈承豐， 等. 基于有偏向的重啟隨機游走鏈路預(yù)測算法［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］ 伍杰華， 朱岸青， 蔡雪蓮， 等. 基于隱樸素貝葉斯模型的社會關(guān)系推薦［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é)任編輯 耿金花）