許 爽，李淼磊

(大連民族大學 信息與通信工程學院，遼寧 大連 116605)

在知識經(jīng)濟時代，合作關系隱含著知識在某種社會關系之間的交流、轉(zhuǎn)移、共享[1]。科學家合作網(wǎng)絡是以論文作者為中心的一種社會網(wǎng)絡，其中論文作者是網(wǎng)絡中的節(jié)點，論文作者之間的合作關系是網(wǎng)絡的連邊?？茖W家合作網(wǎng)絡會隨時間推移而演化， 目前學者們主要是從網(wǎng)絡結(jié)構、網(wǎng)絡演化機制、網(wǎng)絡增長及個人合作行為上研究科學家合作網(wǎng)絡。

由于鏈路預測在復雜網(wǎng)絡研究中具有重要價值。因此，對鏈路預測方法以及提高預測準確率的研究也自然成為了重點。在鏈路預測中，準確率取決于網(wǎng)絡中提取的相似性特征是否能夠很好的反映出給定網(wǎng)絡的拓撲結(jié)構，而相似性特征的優(yōu)劣則可以通過特征選擇方法來評價。特征選擇是指從原始特征集中選擇出能使某種評價特征最優(yōu)的特征子集[2]。在鏈路預測方法研究中，把鏈路預測與特征選擇相結(jié)合，從而形成一種新的研究思路，對預測結(jié)果和相似性特征進行進一步探究，對于分析不同相似性特征與網(wǎng)絡結(jié)構的關系具有重要意義。

網(wǎng)絡科學領域中研究鏈路預測的方法主要可以分為基于極大似然和概率模型的方法、基于機器學習的方法、基于網(wǎng)絡表示學習的方法、基于相似性的方法[3]；Clauset[4]等人提出了基于網(wǎng)絡層次的最大似然估計模型，該算法在層次結(jié)構比較顯著的網(wǎng)絡中預測效果良好；Fire等[5]利用機器學習中的支持向量機、決策樹和人工神經(jīng)網(wǎng)絡對網(wǎng)絡中缺失的連邊進行預測；Pachaury[6]等人提出了一種基于拓撲特征和集合模型的鏈路預測方法，從網(wǎng)絡圖中提取拓撲特征，用于訓練隨機森林分類器模型，并在兩個公開數(shù)據(jù)集上進行驗證；賈承豐[7]等人將深度學習特征提取算法和優(yōu)化問題中的粒子群算法相結(jié)合，提出了一種基于詞向量的粒子群優(yōu)化算法(word2vec-POS)。

基于相似性的方法，尤其是基于網(wǎng)絡拓撲結(jié)構相似性的方法，由于算法簡便、復雜度低，受到了廣泛關注[8]。每種相似性方法包含不同的相似性特征，如共同鄰居特征[9]、Katz特征[10]、SimRank特征[11]分別屬于基于局部信息、基于路徑和基于隨機游走的相似性特征。

基于網(wǎng)絡拓撲結(jié)構的相似性定義方法是由Liben-Nowell和Kleinberg[12]提出的，同時他們還發(fā)現(xiàn)在大型科學家合作網(wǎng)中，使用節(jié)點共同鄰居和Adamic-Adar特征(Adamic-Adar Index，AA)的準確率最高。周濤等人[13]證實了Liben-Nowell和Kleinberg的研究結(jié)果，并在此基礎上提出了資源分配特征(Resource Allocation Index，RA)和局部路徑特征(Local Path Index，LP)。在最近的研究中，王凱[14]等人定義了節(jié)點間資源承載度相似性特征QN，并提出相應的鏈路預測方法。通過實驗證明，相比于其他方法，該方法擁有較高精度。路蘭[15]等人提出一種基于試驗設計的鏈路預測算法，將三個預測精度高的傳統(tǒng)相似性特征相加，并通過均勻配方試驗設計法給相似性特征賦予權重，構建混合相似性特征，從而應用于鏈路預測中。Kumar[16]等人提出基于二級節(jié)點聚類系數(shù)的鏈路預測方法，該方法定義了二級公共節(jié)點及其聚類系數(shù)的概念，并基于該信息計算節(jié)點相似性。目前，基于網(wǎng)絡拓撲結(jié)構相似性鏈路預測方法的研究中，存在如下問題：(1) 相似性特征類別固定且數(shù)量較少;(2)獨立的相似性特征無法全面反映網(wǎng)絡演化的多樣性和復雜性，對眾多相似性特征之間的協(xié)作關系和同類別相似性特征的影響力無法具體分析。

