基于分包的混合樸素貝葉斯鏈路預測模型

曾茜 韓華 李秋暉 李巧麗

摘要：

隱樸素貝葉斯模型（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.

（責任編輯 耿金花）