使用監(jiān)督學習技術在學術社交網絡中進行鏈路預測

趙素芬

摘? 要： 鏈路預測是社交網絡研究中最核心、最本質的研究問題。文章基于學術合作關系社交網絡，采用多種現(xiàn)有的經典機器學習算法進行鏈路預測。針對現(xiàn)有監(jiān)督學習算法中特征集使用不夠全面的問題，抽取了三大類別的特征。針對數據高度偏斜問題，采用了欠采樣的方式使模型不對主要類別過度偏斜，以此保證分類器的有效性。實驗結果表明，Adaboost和多層前饋神經網絡模型在精確率、召回率以及F1-measure指標上優(yōu)于其他監(jiān)督學習方法，而樸素貝葉斯方法在本問題上表現(xiàn)最差。

關鍵詞： 社交網絡; 鏈路預測; 機器學習; 監(jiān)督學習; 數據偏斜

中圖分類號：TP311? ? ? ? ? 文獻標志碼：A? ? ?文章編號：1006-8228（2019）01-39-04

Abstract： Link prediction is the core and essential research issue in social networks research. Based on the academic co-authorship networks， eight existing classical machine learning algorithms are used for link prediction. Three categories of features are extracted for link prediction to solve the problem that the features don't be used comprehensively in the existing supervised learning algorithms. And the under-sampling is used for the problem of high skewness of data， to overcome the model skewness and to ensure the validity of the classifiers. Experimental results show that Adaboost and Multi-Layer Perceptron model are superior to the other six models in Precision， Recall and F1-measure. However， Naive Bayesian performs the worst.

Key words： social networks; link prediction; machine learning; supervised learning; data skewness

0 引言

鏈路預測是圖挖掘的核心，因其能夠揭示社交網絡演化的本質，故具有十分重要的研究意義。本文基于學術合作關系網絡進行鏈路預測。學術合作網絡即學者基于互相合作發(fā)表學術論文而構建的合作關系網。這種合作關系可以很方便地從在線的文獻發(fā)表數據集中抽取，例如dblp， ACM， Google Scholar等等。我們的研究問題是，基于現(xiàn)有的合作關系網絡，預測將來很可能出現(xiàn)的合作關系。對該問題的深入研究，能夠為揭示學者之間的研究合作模式、了解合作關系建立的本質，以及為學者推薦最有潛在合作價值的合作關系提供良好的基礎。

針對鏈路預測問題，現(xiàn)有的研究方法主要分為兩個大的類別。①無監(jiān)督的方式[1，2，12]。這種方式，主要針對社交網絡的拓撲結構抽取特征，這些無監(jiān)督的指標能夠體現(xiàn)出網絡中的兩個節(jié)點建立關系的潛在可能性。絕大多數無監(jiān)督指標的計算方式比較簡單，其計算復雜度都很低。但是，無監(jiān)督指標適合排序，如果進行鏈路預測就需要指定一個分類的閾值。這種情況下，鏈路預測的指標閾值如何設定，這是一個很難把握的部分。并且，這種情形下很難綜合考慮多個不同的預測指標。②監(jiān)督學習的方式[3，4，6，8，11]。隨著機器學習技術的快速發(fā)展，一些研究者選擇使用監(jiān)督學習技術進行鏈路的預測[3-4]。監(jiān)督學習方式能夠根據抽取的顯式特征或者隱式特征自動學習出分類模型，比較好地克服無監(jiān)督指標的一些缺陷。但是，目前針對學術社交網絡的鏈路預測中，其使用的特征均十分有限，這制約了鏈路預測的效果。

因此，為了克服現(xiàn)有的監(jiān)督學習模型中的問題，本文中，我們基于學術社交網絡，抽取了三大類別的特征，包括網絡拓撲結構相關特征（節(jié)點之間的最短圖距離、共同鄰居的個數、Jaccard系數、偏好依附值、AA指標、重啟隨機游走分數等[1-2]）、以及學者的研究興趣相似度特征（標題文本相似度）、以及學者的學術地位因素（作者發(fā)表論文數之和）等八個特征。

