趙素芬

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

關(guān)鍵詞： 社交網(wǎng)絡(luò); 鏈路預(yù)測; 機(jī)器學(xué)習(xí); 監(jiān)督學(xué)習(xí); 數(shù)據(jù)偏斜

中圖分類號(hào)：TP311? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：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 引言

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

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

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

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

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

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

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

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

1 研究問題描述

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

定義1 學(xué)術(shù)社交網(wǎng)絡(luò)中的鏈路預(yù)測：給定t時(shí)刻的學(xué)術(shù)合作關(guān)系網(wǎng)絡(luò)圖G，針對G中沒有建立鏈路關(guān)系的任意一對節(jié)點(diǎn)i和j，預(yù)測在t+Δt時(shí)刻，節(jié)點(diǎn)i和節(jié)點(diǎn)j之間是否會(huì)建立連接[2，10]。

2 鏈路預(yù)測模型

2.1 鏈路預(yù)測框架概覽

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

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

2.2 鏈路預(yù)測

2.2.1 數(shù)據(jù)集的解析和預(yù)處理

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

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

2.2.2 生成訓(xùn)練樣本集

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

學(xué)術(shù)社交網(wǎng)絡(luò)是極度稀疏的網(wǎng)絡(luò)，數(shù)據(jù)的稀疏導(dǎo)致數(shù)據(jù)集的高度偏斜[7]。正負(fù)樣本的極度不均衡性，會(huì)極大的影響分類模型的性能。因此，在我們構(gòu)造訓(xùn)練集的步驟中，對負(fù)樣本采用欠采樣的方式，來保持正樣本和負(fù)樣本數(shù)目的大致均衡。具體來說，我們在生成了全部正樣本之后，隨機(jī)采樣和正樣本數(shù)目相同的負(fù)樣本，以此作為整個(gè)模型的訓(xùn)練集合T。

2.2.3 特征提取

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

⑴ 最短圖距離SP

最短圖距離能反應(yīng)兩個(gè)用戶互相認(rèn)識(shí)的難度有多大，其值為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的拓?fù)浣Y(jié)構(gòu)最短距離。

⑵ 共同鄰居的個(gè)數(shù)CN

共同鄰居的個(gè)數(shù)能反應(yīng)兩個(gè)作者建立潛在關(guān)系的渠道有多少，其計(jì)算公式為：。

⑶ Jaccard系數(shù)JC

Jaccard系數(shù)在信息檢索領(lǐng)域，被大量應(yīng)用于計(jì)算文本相似度，具有較好的效果。其計(jì)算公式是：。

⑷ 偏好依附PA

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

⑸ Academic/Adar（AA）指標(biāo)

AA指標(biāo)仍然是一個(gè)拓?fù)浣Y(jié)構(gòu)相關(guān)的相似度指標(biāo)[1-2]，其計(jì)算公式是：。

⑹ RWR分?jǐn)?shù)

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

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

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

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

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

2.2.4 模型訓(xùn)練和評估

在全部的關(guān)系對抽取出來之后，我們依據(jù)2.2.3中定義的特征集，計(jì)算訓(xùn)練階段中每個(gè)樣本的特征向量，生成特征矩陣X。因?yàn)樘卣骷臄?shù)據(jù)分布有很大的不一致，為了避免對各種機(jī)器學(xué)習(xí)算法的性能產(chǎn)生影響，我們將特征矩陣X進(jìn)行了z-score標(biāo)準(zhǔn)化，即均值為0，方差為1。接下來，標(biāo)準(zhǔn)化之后的特征矩陣X和標(biāo)記矩陣y輸入到各種機(jī)器學(xué)習(xí)的模型中進(jìn)行訓(xùn)練。

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

3 實(shí)驗(yàn)結(jié)果

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

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

4 結(jié)束語

針對鏈路預(yù)測問題，我們基于學(xué)術(shù)合作網(wǎng)絡(luò)，使用了8種經(jīng)典的機(jī)器學(xué)習(xí)算法進(jìn)行了合作關(guān)系的預(yù)測，并進(jìn)行了預(yù)測性能的比較。

未來，將深入分析學(xué)術(shù)社交網(wǎng)絡(luò)中鏈路形成的機(jī)制，考慮增加更多的特征，例如學(xué)者之間地理位置的距離特征以及隱式特征，并對分類特征的顯著性進(jìn)行探討。除此以外，還將研究社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化的時(shí)間序列信息[9]，力求對鏈路關(guān)系的預(yù)測更加精確。

參考文獻(xiàn)（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