基于骨干度與網絡編碼的鏈路預測模型研究

胡旭飛　許云峰

摘 要：為了研究網絡表示學習在社交網絡中鏈路預測方面的應用，提出了一種基于骨干度與網絡編碼的鏈路預測模型（BDLINE）。在網絡表示學習算法LINE的基礎上融入骨干度算法，通過給一階相似度和二階相似度中增添骨干權重，將網絡編碼到多維向量空間中，調試到最優參數。實驗采用2個真實數據的數據集，分別在不同的算法模型上進行多次實驗。實驗結果表明：在鏈路預測方面，BDLINE均比其他網絡表示學習算法的性能有所提升，AUC評測值更高，預測效果表現得更好。因此，所提出的方法可以方便地提取網絡特征信息，更好地處理社交網絡在鏈路預測中的隨機性，對社交網絡中預測網絡節點的關聯性和有效性具有一定的參考。

關鍵詞：計算機網絡;網絡表示學習;鏈路預測;社交網絡;相似性

中圖分類號：TP391?? 文獻標志碼：A

Abstract：In order to study the application of network representation learning in link prediction in social networks， a link prediction model based on backbone and network coding （BDLINE） is proposed. The model integrates the backbone algorithm based on the network representation learning algorithm LINE. By adding the backbone weight to the first-order similarity and the second-order similarity， the network is encoded into the multi-dimensional vector space and debugged to the optimal parameters. The data set used in the experiment is two different real data， and multiple experiments are performed on different algorithm models. The experimental results show that in terms of link prediction， the proposed algorithm model has improved performance compared to other network representation learning algorithms; the AUC evaluation value is higher， and the prediction effect is better. It is more convenient for extracting network feature information by using the method， and can better deal with the randomness problem of social network in link prediction. The method has certain guiding significance for predicting the relevance and effectiveness of network nodes in social networks.

Keywords：computer network; network representation learning; link prediction; social network; similarity

現實世界中存在著大量而又復雜的社交網絡，如何對網絡數據進行有效合理的表示是現今學術研究中的一個重要挑戰，網絡表示學習正是為了迎接這種挑戰而出現的，是解決大規模社交網絡問題的基礎方法[1-4]，其研究領域有著非常廣泛的應用場景，如可視化[5]、節點分類[6]、鏈路預測[7]等。網絡表示學習是一個網絡編碼的過程，是根據網絡頂點在網絡中的結構作用，通過無監督學習，將網絡頂點映射到多維空間。從直觀的角度分析，在網絡中拓撲結構[8]相似的頂點所表示出的向量關系更緊密，這里向量關系的相似性一般用向量間的余弦距離或者歐氏距離來表示[9]。

近年來，網絡表示學習問題開始成為學術界的焦點，尤其是社交網絡中鏈路預測的研究越來越受到國內外學者的廣泛關注。鏈路預測可以識別一個不斷發展的社交網絡中可能存在但尚未建立的鏈接，從而為用戶提供信息。真實世界的網絡頂點數量非常多，因此，使用考慮全局結構的算法計算鏈路概率非常困難。早期的工作集中在頂點對之間直接的相似性度量上[10]。最近幾年的網絡表示學習算法主要有node2vec[11]，DeepWalk[12]，MMB[13]，LINE[14]等，可以學習網絡各頂點的潛在網絡結構特征，將網絡表征到多維空間中。本文提出的網絡表示學習算法BDLINE是在LINE的基礎上融入骨干度[15]，重新調整網絡參數模型，提高網絡在向量空間中的相似性，最后通過鏈路預測實驗分別進行各算法對比。結果表明所提出的算法AUC評測值更高，取得的預測效果最好。

1 基于骨干度與網絡編碼的鏈路預測

在社交網絡中處理網絡中的數據，需要對網絡進行清晰的定義。首先定義一個信息網絡

[WTBX]G=（V，E），其中V是頂點集合，E是頂點之間的邊集合，邊e=（u，v）∈E表示了u到v的一條邊。BDLINE模型是在LINE的基礎上建立的，LINE的算法定義了使用一階和二階相似度來解決大規模網絡信息編碼問題。

所有的連邊計算完之后，得到AUC值。AUC值最少應大于0.5，最大值不超過1。AUC值越高，說明算法的預測結果越精確，性能越好。

2.3 實驗環境與實驗參數

實驗環境：Linux操作系統;實驗算法模型均采用Python語言實現;所提算法BDLINE和LINE使用TensorFlow機器學習框架。

實驗參數設置：BDLINE設置向量size大小為128，根據實驗經驗，此值效果最好;負采樣值為5，epoch=10;線程數為8，學習率[WTBX]lr=0.001。

2.4 實驗結果