目前關于特征選擇方法的研究主要分為過濾法(Filter)、封裝法(Wrapper)和嵌入法(Embedded)[17]。過濾法的應用非常普遍，其關鍵就是找到一種能度量特征重要性的方法，比如Pearson相關系數(shù)[18]、最大信息壓縮指數(shù)[19]、信息增益、互信息及最大信息系數(shù)[20]等。很多研究者在進行特征選擇時對上述方法進行了改進或提出了新的度量方法。張海洋[21]在持股集中度與股票價格關系的研究中應用了最大信息數(shù)的特征選擇方法。孫廣路等人[22]提出了基于最大信息數(shù)和近似馬爾科夫毯的兩階段特征選擇方法，分別對特征的相關性和冗余性進行分析，得到了很好的效果。在封裝法中，對于一個待評價的特征子集，需要訓練一個分類器，根據(jù)分類器的性能對該特征子集進行評價。封裝法中用以評價特征的學習方法是多種多樣的，例如決策樹、神經(jīng)網(wǎng)路、近鄰法以及支持向量機等[23]機器學習方法。關于封裝法的研究中， Hancer[24]等人提出一種基于人工蜂群優(yōu)化的特征選擇方法，并使用KNN分類算法選擇最優(yōu)特征子集。Wei[25]等人提出一種基于記憶更新和增強變異機制的BPSO-SVM算法，對標準二進制粒子群優(yōu)化算法(BPSO)進行改進，且采用SVM模型作為特征評估部分，實驗結(jié)果表明，該算法具有較高的精度。嵌入法將特征選擇過程與機器學習模型相結(jié)合，其特征選擇精度主要依賴于選取的特征選擇方法和分類模型。有關嵌入法的研究中，傅昊[26]等人提出基于隨機森林和RFE的組合特征選擇方法，分別采取隨機森林算法和SVM-RFE算法，將得到的兩個特征子集進行綜合，得到最終的最優(yōu)子集，然后使用SVM模型對入侵檢測系統(tǒng)中的未知樣本進行預測。

綜上所述，本文提出了多類別網(wǎng)絡結(jié)構的鏈路預測方法，將網(wǎng)絡結(jié)構特征分為五類特征，分別是基于節(jié)點度和中心性相似性特征、基于節(jié)點和邊的共同鄰居相似性特征以及基于鄰居和邊的子圖相似性特征。先計算網(wǎng)絡中同類別特征統(tǒng)計量，即特征工程的建立，然后計算各個特征統(tǒng)計量的影響力和相互關系，即進行特征選擇，最后通過有監(jiān)督的二分類機器學習算法實現(xiàn)鏈路預測。衡量鏈路預測方法的好壞，最終要通過評價標準來實現(xiàn)。研究結(jié)果表明，基于子圖的相似性特征在科學家合作網(wǎng)絡中具有最好的預測效果；此外，研究中分析并選擇合適的特征選擇方法，通過選取最優(yōu)子集來揭示特征統(tǒng)計量類內(nèi)相互關系，便于更加直觀的比較各類別特征統(tǒng)計量對鏈路預測的影響。

1 數(shù)據(jù)說明和網(wǎng)絡構建

1.1 數(shù)據(jù)說明

本文采用的科學家合作網(wǎng)主要有5個，分別為：netscience、cond-mat、hep-th、geom和GrQc。這5個數(shù)據(jù)集都記錄了科學家之間的協(xié)作關系，它們的區(qū)別是數(shù)據(jù)集的大小不同。

(1) netscience網(wǎng)絡：是由研究網(wǎng)絡科學的科學家組成的合作網(wǎng)絡，節(jié)點表示從事網(wǎng)絡科學研究的科學家，連邊表示兩個科學家有合作關系。

(2) cond-mat網(wǎng)絡：是基于凝聚態(tài)物理學家在1995-1999年間發(fā)表的預印樣本的科學家合作網(wǎng)絡。

(3) hep-th網(wǎng)絡：包含了1995年-1999年在電子出版物Arxiv中發(fā)表高能物理理論相關論文的所有作者之間的合作關系。

(4) geom網(wǎng)絡：是由2002年計算幾何數(shù)據(jù)庫中作者之間的科學合作關系構建的網(wǎng)絡。

(5) GrQc網(wǎng)絡：涵蓋了1993-2003年間電子出版物Arxiv中廣義相對論與量子宇宙學范疇的論文作者之間的科學協(xié)作關系。

5個科學家合作網(wǎng)中的節(jié)點數(shù)和連邊數(shù)見表1。

表1 科學家合作網(wǎng)數(shù)據(jù)說明

根據(jù)所給數(shù)據(jù)，本文首先將網(wǎng)絡數(shù)據(jù)文件讀取出來并轉(zhuǎn)換成后綴為.txt的文件，為下一步構建網(wǎng)絡做準備。

1.2 構建網(wǎng)絡

