基于有效路徑拓撲穩定性的鏈路預測方法

摘 要： 許多鏈路預測方法來源于復雜網絡中路徑上的資源傳輸過程，但缺少考慮路徑周圍結構的拓撲穩定性，使得路徑上的資源傳輸有效性不高。針對此問題，提出了基于有效路徑拓撲穩定性的鏈路預測方法。該方法首先利用路徑兩端節點間所有共同鄰居的聚類系數量化路徑周圍結構的拓撲穩定性；然后再利用兩端節點的度和共同鄰居個數量化預測節點間二階路徑上的雙向資源傳輸有效性；最終結合量化的拓撲結構穩定性和資源傳輸有效性定義有效路徑拓撲穩定性指標。通過九個網絡仿真表明，提出的指標具有較高的預測精度與良好的魯棒性。

關鍵詞： 復雜網絡； 有效路徑； 鏈路預測； 資源傳輸； 拓撲穩定性

中圖分類號： TP183"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-016-0090-06

doi：10.19734/j.issn.1001-3695.2021.06.0231

Link prediction method based on topology stability of effective path

Liu Yingjie1， Liu Shihu1， Xu Weihua2

（1.School of Mathematics amp; Computer Science， Yunnan Minzu University， Kunming 650504， China； 2.School of Artificial Intelligence， Southwest University， Chongqing 400715， China）

Abstract： Many link prediction methods come from the resource transmission process on the path in complex networks.However，they don’t take the topological stability of the structure around the path into account.So，the resources transmission effectiveness on the path is low.To solve this problem，this paper developed the prediction method based on topological stability of effective path.

Initially，this method used the clustering coefficients of all common neighbors between two

end nodes of the path to quantify the topological stability of the structure around the path.Then，it utilized the degree and common neighbor number of predicted nodes to quantify their bidirectional resource transmission effectiveness of the second-order path.

Finally，it combined the quantified topological stability with the resource transmission effectiveness to define the effective path topological stability index.Through nine network simulations provide that the proposed index possesses higher prediction accuracy and fine robustness.

Key words： complex network； effective path； link prediction； resource transmission； topological stability

0 引言

隨著網絡科學的蓬勃發展，復雜網絡在復雜系統［1］的分析和挖掘方面展現了重要作用［2，3］。復雜系統中實體和實體間的關系可用復雜網絡來抽象表示。常見的復雜網絡有社區網絡［4］、生物網絡［5］和引文網絡［6］等。鏈路預測作為復雜網絡中的重要研究工具［7］，旨在借助網絡中已有的拓撲信息來預測兩節點間存在連邊的可能性。這種預測既包含對未知連邊［8］的預測，也包含對未來連邊［9］的預測。未知連邊是指網絡中真實存在卻因信息缺失而未觀察到的連邊；未來連邊是指目前不存在，但隨著時間的變化在未來很有可能產生的連邊。近年來，對未知連邊的預測一直都是復雜網絡中的一個熱門研究課題。

鏈路預測在諸多領域中都具有重要的實際應用價值，因此受到不同背景研究者的廣泛關注。比如，在蛋白質—蛋白質相互作用網絡［10］、新陳代謝網絡［11］以及基因調控網絡［12］等生物網絡領域的研究中，使用鏈路預測技術指導實驗，不僅能提高實驗的成功率，還可以減少實際的實驗次數來降低實驗成本并加快揭示這些生物網絡的真實面目［13］。在社交網絡中，根據網友在網站中的瀏覽信息使用鏈路預測技術預測網友之間的好友關系并為其推薦合適的好友，可以增加網友們對該網站的使用量［14］。在電信網絡中使用鏈路預測技術能快速揭開隱藏的通聯關系，從而有助于發現電信詐騙的源頭［15，16］。此外，在電子商務網絡中根據顧客的購物需求和習慣使用鏈路預測技術推薦令其滿意的商品［17］，可為電商平臺創造巨大的商業價值。

