基于子圖特征的科學家合作網絡鏈路預測

許 爽，李淼磊

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

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

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

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

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

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

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

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

1 數據說明和網絡構建

1.1 數據說明

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

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

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

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

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

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

5個科學家合作網中的節點數和連邊數見表1。

表1 科學家合作網數據說明

根據所給數據，本文首先將網絡數據文件讀取出來并轉換成后綴為.txt的文件，為下一步構建網絡做準備。

1.2 構建網絡

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

2 網絡結構統計特征

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

2.1 節點度及中心性特征

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

x=cAx。

(6)

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

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

(7)

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

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

(8)

2.2 共同鄰居特征

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

2.2.1 基于節點的共同鄰居特征

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

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

(9)

(13)

(14)

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

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

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

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

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

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

(18)

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

圖1 共同鄰居與共同鄰居朋友數特征

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

(19)

(20)

(21)

(22)

(23)

(24)

2.3 子圖特征

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

2.3.1 基于鄰居子圖的特征

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

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

圖2 鄰居子圖結構

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

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

(25)

根據v的鄰居子圖和鄰居子圖數目的定義，可以推導出兩個節點u和v的鄰居子圖和數目定義為：

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

(26)

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

(27)

(28)

(29)

(30)

(31)

(32)

2.3.2 基于邊子圖的特征

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

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

(33)

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

圖3 邊子圖結構

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

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

(34)

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

(35)

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

(36)

(37)

(38)

(39)

(40)

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

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

3.1 多類別特征的構建

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

表2 節點特征及表示符號

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

表3 連邊特征及表示符號

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

表4 子圖特征及表示符號

續表4 子圖特征及表示符號

3.2 多類別特征的選擇

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

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

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

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

(41)

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

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

3.3 XGBoost算法

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

3.4 評價特征

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

(41)

4 實驗結果分析

4.1 基于科學家合作網的鏈路預測結果分析

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

表5 5種科學家合作網的鏈路預測結果

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

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

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

圖4 5個科學家合作網度分布

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

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

表6 網絡模塊度及社團數量

圖5 鄰居子圖和邊子圖結構對比圖

4.2 基于節點的類內特征分析

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

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

圖6 節點特征排序

4.2.1 特征相關性分析

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

圖7 特征相關性

4.2.2 鏈路預測結果

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

表7 鏈路預測結果

4.3 子圖特征分析

使用基于XGBoost模型的特征排序可以得到基于鄰居子圖的特征的影響力分值。將得到的影響力分值進行整理、排序，繪制。基于鄰居子圖相似性特征的影響力排序柱狀圖如圖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 鏈路預測結果

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

表8 鏈路預測結果

4.4 基于邊子圖的特征

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

圖10 子圖特征排序

4.4.1 特征相關性分析

通過最大信息數(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 鏈路預測結果

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

表9 鏈路預測結果

4.5 所有特征分析

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

圖12 netscience網絡所有特征排序

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

圖13 netscience網絡排序前15的特征相關性

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

表10 鏈路預測結果

5 結 論

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