基于子圖特征的科學(xué)家合作網(wǎng)絡(luò)鏈路預(yù)測(cè)

許 爽，李淼磊

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

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

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

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

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

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

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

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

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

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

(1) netscience網(wǎng)絡(luò)：是由研究網(wǎng)絡(luò)科學(xué)的科學(xué)家組成的合作網(wǎng)絡(luò)，節(jié)點(diǎn)表示從事網(wǎng)絡(luò)科學(xué)研究的科學(xué)家，連邊表示兩個(gè)科學(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年計(jì)算幾何數(shù)據(jù)庫中作者之間的科學(xué)合作關(guān)系構(gòu)建的網(wǎng)絡(luò)。

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

5個(gè)科學(xué)家合作網(wǎng)中的節(jié)點(diǎn)數(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é)點(diǎn)集合，E為網(wǎng)絡(luò)中的邊集合。對(duì)于網(wǎng)絡(luò)中每兩個(gè)節(jié)點(diǎn)u,v∈V來說，鏈路預(yù)測(cè)就是判斷u與v之間存在鏈接的可能性。針對(duì)本文所使用的科學(xué)家合作關(guān)系數(shù)據(jù)，網(wǎng)絡(luò)中節(jié)點(diǎn)代表各個(gè)科學(xué)家，連邊代表科學(xué)家之間有合作關(guān)系，鏈路預(yù)測(cè)也就是判斷科學(xué)家之間有合作關(guān)系的可能性。將處理后的數(shù)據(jù)集分為兩部分：訓(xùn)練集ET和測(cè)試集EP，本文使用的訓(xùn)練集和測(cè)試集的比例為9∶1。

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

x=cAx。

(6)

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

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

(7)

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

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

(8)

2.2 共同鄰居特征

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

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

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

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

(9)

(13)

(14)

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

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

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

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

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

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

(18)

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

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

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

(19)

(20)

(21)

(22)

(23)

(24)

2.3 子圖特征

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

2.3.1 基于鄰居子圖的特征

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

nh-subgraph(v)={(x,y),(y,z),(z,x)∈E|x,y,z∈Γ(v)}。鄰居子圖就是節(jié)點(diǎn)的鄰居節(jié)點(diǎn)構(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)出兩個(gè)節(jié)點(diǎn)u和v的鄰居子圖和數(shù)目定義為：

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

(26)

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

(27)

(28)

(29)

(30)

(31)

(32)

2.3.2 基于邊子圖的特征

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

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

(33)

邊子圖刻畫了節(jié)點(diǎn)u和v的鄰居節(jié)點(diǎn)之間構(gòu)成的三節(jié)點(diǎn)圖結(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ù)目的定義，將基于共同鄰居的特征擴(kuò)展為基于邊子圖的特征，定義為：

(36)

(37)

(38)

(39)

(40)

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

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

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

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

表2 節(jié)點(diǎn)特征及表示符號(hào)

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

表3 連邊特征及表示符號(hào)

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

表4 子圖特征及表示符號(hào)

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

3.2 多類別特征的選擇

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

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

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

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

(41)

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

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

3.3 XGBoost算法

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

3.4 評(píng)價(jià)特征

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

(41)

4 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

使用最大信息數(shù)(MIC)計(jì)算得到的特征之間的相關(guān)性如圖7。這5個(gè)特征與其它特征之間的相關(guān)性均低于0.9，即這些特征都是相互獨(dú)立的，它們?cè)阪溌奉A(yù)測(cè)中的作用不同，因此這些特征之間不可以相互替代。

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

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

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

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

4.3 子圖特征分析

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

圖8 子圖特征排序

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

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

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

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

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

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

4.4 基于邊子圖的特征

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

圖10 子圖特征排序

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

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

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

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

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

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

4.5 所有特征分析

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

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

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

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

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

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

5 結(jié) 論

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