為了克服數據集的偏斜性，本文中采用欠采樣的方式對負樣本進行采樣，以保證正負樣本的大致均衡，避免訓練出對主要類別過度傾斜的分類器。然后，我們選擇了八種現(xiàn)有的經典機器學習算法，來進行鏈路的預測。實驗結果表明，Adaboost和多層前饋神經網絡，在眾多的監(jiān)督學習方法中性能表現(xiàn)最優(yōu)，而樸素貝葉斯在本問題中的表現(xiàn)最差。

總的來說，本文的研究有如下方面：

⑴ 本文對比了八個不同的機器學習算法在鏈路預測問題上的不同的性能，這對于進一步設計更高效的預測模型和合作關系推薦模型具有啟發(fā)式的意義。

⑵ 與現(xiàn)有的方法相比，我們的模型使用了一些其他研究中沒有使用的特征，例如作者發(fā)表論文的標題相似度以及發(fā)表論文數之和。

⑶ 本文使用欠采樣的方式，來克服數據集高度偏斜的問題。

1 研究問題描述

基于文獻發(fā)表數據集，我們可以從中抽取合作關系網絡。我們首先把學者抽象為網絡中的節(jié)點，如果兩個學者u，v之間至少合作了一篇論文，那么這兩個學者的節(jié)點之間便存在一條邊（u，v）∈E。通過這樣的方式，我們可以抽取出整個合作關系網絡G=（V，E）。圖1給出了一個例子。作者A，B，C，D，E經由共同發(fā)表了三篇學術論文p1，p2和p3，建立了如圖1粗實線所示的學術合作關系。

定義1 學術社交網絡中的鏈路預測：給定t時刻的學術合作關系網絡圖G，針對G中沒有建立鏈路關系的任意一對節(jié)點i和j，預測在t+Δt時刻，節(jié)點i和節(jié)點j之間是否會建立連接[2，10]。

2 鏈路預測模型

2.1 鏈路預測框架概覽

針對定義1中的鏈路預測問題，我們選擇了8種機器學習模型進行鏈路預測，包括：K近鄰（KNN）、logistic回歸（LR）、決策樹（DT）、支持向量機（SVM）、樸素貝葉斯（NB）、多層前饋神經網絡（MLP）以及集成學習算法隨機森林（RF）、Adaboost等。

圖2中給出了我們的預測模型的框架。從圖2中可以看出，預測模型的構建分為幾個主要的步驟：數據集的解析和預處理-->生成訓練樣本集-->特征提取-->模型訓練-->模型評估。在2.2節(jié)中將詳細介紹每一個步驟。

2.2 鏈路預測

2.2.1 數據集的解析和預處理

本文中使用的文獻發(fā)表數據集是Dblp數據集（ 2018-01版本），其中包含了2104606篇會議論文和1758872篇期刊論文，論文發(fā)表的時間范圍是從1969～2018。

在對Dblp的原始XML數據集進行解析之后，我們對論文數據進行了預處理操作。首先去除了1990年以前發(fā)表的論文數據，然后在剩下的論文中選取了機器學習和數據挖掘領域相關的22個會議和23個期刊的論文作為子數據集（共計96174篇）。然后，將這些論文數據以2011年為分割點分成兩個數據集：1990～2011年期間為訓練階段，2012～2018為測試階段。接著，選擇了在訓練階段和測試階段發(fā)表論文的數目均不小于3（即3核）的全部作者，共計3609個作者。最終以這3609個作者的發(fā)表論文的數據集作為選取的子數據集。并以2011年作為分割點，構成最終的訓練階段論文集29877篇，測試階段論文集22293篇。

2.2.2 生成訓練樣本集

