端點活躍度對鏈接預測的影響研究

楊凱凱,錢宇華,馬國帥,艾 科

(山西大學 大數據科學與產業研究院,太原 030006) (山西大學 計算智能與中文信息處理教育部重點實驗室,太原 030006) (山西大學 計算機與信息技術學院,太原 030006)

1 引 言

現實生活中,許多復雜系統都可以建模成復雜網絡進行分析,復雜網絡的重要節點和鏈接的挖掘[1]、社區發現[2]、鏈路預測[3]等研究得到了越來越多的國內外研究學者的關注.鏈路預測(Link Prediction)[4]旨在通過已知的網絡結構信息和節點屬性信息預測網絡中尚未產生鏈接的兩個節點之間是否可能產生鏈接,主要用于還原缺失信息和預測未知信息,在社交網絡推薦[5]、生物信息分析[6]、交通網絡設計等領域具有巨大的實際應用價值.

基于相似性的鏈路預測的基本假設是:兩個節點之間的相似性越大,它們之間存在鏈接的可能性就越大.本文將兩個目標節點稱為端點,以區分鄰居節點、路徑中間節點等其他節點.研究學者從兩個角度刻畫端點間的相似性:一種是基于網絡的拓撲結構信息[7],根據端點間的連接關系進行預測;另一種是基于網絡節點的真實屬性信息[3],結合機器學習[8]的方法進行鏈接的預測.但是由于節點屬性信息不易獲取且常伴隨著大量噪音,相比而言,網絡的結構信息容易獲取且比較可靠;同時基于拓撲結構的預測方法對于結構相似的網絡具有普適性.因此,本文主要研究基于網絡拓撲結構的鏈路預測算法,它主要分為三類相似性指標,一種是共同鄰居指標CN[9],通過節點間共同鄰居的個數來估計節點之間的相似性,隨后研究者又從不同的角度對其進行改進[10].第二種是基于路徑的相似性指標,如LP指標[11]、Katz指標[12],它們認為兩端點間可以通信的路徑條數越多、長度越短,其產生鏈接的可能性越大.第三種是基于隨機游走的相似性指標:RWR指標[12],SRW指標[14].

現有的鏈路預測指標僅考慮兩端點間的連接關系,忽略了端點自身活躍性對鏈接產生的不同影響.例如在社交網絡中名人更容易交到更多的朋友;交通網絡中新線路多是與樞紐節點相連;萬維網中,網頁中的新鏈接多是指向權威網站,由此可見往往越是活躍的端點,其產生鏈接的可能性更大.本文從度中心性[15]、介數中心性[16]、接近中心性[17]、Pagerank[13]四個角度刻畫端點的活躍度,研究不同的端點活躍度對鏈接產生的不同影響.通過大量的實證分析發現,端點的活躍度越強,其產生鏈接的可能性越大,其中又以度中心性,Pagerank表現更為顯著.因此,本文在基于端點間連接關系的基礎上考慮端點自身活躍程度,提出了一類基于端點活躍度的鏈路預測方法,并在8個真實網絡數據上進行實驗,預測精度比原有的指標有較大的提高.

本文其它章節內容安排如下:第二節中介紹了四種刻畫端點活躍度的方法;鏈路預測實驗設計方法;幾種經典的鏈路預測指標和本文中用到的8個真實數據.第三節分析討論了端點活躍性對鏈接產生的影響.第四節介紹了利用端點活躍度對傳統鏈路預測指標進行改進,并比較原有指標和改進后的指標的預測精度.第五節對本研究的總結與展望.

2 相關工作

2.1 節點中心性

網絡中端點的活躍度越大,其可能更容易產生新的鏈接.本文從度中心性[15]、介數中心性[16]、接近中心性[17]、Pagerank[13]四個角度刻畫端點的活躍度.

1)度中心性(Degree Centrality,DC)[15]

度中心性通過端點可直接交互的鄰居數量來刻畫端點的活躍度,其定義為:

(1)

其中ki為節點的度值,N為網絡節點個數.

2)介數中心性(Betweeness Centrality,BC)[16]

網絡中經過某端點傳遞信息的路徑越多,它就越活躍,這就是介數中心性,其定義為:

(2)

3)接近中心性(Closeness Centrality,CC)[17]

接近中心性表明了端點與其他節點交互的便利程度,該端點到其他節點的平均路徑越短,它就越活躍.其定義為:

(3)

其中,dij表示節點i到節點j的距離.

4)Pagerank(PR)[13]

端點能交互的節點越多,這些節點越重要,該節點就越活躍,這種活躍度稱為Pagerank,其定義為:

