許 爽，李淼磊

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 構(gòu)建網(wǎng)絡(luò)

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

x=cAx。

(6)

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

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

(7)

式中：標(biāo)度常數(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ù)測中具有復(fù)雜度低且準(zhǔn)確率較高的優(yōu)勢。研究中將共同鄰居特征以及由共同鄰居衍生出的一些特征歸為一個大類，從節(jié)點和邊的角度出發(fā)將共同鄰居特征分為基于節(jié)點和連邊兩類特征。

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

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

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é)點之間的關(guān)系，且在預(yù)測中具有復(fù)雜度低且準(zhǔn)確率較高的優(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é)構(gòu)復(fù)雜的網(wǎng)絡(luò)中，子圖可以清晰的刻畫出網(wǎng)絡(luò)中的局部結(jié)構(gòu)，有助于分析節(jié)點在局部結(jié)構(gòu)中的特性，因此將子圖特征引入到鏈路預(yù)測中。本文將子圖特征分為基于鄰居子圖和邊子圖兩大類。

2.3.1 基于鄰居子圖的特征

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

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

圖2 鄰居子圖結(jié)構(gòu)

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

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

(25)

根據(jù)v的鄰居子圖和鄰居子圖數(shù)目的定義，可以推導(dǎo)出兩個節(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é)點之間構(gòu)成的三節(jié)點圖結(jié)構(gòu)如圖3，圖中虛線框中的部分就是邊子圖結(jié)構(gòu)。

圖3 邊子圖結(jié)構(gòu)

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

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

(34)

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

(35)

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

(36)

(37)

(38)

(39)

(40)

3 多類別特征的鏈路預(yù)測方法

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

3.1 多類別特征的構(gòu)建

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

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

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

表3 連邊特征及表示符號

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

表4 子圖特征及表示符號

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

3.2 多類別特征的選擇

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

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

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

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

(41)

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

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

3.3 XGBoost算法

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

3.4 評價特征

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

(41)

4 實驗結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.1 特征相關(guān)性分析

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

圖7 特征相關(guān)性

4.2.2 鏈路預(yù)測結(jié)果

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

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

4.3 子圖特征分析

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

圖8 子圖特征排序

4.3.1 特征相關(guān)性分析

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

圖9 基于子圖特征相關(guān)性

4.3.2 鏈路預(yù)測結(jié)果

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

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

4.4 基于邊子圖的特征

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

圖10 子圖特征排序

4.4.1 特征相關(guān)性分析

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

圖11 基于子圖特征相關(guān)性

4.4.2 鏈路預(yù)測結(jié)果

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

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

4.5 所有特征分析

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

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

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

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

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

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

5 結(jié) 論

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