本文使用了科學家合作數(shù)據(jù)來構建無權無向社交網(wǎng)絡。G=(V,E)定義為社交網(wǎng)絡的拓撲結(jié)構。網(wǎng)絡中的邊用e=(u,v)∈E來表示，其中u,v∈V，V為網(wǎng)絡中的節(jié)點集合，E為網(wǎng)絡中的邊集合。對于網(wǎng)絡中每兩個節(jié)點u,v∈V來說，鏈路預測就是判斷u與v之間存在鏈接的可能性。針對本文所使用的科學家合作關系數(shù)據(jù)，網(wǎng)絡中節(jié)點代表各個科學家，連邊代表科學家之間有合作關系，鏈路預測也就是判斷科學家之間有合作關系的可能性。將處理后的數(shù)據(jù)集分為兩部分：訓練集ET和測試集EP，本文使用的訓練集和測試集的比例為9∶1。

2 網(wǎng)絡結(jié)構統(tǒng)計特征

研究中，將目前通用的相似性特征分為三類，分別是基于節(jié)點度及中心性、基于節(jié)點的共同鄰居和基于邊的共同鄰居相似性特征；同時為了進一步提高預測準確率，提出了兩類新特征，分別是基于節(jié)點的子圖特征和基于邊的子圖特征。

2.1 節(jié)點度及中心性特征

節(jié)點特征計算了單個節(jié)點在網(wǎng)絡中的特性，是通過網(wǎng)絡結(jié)構和單個節(jié)點與鄰居節(jié)點的關系得到的一類相似性特征。該類相似性特征反映了節(jié)點在網(wǎng)絡中的重要性和節(jié)點間的相互關系。包括節(jié)點的度、平均鄰度、聚類系數(shù)、度中心性、特征向量中心性、PageRank中心性，以及介數(shù)中心性這7個特征特征。

(1)節(jié)點的度。令v∈V，定義v的鄰居朋友集合為Γ(v)，即Γ(v)中的節(jié)點都為v的鄰節(jié)點，則節(jié)點v的度定義為：

d(v)=|Γ(v)|。

(1)

(2)平均鄰度。在無向網(wǎng)絡中，該特征是一個常見且比較簡單的統(tǒng)計量，它指的是網(wǎng)絡中所有節(jié)點度的平均值。節(jié)點v的平均鄰度是v的所有鄰居節(jié)點度的平均，定義為：

(2)

式中：Γ(v)為節(jié)點v的鄰居集合；ku代表v的鄰居節(jié)點u的度。

(3)

(4)度中心性。該特征指的是節(jié)點在與其直接相連的鄰居節(jié)點當中的中心程度，中心性較高的節(jié)點具有較多的連接關系，因此節(jié)點的度值中心性大小體現(xiàn)了節(jié)點的活躍特性。假設一個網(wǎng)絡中包含N個節(jié)點，節(jié)點的最大可能度值為N-1，則度為kv的節(jié)點歸一化的度的中心性值定義為：

(4)

(5)特征向量中心性。是一個節(jié)點會由于連接到一些本身很重要的節(jié)點，而使自身的重要性得到提升。它指派給網(wǎng)絡中的每個節(jié)點一個相對得分，對于某個節(jié)點分值的貢獻，連到高分值的節(jié)點比連到低分值節(jié)點的貢獻大。對于節(jié)點v，記FEC(v)為節(jié)點v的主要性度量值，則有

(5)

式中：auv為網(wǎng)絡的鄰接矩陣；β為一比例常數(shù)且小于鄰接矩陣最大特征值的倒數(shù)。

x=cAx。

(6)

式中：x是矩陣A與特征值c-1對應的特征向量，故稱為特征向量中心性。

(6)PageRank中心性。PageRank中心性基于網(wǎng)絡節(jié)點的入度連接計算網(wǎng)絡中節(jié)點的中心性排序，最初用來對萬維網(wǎng)中頁面的搜索相關性進行排序。其迭代公式定義為：

(7)

式中：標度常數(shù)s∈(0,1)，在本文中取s=0.85。

(7)介數(shù)中心性。以經(jīng)過某個節(jié)點的最短路徑的數(shù)目來刻畫節(jié)點重要性的特征就稱為介數(shù)中心性。該特征反映了信息流經(jīng)給定節(jié)點的可能性，節(jié)點的介數(shù)中心性會隨著經(jīng)過該節(jié)點的信息流的增大而增大。具體的節(jié)點v的介數(shù)定義為：

(8)

2.2 共同鄰居特征

共同鄰居特征是指兩個未連接的節(jié)點如果有更多的共同鄰居，則它們更傾向于連邊。共同鄰居特征在預測中具有復雜度低且準確率較高的優(yōu)勢。研究中將共同鄰居特征以及由共同鄰居衍生出的一些特征歸為一個大類，從節(jié)點和邊的角度出發(fā)將共同鄰居特征分為基于節(jié)點和連邊兩類特征。

2.2.1 基于節(jié)點的共同鄰居特征