(4)

2.2 鏈路預測

定義G(V,E)為一個無向網絡,其中V為節點集合,E為邊集合.網絡總的節點數為N,邊數為M.此網絡共有N(N-1)/2個節點對,即全集U.將已知的鏈接E分為兩部分,訓練集ET和測試集EP.在訓練集中計算節點對的相似性,在測試集中,通過AUC來衡量鏈路預測算法精確度.AUC 可以理解為在測試集中的邊的分數值比隨機選擇的一個不存在的邊的分數值高的概率,其大于0.5的程度衡量了算法在多大程度上比隨機選擇的方法精確.

基于網絡拓撲結構的鏈路預測方法主要分為三類:共同鄰居方法,基于路徑的方法,和基于隨機游走的方法.下面分別介紹這幾種方法的代表性指標.

1)共同鄰居(CN)[9]

對于網絡中的節點x,定義其鄰居集合為Γ(x),則兩個節點x和y的相似性定義為他們共同鄰居數(CN),即:

(5)

CN指標只考慮共同鄰居的個數,后來,陳嘉穎[18]等人考慮共同鄰居節點的重要性提出了CN-DC,CN-BC,CN-CC,CN-PR等方法,其定義為:

(6)

其中Cz表示節點z不同的中心性指標(DC,BC,CC,PR).

2)局部路徑指標(LP)[11]

LP指標是一種基于路徑的局部性指標,該指標只考慮二階路徑和三階路徑對鏈接產生的影響.其定義為:

(7)

其中α為可調參數,A為鄰接矩陣,A2,A3分別表示節點x與節點y之間長度為2,3的路徑數目.

3)全局路徑指標(Katz)[12]

Katz指數是一種基于所有路徑的全局性指標,定義為:

(8)

其中,β>0為控制路徑權重的可調參數.

4)有重啟的全局隨機游走指標(RWR)[12]

RWR指標是一種基于全局信息的隨機游走指標,它假設隨機游走粒子在每走一步的時候都以一定的概率返回初始位置.若某一粒子初始時刻在節點x處,那么時刻該粒子到達網絡各個節點的概率向量為:

(9)

(10)

5)局部隨機游走指標(SRW)[14]

基于全局的隨機游走指標計算復雜度比較高,劉偉平和呂琳媛提出有疊加效應的局部隨機游走的相似性指標SRW.一個粒子t時刻從節點x出發,定義為t+1時刻這個粒子正好走到節點y的概率:

πx(t+1)=PTπx(t),t≥0

(11)

(12)

將t步及其以前的結果加總便得到的值,即:

(13)

2.3 數據集

本文采用了8個真實的網絡數據,涉及社會網絡、生物網絡和技術網絡等領域. 在表1中羅列出刻畫網絡特征常用的7個統計量符號及其含義,表2中將8個真實網絡的7個統計量值呈現出來.

表1 統計符號及含義
Table 1 Statistical symbols and meaning

符號含 義符號含 義N網絡的節點數M網絡的邊數網絡的平均度C網絡的集聚系數D網絡的直徑L平均路徑長度ρ網絡的密度

表2 8個真實網絡的統計量
Table 2 Statistical measure of eight real networks

網絡NMCDLρadjnoun1124257.5890.17352.5360.068ucforum899701915.6150.07162.8660.017brain9158212.7910.86031.8680.142router502262582.4920.012156.4490.001foodweb183243426.6010.32342.1470.146florida128207532.4220.33531.7760.255karate34784.5880.57152.4080.139polblogs12221671427.3550.32082.7380.022

3 端點活躍度對鏈接的影響

以上介紹的各項基于網絡拓撲結構的鏈路預測指標僅考慮兩端點間的連接關系,忽略了端點活躍度對鏈接的不同影響,往往端點越活躍,其更容易產生新的鏈接.本文為研究端點活躍度對鏈接的影響進行了三項分析:

1.活躍度對鏈接的影響分析:計算不同活躍值下,端點平均產生鏈接的條數.

2.不同活躍度對鏈接的影響程度分析:計算基于鏈接的活躍度均值與端點的活躍度均值的大小關系,以及其在活躍度分布中的位置.

3.活躍度對鏈接的影響驗證:假設端點間產生鏈接的概率只與端點活躍度成正比,進行鏈路預測,驗證不同活躍度對鏈接的不同影響.

通過上述方法研究在不同活躍度下,端點對鏈接產生的不同影響.圖1是分析過程.

3.1 活躍度對鏈接的影響分析