將本文提出的算法模型BDLINE分別在2個數據集上進行實驗，為了呈現更好的預測效果，對訓練集在真實數據集所占的比例由低到高依次選取，選取數據的過程都具有隨機性。每個算法訓練模型都進行11次測試，獲得測試結果并取其平均值。所有的實驗結果如表2和表3所示。

可以看出，當只保留15%的邊用于訓練時，評測AUC值都很低，所有方法的性能都很差，大多數頂點是孤立的，而且毫無意義。隨著訓練集所占的比例越來越大，訓練的邊也越來越多，AUC值也越來越高。通過縱向對比發現，BDLINE相對于其他算法來說，AUC值均有所提高，說明了該算法在鏈路預測任務中的有效性，驗證了該算法具有精確建模頂點間關系的能力。通過引入骨干度，學習到的網絡感知能力比LINE有較大的改進，即一個特定的頂點在與其他頂點交互時應該扮演不同的角色，從而有利于相關鏈路的預測任務。

3 結 論

1）針對現有的社交網絡在鏈路預測方面的問題，提出了基于骨干度與網絡編碼的鏈路預測模型BDLINE，首次將骨干度引入到LINE算法中。實驗證明，BDLINE比現有的眾多網絡表示學習算法有著更加準確的預測結果。

2）BDLINE網絡表示學習算法可以學習高質量的網絡結構編碼，有助于準確估計頂點之間的關系，提高頂點間的相似度，對社交網絡中預測網絡節點的關聯性和有效性有一定的借鑒意義。

3）本次實驗雖然取得了不錯的效果，但仍有不足之處，對于多屬性的大規模復雜網絡，處理的時間復雜度較高，測試結果隨機性太大，不夠穩定，今后會進行優化改善。在未來的研究中，會嘗試用對抗性網絡學習機制來處理具有復雜屬性的網絡，用深度學習技術進一步提高網絡骨干度權重的精確值。

參考文獻/References：

[1] AMED A， SERVASIDZE N， NARAYANAMURTY S， et al. Distributed large-scale natural graph factorization[C]// Proceedings of the 22nd International Conference on World Wide Web. New York：ACM， 2013：37-48.

[2] LEVY O， GOLDBERG Y. Neural word embedding as implicit matrix factorization. Advances in Neural Information Processing Systems， 2014（3）：2177-2185.

[3] LE Q， MIKOLOV T. Distributed representations of sentences and documents[C]// Proceedings of the 31st International Conference on International Conference on Machine Learning. Beijing：[s.n.]，2014：1188-1196.

[4] CANG Shiyu， AN Wei， TANG iliang， et al. eterogeneous network embedding via deep architectures[C]// Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York：ACM，2015：119-128.

[5] TANG ian， LIU ingzhou， ZANG Ming， et al. Visualization large-scale and high-dimensional data. Machine Learning，2016： 10.1145/2872427.2883041.

[6] BAGAT S， CORMODE G， MUTUKRISNAN S. Node classification in social networks. Social Network Data Analytics， 2011， 16（3）：115-148.

[7] LIBEN-NOWELL D， KLEINBERG . The Link-Prediction Problem for Social Networks[M].[S.l.]： ohn Wiley & Sons， 2007.

[8] TANAY B， KANDEMIR M B. Topological structure of fuzzy soft sets. Computers & Mathematics with Applications， 2011， 61（10）：2952-2957.

[9] TU Cunchao， LIU an， LIU Zhiyuan， et al. CANE： Context-aware network embedding for relation modeling[C]// Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics （Volume 1： Long Papers）. Vancouve： Association for Computational Linguistics， 2017： 1722-1731.

[10]L Linyuan， ZOU Tao. Link prediction in complex networks： A survey. Physica A： Statistical Mechanics and Its? Applications， 2011， 390（6）：1150-1170.

[11]GROVER A， LESKOVEC . node2vec： Scalable feature learning for networks[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York：ACM， 2016：855-864.

[12]PEROZZI B， Al-RFOU R， SKIENA S. DeepWalk： Online learning of Social representations[C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM， 2014：701-710.

[13]AIROLDI E M， BLEI D M， FIENBERG S E， et al. Mixed membership stochastic blockmodels. The ournal of Machine Learning Research， 2008，9：1981-2014.

[14]TANG ian， QU Meng， WANG Mingzhe， et al. LINE： Large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web. Florence：[s.n.]，2015：1067-1077.

[15]XU Yunfeng， XU ua， ZANG Dongwen. A novel disjoint community detection algorithm for social networks based on backbone degree and expansion. Expert Systems with Applications， 2015， 42（21）：8349-8360.

[16]TANG ie， ZANG ing， YAO Limin， et al. ArnetMiner： Extraction and mining of academic social networks[C]// Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York：ACM， 2008：990-998.