<address id="japib"><nav id="japib"></nav></address>

<cite id="japib"></cite>

        一種基于MH改進的重啟隨機游走鏈路預測算法

        呂亮 何敏 易燦

        引用本文:
        Citation:

        一種基于MH改進的重啟隨機游走鏈路預測算法

          作者簡介: 呂 亮(1994?),男,湖北人,碩士生,主要研究社會網絡、鏈路預測. E-mail:leonlv1004@mail.ynu.edu.cn;
          通訊作者: 何敏, hemin@ynu.edu.cn
        • 中圖分類號: TP391

        An improved MH link prediction algorithm combining with Random Walk with Restart

          Corresponding author: HE Min, hemin@ynu.edu.cn ;
        • CLC number: TP391

        • 摘要: 基本隨機游走相似性指標由于其轉移概率僅由當前節點的度決定,影響鏈路預測效果. 鑒于此,在MH算法的基礎上,充分利用鄰居節點的度信息,并采用將當前節點的自環率按鄰居節點的度值加權分配給鄰居節點的方法重構轉移概率矩陣,再融合重啟隨機游走(Random Walk with Restart, RWR)相似性指標,提出一種改進MH的鏈路預測算法. 首先根據當前節點與鄰居節點的度信息重新定義節點間的轉移概率,然后將新的轉移概率重構成概率矩陣,最后融合RWR相似性指標進行鏈路預測實驗. 實驗表明,新算法相較于RWR、CN等7種基準算法在AUC指標上均有提升,在排序分指標上也有所改善;AUC指標上最高可提升3.98%,排序分指標上最高下降1.92%,提升了鏈路預測的準確性.
        • 圖 1  簡單網絡示意圖

          Figure 1.  The diagrammatic graph of a simple network

          圖 2  邊集維恩圖

          Figure 2.  Venn diagram of edge set

          圖 3  MHRW轉移概率圖

          Figure 3.  The transition probability graph of MHRW

          圖 4  IMRWR轉移概率圖

          Figure 4.  The transition probability graph of IMRWR

          圖 5  局部相似性指標(a)與路徑相似性指標(b)比較直方圖

          Figure 5.  The comparison histogram of local similarity index (a) and path similarity index (b)

          圖 6  AUC指標(a)與排序分指標(b)比較折線圖

          Figure 6.  The comparison line chart of AUC index (a) and Ranking Score index (b)

          表 1  各數據集的網絡結構特征

          Table 1.  Network structure features of each dataset

          網絡NHKCD
          USAir[36] 332 212612.8070.7496
          PolBooks[36] 105 441 8.4000.4887
          E-mail[36]1133 5451 9.6220.2208
          Karate[36] 34 78 4.5880.5715
          Dolphin[37] 62 159 5.1260.2598
          PolBlogs[38]12221671427.3550.3208
          C.elegens[39] 297 214814.4650.2925
          下載: 導出CSV

          表 2  各數據集在不同的基準方法下 AUC 值

          Table 2.  The AUC value of each data set under different benchmark methods

          網絡IMRWRMHRWRWRCNHPIAAPAKatzACT
          USAir[36]0.95270.95230.94090.94340.87910.95020.90070.93360.8994
          PolBooks[36]0.91310.90300.90020.87880.89070.89500.66750.89890.7565
          E-mail[36]0.92850.92790.92280.85420.85000.85560.79970.91550.8074
          Karate[36]0.86510.73000.83960.68080.68920.70900.67180.72410.6402
          Dolphin[37]0.85310.84910.81330.77850.77420.79190.67260.82270.7734
          PolBlogs[38]0.93310.92820.92310.91980.85260.92370.90530.92300.8885
          C.elegens[39]0.89250.86360.85790.84990.80620.86040.75510.85240.7392
          下載: 導出CSV

          表 3  各數據集在不同的基準方法下 排序分 值

          Table 3.  The Ranking Score value of each data set under different benchmark methods

          網絡IMRWRMHRWRWR
          USAir[36]0.27470.27520.2807
          PolBooks[36]0.29910.30420.3056
          E-mail[36]0.28590.28630.2887
          Karate[36]0.35310.42040.3655
          Dolphin[37]0.34010.34210.3593
          PolBlogs[38]0.28370.28610.2887
          C.elegens[36]0.30500.31880.3225
          下載: 導出CSV
          幸运快三
        • [1] Wang S, Du Y, Deng Y, et al. A new measure of identifying influential nodes: Efficiency centrality[J]. Communications in Nonlinear Science and Numerical Simulation, 2017, 47: 151-163. DOI:  10.1016/j.cnsns.2016.11.008.
          [2] Grover A, Leskovec J. node2vec: Scalable feature learning for networks[C]//22th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016, San Francisco, USA, 2016: 855-864. DOI:  10.1145/2939672.2939754
          [3] Cao Z, Wang L, de Melo G, et al. Link prediction via subgraph embedding-based convex matrix completion[C]//32th AAAI Conference on Artificial Intelligence, AAAI 2018, New Orleans, USA, 2018: 2 803-2 810.
          [4] Wang Z, Liang J, Li R, et al. A fusion probability matrix factorization framework for link prediction[J]. Knowledge Based Systems, 2018, 159: 72-85. DOI:  10.1016/j.knosys.2018.06.005.
          [5] Jiao P, Cai F, Feng Y, et al. Link predication based on matrix factorization by fusion of multi class organizations of the network[J]. Scientific Reports, 2017, 7(1): 8 937. DOI:  10.1038/s41598-017-09081-9.
          [6] Yin L, Zheng H, Bian T, et al. An evidential link prediction method and link predictability based on Shannon entropy[J]. Physica A: Statistical Mechanics and its Applications, 2017, 482: 699-712. DOI:  10.1016/j.physa.2017.04.106.
          [7] Luo P, Wu C, Li Y, et al. Link prediction measures considering different neighbors' effects and application in social networks[J]. International Journal of Modern Physics C, 2017, 28(3): 1 750 033. DOI:  10.1142/S0129183117500334.
          [8] Zhang C, Zeng A. Prediction of missing links and reconstruction of complex networks[J]. International Journal of Modern Physics C, 2016, 27(10): 1 650 120. DOI:  10.1142/S0129183116501205.
          [9] Zhang P, Wang X, Wang F, et al. Measuring the robustness of link prediction algorithms under noisy environment[J]. Scientific Reports, 2016, 6(1): 18 881. DOI:  10.1038/srep18881.
          [10] Liu Y, Zhao C, Wang X, 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. DOI:  10.1016/j.physa.2016.02.014.
          [11] 呂琳媛. 復雜網絡鏈路預測[J]. 電子科技大學學報, 2010, 39(5): 651-661. Lyu L Y. Link Prediction on Complex Networks[J]. Journal of University of Electronic Science and Technology of China, 2010, 39(5): 651-661.
          [12] Hasan M A, Chaoji V, Salem S, et al. Link prediction using supervised learning[C]//Proceedings of SDM: Workshop on Link Analysis, Counter-terrorism and Security, LACTS 2006, San Diego, USA, 2006.
          [13] Lyu L, Zhou T. Link prediction in complex networks: A survey[J]. Physica A: Statistical Mechanics and its Applications, 2011, 390(6): 1 150-1 170. DOI:  10.1016/j.physa.2010.11.027.
          [14] 陳維政, 張巖, 李曉明. 網絡表示學習[J]. 大數據, 2015, 1(3): 8-22. Chen W Z, Zhang Y, Li X M. Network representation learning[J]. Big Data Research, 2015, 1(3): 8-22.
          [15] Mikolov T, Sutskever I, Chen K, et al. Distributed Representations of Words and Phrases and their Compositionality[C]//27th Annual Conference on Neural Information Processing Systems, NIPS 2013, Lake Tahoe, USA, 2013: 3 111-3 119.
          [16] Perozzi B, Alrfou R, Skiena S, et al. DeepWalk: Online learning of social representations[C]//20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2014, New York, USA, 2014: 701-710. DOI:  10.1145/2623330.2623732
          [17] Metropolis N, Rosenbluth A W, Rosenbluth M N, et al. Equation of state calculations by fast computing machines[J]. Journal of Chemical Physics, 1953, 21(6): 1 087-1 092. DOI:  10.1063/1.1699114.
          [18] Gjoka M, Kurant M, Butts C T, et al. Walking in Facebook: A case study of unbiased sampling of OSNs[C]// International Conference on Computer Communications, IEEE INFOCOM 2010, San Diego, USA, 2010: 2 498-2 506.
          [19] 王棟, 李振宇, 謝高崗. 在線社會網絡無偏采樣技術[J]. 計算機研究與發展, 2016, 53(5): 949-967. Wang D, Li Z Y, Xie G G. Unbiased sampling technologies on online social network[J]. Journal of Computer Research and Development, 2016, 53(5): 949-967.
          [20] 王文濤, 黃燁, 吳淋濤, 等. 基于改進隨機游走的網絡表示學習算法[J]. 計算機應用, 2019, 39(3): 651-655. Wang W T, Huang Y, Wu L T, et al. Network representation learning algorithm based on improved random walk[J]. Journal of Computer Applications, 2019, 39(3): 651-655.
          [21] 劉思, 劉海, 陳啟買, 等. 基于網絡表示學習與隨機游走的鏈路預測算法[J]. 計算機應用, 2017, 37(8): 2 234-2 239. DOI:  10.11772/j.issn.1001-9081.2017.08.2234. Liu S, Liu H, Chen Q M, et al. Link prediction algorithm based on network representation learning and random walk[J]. Journal of Computer Applications, 2017, 37(8): 2 234-2 239.
          [22] Jin W, Jung J, Kang U, et al. Supervised and extended restart in random walks for ranking and link prediction in networks[J]. PLoS ONE, 2019, 14(3): e0213857. DOI:  10.1371/journal.pone.0213857.
          [23] 呂亞楠, 韓華, 賈承豐, 等. 基于有偏向的重啟隨機游走鏈路預測算法[J]. 復雜系統與復雜性科學, 2018, 15(4): 17-24. DOI:  10.13306/j.1672-3813.2018.04.003. Lyu Y N, Han H, Jia C F, et al. Link prediction algorithm based on biased random walk with restar[J]. Complex Systems and Complexity Science, 2018, 15(4): 17-24.
          [24] 李舟軍, 范宇, 吳賢杰. 面向自然語言處理的預訓練技術研究綜述[J]. 計算機科學, 2020, 47(3): 162-173. Li Z J, Fan Y, Wu X J. Survey of natural language Processing pretraining techniques[J]. Computer Science, 2020, 47(3): 162-173.
          [25] Tong H, Faloutsos C, Pan J, et al. Fast random walk with restart and its applications[C]//6th International Conference on Data Mining, ICDM 2006, Hong Kong, China, 2006: 613-622.
          [26] 鄭偉, 王朝坤, 劉璋, 等. 一種基于隨機游走模型的多標簽分類算法[J]. 計算機學報, 2010, 33(8): 1 418-1 426. DOI:  10.3724/SP.J.1016.2010.01418. Zheng W, Wang C K, Liu Z, et al. A multi-label classification algorithm based on random walk model[J]. Chinese Journal of Computers, 2010, 33(8): 1 418-1 426.
          [27] Lorrain F, White H C. Structural equivalence of individuals in social networks[J]. Journal of Mathematical Sociology, 1971, 1(1): 49-80. DOI:  10.1080/0022250X.1971.9989788.
          [28] Ravasz E, Somera A L, Mongru D A, et al. Hierarchical organization of modularity in metabolic networks[J]. Science, 2002, 297(5586): 1 551-1 555. DOI:  10.1126/science.1073374.
          [29] Adamic L A, Adar E. Friends and neighbors on the Web[J]. Social Networks, 2003, 25(3): 211-230. DOI:  10.1016/S0378-8733(03)00009-1.
          [30] Zhou T, Lyu L, Zhang Y, et al. Predicting missing links via local information[J]. The European Physical Journal B: Condensed Matter and Complex Systems, 2009, 71(4): 623-630. DOI:  10.1140/epjb/e2009-00335-8.
          [31] Katz L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39-43. DOI:  10.1007/BF02289026.
          [32] Klein D J, Randic M. Resistance distance[J]. Journal of Mathematical Chemistry, 1993, 12(1): 81-95. DOI:  10.1007/BF01164627.
          [33] Hanley J A, Mcneil B J. The meaning and use of the area under a Receiver Operating Characteristic (ROC) curve[J]. Radiology, 1982, 143(1): 29-36. DOI:  10.1148/radiology.143.1.7063747.
          [34] Herlocker J L, Konstan J A, Terveen L, et al. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems, 2004, 22(1): 5-53. DOI:  10.1145/963770.963772.
          [35] Zhou T, Ren J, Medo M, et al. Bipartite network projection and personal recommendation[J]. Physical Review E, 2007, 76(4): 046 115. DOI:  10.1103/PhysRevE.76.046115.
          [36] Li L, Fang S, Bai S, et al. Effective link prediction based on community relationship strength[J]. IEEE Access, 2019, 7: 43 233-43 248. DOI:  10.1109/access.2019.2908208.
          [37] Lusseau D, Schneider K, Boisseau O, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405. DOI:  10.1007/s00265-003-0651-y.
          [38] Adamic L, Glance N. The political blogosphere and the 2004 U. S. election: Divide they blog [C]//3th International Workshop on Link Discovery, linkKDD 2005, New York, USA, 2005: 36-43.
          [39] Watts D J, Strogatz S H. Collective dynamics of ‘small-world' networds[J]. Nature, 1998, 393(6684): 440-442. DOI:  10.1038/30918.
        • [1] 張強龍華王晨歌邵玉斌 . 基于有向通信網絡的鏈路重要性評價方法*. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20160096
          [2] 陳為民徐東霞 . 一種基于灰度相似性的指紋紋線密度提取方法. 云南大學學報(自然科學版),
          [3] 于佳麗郭敏 . 融合灰度和梯度方向信息的隨機游走的圖像分割. 云南大學學報(自然科學版),
          [4] 王長城周冬明劉琰煜謝詩冬 . 多尺度形態聚焦測量和優化隨機游走的多聚焦圖像融合算法. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20200019
          [5] 何樹紅夏梓祥 . 隨機利率下時間盈余風險模型的破產概率. 云南大學學報(自然科學版),
          [6] 牛勤趙東風何敏 . 概率函數檢測隨機多址接入無線傳感器網絡MAC協議分析. 云南大學學報(自然科學版),
          [7] 李春芬趙東風丁洪偉 . 雙時二維概率多通道多業務隨機多址協議分析. 云南大學學報(自然科學版),
          [8] 錢民唐克生 . 基于定性動態概率網絡的交通狀態預測及改進. 云南大學學報(自然科學版),
          [9] 唐菁敏張曉潁曹操馬社方 . 基于粒子群算法的認知無線電下行鏈路中的OFDMA資源分配算法. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20150023
          [10] 佘明輝林琳趙東風 . 自適應多通道二維概率型時隙式隨機多址無線通信網絡協議分析. 云南大學學報(自然科學版),
          [11] 黃海群劉琳肖維毅堯珍玉王亞龍 . 成型紙上香料單體在卷煙主流煙氣中的轉移率研究. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20150326
          [12] 馮源朱建華肖文發畢艷玲皇寶林溫慶忠鄧喜慶 . 迪慶州云杉老齡林生態系統碳轉移. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20170320
          [13] 王文強李壽佛黃山 . 非線性隨機延遲微分方程半隱式Euler方法的收斂性. 云南大學學報(自然科學版),
          [14] 劉飛虎郭鴻彥鄧綱頓昊陽李飛楊明 . 大麻莖皮出麻率早期非破壞性預測技術研究. 云南大學學報(自然科學版),
          [15] 王崢包桂蓉王華李法社李秀鳳陳曉萍毛朋濤 . 焙燒溫度對Cu/Mg/Al催化劑催化纖維素轉移加氫液化的影響. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20130440
          [16] 白慧吳戰平龍俐周濤 . 基于標準化前期降水指數的氣象干旱指標在貴州的適用性分析. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20120483
          [17] 倉定幫陳藏宋曉秋 . 雙連續C半群的概率逼近問題. 云南大學學報(自然科學版),
          [18] 喬克林李晉枝何樹紅 . 復合二項風險模型的破產概率. 云南大學學報(自然科學版),
          [19] 楊善兵房厚慶 . 兩相依聚集索賠風險模型的生存概率. 云南大學學報(自然科學版),
          [20] 何樹紅馬麗娟趙金娥 . 帶干擾的廣義Poisson風險模型的破產概率. 云南大學學報(自然科學版),
        • 加載中
        圖(6)表(3)
        計量
        • 文章訪問數:  245
        • HTML全文瀏覽量:  249
        • PDF下載量:  12
        • 被引次數: 0
        出版歷程
        • 收稿日期:  2020-05-18
        • 網絡出版日期:  2020-09-22

        一種基于MH改進的重啟隨機游走鏈路預測算法

          作者簡介:呂 亮(1994?),男,湖北人,碩士生,主要研究社會網絡、鏈路預測. E-mail:leonlv1004@mail.ynu.edu.cn
          通訊作者: 何敏, hemin@ynu.edu.cn
        • 云南大學 信息學院,云南 昆明 650500

        摘要: 基本隨機游走相似性指標由于其轉移概率僅由當前節點的度決定,影響鏈路預測效果. 鑒于此,在MH算法的基礎上,充分利用鄰居節點的度信息,并采用將當前節點的自環率按鄰居節點的度值加權分配給鄰居節點的方法重構轉移概率矩陣,再融合重啟隨機游走(Random Walk with Restart, RWR)相似性指標,提出一種改進MH的鏈路預測算法. 首先根據當前節點與鄰居節點的度信息重新定義節點間的轉移概率,然后將新的轉移概率重構成概率矩陣,最后融合RWR相似性指標進行鏈路預測實驗. 實驗表明,新算法相較于RWR、CN等7種基準算法在AUC指標上均有提升,在排序分指標上也有所改善;AUC指標上最高可提升3.98%,排序分指標上最高下降1.92%,提升了鏈路預測的準確性.

        English Abstract

        • 當今社會,復雜網絡無處不在[1]. 網絡由節點和連邊構成,節點表示不同的事物;連邊表示事物間的聯系,即事物間的鏈路關系. 鏈路預測可以幫助學者們分析復雜網絡中事物間的聯接關系,因而得到了廣泛的研究[2].

          鏈路預測是網絡科學和機器學習的基礎[3],也是數據分析中一個重要的研究課題[4]. 鏈路預測是對復雜網絡中潛在的或未被發現的鏈接進行預測[5],具有重要的理論價值和實際意義[6]. 在現實生活中,鏈路預測有著廣泛的應用,例如,好友推薦[7]、網絡重構[8]、社區發現[9]等. 在解釋網絡演化的過程中,鏈路預測也起著重要作用[10]. 因此,如何提高鏈路預測的準確性,成為研究復雜網絡的核心內容之一. 基本的鏈路預測算法分為兩大類,一是基于節點相似性指標[11],二是基于機器學習算法[12].

          基于節點相似性指標的鏈路預測算法簡單、實用,一直是研究的熱點. 相似性理論認為,網絡中兩個節點的結構特征越相似,它們之間產生鏈接的可能性越大[13]. 近年來,機器學習算法的性能大幅提升,學者們將其引入鏈路預測以提升預測效果,其中,網絡表示學習 (Network Presentation Learning,NPL)算法被大量應用[14]. Mikolov等[15]提出的神經網絡模型Word2vec在詞嵌入向量中取得良好效果;Perozzi等[16]提出的DeepWalk模型,利用隨機游走 (Random Walk,RW)進行采樣,結合Word2vec模型,得到節點的向量表示,并應用于鏈路預測,效果顯著. Gjoka等[17]借鑒MH (Metropolis-Hasting)算法,改變RW等概率采樣鄰居節點的策略,提出無偏采樣算法(Metropolis-Hasting Random Walk,MHRW),其采樣的樣本集更能全面的表達原始網絡的結構特征[18-19]. 王文濤等[20]基于MHRW算法,刪除自環率,設計出RLP-MHRW (Remove self-Loop Probability for MHRW)算法,提高了NLP的表示性能. 劉思等[21]利用DeepWalk模型通過將節點表征到低維向量空間獲得節點的潛在相似性來進行鏈路預測. Jin等[22]提出有擴展和監督的重啟隨機游走 (Random Walk with Restart,RWR)算法,使隨機游走更具表現性,并將其應用于排序和鏈路預測. 呂亞楠等[23]考慮節點度值對粒子轉移概率的影響,提出有偏向的鏈路預測算法,提升了預測的AUC指標.

          基本隨機游走相似性指標僅考慮當前節點的度對轉移概率的影響而忽略了鄰居節點的貢獻,影響鏈路預測效果. 因此,本文在MH的基礎上,提出一種改進的重啟隨機游走鏈路預測算法 (Improved MH with RWR,IMRWR). 算法在定義節點間的轉移概率時,綜合考慮當前節點及其鄰居節點的度對轉移概率的影響,并將節點的自環率按鄰居節點的度值加權分配給鄰居節點,以增大游走粒子轉移到與其更加相似的節點上的概率,從而獲得相似節點的隨機游走序列,提高預測的準確性.

          • 設網絡 $ G=(V,E) $ 表示無向圖,其中 $ V=\{{v}_{1},{v}_{2},\cdots ,{v}_{N}\} $ 表示節點集合,$ E= \{{e}_{i1,j1},{e}_{i2,j2},\cdots ,{e}_{iH,jH}\} $ 表示連邊集合,網絡中不允許有自連邊和重邊. 節點 $ {v}_{i},{v}_{j}\in V $ 間的連邊記為$ ({v}_{i},{v}_{j}) $$ {e}_{ij} $,節點 $ {v}_{i} $ 的鄰居節點集合記為 $ \Gamma \left(i\right) $,記 $ {k}_{i} $ 為節點 $ {v}_{i} $ 的度. 如圖1所示,$V\!=\!\{1, 2, 3, \mathrm{4,5}\}$,$E=\{\left(\mathrm{1,2}\right), \left(\mathrm{2,3}\right),\left(\mathrm{3,4}\right),\left(\mathrm{3,5}\right),\left(\mathrm{4,5}\right)\}$,$ \Gamma \left(3\right)=(\mathrm{2,4},5) $,$ {k}_{3}=3 $. 在進行鏈路預測實驗時,連邊集合 $ E $ 將被劃分成訓練集 $ {E}^{{\rm{T}}} $ 和測試集 $ {E}^{{\rm{P}}} $ 兩部分,有 $ E={E}^{{\rm{T}}}\cup {E}^{{\rm{P}}} $,$ {E}^{{\rm{T}}}\cap {E}^{{\rm{P}}}=\varnothing $,同時,由節點對構成的連邊 $ ({v}_{i},{v}_{j}) $ 將被賦予一個分數值 $ {s}_{ij} $.

            圖  1  簡單網絡示意圖

            Figure 1.  The diagrammatic graph of a simple network

            在自然語言處理 (Natural Language Processing,NLP)中[24],用鄰接矩陣 $ {{A}} $ 來表示并存儲網絡 $ G $,$ {{A}} $$ N\times N $ 的非零對稱矩陣,其中,元素 $ {a}_{ij} $ 定義為:

            $ {a}_{ij}=\left\{\begin{array}{l}1,\left({v}_{i},{v}_{j}\right)\subseteq E;\\ 0,{\text{其它}}.\end{array}\right.$

            假定:① $ U $ 為網絡中 $ N $ 個節點互連構成的邊集合,則 $ U $ 中有 $ (N(N-1))/2 $ 條邊;② $ B $ 為不存在邊集,有 $ B\in U $,$ B\notin E $;③ W為未知邊集,有 $ W\in U $,$ W\notin {E}^{{\rm{T}}} $$ W=B\cup {E}^{{\rm{P}}} $. 由圖1得,${{U}}=\{\left(\mathrm{1,2}\right), \left(\mathrm{1,3}\right),$$\left(\mathrm{1,4}\right),\left(\mathrm{1,5}\right),\left(\mathrm{2,3}\right),\left(\mathrm{2,4}\right),\left(\mathrm{2,5}\right)\left(\mathrm{3,4}\right),\left(\mathrm{3,5}\right),\left(\mathrm{4,5}\right)\}$,$ B= \{\left(\mathrm{1,3}\right),\left(\mathrm{1,4}\right),\left(\mathrm{1,5}\right),\left(\mathrm{2,4}\right),(\mathrm{2,5}\left)\right\} $,鏈路預測即是預測 $ B $ 中的邊未來會出現的概率大小. 圖2所示為邊集 $ {U,E,B,W,E}^{{\rm{T}}},{E}^{{\rm{P}}} $ 的關系維恩圖.

            圖  2  邊集維恩圖

            Figure 2.  Venn diagram of edge set

          • RWR[25]屬于基本的隨機游走相似性指標,其假設游走粒子在每走一步時都按一定的概率返回初始節點. 設粒子隨機選取下一個鄰居節點進行游走的概率為 $ c $,則隨機返回初始節點的概率為 $ 1-c $,可得到網絡的轉移概率矩陣 $ {{P}} $,其中,元素 $ {p}_{ij} $ 定義為:

            $ {p}_{ij}=\left\{\begin{array}{c}\dfrac{1}{{k}_{i}},{v}_{j}\subseteq \Gamma \left(i\right);\\ 0,{\text{其它}}.\end{array}\right. $

            若初始時刻,游走粒子在節點 $ {v}_{i} $ 處,則在 $ t+1 $ 時刻,該粒子到達網絡中各節點的概率向量為:

            $ {{\pi }}_{{i}}\left(t+1\right)=c {{{P}}}^{{\rm{T}}}{\pi }_{i}\left(t\right)+\left(1-c\right) {{{e}}}_{i}.$

            (3)式穩態解為:

            $ {{\pi }}_{{i}}=\left(1-c\right) {\left({{I}}-c{{{P}}}^{{\rm{T}}}\right)}^{-1}{{{e}}}_{i}, $

            其中,$ {{{e}}}_{i} $ 為粒子在節點 $ {v}_{i} $ 處的初始狀態,其與 $ {{I}} $ 同為單位矩陣.

            RWR相似性表達式為:

            $ {{{S}}}_{ij}={\pi }_{ij}+{\pi }_{ji},$

            其中,$ {\pi }_{ij} $ 為游走粒子從節點 $ {v}_{i} $ 出發最終游走到節點 $ {v}_{j} $ 的概率.

            由式(2)可知,在RWR方法中,游走粒子從節點 $ {v}_{i} $ 轉移到鄰居節點 $ {v}_{j} $ 的概率僅與當前節點 $ {v}_{i} $ 的度有關.

          • 在MH的基礎上,論文提出一種改進的算法IMRWR,同時考慮當前節點及其鄰居節點的度對轉移概率的影響,并將節點的自環率按鄰居節點的度值加權分配給鄰居節點,以增強轉移過程中表示出的節點相似性,再融合重啟隨機游走RWR相似性指標進行鏈路預測.

          • 基于MH算法的思想,Gjoka等結合RW提出無偏采樣算法MHRW[18],其定義節點間的轉移概率 $ {r}_{ij} $ 為:

            $ {r}_{ij}=\left\{\begin{array}{l}\dfrac{1}{{k}_{i}} \min\left(1,\dfrac{{k}_{i}}{{k}_{j}}\right),{v}_{j}\subseteq \Gamma \left(i\right);\\ 1-\displaystyle\sum\limits _{x}{r}_{i,x},{v}_{j}={v}_{i},{v}_{x}\subseteq \Gamma \left(i\right);\\ 0,{\text{其他}}.\end{array}\right. $

            $ {r}_{ij} $ 表示從節點 $ {v}_{i} $ 到其鄰居節點集合 $ \Gamma \left(i\right) $(包括自身節點)中選取節點 $ {v}_{j} $ 進行采樣的轉移概率,當 $ {v}_{j}={v}_{i} $ 時,表示繼續采樣當前節點.

          • 圖1的基礎上,根據式(6)計算出節點間的轉移概率,如圖3所示,自環率 $ {r}_{ii} $ 表示采樣當前節點的概率. 然而,節點 $ {v}_{1} $ 僅有一個鄰居 $ {v}_{2} $,若從節點 $ {v}_{1} $ 進行采樣,下一個節點只能是 $ {v}_{2} $,節點 $ {v}_{1},{v}_{2} $ 間的轉移概率應為 $ {r}_{\mathrm{1,2}}=1 $,但在MHRW中,節點 $ {v}_{1} $ 的自環率高達0.5,自采樣概率偏高,干擾了深度采樣,從而影響游走粒子的轉移過程.

            圖  3  MHRW轉移概率圖

            Figure 3.  The transition probability graph of MHRW

            為充分利用鄰居節點的度對網絡節點間的轉移概率的作用效果,同時消除自環率的不利影響,增加節點間的轉移概率,使游走粒子能夠轉移到更加相似的節點上,以提高節點間的相似性. 本文利用MHRW算法,將當前節點的自環率按鄰居節點的度值加權分配給鄰居節點,則節點間的轉移概率 $ {m}_{ij} $ 為:

            $ {m}_{ij}=\left\{\begin{array}{l}\dfrac{1}{{k}_{i}} \min\left(1,\dfrac{{k}_{i}}{{k}_{j}}\right)+\dfrac{{k}_{j}}{\displaystyle\sum _{x}{k}_{x}}\bullet {r}_{ii}{,v}_{j},{v}_{x}\subseteq \Gamma \left(i\right);\\ 0,{\text{其他}}.\end{array}\right.$

            其中,$ {r}_{ii} $ 由式(6)計算得到.

            由式(7)可知,游走粒子在選取鄰居節點進行游走時,既考慮當前節點的度又考慮其鄰居節點的度對轉移概率的影響,同時除去了自環率,使游走粒子能夠轉移到網絡的更深處尋找更加相似的節點. 如圖4所示,從節點 $ {v}_{1} $$ {v}_{2} $ 的轉移概率由原來的0.5提高到1,從節點 $ {v}_{5} $$ {v}_{3} $ 的轉移概率由原來的0.333提高到0.433,可見,本文算法利用鄰居節點的度信息增加了節點間的轉移概率,使游走粒子轉移到相似節點的概率增大.

            圖  4  IMRWR轉移概率圖

            Figure 4.  The transition probability graph of IMRWR

          • 根據式(6)得到MHRW算法的網絡轉移概率矩陣 $ {{R}} $. MHRW算法流程如下:

            算法1 MHRW算法

            輸入:網絡的鄰接矩陣 $ {{A}}=\left[{a}_{ij}\right] $,重啟因子 $ c $

            輸出:節點間的相似性分數矩陣 $ {{{S}}}_{R}=\left[{s}_{ij}\right] $

            步驟1 初始化:$ i=1 $,轉移矩陣 $ {{R}}\leftarrow {0}_{N\times N} $,相似 性分數矩陣 $ {{S}}\leftarrow {I}_{N\times N} $;

            步驟2 利用式(6)計算各節點與其鄰居節點間的轉移概率,得到網絡的真實轉移矩陣 $ {{R}} $;

            步驟3 若 $ i<=N $,執行下一步;否,執行步驟6;

            步驟4 利用式 $ {{\pi }}_{{i}}=\left(1-c\right){ \left(I-c{{{R}}}^{{\rm{T}}}\right)}^{-1}{{{e}}}_{i} $ 計算節點 $ {v}_{i} $ 與其他節點間的相似性分數值 $ {s}_{ij} $,并實時更新S;

            步驟5 判斷 $ {{S}} $ 是否收斂,若不收斂,$ i++ $,執行步驟3;否則,執行步驟6;

            步驟6 輸出 $ {{S}} $.

            根據式(7)得到本文IMRWR算法的網絡轉移概率矩陣 $ {{M}} $. IMRWR算法流程如下:

            算法2 IMRWR算法

            輸入:網絡的鄰接矩陣 $ {{A}}=\left[{a}_{ij}\right] $,重啟因子 $ c $

            輸出:節點間的相似性分數矩陣 $ {{{S}}}_{M}=\left[{s}_{ij}\right] $

            步驟1 初始化:$ i=1 $,轉移矩陣 $ {{M}}\leftarrow {0}_{N\times N} $,相似 性分數矩陣 $ {{S}}\leftarrow {I}_{N\times N} $;

            步驟2 利用式(7)計算各節點與其鄰居節點間的轉移概率,得到網絡的真實轉移矩陣 $ {{M}} $;

            步驟3 若 $ i<=N $,執行下一步;否,執行步驟6;

            步驟4 利用式 $ {{\pi }}_{{i}}=\left(1-c\right){ \left(I-c{M}^{{\rm{T}}}\right)}^{-1}{{\rm{e}}}_{i} $ 計算節點 $ {v}_{i} $ 與其他節點間的相似性分數值 $ {s}_{ij} $,并實時更新S;

            步驟5 判斷 $ {{S}} $ 是否收斂,若不收斂,$ i++ $,執行步驟3;否則,執行步驟6;

            步驟6 輸出 $ {{S}} $.

          • (1)因為轉移矩陣 $ {{R}},{{M}} $ 均為非負矩陣,游走粒子可以轉移到網絡 $ G $ 的任意節點, $ 0<c<1 $,則網絡中任意兩個節點 $ {v}_{i},{v}_{j} $ 間的相似性分數 $ {s}_{ij} $ 都能得到,所以 $ {{R}},{{M}} $ 是不可約的;

            (2)重啟隨機游走中,當游走粒子轉移到某一節點后,能否再次轉移到該節點是不確定的,說明粒子的轉移過程是非周期的;

            (3)粒子轉移到某一節點后返回初始節點,有可能在一定的步長內再次轉移到該節點,但兩次轉移到同一節點的步長可能相同也可能不同,說明粒子的轉移過程具有不確定性.

            由以上3點可得,本文IMRWR算法是各態歷經的[26],說明本文算法收斂,所以 $ {{S}} $ 也收斂.

          • 已經提出了許多經典的相似性鏈路預測算法,這些算法常作為基準方法與提出的新算法進行比較. 本文從3種類型的相似性指標中選取7種具有代表性的算法作為基準方法:①基于局部相似性的CN[27],HPI[28],AA[29],PA[30]指標;②基于路徑相似性的Katz[31]指標;③基于隨機游走相似性的RWR[25],ACT[32]指標.

            (1) 共同鄰居 (Common Neighbors,CN)指標 CN指標為最基本的相似性指標,其相似性定義為兩個節點間共同鄰居的數目. 其相似性表達式為:

            $ {S}_{ij}=\left|\Gamma \left(i\right)\cap \Gamma \left(j\right)\right|. $

            (2) 大度節點有利 (Hub Promoted Index,HPI)指標 HPI指標是在CN指標的基礎上,并考慮了兩個相連節點度的影響. 其相似性表達式為:

            $ {S}_{ij}=\frac{\left|\mathrm{\Gamma }\left(i\right)\cap \mathrm{\Gamma }\left(j\right)\right|}{\mathrm{m}\mathrm{i}\mathrm{n}\{{k}_{i},{k}_{j}\}}. $

            (3) AA(Adamic-Adar)指標 AA指標根據共同鄰居節點的度為每對節點賦予一個權重值. 其相似性表達式為:

            $ {S}_{ij}=\sum\limits _{z\in \mathrm{\Gamma }\left(i\right)\cap \mathrm{\Gamma }\left(j\right)}\frac{1}{\mathrm{log}{k}_{z}}. $

            (4) 優先鏈接 (Preferential Attachment,PA)指標 PA指標認為新鏈接的節點對 $ [{v}_{i},{v}_{j}] $ 間的連接概率正比于兩個節點度的乘積. 其相似性表達式為:

            $ {S}_{ij}={k}_{i}{k}_{j}. $

            (5) 全局路徑Katz指標 Katz指標考慮了網絡的所有路徑. 其相似性表達式為:

            $ {S}_{ij}=\sum\limits _{l=1}^{\infty }{\alpha }^{l}\bullet \left|{{\rm{path}}s}_{i,j}^{<l>}\right|. $

            其中,$ \alpha >0 $ 為控制路徑權重的可調參數,$ \left|{{\rm{path}}s}_{i,j}^{<l>}\right| $ 表示連接節點 $ {v}_{i} $$ {v}_{j} $ 的路徑中長度為 $ l $ 的路徑數.

            (6) 平均通勤時間 (Average Commute Time,ACT)指標 ACT指標屬于基本隨機游走相似性指標的一種,設隨機游走粒子從節點 $ {v}_{i} $ 到節點 $ {v}_{j} $ 的平均步數的平均首達時間為 $ m\left(i,j\right) $,則節點 $ {v}_{i} $ 和節點 $ {v}_{j} $ 的平均通勤時間定義為:

            $ n\left(i,j\right)=m\left(i,j\right)+m\left(j,i\right), $

            式中的數值解可通過該網絡的拉普拉斯矩陣 $ L $ 的偽逆矩陣 $ {{{L}}}^{+} $ 求得,

            $ n\left(i,j\right)=H\left({l}_{ii}^{+}+{l}_{jj}^{+}-{2l}_{ij}^{+}\right). $

            其相似性表達式為:

            $ {S}_{ij}=\frac{1}{{l}_{ii}^{+}+{l}_{jj}^{+}-{2l}_{ij}^{+}}, $

            其中,$ H $ 為網絡的總邊數,$ {l}_{ij}^{+} $ 表示矩陣 $ {{{L}}}^{+} $ 中第 $ i $$ j $ 列的位置對應的元素.

          • 驗證鏈路預測算法準確性的評價指標主要有3種,分別是:AUC(Area Under Curve)、精確度(Precision)、和排序分(Ranking Score). 這3種指標的側重點不同,其中,AUC指標能從整體上評價算法的準確性[33],一直作為最主要的評價指標;精確度指標只計算預測前 $ X $ 條邊中預測的準確率[34];排序分指標只考慮測試邊的最終排序情況[35]. 本文選取AUC和排序分兩種評價指標作為評測依據.

            (1) AUC指標 AUC指標定義為在測試集 $ {E}^{P} $ 中隨機選擇一條邊的分數值比在不存在邊集 $ B $ 中隨機選擇一條邊的分數值高的概率,隨機比較 $ n $ 次,若有 $ {n}^{'} $ 次分數值高,每高一次加1分,有 $ {n}^{''} $ 次分數值相等,每等一次加 $ 0.5 $ 分. AUC值定義為:

            $ U_{{\rm{AUC}}}=\frac{{n}^{'}+0.5{n}^{''}}{n}. $

            AUC值在0~1之間,值越大的鏈路預測方法準確性越高. 若所有的分數 $ {s}_{ij} $ 都隨機產生,$ \mathrm{A}\mathrm{U}\mathrm{C}\approx 0.5 $.

            (2) 排序分(Ranking Score)指標 排序分指標只考慮測試邊 $ e\in {E}^{P} $ 最終排列的位置,由1.1節定義可知,未知邊集合為 $ W $,設 $ {r}_{e} $ 為測試邊 $ e $ 在排序中的排名,則這條測試邊的排序分定義為:

            $ {RS}_{e}=\frac{{r}_{e}}{\left|W\right|},$

            遍歷所有的測試邊,得到整個系統的排序分指標為:

            $ RS=\frac{1}{\left|{E}^{{\rm{P}}}\right|}\sum\limits _{e\in {E}^{{{P}}}}{RS}_{e}=\frac{1}{\left|{E}^{{\rm{P}}}\right|}\sum\limits _{e\in {E}^{{{P}}}}\frac{{r}_{e}}{\left|W\right|}. $

            排序分指標與AUC指標不同,分數值越小預測越準確.

          • 本文選取了7個不同領域、不同規模且具代表性的真實網絡數據集,這些數據集均為無向網絡. 數據集包括:美國航空網絡(USAir)數據集,政治書籍網絡(PolBooks)數據集,電子郵件網絡(E-mail)數據集等. 7個數據集的網絡結構特征如表1. 其中,N表示網絡的節點數,H表示網絡的邊數,$ \left\langle K \right\rangle $ 表示網絡的平均度,$ \left\langle C \right\rangle $ 表示網絡的平均聚集系數,D表示網絡的相對直徑. 由表1可知,在給出的數據集中,Karate、Dolphin 、PolBooks為相對小規模網絡,C.elegens 、USAir 為相對中小規模網絡,E-mail、PolBlogs為相對大規模網絡.

            網絡NHKCD
            USAir[36] 332 212612.8070.7496
            PolBooks[36] 105 441 8.4000.4887
            E-mail[36]1133 5451 9.6220.2208
            Karate[36] 34 78 4.5880.5715
            Dolphin[37] 62 159 5.1260.2598
            PolBlogs[38]12221671427.3550.3208
            C.elegens[39] 297 214814.4650.2925

            表 1  各數據集的網絡結構特征

            Table 1.  Network structure features of each dataset

          • 實驗參數設置:重啟因子 $ c=0.85 $,網絡測試集劃分比例 $ \eta ={E}^{P}/E=10\% $. 每個數據集上獨立重復實驗 $ 50 $ 次,評價指標采用AUC和排序分,取平均值. 本文與7種基準方法比較了AUC指標,與MHRW、RWR算法比較了排序分指標. 實驗結果如表2、3圖5、6所示. 表2比較了本文方法與各基準算法在7個數據集上預測結果的AUC值;表3比較了IMRWR算法與MHRW、RWR算法在7個數據集上預測結果的排序分;圖5給出了同一類型的基準方法在7個數據集上預測結果的AUC直方圖;圖6給出了本文方法與基準方法在7個數據集上預測結果的AUC折線圖和排序分折線圖.

            網絡IMRWRMHRWRWRCNHPIAAPAKatzACT
            USAir[36]0.95270.95230.94090.94340.87910.95020.90070.93360.8994
            PolBooks[36]0.91310.90300.90020.87880.89070.89500.66750.89890.7565
            E-mail[36]0.92850.92790.92280.85420.85000.85560.79970.91550.8074
            Karate[36]0.86510.73000.83960.68080.68920.70900.67180.72410.6402
            Dolphin[37]0.85310.84910.81330.77850.77420.79190.67260.82270.7734
            PolBlogs[38]0.93310.92820.92310.91980.85260.92370.90530.92300.8885
            C.elegens[39]0.89250.86360.85790.84990.80620.86040.75510.85240.7392

            表 2  各數據集在不同的基準方法下 AUC 值

            Table 2.  The AUC value of each data set under different benchmark methods

            網絡IMRWRMHRWRWR
            USAir[36]0.27470.27520.2807
            PolBooks[36]0.29910.30420.3056
            E-mail[36]0.28590.28630.2887
            Karate[36]0.35310.42040.3655
            Dolphin[37]0.34010.34210.3593
            PolBlogs[38]0.28370.28610.2887
            C.elegens[36]0.30500.31880.3225

            表 3  各數據集在不同的基準方法下 排序分 值

            Table 3.  The Ranking Score value of each data set under different benchmark methods

            圖  5  局部相似性指標(a)與路徑相似性指標(b)比較直方圖

            Figure 5.  The comparison histogram of local similarity index (a) and path similarity index (b)

            圖  6  AUC指標(a)與排序分指標(b)比較折線圖

            Figure 6.  The comparison line chart of AUC index (a) and Ranking Score index (b)

            表2可知,與各基準方法相比,本文IMRWR算法在7個實驗數據集上的AUC值均為最高,相較于MHRW算法也有提升. 由圖5(a)知,在局部相似性指標CN、HPI、AA、PA中,AA指標不僅考慮了共同鄰居,還認為共同鄰居中度小的節點對相似性的貢獻更大,因此,其在局部相似性指標中表現相對較好. 由圖5(b)知,Katz為路徑相似性指標,因此,其在考慮路徑的航空網絡USAir數據集上的AUC值最高,若將它應用于路徑的預測會有很好的效果. RWR、ACT均為隨機游走相似性指標,其中,RWR表現最佳,與RWR算法相比,本文IMRWR算法在AUC指標上平均提升2.00%,最高提升可達3.98%. 同時,IMRWR算法在小規模數據集的AUC值提升比大于大規模數據集的提升比,說明本文算法更有利于小數據集鏈路預測效果的改善,并且AUC值隨著數據集規模增大而增大,說明本文算法對大規模數據集上的鏈路預測同樣有效.

            表3知,IMRWR算法在7個實驗數據集上的排序分均比MHRW、RWR算法低,與RWR算法相比,平均下降0.99%,最高下降1.92%,也說明了IMRWR算法可提升預測準確性. 由圖6(a)可知,同一算法在不同類型的數據集上AUC值波動明顯,且同一數據集利用不同的預測方法得到的預測結果相差較大,說明不同的預測方法有著各自側重的預測數據集;而本文算法與其他算法相比,在7個數據集的AUC值波動相對平緩,說明本算法有著更加穩定的預測性能;且由圖6(b)可知,IMRWR算法與RWR算法的預測結果走勢基本相同,說明IMRWR算法有著一定的魯棒性.

          • 本文針對重啟隨機游走相似性指標忽略鄰居節點的度對轉移概率產生影響,提出一種改進的MH重啟隨機游走鏈路預測算法IMRWR. 該算法在定義網絡節點間的轉移概率時,綜合考慮了當前節點和鄰居節點的度對粒子轉移過程的影響,并將自環率按鄰居節點的度值加權分配給鄰居節點,從而使游走粒子能夠轉移到更加相似的節點上,以提高隨機游走獲得的節點序列中各節點的相似性. 實驗結果表明,本文所提算法在AUC指標和排序分指標上均有改善,本文算法在AUC指標上平均提升2.00%,最高提升3.98%,在排序分指標上平均下降0.99%,最高下降1.92%,提升了鏈路預測的準確性.下一步,將考慮結合邊權值對轉移概率的貢獻,研究有權網絡的鏈路預測性能.

        參考文獻 (39)

        目錄

          /

          返回文章
          返回