本文從度中心性DC、介數中心性BC、接近中心性CC、Pagerank(PR)四個角度來刻畫端點的活躍程度,計算基于不同中心性的活躍度下,端點產生鏈接的情況.圖2展示了在8個真實網絡中,不同活躍值下,端點平均產生鏈接的條數.圖2中,橫坐標表示不同的活躍值區間,即不同的活躍度c;縱坐端點活躍度對鏈接影響的分析過程

輸入:網絡G=(V,E),其中V和E分別表示G的節點集和邊集.

輸出:在基于不同中心性的活躍度下,端點對鏈接產生的不同影響.

過程:

1.將網絡分為訓練集和測試集,保證訓練集的連通性.

2.在訓練集中,計算網絡的各種中心性指標(包含DC,BC,CC, PR)C={C1,C2,C3,…,Cn},其中(1,2,3,…,n)∈V.

3.在測試集中,計算活躍值為c的端點平均產生鏈接的條數:

4.計算基于鏈接的中心性均值與節點中心性差值的大小關系:

6.利用端點活躍度進行鏈路預測:sim(x,y)=CxCy.

7.分析不同活躍度對鏈接產生的不同影響.

圖1 端點活躍度對鏈接影響的分析過程
Fig.1 Analysis method about the impact of endpoint
activity on links

標表示產生鏈接的條數R(c);柱狀圖中,灰色柱、黑色柱、白色柱、o型填充柱(從左到右)分別表示基于DC,BC,CC,PR的活躍值c下,端點平均產生鏈接的條數R(c).

圖2 端點的活躍程度對鏈接的影響Fig.2 Impact of endpoint activity of on links

從圖2中分析可得,在基于DC,BC,CC,PR的各種活躍性下,端點的活躍值較小時,其產生的鏈接也比較少,隨著活躍值的增大,其產生鏈接的條數也在增多.因此可得:端點越活躍,其產生鏈接的條數越多.

3.2 不同活躍度對鏈接的影響程度分析

·當d< 0時,說明活躍端點之間并不會更容易產生鏈接.

表3 不同中心性下的d值
Table 3dbased different centralities

網絡d(DC)d(BC)d(CC)d(PR)adjnoun1.0731-0.0603-0.06164.9458ucforum1.8691-0.1342 -0.022039.8743brain1.11400.31801.001414.5652router12.5038-0.4711-0.024042.3130foodweb 0.62480.14480.181015.0712 florida0.49890.00180.017912.3591karate0.4153-0.00840.34640.8566polblogs1.7513-0.17930.001136.6757

表3中,DC,PR的d值均為正值且較大,其中PR中心性表現尤為明顯,而在BC,CC中心性中,d值的負值較多,且正值較小,由此可見節點的Pagerank中心性越大,產生鏈接的可能性越大,DC次之,CC,BC表現效果差,其中BC指標可能起相反的作用.

通過大量的實證分析得出:端點越活躍,其產生鏈接的可能性越大,其中DC和Pagerank大的端點可能更容易產生新的鏈接.

3.3 活躍度對鏈接的影響驗證

根據上述結論,假設兩個端點是否產生鏈接只與兩個端點的活躍度有關,即端點產生新鏈接的概率正比于該端點的活躍值,定義相似性指標.

sim(x,y)=CxCy

(14)

來進行鏈路預測(其中Cx表示節點x的中心值).基于不同的活躍度產生不同的相似性指標,計算不同活躍性下的鏈接預測結果,如表5所示(括號中表示不同活躍度下預測算法的預測結果排序,黑體是預測效果最好的相似性指標).

網絡pos(cl)(DC)pos(cl)(BC)pos(cl)(CC)pos(cl)(PR)adjnoun0.81230.47160.69240.6129ucforum0.96290.46380.69770.6499brain0.87100.87690.88540.8377router0.99680.46540.67450.9223foodweb 0.76510.62070.84480.6725florida0.72900.52130.72260.5572karate0.68760.63060.67740.6912polblogs0.88730.46120.76240.6960

表5 不同中心性下的預測結果AUC
Table 5 AUC based different centralities

數據DCBCCCPRadjnoun0.7620(1)0.7362(4)0.7446(3)0.7604(2)ucforum0.8578(1)0.8412(4)0.8469(3)0.8548(2)brain0.9784(2)0.8516(4)0.9783(3)0.9842(1)router0.9544(1)0.9206(3)0.6986(4)0.9429(2)foodweb 0.8324(2)0.8100(3)0.7981(4)0.8415(1)florida0.7311(1)0.6985(4)0.7281(2)0.7258(3)karate0.7365(2)0.6420(4)0.6937(3)0.7654(1)polblogs0.9101(1)0.8818(4)0.8830(3)0.9093(2)