包括共同鄰居CN特征，以及在此基礎上得到的Salton特征(余弦相似性)、Jaccard特征、Sorenson特征、HPI特征(Hub Promoted Index，大度節(jié)點有利特征)、HDI特征(Hub Depresed Index，大度節(jié)點不利特征)和LHN-I特征引入到鏈路預測中。這7種特征具體表達方式如下：

Covertex(u,v)=|Γ(u)∩Γ(v)|；

(9)

(13)

(14)

Γ(u)是節(jié)點u的鄰居集合，Γ(v)是節(jié)點v的鄰居集合，ku和kv分別是節(jié)點u和v的度。

2.2.2 基于連邊的共同鄰居特征

基于連邊的共同鄰居特征是指節(jié)點u和節(jié)點v的共同鄰居的鏈接數(shù)目。該類特征描述了兩個節(jié)點及其鄰居節(jié)點之間的關系，且在預測中具有復雜度低且準確率較高的優(yōu)勢。主要包括共同鄰居朋友數(shù)特征，以及基于連邊的Salton特征、Jaccard特征、Sorenson特征、HPI特征、HDI特征和LHN-I特征。

共同鄰居朋友數(shù)特征的具體定義式為：

Coedge(u,v)=|friends-measure(u,v)|，(16)

其中，定義δ(x,y)函數(shù)為：

(18)

該特征計算了兩個節(jié)點u、v的鄰居節(jié)點之間的連邊數(shù)，共同鄰居朋友數(shù)特征將共同鄰居節(jié)點也定義為有連邊的情況，因此共同鄰居朋友數(shù)特征包含共同鄰居特征如圖1。

圖1 共同鄰居與共同鄰居朋友數(shù)特征

使用朋友數(shù)特征，對上面的6個基于共同鄰居的相似性特征進行擴展，得到基于共同鄰居連邊的特征，具體定義為：

(19)

(20)

(21)

(22)

(23)

(24)

2.3 子圖特征

在節(jié)點較多、結(jié)構復雜的網(wǎng)絡中，子圖可以清晰的刻畫出網(wǎng)絡中的局部結(jié)構，有助于分析節(jié)點在局部結(jié)構中的特性，因此將子圖特征引入到鏈路預測中。本文將子圖特征分為基于鄰居子圖和邊子圖兩大類。

2.3.1 基于鄰居子圖的特征

首先根據(jù)鄰居朋友的定義，推導出單個節(jié)點v的鄰居子圖定義如下：

nh-subgraph(v)={(x,y),(y,z),(z,x)∈E|x,y,z∈Γ(v)}。鄰居子圖就是節(jié)點的鄰居節(jié)點構成的三角形如圖2。圖中虛線框住的部分就是鄰居子圖結(jié)構。

圖2 鄰居子圖結(jié)構

在此基礎上得出v的鄰居子圖數(shù)目的定義為：

Subgraph-num(v)=|nh-subgraph(v)|。

(25)

根據(jù)v的鄰居子圖和鄰居子圖數(shù)目的定義，可以推導出兩個節(jié)點u和v的鄰居子圖和數(shù)目定義為：

Subvertex-num(u,v)=max{Subgraph-num(u),Subgraph-num(v)}。

(26)

根據(jù)節(jié)點u和v鄰居子圖數(shù)目的定義，將基于共同鄰居的特征擴展為基于鄰居子圖的特征，定義如下：

(27)

(28)

(29)

(30)

(31)

(32)

2.3.2 基于邊子圖的特征

首先使用鄰居朋友的定義，得出節(jié)點u和v的邊子圖特征為：

nh-edge-subgraph(u,v)={(x,y)∈E|x,y∈Γ(u)∪Γ(v)} 。

(33)

邊子圖刻畫了節(jié)點u和v的鄰居節(jié)點之間構成的三節(jié)點圖結(jié)構如圖3，圖中虛線框中的部分就是邊子圖結(jié)構。

圖3 邊子圖結(jié)構

通過上面的定義，能夠得出邊子圖的數(shù)目如下：

K-Subedge-num(u,v)=|nh-edge-subgraph(u,v)|。

(34)

將共同鄰居連邊特征中的朋友特征與邊子圖特征結(jié)合可以得到基于邊子圖的共同鄰居連邊特征，定義如下：

(35)

根據(jù)邊子圖數(shù)目的定義，將基于共同鄰居的特征擴展為基于邊子圖的特征，定義為：

(36)

(37)

(38)

(39)

(40)

3 多類別特征的鏈路預測方法

研究中首先將提取出的一系列網(wǎng)絡結(jié)構特征分為五類，然后選取合適的特征選擇方法，揭示類內(nèi)特征之間的關系和影響力，并使用二分類機器學習算法進行鏈路預測，最后通過評價特征AUC來衡量鏈路預測的結(jié)果。