現有的鏈路預測問題主要是基于節點相似性［18，19］的方法來展開研究的。基于節點相似性的鏈路預測方法因具有實現簡單、預測效果好等特點，所以多年來備受研究者的重視［20，21］。該方法通過度量網絡中兩節點的相似性，以表征它們之間存在連邊的可能性。因此，鏈路預測研究的關鍵問題是如何定義度量節點相似性的鏈路預測方法。目前，已提出了多種基于節點相似性的鏈路預測方法，比如根據兩節點度來定義節點相似性的偏好連接PA（preferential attachment）指標［22］，兩節點間共同鄰居的共享比例越高、兩節點就越相似的Jaccard指標［23］，考慮兩節點共同鄰居之間的連邊數量的CAR（cannistrai-alanis-ravai）指標［24］，以及兩節點度的乘積與它們共同鄰居數的期望值成正比的LHN指標［25］等。此外，常見的方法還有余弦相似性Salton指標［26］、用于量化新陳代謝網絡中每對反應物拓撲重疊性的HPI（hub promoted index）指標［27］、HDI（hub depressed index）指標［28］和用于生態數據研究的Sorensen指標［29］。近年來，已有文獻表明，網絡中的聚類結構可以提升大多數鏈路預測方法的預測精度［30，31］。此外，聚類系數作為描述網絡中拓撲結構特征的一個基本統計參數，可以度量任意一個節點的鄰居節點之間存在連邊的概率，進而能促進網絡中聚類結構的形成［32，33］。然而，現有的鏈路預測方法沒有綜合考慮到在進行資源傳輸的兩節點間，它們共同鄰居的聚類系數對端節點與共同鄰居之間的兩條資源傳輸路徑所在拓撲結構穩定性的影響。因為實際的資源傳輸過程中，路徑周圍結構的穩定性能減少路徑上大量的資源損失，使兩端節點接收到更多的資源量，從而使兩節點更相似，所以考慮路徑周圍結構的拓撲穩定性能提升鏈路預測方法的精度。

基于上述分析，為了提升鏈路預測方法的預測精度，本文結合了共同鄰居的聚類系數和路徑兩端節點之間的資源傳輸等網絡的拓撲信息，提出了一種基于有效路徑拓撲穩定性指標的鏈路預測方法。為了測試該指標的預測性能，本文在九個真實網絡中進行了仿真實驗。結果表明，相比現有的八個基于節點相似性的鏈路預測指標，有效路徑拓撲穩定性指標具有良好的預測性能和魯棒性。

4 實驗結果分析

為了驗證EPTS指標的預測性能，本文首先在九個網絡中將EPTS指標與現有的八個基于節點相似性的鏈路預測指標進行AUC值的比較；其次對實驗中各指標的復雜性進行分析；然后探究所有指標在不同數據集劃分比例下的魯棒性。

4.1 可行性分析

圖5給出了在多個不同類型的網絡中，ETPS指標與其他相似性指標的AUC結果對比情況。可以看出，在所有的九個網絡中，EPTS指標能在七個網絡中取得最高的AUC值，一定程度上說明了本文方法的有效性和可行性。

在實驗的其他八個對比指標中，PA指標僅考慮了節點的度信息，剩余的七個指標均考慮了網絡中節點之間的共同鄰居數。本文的EPTS指標不僅考慮了節點的度信息和節點之間的共同鄰居數，還將共同鄰居的聚類系數融入節點相似性的計算當中。結果表明，PA指標的AUC波動較大，僅在Wiki-vote網絡中表現較好；另外七個指標的AUC變化不大，但預測效果不太理想；EPTS指標在七個網絡中均取得了最高的AUC且在所有網絡中表現得相對穩定。不難看出，考慮了路徑周圍結構的拓撲穩定性和路徑上的資源傳輸有效性后，EPTS指標相比其他指標的AUC明顯提高了，這說明網絡結構的拓撲穩定性確實能夠促進其結構內部路徑上的資源傳輸有效性，使得路徑兩端節點彼此可以接收到更多的資源量，從而使得兩個節點更相似。總體上看，EPTS指標在King James、Net Science、Political Blogs、Polbooks、Metabolic、Lesmis和USAir等多個網絡中的AUC提升幅度較高，相比其余指標的AUC，提升比率能達到8.7%～49.1%，平均提升比例達到24.3%左右，而在Jazz和Wiki-vote網絡中分別略低于Salton和PA指標。