從以上的驗證分析中可以得出:在網絡中,端點基于度中心性和Pagerank的活躍度越強,其產生鏈接的可能性更大,因此本文在基于端點間連接關系的基礎上考慮端點的活躍度,提出一類基于端點活躍度的鏈路預測方法.

4 一類基于端點活躍度的鏈路預測方法

傳統的鏈路預測算法僅僅考慮網絡中兩端點的連接關系,并未考慮端點自身活躍度對鏈接產生的影響,從第三節的實證分析中可以得出:在真實網絡中,端點基于度中心性和Pagerank的活躍度越強,產生鏈接的可能性越大.因此,本文在基于兩端點間連接關系的基礎上考慮端點的活躍度,提出了一類基于端點活躍度(Endpoint Activity,EA)的鏈路預測方法:

EAsim(x,y)=CxCysim(x,y)

(15)

其中,Cx表示節點的中心值,sim(x,y)表示原有的相似性算法.本文選取了原始指標是共同鄰居CN指標,局部路徑指標LP、全局性指標Katz(分別取參數值0.01,0.001),全局性隨機游走指標RWR(分別取參數值0.85,0.95)和局部性指標SRW(分別取參數值3,4,5).

實驗結果如圖3和圖4所示:圖中橫坐標表示不同的鏈路預測指標;縱坐標表示AUC預測精度;在柱狀圖中,淺色柱代表原有指標的預測精度,灰色柱代表基于度中心性的端點活躍度預測指標,深灰色柱代表基于PageRank的端點活躍度預測指標.

圖3 不同相似性指標下的AUC預測結果Fig.3 AUC results for different similarity indexes

從圖3中可以看出考慮兩個端點基于度中心性和Pagerank活躍度指標的預測精度比原指標有極大改進,其中在adjnoun,ucforum數據中改進效果明顯,在brain,router數據中,在原有指標預測精度已經高達0.90以上后,活躍度指標仍能使預測精度有一定的提升.

圖4 不同相似性指標下的AUC預測結果Fig.4 AUC results for different similarity indexes

在foodweb,florida數據中,除RWR指標外,對其他指標均有改進.在karate數據中,DC對原有指標的改進效果并不理想,PR中心性除RWR指標外,對其他指標均有改進.在polblog數據中,雖然對原有指標改進效果并不理想,但是可以通過改進得到預測效果最佳的新指標.

隨后,本文在已經考慮了共同鄰居的節點中心性指標的CN-DC,CN-PR的基礎上增加考慮端點的活躍度,按照公式(15)形成新的鏈路預測指標EA_CNDC,EA_CNPR.

觀察表6可得,除了polblogs數據外,其他數據的他預測精度均有提升,并且提升幅度較大.即便是在polblogs數據上,其預測精度與原有指標的預測進度相差無幾.因此可以得出,增加考慮端點活躍度可以提高預測精度.

由上述實驗可得,對原有鏈路預測指標加入端點基于度中心性和Pagerank中心性的活躍性后,其預測精度得到有效提升.因此在鏈路預測過程中考慮端點活躍度是一種有效的提升策略.

表6 不同相似性指標下的AUC預測結果
Table 6 AUC for different similarity indexes

數據CN-DCEA_CNDCCN-PREA_CNPRadjnoun0.68130.70140.69260.7007ucforum0.73810.74980.74590.7494brain0.73990.96040.79650.9615router0.65470.65520.65590.6563foodweb 0.75670.78840.76360.7803florida0.6080.65030.61870.6473karate0.70960.75130.70480.7542polblogs0.92280.92180.92380.9223

5 總結與展望

在基于網絡拓撲結構的鏈路預測算法中,主要關注兩端點之間的連接關系,忽略了端點的活躍度對鏈接的影響.本文選取了四種常用的節點中心性指標來刻畫節點的活躍程度.通過實驗分析可得端點越活躍,其產生鏈接的可能性也就越大,其中度中心性和Pagerank對鏈接產生的影響更為顯著.基于此現象,本文將基于度中心性和Pagerank的端點活躍度增加到現有的指標中,提出了一類基于端點活躍性的鏈路預測方法,并在8個真實網絡數據上進行實驗,發現此類方法的預測精度比原有指標有較大的提高.

本文通過研究了四種不同的端點活躍度對鏈接產生的不同影響,未來將融合端點活躍度與具體的網絡結構,根據實際情況有針對性地改進預測算法.另外,節點真實屬性也是影響鏈路預測的重要因素,如何將節點的真實屬性運用到鏈路預測中是未來研究的重點.