生成了訓練階段的論文集和測試階段的論文集之后，分別抽取出這兩個階段的合作關系鄰接矩陣Gtrain和Gtest。接下來，依據這兩個鄰接矩陣的元素值，依次判斷每兩個作者i和作者j之間的關系，如果他們在t時刻前未建立關系，則將二元對<i，j>加入候選樣本集。也就是說，我們僅僅對在訓練階段尚未建立關系的用戶對進行建模。接下來，依據他們在測試階段是否建立關系來確定這個二元對<i，j>的標記：如果測試階段建立了關系，標記<i，j>為正樣本（y=1）;否則標記<i，j>為負樣本（y=0）。

學術社交網絡是極度稀疏的網絡，數據的稀疏導致數據集的高度偏斜[7]。正負樣本的極度不均衡性，會極大的影響分類模型的性能。因此，在我們構造訓練集的步驟中，對負樣本采用欠采樣的方式，來保持正樣本和負樣本數目的大致均衡。具體來說，我們在生成了全部正樣本之后，隨機采樣和正樣本數目相同的負樣本，以此作為整個模型的訓練集合T。

2.2.3 特征提取

本文中，我們從數據集中抽取和使用了如下8個特征。其中，N（i）表示的是節(jié)點i的鄰居節(jié)點;|N（i）|表示的是節(jié)點i的鄰居節(jié)點的個數。

⑴ 最短圖距離SP

最短圖距離能反應兩個用戶互相認識的難度有多大，其值為從節(jié)點i到節(jié)點j的拓撲結構最短距離。

⑵ 共同鄰居的個數CN

共同鄰居的個數能反應兩個作者建立潛在關系的渠道有多少，其計算公式為：。

⑶ Jaccard系數JC

Jaccard系數在信息檢索領域，被大量應用于計算文本相似度，具有較好的效果。其計算公式是：。

⑷ 偏好依附PA

偏好依附指標的原理是：社交網絡中，新關系的建立具有“馬太效應”，即如果現(xiàn)有的節(jié)點具有更大的度，則新關系的建立的可能性更大，其計算公式是：。

⑸ Academic/Adar（AA）指標

AA指標仍然是一個拓撲結構相關的相似度指標[1-2]，其計算公式是：。

⑹ RWR分數

重啟隨機游走的主要思想是：從源節(jié)點S出發(fā)，在網絡中進行隨機游走，每一步以α的概率回到S，以1-α的概率游走到其他節(jié)點。在經過有限步驟的隨機游走之后，到達網絡中每個節(jié)點的概率會達到穩(wěn)定分布。這個平穩(wěn)分布的概率值可以用來測量網絡中每個節(jié)點和源端節(jié)點S的相似度。由于從節(jié)點i出發(fā)穩(wěn)定在節(jié)點j的概率不等價于從j出發(fā)穩(wěn)定在i的概率，我們計算了這兩個概率的平均值來表示用戶i和用戶j的相似度分數。

⑺ 兩個作者發(fā)表的論文之和TP

兩個用戶中至少有一個是精英學者，對于建立合作關系來說是一個極為有利的指征[5]。因此，我們將兩個學者的發(fā)表論文的數目作為體現(xiàn)其研究地位的指標。

⑻ 用戶的研究興趣相似度TS

我們將兩個用戶的發(fā)表論文的標題取出，分詞并去除停用詞，然后計算標題文本的Jaccard相似度作為用戶的研究興趣相似度。

2.2.4 模型訓練和評估

在全部的關系對抽取出來之后，我們依據2.2.3中定義的特征集，計算訓練階段中每個樣本的特征向量，生成特征矩陣X。因為特征集的數據分布有很大的不一致，為了避免對各種機器學習算法的性能產生影響，我們將特征矩陣X進行了z-score標準化，即均值為0，方差為1。接下來，標準化之后的特征矩陣X和標記矩陣y輸入到各種機器學習的模型中進行訓練。

各個預測模型訓練完之后，使用測試集驗證每個模型的預測性能。實驗中采用5折交叉驗證。本文中，我們選擇了三個最流行的分類性能評估指標：精確率（Precision）、召回率（Recall）以及F1-measure。

3 實驗結果