3.1 多類別特征的構建

特征工程是鏈路預測當中一個重要環(huán)節(jié)，在實驗中將所有特征分為五類，分別是節(jié)點的度和中心性特征、共同鄰居節(jié)點特征、共同鄰居連邊特征、基于共同鄰居的子圖特征以及基于邊的子圖特征，并計算了在科學家合作網(wǎng)絡中節(jié)點的特征值。節(jié)點屬性特征見表2。

表2 節(jié)點特征及表示符號

連邊特征見表3。分為兩類，基于共同鄰居節(jié)點的特征和基于共同鄰居連邊的特征。

表3 連邊特征及表示符號

子圖特征見表4，包括基于鄰居子圖和邊子圖的兩類特征，鄰居子圖和邊子圖的定義已在2.3節(jié)中做了詳細說明。

表4 子圖特征及表示符號

續(xù)表4 子圖特征及表示符號

3.2 多類別特征的選擇

特征選擇方法大致可分為封裝法、過濾法和嵌入法，這三種方法的主要區(qū)別在于特征選擇與機器學習分類算法的結(jié)合方式不同[27-29]。過濾法是將所有的特征作為初始的特征子集，然后釆用與類別相關的評價特征來衡量特征對類別的區(qū)分能力，由于特征選擇過程獨立于分類過程，過濾方法僅依靠數(shù)據(jù)的內(nèi)在屬性來評估特征的相關性[30]。封裝法是將模型假設搜索加入到特征選擇過程中，即搜索算法被“封裝”到分類模型中，是以達到最大分類準確率為引導的一類特征選擇方法。在封裝模型中，分類算法被當作一個黑盒用來評價特征子集的性能，其特征選擇是利用分類學習算法的性能來評價特征本身的優(yōu)劣[31]。嵌入法是過濾法和封裝法的綜合，將特征選擇方法嵌入到模型學習中。嵌入法的分類效果取決于選擇的特征模型和具體學習算法。其中，最關鍵的就是損失函數(shù)和參數(shù)的確定。這也是該方法中的難點，需要靠一定的經(jīng)驗來尋找到最優(yōu)參數(shù)，使得特征選擇結(jié)果最佳[32-33]?；谇度敕ù嬖谏鲜鋈秉c，因此在后續(xù)實驗中不考慮該特征選擇方法。

綜合過濾法與封裝法各自的優(yōu)劣和研究中普遍使用的方法的優(yōu)缺點，本文采用了最大信息數(shù)與基于XGBoost模型的特征排序相結(jié)合的特征選擇方法。

基于XGBoost模型的特征排序方法本質(zhì)上是根據(jù)XGBoost算法的預測性能來衡量特征的優(yōu)劣，在模型訓練過程中，可以得到每個特征的評分值。分值越高說明特征在模型分裂決策樹過程中的權值越大，即特征對模型預測效果有著巨大的影響，特征分數(shù)值越高，則該特征在預測過程中越重要。

最大信息數(shù)(maximal information coefficient, MIC)是2011年發(fā)表在science上的一種基于互信息的新奇關聯(lián)方法[34]，具備普適性、公平性和對稱性的特點。普適性是指MIC支持多種類變量間的函數(shù)關系及非函數(shù)關系；公平性是指在樣本量足夠大的情況下，能對不同類型單噪聲程度相似的相關關系賦予相近的相關系數(shù)；對稱性是指MIC(X,Y)=MIC(Y,X)[35-36]。MIC的計算主要包括三個步驟：首先對于給定列數(shù)i和行數(shù)j，將變量(X,Y)構成的散點圖進行i列j行網(wǎng)格化，并求出最大互信息值；然后對最大的互信息值進行歸一化；最后將不同尺度下互信息的最大值作為MIC值。MIC的定義如下：

(41)

式中：I[X;Y]表示變量X和Y之間的互信息；|X|,|Y|表示散點圖網(wǎng)格在X和Y方向上分別被分成了多少段，|X||Y|

本文利用MIC來分析相似性特征類內(nèi)和類間的相互關系，定義MIC(fi,fj)為任意兩個相似性特征fi和fj之間的相關性(也是冗余性)。MIC(fi,fj)的值越大，說明fi和fj之間的相關性越高，即相似程度越高，互為冗余特征。MIC(fi,fj)=0說明fi和fj之間相互獨立。

3.3 XGBoost算法