4.2 復雜性分析

表3給出了在九個網絡中計算各相似性指標的AUC所需的時間代價，每個值為對應實驗設置中進行獨立重復實驗次數的平均值，下畫線上的加粗數字為九個相似性指標中所需時間代價最多的一個。由表3可知，EPTS指標在Jazz、Metabolic、Political Blogs、USAir和Wiki-vote五個網絡中的時間代價略高于其他指標。在Net Science、King James、Lesmis和Polbooks四個網絡中，EPTS指標能夠在時間復雜性上低于HPI、HDI和PA等指標。總體來看，EPTS指標的時間代價在其他八個指標之間處于中等偏上的位置，時間復雜性上還需要進行改進。

4.3 魯棒性分析

為了進一步對EPTS指標的性能進行分析，本文將在不同的訓練集劃分比例p下測試EPTS指標與其余相似性指標在各網絡中的魯棒性。圖6給出了比例p從0.9開始每次減小0.1～0.5時各指標的AUC變化曲線。其中各指標在不同比例p下的AUC值仍然是對小于1 000個節點的網絡取1 000次獨立重復實驗結果的平均值，對大于1 000個節點的網絡取100次獨立重復實驗結果的平均值。

由圖6可知，多數指標的AUC曲線隨訓練集劃分比例p的減小而下降。因為隨著p減小，訓練集所占比例隨之減少，這使得網絡中的已知拓撲信息減少，所以許多指標的預測性能也隨之下降。在圖6中，EPTS指標的AUC曲線隨著p的減小而呈下降趨勢，但在僅有50%可觀測數據的條件下，卻依然能夠取得相對更好的AUC結果，這表明了EPTS指標在各個網絡中具有良好的魯棒性。總體而言，EPTS指標與HIP、HDP、CAR、Salton、Jaccard和Sorenson六個經典指標相比，其在各網絡中的魯棒性較為明顯。

其中，HDI指標和HPI指標的變化范圍雖不大，但它們的AUC曲線在多數網絡中都明顯低于EPTS指標。實驗中還發現了兩個有趣的現象：a）LHN指標的AUC曲線在Metabolic、USAir和Political Blogs這三個網絡中隨著比例p的減小而上升，說明LHN指標在網絡已知信息較少時或許會有更好的預測性能，但是圖6中顯示它們的AUC曲線在不同比例p下始終都低于EPTS指標；b）對于PA指標，除了在Lesmis網絡中PA指標的AUC曲線隨著比例p的減小而下降比較明顯以外，在其他的網絡中幾乎不會受到由p的變化所帶來的負面影響，不過PA指標在多數網絡中的AUC曲線仍然是低于EPTS指標的，尤其是在King James、Jazz和Polbooks三個網絡中較為明顯。

上述的兩個實驗現象說明了在鏈路預測問題中，利用了節點相似性的指標在預測性能上可能會對目標網絡具有不同程度的偏好，正如在實驗中所發現的不同指標的預測性能隨訓練集劃分比例p變化的敏感程度不同。因此，在對鏈路預測問題進行研究時，可以根據目標網絡的拓撲結構特征對某一類鏈路預測指標不斷地進行測試，以提升該指標的預測性能。比如給所提出的鏈路預測指標加上一個可調節的參數，以降低不同網絡拓撲結構對鏈路預測指標在計算節點相似性時的影響強度，這也是本文接下來將要進行的研究工作。

5 結束語

針對資源傳輸過程中網絡拓撲結構穩定性影響路徑的資源傳輸有效性的情況，本文提出了一種基于有效路徑拓撲穩定性的鏈路預測方法。該方法以共同鄰居的聚類系數和路徑節點間的資源傳輸為落腳點，從拓撲結構穩定性促進路徑的資源傳輸有效性角度，提出了一種基于有效路徑拓撲穩定性指標的鏈路預測方法。在九個真實網絡中的實驗結果表明，有效路徑拓撲穩定性指標相比現有的指標既能提升預測精度，也具有良好的魯棒性，不過在時間復雜性方面，有效路徑拓撲穩定性指標相比其他指標要略微偏高。在后續的工作中，將對本文指標的時間復雜性進行改進，并根據網絡拓撲結構中的不同特征為該指標設計出合適的調節參數來進行豐富和擴展，以此作為下一步的研究方向，使得有效路徑拓撲穩定性指標更具研究意義。