從表1可以看出，在基本的機器學習模型中，多層感知機表現(xiàn)最好，而樸素貝葉斯方法表現(xiàn)最差。其他幾種算法logistic回歸、決策樹和SVM性能性能大體一致。K近鄰方法僅優(yōu)于樸素貝葉斯。

這說明，由于樸素貝葉斯假定了特征之間的條件獨立性，這在本問題中很難成立，因而影響了分類效果;而多層感知機神經網絡由于隱藏層可以捕捉特征之間的非線性關系，并在較高層次進行抽象，所以能更好的擬合訓練數據，訓練出精確度更高的模型。在集成學習模型中，隨機森林對于決策樹算法基本沒有提升，而Adaboost方法對決策樹算法提升的效果很好，其預測性能超越了所有其他的基本分類器的預測效果。其原因是，我們的特征集的數目較小，而隨機森林更適合處理高維數據;Adaboost則由于其組建強分類器的思路是根據弱分類器的反饋，自適應地調整樣本權重和分類器權重，從而調整分類錯誤率，多數情況下都能有效的提升分類器的性能。

4 結束語

針對鏈路預測問題，我們基于學術合作網絡，使用了8種經典的機器學習算法進行了合作關系的預測，并進行了預測性能的比較。

未來，將深入分析學術社交網絡中鏈路形成的機制，考慮增加更多的特征，例如學者之間地理位置的距離特征以及隱式特征，并對分類特征的顯著性進行探討。除此以外，還將研究社交網絡拓撲結構變化的時間序列信息[9]，力求對鏈路關系的預測更加精確。

參考文獻（References）：

[1] David Liben-Nowell， Jon Kleinberg. The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology，2007.58（7）：1019-1031

[2] Víctor Martínez， Fernando Berzal， and Juan-Carlos Cubero. A Survey of Link Prediction in Complex Networks. ACM Computing Surveys， 2016.49（4）：69

[3] Gabriel P. Gimenses， Hugo Gualdron， etc. Supervised-Learning Link Recommendation in the DBLP co-authoring network. The Second IEEE International Workshop on Social and Community Intelligence，2014：563-568

[4] Nesserine Benchettara， Rushed Kanawati， etc. Asupervised Machine Learning Link Prediction Approach for Academic Collaboration Recommendation. Proceedings of the fourth ACM conference on Recommender systems（RecSys）， 2010：253-256

[5] Yuxiao Dong， JieTang， Jilei Tian， Nitesh V.Chawla，?Jinghai Rao， HuanHuan Cao. Link prediction and Recommendation across heterogeneous social networks. IEEE International Conference on Data Mining，2012：181-190

[6] Salvatore Scellato， Anastasios Noulas， Cecilia Mascolo.Exploiting place features in link prediction on location-based social networks. International Conference on Knowledge Discovery and Data Mining，2011：1046-1054

[7] Ryan N. Lichtenwalter， Jake T. Lussier， Nitesh V. Chawla.New perspectives and methods in link prediction. International Conference on Knowledge Discovery and Data Mining，2010：243-252

[8] Kurt T.Miller， Thomas L. Griffiths， Michael I.Jordan.?Nonparametric latent feature models for link prediction. International Conference on Neural Information Processing Systems，2009：1276-1284

[9] Zan Huang， Dennis K.J.Lin. The Time-Series Link Prediction Problem with Applications in Communication Surveillance. INFORMS Journal on Computing，2009.21（2）：286-303

[10] Behnaz Moradabadi， Mohammad Reza Meybody. Link?Prediction in weighted social networks using Learning automata. Engineering Applications of Artificial Intelligence，2018.70：16-24

[11] Yongli Li， Peng Luo， Zhi-ping Fan， Kun Chen， Jiaguo Liu. A utility-based link prediction method in social networks. European Journal of Operational Research，2017.260：693-705.

[12] Wang Peng， Xu BaoWen， Wu YuRong， Zhou Xiao Yu.?Link prediction in social networks： the state-of-the-art. Science China Information Science，2015.58（1）：1-38