XGBoost算法的全稱為Extreme Gradient Boosting，是一種基于決策樹的分布式高效梯度提升算法[37]。通過集成多個性能較差的弱學習器而形成一個強學習器，從而很好的擬合訓練數(shù)據(jù)并描述輸入輸出數(shù)據(jù)間的復雜非線性關系，提升計算精度，確保模型的計算效率。XGBoost算法在傳統(tǒng)GBDT算法的基礎上進行了改進，相比于只利用一階導數(shù)信息的傳統(tǒng)GDBT，XGBoost對損失函數(shù)進行了二階泰勒展開，且在目標函數(shù)中增加了正則化項，整體求最優(yōu)解，從而控制目標函數(shù)和模型的復雜程度，有利于防止過擬合，提高模型的泛化能力[38]。XGBoost算法步驟主要包括定義樹提升模型、目標函數(shù)構建、梯度提升策略和目標函數(shù)優(yōu)化。

3.4 評價特征

本文使用AUC(area under the receiver operating characteristic curve)作為評價特征，它是最常用的一種衡量特征，從整體上來衡量算法的精確度。AUC是計算在測試集中隨機選擇一條邊的分數(shù)值比隨機選擇的一條不存在的邊的分數(shù)值高的概率。具體過程為每次隨機從測試集中選取一條邊，再從不存在的邊中隨機選擇一條，如果測試集中的邊分數(shù)值大于不存在的邊的分數(shù)，就加1分；如果兩個分數(shù)值相等，就加0.5分。這樣獨立比較次，如果有次測試集中的邊分數(shù)值大于不存在的邊分數(shù)，有次兩次分數(shù)值相等[39]，則AUC定義為：

(41)

4 實驗結(jié)果分析

4.1 基于科學家合作網(wǎng)的鏈路預測結(jié)果分析

基于科學家合作網(wǎng)，使用上述五類網(wǎng)絡結(jié)構特征進行鏈路預測，并分析實驗結(jié)果。在對5類相似性特征分別使用XGBoost算法進行鏈路預測，并與傳統(tǒng)預測方法比較的基礎之上，接下來又針對5個科學家合作網(wǎng)，使用機器學習算法XGBoost對5類特征類別間的預測結(jié)果進行了比較分析見表5。

表5 5種科學家合作網(wǎng)的鏈路預測結(jié)果

根據(jù)表中的預測結(jié)果分析可知，在前4種科學家合作網(wǎng)中，使用基于邊子圖的特征得到的AUC值最高，因此該類特征在鏈路預測中的效果最好。由于科學家合作網(wǎng)作者之間的合作關系呈現(xiàn)的主要特征就是邊子圖形式，因此基于邊子圖特征的預測準確率高。

在geom網(wǎng)絡中，鄰居子圖特征的預測結(jié)果要高于邊子圖特征，為了探究其具體原因，從網(wǎng)絡結(jié)構出發(fā)，對5個科學家合作網(wǎng)的度分布和社團特性進行了具體分析。

根據(jù)圖4的網(wǎng)絡度分布，發(fā)現(xiàn)科學家合作網(wǎng)的度分布呈現(xiàn)相同的趨勢，度值較小的節(jié)點在網(wǎng)絡中的比例較大。度值范圍在0～5之間的節(jié)點在網(wǎng)絡中的比例在70%～80%左右，且網(wǎng)絡中占比最大的節(jié)點度值集中在1～2。由此可知，科學家合作網(wǎng)中的社團結(jié)構較為明顯。

圖4 5個科學家合作網(wǎng)度分布

根據(jù)表6可以看出與其他4個網(wǎng)絡相比，網(wǎng)絡geom的模塊度較低且社團數(shù)量遠遠高于其他網(wǎng)絡。因此該網(wǎng)絡的聚合程度較低，即節(jié)點之間的聯(lián)系不夠緊密。這樣就會導致社團劃分之后的社團數(shù)量很多。

根據(jù)圖5分析可知，構成鄰居子圖至少需要4個節(jié)點，邊子圖由于計算的是兩個節(jié)點之間的結(jié)構，因此構成該結(jié)構至少需要5個節(jié)點。而在geom網(wǎng)絡中社團數(shù)目較多，因此包含5個節(jié)點以上的社團結(jié)構的比例較少，構成邊子圖的可能性也較低，因此在預測中，鄰居子圖特征的預測結(jié)果高于邊子圖特征。

表6 網(wǎng)絡模塊度及社團數(shù)量

圖5 鄰居子圖和邊子圖結(jié)構對比圖

4.2 基于節(jié)點的類內(nèi)特征分析

為了具體分析每類特征對鏈路預測的影響，本文在接下來的實驗中以netscience網(wǎng)絡為例，進一步對每類特征做了特征排序以及特征相關性分析。

如圖6基于分類模型算法得到的節(jié)點特征影響力排序。從中可以看出，該類特征對鏈路預測的影響力依次遞減。PageRank中心性對鏈路預測的影響最大，節(jié)點的度和度中心性對鏈路預測的影響最小。

圖6 節(jié)點特征排序

4.2.1 特征相關性分析

使用最大信息數(shù)(MIC)計算得到的特征之間的相關性如圖7。這5個特征與其它特征之間的相關性均低于0.9，即這些特征都是相互獨立的，它們在鏈路預測中的作用不同，因此這些特征之間不可以相互替代。