參考文獻：

［1］Hofmann S G，Curtiss J，McNally R J.A complex network perspective on clinical science［J］.Perspectives on Psychological Science，2016，11（5）：597-605.

［2］Batool K，Niazi M A.Modeling the Internet of Things：a hybrid mode-ling approach using complex networks and agent-based models［J］.Complex Adaptive Systems Modeling，2017，5（1）：1-19.

［3］劉樹新，季新生，劉彩霞，等.一種信息傳播促進網絡增長的網絡演化模型［J］.物理學報，2014，63（15）：1-11. （Liu Shuxin，Ji Xinsheng，Liu Caixia，et al.A complex network evolution model for network growth promoted by information transmission［J］.Acta Phy-sica Sinica，2014，63（15）：1-11.）

［4］Hoyt J R，Langwig K E，White J P，et al.Cryptic connections illuminate pathogen transmission within community networks［J］.Nature，2018，563（7733）：710-713.

［5］Valdeolivas A，Tichit L，Navarro C，et al.Random walk with restart on multiplex and heterogeneous biological networks［J］.Bioinformatics，2019，35（3）：497-505.

［6］Ding Ying.Scientific collaboration and endorsement：network analysis of coauthorship and citation networks［J］.Journal of Informetrics，2011，5（1）：187-203.

［7］Benson A R，Abebe R，Schaub M T，et al.Simplicial closure and higherorder link prediction［J］.Proceedings of the National Academy of Sciences，2018，115（48）：11221-11230.

［8］Yang Yang，Lichtenwalter R N，Chawla N V.Evaluating link prediction methods［J］.Knowledge and Information Systems，2015，45（3）：751-782.

［9］Li Shibao，Huang Junwei，Zhang Zhigang，et al.Similarity-based future common neighbors model for link prediction in complex networks［J］.Scientific Reports，2018，8（1）：1-11.

［10］Huang Zhian，Huang Yuan，You Zhuhong，et al.Novel link prediction for large-scale miRNA-lncRNA interaction network in a bipartite graph［J］.BMC Medical Genomics，2018，11（6）：17-27.

［11］Zhang Hui，Ming Zhong，Fan Chunlong，et al.A path-based computational model for long non-coding RNA-protein interaction prediction［J］.Genomics，2020，112（2）：1754-1760.

［12］Chen Xing，Xie Di，Wang Lei，et al.BNPMDA：bipartite network projection for MiRNA-disease association prediction［J］.Bioinformatics，2018，34（18）：3178-3186.

［13］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.

［14］Esslimani I，Brun A，Boyer A.Densifying a behavioral recommender system by social networks link prediction methods［J］.Social Network Analysis and Mining，2011，1（3）：159-172.

［15］Lyu Linyuan，Zhou Tao.Link prediction in complex networks：a survey［J］.Physica A：Statistical Mechanics and Its Applications，2011，390（6）：1150-1170.

［16］Martínez V，Berzal F，Cubero J C.A survey of link prediction in complex networks［J］.ACM Computing Surveys，2016，49（4）：1-33.

［17］Zhang Lingling，Li Jing，Zhang Qiuliu，et al.Domain knowledge-based link prediction in customer-product bipartite graph for product recommendation［J］.International Journal of Information Technology amp; Decision Making，2019，18（1）：311-338.

［18］Lyu Linyuan.Link prediction on complex networks［J］.Journal of University of Electronic Science and Technology of China，2010，39（5）：651-661.

［19］Yu Chuanming，Zhao Xiaoli，An Lu，et al.Similarity-based link prediction in social networks：a path and node combined approach［J］.Journal of Information Science，2017，43（5）：683-695.

［20］Dai Caiyan，Chen Ling，Bin Li.Link prediction in complex network based on modularity［J］.Soft Computing，2017，21（15）：4197-4214.

［21］Lu Yiding，Guo Yufan，Korhonen A.Link prediction in drug-target interactions network using similarity indices［J］.BMC Bioinformatics，2017，18（1）：1-9.

［22］Xie Yanbo，Zhou Tao，Wang Binghong.Scale-free networks without growth［J］.Physica A：Statistical Mechanics and its Applications，2008，387（7）：1683-1688.

［23］Tuan T M，Chuan P M，Ali M，et al.Fuzzy and neutrosophic modeling for link prediction in social networks［J］.Evolving Systems，2019，10（4）：629-634.

［24］Cannistraci C V，Alanis-Lobato G，Ravasi T.From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks［J］.Scientific Reports，2013，3（1）：1-14.

［25］Leicht E A，Holme P，Newman M E J.Vertex similarity in networks［J］.Physical Review E，2006，73（2）：026120.

［26］Lyu Linyuan，Jin Cihang，Zhou Tao.Similarity index based on local paths for link prediction of complex networks［J］.Physical Review E，2009，80（4）：046122.

［27］Bliss C A，Frank M R，Danforth C M，et al.An evolutionary algorithm approach to link prediction in dynamic social networks［J］.Journal of Computational Science，2014，5（5）：750-764.

［28］Zhou Tao，Lyu Linyuan，Zhang Yicheng.Predicting missing links via local information［J］.The European Physical Journal B，2009，71（4）：623-630.

［29］Mahapatra R，Samanta S，Pal M，et al.RSM index：a new way of link prediction in social networks［J］.Journal of Intelligent amp; Fuzzy Systems，2019，37（2）：2137-2151.

［30］Wang Meixi，Lou Xuyang，Cui Baotong.A degree-related and link clustering coefficient approach for link prediction in complex networks［J］.The European Physical Journal B，2021，94（1）：1-12.

［31］高楊，張燕平，錢付蘭，等.結合節點度和節點聚類系數的鏈路預測算法［J］.小型微型計算機系統，2017，38（7）：1436-1441. （Gao Yang，Zhang Yanping，Qian Fulan，et al.Combined with node degree and node clustering coefficient of link prediction algorithm［J］.Journal of Chinese Computer Systems，2017，38（7）：1436-1441.）

［32］McAssey M P，Bijma F.A clustering coefficient for complete weighted networks［J］.Network Science，2015，3（2）：183-195.

［33］Yin H，Benson A R，Leskovec J.Higher-order clustering in networks［J］.Physical Review E，2018，97（5）：052306.

［34］Yang Jinxuan，Zhang Xiaodong.Predicting missing links in complex networks based on common neighbors and distance［J］.Scientific Reports，2016，6（1）：1-10.

［35］Zhu Yuxiao，Lyu Linyuan，Zhang Qianming，et al.Uncovering missing links with cold ends［J］.Physica A：Statistical Mechanics and Its Applications，2012，391（22）：5769-5778.

［36］Feng Xu，Zhao Jichang，Xu Ke.Link prediction in complex networks：a clustering perspective［J］.The European Physical Journal B，2012，85（1）：1-9.

［37］王凱，李星，蘭巨龍，等.一種基于資源傳輸路徑拓撲有效性的鏈路預測方法［J］.電子與信息學報，2020，42（3）：653-660. （Wang Kai，Li Xing，Lan Julong，et al.A new link prediction method for complex networks based on topological effectiveness of resource transmission paths［J］.Journal of Electronics amp; Information Technology，2020，42（3）：653-660.）

［38］李治成，吉立新，劉樹新，等.基于拓撲穩定性的有向網絡鏈路預測方法［J］.計算機應用研究，2020，37（12）：3744-3748. （Li Zhicheng，Ji Lixin，Liu Shuxin，et al.Link prediction method based on topological stability in directed network［J］.Application Research of Computers，2020，37（12）：3744-3748.）

［39］Liu Haifeng，Hu Zheng，Haddadi H，et al.Hidden link prediction based on node centrality and weak ties［J］.Europhysics Letters，2013，101（1）：18004-18010.

［40］Tian Yang，Li Han，Zhu Xuzhen，et al.Link prediction based on combined influence and effective path［J］.International Journal of Modern Physics B，2019，33（22）：1950249-1950262.