圖7 特征相關性

4.2.2 鏈路預測結(jié)果

將節(jié)點屬性特征作為模型的輸入，使用分類器模型預測網(wǎng)絡中的鏈路得到鏈路預測AUC值見表7。從表中可以看出，使用所有節(jié)點特征得到的AUC值為0.748，去掉特征排序中影響力等級最低的節(jié)點的度和度中心性后，AUC值為0.711，與所有特征的AUC值相差較小，所以節(jié)點的度和度中心性特征對鏈路預測結(jié)果影響非常小，因為通過計算發(fā)現(xiàn)節(jié)點的度值在1～30之間變化，差距較小，因此該特征不足以區(qū)分節(jié)點間差異。度中心性計算的是一個節(jié)點的度值占整個網(wǎng)絡最大可能度值的比例，而使用的科學家合作網(wǎng)網(wǎng)絡節(jié)點數(shù)為7 886，網(wǎng)絡最大可能度值也就是7 886，導致計算度中心性時分母與分子差距較大，得到的每個節(jié)點的度中心性值相差很小，無法體現(xiàn)出不同節(jié)點之間的差異。在去掉節(jié)點的度和度中心性的基礎上，又根據(jù)特征相關性，發(fā)現(xiàn)剩余的5個特征之間的相關性都較小，因此這些特征都是相對獨立的。通過以上去冗余、去相關，可以得到該類特征的最優(yōu)特征子集U1，U1={Average_neighbor_degree, eigenvector_centrality, pageran-k，clustering_coefficient，betweenness_centrality}

表7 鏈路預測結(jié)果

4.3 子圖特征分析

使用基于XGBoost模型的特征排序可以得到基于鄰居子圖的特征的影響力分值。將得到的影響力分值進行整理、排序，繪制?；卩従幼訄D相似性特征的影響力排序柱狀圖如圖8。從圖中可以看出，部分特征影響力分值較高，如jaccard_subvertex、HD_subvertex、LHN_subvertex和subvertex，這些特征對鏈路預測影響較大；其他基于鄰居子圖特征影響力分值較低，如HP_subvertex的分值最低，因此這個特征對鏈路預測影響較小。

圖8 子圖特征排序

4.3.1 特征相關性分析

特征排序前4的子圖特征之間的相關性如圖9。這4個特征中jaccard_subvertex和HD_subvertex之間的相關性較高，說明這2個特征比較相似。LHN_subvertex和subvertex特征與其他特征之間相關性較低，說明這兩個特征在預測中相對獨立。

圖9 基于子圖特征相關性

4.3.2 鏈路預測結(jié)果

使用基于鄰居子圖相似性特征作為XGBoost模型的輸入得到的AUC值與進行特征選擇后的AUC值見表8。從表中可以看出，使用所有特征得到的AUC值為0.831，只保留特征排序中影響力等級前4的特征后，AUC值為0.825，與所有相似性特征的AUC值相差較小，所以這些特征對鏈路預測結(jié)果影響較小。在去掉影響力低的特征基礎上，又根據(jù)特征相關性，去掉了強相關特征中的HD_subvertex，得到的AUC值為0.705，與上一步的AUC值差距較大，分析原因發(fā)現(xiàn)，雖然jaccard_subvertex和HD_subvertex之間的相關性較高，可能是冗余特征，但是這兩個特征在影響力排序中占據(jù)第1和第2位，十分重要，刪除其中一個會對預測結(jié)果影響較大。因此在去冗余、去相關的時要綜合考慮特征排序和相關性，根據(jù)特征選擇去除冗余特征之后，可以得到基于鄰居子圖相似性特征的最優(yōu)子集U2，U2={jaccard_subvertex，HD_subvertex，LHN_subvertex，subvertex}

表8 鏈路預測結(jié)果

4.4 基于邊子圖的特征

使用基于XGBoost模型的特征排序方法，可以根據(jù)特征特征在模型訓練過程中的重要程度得出特征特征的影響力分值。通過基于XGBoost模型的特征排序方法，可以得到基于邊子圖特征的影響力分值。該影響力分值得到的影響力排序柱狀圖如圖10。從圖中可以看出，部分特征影響力分值較高，如commonfriends_subedge、subedge、LHN_subedge、HD_subedge和HP_subedge，這些特征對鏈路預測影響較大；其他鄰居子圖相似性特征影響力分值較低，如sorenson_subedge的分值最低，因此這個特征對鏈路預測影響較小。

圖10 子圖特征排序

4.4.1 特征相關性分析

通過最大信息數(shù)(MIC)可以衡量各個特征間的相關性。MIC值的范圍是0～1，MIC值越大，說明兩個特征間相關性越高，越相似。去掉影響力排序后3位的salton_subedge、sorenson_subedge和jaccard_subedge后，得到的前5位邊子圖相似性特征之間的相關性如圖11。這5個特征可以分為三類，第一類為commonfriends_subedge，這個特征僅與其本身的相關性較高，與其他特征之間的相關性很低，因此相對獨立；第二類為subedge和HD_subedge，這兩個特征與除了第一類的其他特征之間的相關性較高，分值集中在0.7～0.9；第三類為LHN_subedge和HP_subedge特征，它們之間具有很強的相關性。

圖11 基于子圖特征相關性

4.4.2 鏈路預測結(jié)果

使用基于邊子圖特征作為模型的輸入得到的AUC值見表9。從表中可以看出，使用所有特征得到的AUC值為0.867，只保留特征排序中影響力等級前5的特征后，AUC值為0.854，與所有特征的AUC值相差很小，所以這些特征對鏈路預測結(jié)果影響較大。在去掉影響力低的特征基礎上，又根據(jù)特征相關性，去掉了第二類強相關特征中的HP_subedge，得到的AUC值為0.850，與上一步的AUC值相同，因此根據(jù)相關性去掉部分冗余特征后，可以達到與之前接近的預測效果。根據(jù)特征選擇去除冗余特征之后，可以得到子圖特征的最優(yōu)子集U3，U3={commonfriends_subedge，subedge，HD_subedge, LHN_subedge }

表9 鏈路預測結(jié)果

4.5 所有特征分析

為了分析相似性特征在鏈路預測中的重要性，刪除冗余特征，我們將單類特征選擇分析中得到的最優(yōu)子集U1、U2、U3、U4、U5合并為特征子集U，并對該特征子集中的相似性特征使用基于XGBoost模型的特征排序方法進行了重要性排序，結(jié)果如圖12。根據(jù)特征排序可知，這些特征在預測中的重要性呈現(xiàn)遞減趨勢。因此，在鏈路預測中，排序靠前的特征特征比排序落后的特征更具影響力。在后續(xù)分析中保留了前10個影響力大的特征。

圖12 netscience網(wǎng)絡所有特征排序

為了分析特征之間的相互關系，刪除在鏈路預測中相關性非常高的相似特征，我們對前10個影響力大的相似性特征使用MIC進行相關性分析如圖13。5類特征中， LHN_coedge和commonfriends_subedge特征之間有較強相關性；對于這些強相關特征，在鏈路預測中只保留其中一個即可，因此，結(jié)合圖123特征排序，刪除了排序較后的LHN_coedge特征，使得最終保留的9個特征之間都相互獨立。

圖13 netscience網(wǎng)絡排序前15的特征相關性

將所有特征作為XGBoost模型的輸入，使用分類器模型預測網(wǎng)絡中的鏈路得到鏈路預測AUC值見表10。從表中可以看出，使用未進行特征選擇的所有特征得到的AUC值為0.967，而使用單類特征選擇之后得到的子集U的AUC值為0.965，與特征選擇之間相差很小，說明特征選擇過程可以幫助我們刪除預測中部分冗余特征。對特征子集U進一步做特征選擇，去掉特征排序中影響力等級低的相似性特征以及特征相關性中的部分強相關特征后，AUC值為0.959，與特征子集U的AUC值相差較小，說明在去冗余和去相關之后得到了與原始特征非常接近的預測結(jié)果。說明特征選擇在多類別的網(wǎng)絡結(jié)構特征中起到了關鍵性作用，進行特征選擇可以在降低特征維數(shù)的同時，保證預測效果達到與特征選擇之前相近的水平。

表10 鏈路預測結(jié)果

5 結(jié) 論

本文提出基于多類別網(wǎng)絡結(jié)構特征的鏈路預測方法，對科學家合作網(wǎng)絡中的作者合作關系進行了研究。首先根據(jù)短信數(shù)據(jù)構建了無向無權社交網(wǎng)絡。其次，提取了一系列網(wǎng)絡結(jié)構特征并將其征分為五類，包括節(jié)點特征、基于共同鄰居的節(jié)點特征、基于共同鄰居的邊特征、基于鄰居的子圖特征和基于邊的子圖特征。同時使用基于模型的特征排序和最大信息數(shù)特征選擇方法分析了特征之間的關系，去除了冗余特征。最后，通過機器學習算法模型進行鏈路預測。使用這種鏈路預測框架對網(wǎng)絡進行分析，可以提高鏈路預測的準確性。與此同時，能夠揭示各個特征在模型訓練中的重要性和特征之間的相互關系，通過類內(nèi)和類間特征相關性分析，更直觀的找到網(wǎng)絡中的強相關特征，即可替代性強的冗余特征。在鏈路預測中，選取合適的特征選擇方法去相關、去冗余的過程可以應用到其他社會網(wǎng)絡中。