一種改進共同鄰居的節(jié)點遍歷鏈路預測算法
2018-03-27 01:26:05張志剛李世寶馬文麗陳海華劉建航
小型微型計算機系統(tǒng) 2018年2期
張志剛,李世寶,馬文麗,何 雅,陳海華,劉建航
(中國石油大學(華東) 計算機與通信工程學院,山東 青島 266580)
1 引 言
自然界中存在的大量復雜系統(tǒng)均可以抽象成由相互連接的節(jié)點所組成的復雜網絡,其中節(jié)點代表個體,鏈接反映個體之間的相互聯(lián)系,譬如社交網絡、生物網絡、交通網絡.通過對復雜網絡進行研究,我們可以更好的理解網絡結構生成和演化機制,也可以用來解決實際復雜系統(tǒng)中的問題.鏈路預測是連接復雜網絡與信息科學的重要紐帶,已成為復雜網絡研究中的熱點之一,其目的是基于已知的鏈接和節(jié)點屬性以及網絡拓撲結構對未知鏈接進行還原和預測[1].
鏈路預測可以對實際復雜系統(tǒng)中存在但未被我們觀察到的鏈接(遺失鏈接)[2]和將來可能產生的鏈接(未來鏈接)進行預測,對復雜系統(tǒng)的研究有巨大的實際應用價值[3].在蛋白質作用網絡中,有80%的相互作用關系是人類尚未挖掘出來的[4],可以利用鏈路預測的方法挖掘那些隱而未露的相互作用,可以降低實驗成本[5].在電子商務網絡中,可以為用戶推薦感興趣的商品.在科學家合作網絡中,可以對科學家之間潛在合作的可能性進行預測.鏈路預測的相關技術可用于在線社交網絡中的朋友推薦[6],也可以用來識別網絡中的虛假鏈接[7].毫無疑問,鏈路預測相關研究具有較高的商業(yè)應用價值,因此成為近年來研究的熱點和重點之一.
本文通過分析傳統(tǒng)鏈路預測算法存在的問題,綜合考慮影響鏈接形成的因素,通過利用節(jié)點間共同鄰居的平均度以及網絡中每個節(jié)點的對鏈接產生的貢獻,提出了一種同時兼顧預測精度和普適性的相似性指標.
2 相關工作
目前鏈路預測相關的研究漸漸趨于成熟,各種各樣的算法被相繼提出.用于鏈路預測的算法模型主要分為三類:基于馬爾科夫鏈、基于概率似然模型和基于拓撲結構的鏈路預測算法.其中基于馬爾科夫鏈和基于概率似然的鏈路預測算法雖然在各種網絡上都具有較好的預測精度,但是計算復雜度很高,不適合處理大規(guī)模網絡.基于網絡拓撲結構的鏈路預測算法則不存在上述問題,在保證預測精度較高同時也有較低的計算復雜度,而且拓撲結構信息容易獲取,適用于處理當今大數據時代網絡數據指數增長的網絡.
基于拓撲結構的鏈路預測算法又可以分為基于局部信息的相似性指標、基于路徑的相似性指標和基于局部信息改進的相似性指標.共同鄰居指標(common neighbor,CN)[8]是基于局部信息的相似性指標中最簡單的一種,該指標認為兩個節(jié)點之間的共同鄰居數目越多,則兩個節(jié)點間產生鏈接的概率越大.對于網絡中的兩個節(jié)點Vx和Vy,定義其鄰居集合分別為Γ(x)和Γ(y),則兩個節(jié)點Vx和Vy的相似性定義為:
Sxy=|Γ(x)∩Γ(y)|
(1)
Leicht等人在CN的基礎上考慮節(jié)點的度的作用提出了LHN指標[9],該指標認為兩個節(jié)點間共同鄰居越多,節(jié)點度的乘積越小,產生鏈接的概率越高,定義為:
(2)
Adamic等人考慮CN中的個體存在差異,提出了Adamic-Adar(AA)指標[10],考慮兩個節(jié)點共同鄰居的度的信息,根據共同鄰居節(jié)點的度為每個節(jié)點賦予一個權重值,該權重等于該節(jié)點的度的對數的倒數,定義為:
(3)
其中Z代表節(jié)點x和節(jié)點y之間的共同鄰居.Zhou等人根據復雜網絡資源分配過程提出了資源分配(Resource Allocation,RA)指標[11],該指標將節(jié)點x和y的共同鄰居看作是傳遞資源的中介,每個中介擁有一定的資源,并將其資源均分給其鄰居,定義為:
(4)
并在多個網絡上具有較好的預測精度.偏好連接相似性指標(preferential attachment,PA)[12]提出了鏈接產生的概率正比于該邊兩個節(jié)點度的乘積.基于路徑的相似性指標中的局部路徑(Local Path,LP)指標[13]是在CN的基礎上考慮節(jié)點間路徑長度為3的路徑數目,預測精度有所提升.Katz指標[14]則是對LP指標的改進,考慮了網絡中的所有路徑.上述指標的優(yōu)點是簡單且計算復雜度低,但預測精度不高,因此目前有很多學者對基于局部信息的指標進行了改進.劉震等人在CN和RA指標的基礎上組合局部貝葉斯模型(local na?ve bayes,LNB)提出了LNB-CN和LNB-RA指標[15],LNB-CN指標在局部樸素貝葉斯模型的基礎上,將CN指標和聚類系數組合在一起形成的新的預測指標,定義為:
(5)
(6)
在食物鏈網絡中該指標的預測精度提高了14%.劉大偉等人提出了局部差異融合算法[16],該方法在AA方法的基礎上考慮共同鄰居集合內部的差異性;綜合考慮基于局部信息指標的特點,Zeng提出了CN+PA的組合指標[17],該指標較傳統(tǒng)的CN指標預測精度提高了約10%.上述指標都是在基于局部信息指標上做的改進,雖然目前已經取得了很多的研究成果,但仍有一些問題尚未被深入研究,因此本文將通過分析已有指標存在的問題提出一種基于共同鄰居的改進算法.
傳統(tǒng)基于局部信息的指標,僅僅考慮的是共同鄰居的數量、共同鄰居的度以及共同鄰居之間的關系,并沒有充分考慮節(jié)點間產生鏈接的因素,導致在某些網絡上的預測精度較低,因此本文通過分析實際網絡中存在的共同鄰居中大度節(jié)點對于節(jié)點間產生連接的貢獻較小的現象,在降低待預測節(jié)點間共同鄰居的大度節(jié)點影響的同時結合網絡中每個節(jié)點對于待預測的兩個節(jié)點產生鏈接的貢獻,提出一個針對無向無權網絡的新的鏈路預測指標,通過大量的實驗證明該指標相比傳統(tǒng)的指標具有較好的普適性和較高的預測精度.
3 鏈路預測問題描述及相似性指標
3.1 鏈路預測問題描述
鏈路預測是在已知網絡拓撲結構和節(jié)點屬性的基礎上預測網絡中沒有觀察到的鏈接產生的可能性.針對鏈路預測問題,首先要利用圖論的相關知識將真實的網絡抽象成復雜網絡,對于一個無向無權的復雜網絡,可以用圖論的理論G(V,E)進行表示,其中V={V1,V2,V3,…,Vn}代表網絡中n個節(jié)點的集合,E={e1,e2,e3,…,em}代表含有的m條邊(鏈接)的集合,其中任意一條邊對應于一個節(jié)點的二元組:ex={Vi,Vj};節(jié)點Vi的度記為ki,即包含節(jié)點Vi的邊的數目.U代表包含所有可能的n(n-1)/2條連邊的集合,目前不存在的連邊(將來有可能存在)的集合為U-E,假設不存在的連邊集合U-E中存在一些遺失的鏈接,鏈路預測的目的就是找出那些遺失的鏈接.如圖1所示,假設一個實際的網絡是由六個節(jié)點
圖1 鏈路預測問題示意圖Fig.1 Link prediction problem
以及七條鏈接組成,在觀察到的網絡AO中遺失了鏈接(1,5),遺失的鏈接EP作為測試集,觀察到的網絡ET作為訓練集,未觀察到的鏈接的集合為U-ET,鏈路預測問題是利用節(jié)點間相似性算法對AO中的任意節(jié)點對(x,y)計算一個相似度得分Sxy,所有的可能存在的邊都被給予一個分數,對所有邊的得分進行降序排序,得分最高的鏈接即為預測出的最可能遺失的鏈接,最后用測試集中的EP測試算法的預測精度.研究鏈路預測問題的核心是相似性指標的設計,因此本文將針對節(jié)點間的相似性指標進行研究.
3.2 一種基于共同鄰居的全局節(jié)點遍歷的鏈路預測算法
傳統(tǒng)的CN指標僅考慮了節(jié)點間共同鄰居的數目,雖然簡單有效,但僅僅利用了共同鄰居數目的信息,使得預測精度還有提升的空間.因此本文通過分析網絡中存在的大度節(jié)點不利現象,并利用網絡中的每個節(jié)點對待預測鏈接產生的貢獻,提出了一個新的鏈路預測算法.
圖2 新浪微博的關系網示意圖Fig.2 Sina weibo network diagram
在新浪微博中,大家關注較多的是當紅明星、各領域專家、網絡紅人,然而這些名人的粉絲之間產生關注的概率很小,稱這種名人對于節(jié)點間產生鏈接的貢獻很小的現象為大度節(jié)點不利現象.如圖2所示是謝娜和普通人張三的微博關系網,在謝娜的新浪微博的8886萬粉絲中,有她的親戚朋友和同學同事,但是其中大部分粉絲都是因為崇拜才關注她的,這些粉絲來自全國各地各行各業(yè),她的粉絲之間產生鏈接的概率就很小,例如她的粉絲中的學生和公務員之間幾乎沒有可能產生鏈接.相反,普通人張三的粉絲很少,關注他的人之間應該有一定的聯(lián)系或者愛好,他的朋友和同學之間產生鏈接的概率就很高.很多網絡中都存在這樣的大度節(jié)點不利現象,在科學家合作網中引用著名學者的作者之間產生合作的概率就沒有引用一般學者的作者之間產生合作的概率大.根據上述分析大度節(jié)點不利現象可以抽象為:
(7)
即兩個節(jié)點x和y之間的相似度Sxy與節(jié)點的共同鄰居的度kc成反比,δ為非零常數的反比例系數.為了減少兩個節(jié)點之間的共同鄰居的度kc的突出差異,降低共同鄰居中的極小度節(jié)點和極大度節(jié)點對相似度的影響,所以利用節(jié)點之間的共同鄰居的平均度的反比更能反映兩個節(jié)點之間的相似度.由于數據在整個值域中不同區(qū)間的差異帶來的影響不同,共同鄰居度小的節(jié)點的差異敏感程度比度大的節(jié)點的差異敏感程度更高,因此對共同鄰居的度kc取對數得到logkc,節(jié)點x和y之間的共同鄰居的平均度MeanCN為:
(8)
結合上述分析的大度節(jié)點不利現象,節(jié)點x、y之間的相似度MZ定義為:
(9)
(10)
圖3 網絡拓撲結構示意圖Fig.3 Network topology diagram
通過對比發(fā)現MZCN的相似性得分更高,主要由于其利用了同時與x,y節(jié)點有共同鄰居的節(jié)點的影響,從而在理論上驗證了該算法的優(yōu)越性.綜合分析上述影響節(jié)點之間相似性的因素,為了能夠使鏈接預測算法在更多的網絡上具有更高的預測精度,保留傳統(tǒng)的CN指標在一些數據集上具有良好的預測精度的優(yōu)點,在其基礎上提出了一種基于共同鄰居的全局節(jié)點遍歷的鏈路預測算法(MZCN-CN),該指標定義為:
(11)
其中α、β是待定參數,需要根據實驗所用的數據集進行試驗確定,本文取σ=1.由于該指標中與兩個參數相關的相似度在某一數據集上預測精度較高,而且這兩項都是基于共同鄰居的指標,它們之間可以通過加權相加的方法發(fā)揮各自的優(yōu)勢,使新的指標在各個數據集上都有著較高的預測精度.
本文將該指標用于鏈路預測算法,為了清晰描述該算法,給出了如下所示的算法1的偽代碼:
算法1.一種改進共同鄰居的節(jié)點遍歷的鏈路預測算法
輸入:給定一個含有V個節(jié)點和E條邊的真實網絡G(V,E);
輸出:未知連邊U-ET在MZCN-CN預測算法中的得分;
a) 將已存在連邊按照9:1的比例隨機劃分訓練集ET和測試集EP;
1 TrainNum = 0;
2 U=V(V-1)/2;
3 While(TrainNum<0.1*|E|)do
4 EP= Random selection from E;
5 TrainNum = TrainNum+1;
6 E=E-EP;
7 End;
8 ET=E;/*其余的已存在的連邊作為訓練集*/
b) 對未知連邊U-ET利MZCN-CN指標進行相似性計算;
9 For z=1 to |U-ET| do
10 Edge(x,y)=select from edge(U-ET);
13 edge(U-ET)=edge(U-ET)-edge(x,y);
14 z=z+1;
15 End for z;
16 Output( The Score[z] of edge(U-ET) );
4 實驗與分析
4.1 實驗數據集
為了證明MZCN-CN指標的優(yōu)越性以及確定指標中的各項參數,本文選取了來自6個不同領域的具有代表性的數據集進行實驗,并與其他傳統(tǒng)的預測指標作比較,選取的數據集分別為:a) 科學家合作網絡(NS)[18]該網絡是由發(fā)表過復雜網絡為主題的論文作者構成.如果兩個作者之間存在合作關系即在節(jié)點之間產生一條連邊,其中節(jié)點代表作者.b) 政治博客網絡(PB)[19]該網絡的節(jié)點代表美國某政治論壇的博客網頁,網絡的連邊的指網頁之間存在超鏈接.c) 蛋白質相互作用網絡(Yeast)[20]該網絡中的蛋白質代表每個節(jié)點,蛋白質之間的相互作用關系表示節(jié)點之間的連邊.d)線蟲的神經網絡(CE)[21]該網絡中的線蟲的神經元代表每個節(jié)點,神經元之間的鏈接代表網絡中存在的邊.e)食物鏈網絡(FWFB)[22]該網絡是由佛羅里達海灣雨季的食物鏈網絡構成,其中節(jié)點代表各種生物以及捕食關系代表連邊信息.f)路由器網絡(Router)[23]該網絡是由路由器代表的節(jié)點以及節(jié)點之間相連直接交換數據包的連邊組成的Internet路由器層次網絡.用于鏈路預測實驗的6個真實網絡的邊以及節(jié)點等基本統(tǒng)計特性如表1所示.
表1 6個真實網絡的基本統(tǒng)計特性
Table 1 Six basic statistical properties of real network
數據NM
其中N=|V|代表網絡中存在的總的節(jié)點數,M=|E|代表網絡中存在的總邊數;
4.2 實驗結果評價模型
(12)
其中n′和n″的初始值都為0,因此AUC的定義為:
(13)
隨機產生的所有連邊的分數,AUC約等于0.5,因此AUC大于0.5的幅度體現算法比隨機選擇的方法的精確程度.
4.3 實驗設計
本文利用MATLAB進行仿真實驗,將上述的6個數據集分別按照9:1的比例隨機劃分訓練集和測試集,然后利用AUC衡量新的指標在各個數據集上的預測精度.本文利用算法搜索MZCN-CN指標的兩個α、β參數的最優(yōu)解,并通過實驗證明求解該參數的算法的可行性,然后通過實驗證明該指標相比傳統(tǒng)指標的優(yōu)越性,具體如下所示.
4.3.1 確定α、β個參數的最優(yōu)解及其可行性分析
為了使新指標在各個數據集都有較好的預測精度,需要解決兩個參數的最優(yōu)化問題,本文采用當β=1時,通過對α在[1,50]的取值范圍內依次賦值并分別在6個數據集上進行試驗得到對應的AUC,能夠使大部分網絡都具有較好的預測精度的α值即為最優(yōu)解αmax,然后當α=αmax時,用同樣的方法在[1,50]的范圍內搜尋最優(yōu)的βmax.當α=1時,經過在[1,50]范圍內實驗搜尋預測精度AUC最優(yōu)的βmax2,通過對比βmax與βmax2的關系,證明該算法的可行性.
4.3.2 MZCN-CN指標的預測效果分析
將上述算法得到的βmax、βmax最優(yōu)參數代入到MZCN-CN指標中,然后分別在6個數據集上對傳統(tǒng)的CN、LHN、AA、RA、LNB-CN、LNB-RA以及MZCN-CN指標進行100次的隨機獨立實驗,取100次獨立實驗預測精度AUC的平均值及其方差,最后與傳統(tǒng)的預測指標的預測精度進行比較.
4.4 實驗結果與分析
基于4.3節(jié)中的設計的實驗內容進行實驗,得到了如下所示的實驗結果.
4.4.1 確定α、β兩個參數的最優(yōu)解及其可行性分析
當β=1時,隨著自變量參數α在[1:1:50]范圍內取不同值時,參數α=2附近6個數據集上的預測精度趨于穩(wěn)定,為了確定最優(yōu)值,縮小α的搜索空間為[1:0.1:3],MZCN-CN指標在6個數據集的預測精度AUC的變化曲線如圖4所示:
從圖中可以看出當α=2.1左右時,FWFB數據集的預測精度開始出現明顯的下降,其余五個數據集的預測精度都達到了最好的預測精度而且以后都趨于穩(wěn)定,所以本文選擇參數α的最優(yōu)解為αmax=2.1.
當α=αmax=2.1時,在6個數據集上的MZCN-CN指標隨著參數β在[1:0.1:3]范圍內變化的趨勢如圖5所示,由圖可知,在β=1.4之前,MZCN-CN指標在FWFB和CE數據集的預測精度隨著β的增加而不斷增長,其他數據及的AUC也基本不變,CE數據集在β等于1.4左右時增長趨于平緩,而且1.4以后FWFB的預測精度也大體趨于穩(wěn)定,所以選取參數βmax=1.4作為最優(yōu)解.
圖4 當β=1時,參數α與AUC的關系Fig.4 When β=1,the relationship between α and AUC
圖5 當α=2.1時,參數β與AUC的關系Fig.5 When α=2.1,the relationship between β and AUC
為了證明該算法確定的參數是最優(yōu)值,選擇在α=1的情況下,分析各個數據集的預測精度隨著β的變化情況來確定最優(yōu)的βmax,其變化曲線如圖6所示,從圖中可以看出當β≈1.4附近時,FWFB數據集取得最高的預測精度的同時其他數據集的預測精度也基本不變.因此取β的最優(yōu)解為βmax1=1.4,與在α=αmax=2.1的情況下確定的βmax2=1.4對比發(fā)現βmax1≈βmax2=1.4;從而證明了該算法的可行性,得到了指標中各個參數的最優(yōu)解,而且有效避免了全局搜索,降低了算法的復雜度.
圖6 當α=1時,參數β與AUC的關系Fig.6 When α=1,the relationship between β and AUC
在α=2.1、β=1.4時該指標在各個數據集上都具有較高的預測精度,因此本文提出MZCN-CN的指標定義為:
(14)
4.4.2 MZCN-CN指標的預測效果分析
傳統(tǒng)的CN、LHN、AA、RA、LNB-CN、LNB-RA指標以及MZCN-CN指標在NS、PB、Yeast、CE、FWFB、Router 6個數據集上的預測精度AUC的評價結果如表2所示,而且100次獨立實驗的AUC方差都穩(wěn)定在0.0001以內,說明隨機抽樣的結果具有可靠性.
表2 不同鏈路預測算法的AUC評價結果
Table 2 AUC results of different link prediction algorithm
數據集CNLHNAARALNB?CNLNB?RAMZCN?CNCE0．84960．72590．86640．87080．86250．86750．8753FWFB0．61990．39970．61790．61720．61370．63020．8219NS0．97800．97250．98140．98190．98030．98170．9806PB0．92320．76320．92660．92770．92590．92800．9358Router0．65280．65220．65310．65320．65320．65070．7520Yeast0．91470．90960．91560．91570．91520．91610．9368
從表2中可以看出,本文提出的MZCN-CN指標相比傳統(tǒng)的預測指標在五個數據集上都具有最高的預測精度,在各個數據集上的預測精度都有顯著提升.只有在NS網絡上表現不是最好,但相比最優(yōu)的RA指標也只相差0.0013,而且在FWFB數據集上的預測精度較傳統(tǒng)最好的指標AUC提高了約20%,在Router數據集上預測精度提高了10%.結合這兩個網絡的統(tǒng)計特性進行分析可知,FWFB的網絡平均度最大,其僅有128個節(jié)點但其平均度達到了32,說明大度節(jié)點較多,MZCN-CN指標的大度節(jié)點不利作用起到了效果,同時其平均最短距離最小、簇系數較大具有小世界效應,說明該指標對具有小世界效應的網絡也有較好的預測效果.Router網絡擁有5022個節(jié)點的平均度僅為2.49,說明網絡中大度節(jié)點較少,所以MZCN-CN指標對其精度的提高僅為10%,該網絡的集聚系數較小,僅為0.033,該由于共同鄰居指標對于集聚系數較低的網絡預測精度較差,而MZCN-CN指標對其預測精度卻有了提高,在一定程度上克服了集聚系數小對于預測精度的影響,證明該指標的預測精度的優(yōu)越性,而且計算復雜度較低,適用于大規(guī)模的網絡.
通過對CN、LHN、AA、RA、LNB-CN、LNB-RA以及MZCN-CN 7個指標分別在NS、PB、Yeast、CE、FWFB、Router六個數據集上進行100次獨立實驗的AUC取平均值后的分布情況如圖7所示,該圖表示各個指標的整體性能,可以看出MZCN-CN指標在各個真實網絡中的預測精度都高于其他傳統(tǒng)的預測指標,說明了該指標預測精度的優(yōu)越性以及其較強的普適性,尤其在FWFB網絡和Router網絡上預測精度表現較為突出,而且該指標的計算復雜度較低,因此本文提出的算法可以適用于大部分的網絡,應用前景廣闊.
5 總 結
本文針對傳統(tǒng)鏈路預測中沒有全面考慮影響節(jié)點間相似性的因素、網絡中的大度節(jié)點不利現象,在基于共同鄰居指標的基礎上,通過對網絡中大度節(jié)點不利現象的分析,在定義了大度節(jié)點對于節(jié)點間產生鏈接的作用的同時,綜合考慮了網絡中每個節(jié)點對于待測節(jié)點間產生鏈接的貢獻,綜合傳統(tǒng)指標的優(yōu)勢,提出了MZCN-CN指標,并通過實驗確定新指標的各項參數,使其具有最好的預測效果,該指標通過在6個真實網絡與6個傳統(tǒng)的預測指標對比AUC結果證明該指標的預測精度高,具有普適性強的優(yōu)勢.
圖7 各個指標的整體性能Fig.7 Overall performance of each indicator
今后的研究重點是針對該指標進一步優(yōu)化,通過引入優(yōu)化算法,將其預測精度進一步提升,使其在更多的網絡上都表現出較好的預測精度,以及研究該指標如何應用到加權或有向網絡中.
[1] Lv Lin-yuan,Zhou Tao.Link prediction in complex networks:a survey [J].Physica A Statistical Mechanics & Its Applications,2011,390(6):1150-1170.
[2] Pan Li-ming,Zhou Tao,Lv Lin-yuan,et al.Predicting missing links and identifying spurious links via likelihood analysis [J].Scientific Reports,2016,6(22955):1-24.
[3] Chuang Ma,Zhou Tao,Zhang Hai-feng.Playing the role of weak clique property in link prediction:A friend recommendation model[J].Scientific Reports,2016,6(30098):1-12.
[4] Yu Hai-yuan,Braun Pascal,Yildirim,et al.High-quality binary protein interaction map of the yeast interactome network [J].Science,2008,322(5898):104-110.
[5] Carlo Vittorio-cannistraci,Gregorio Alanis-lobato,Timothy Ravasi.From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks [J].Scientific Reports,2015,3(4):1613-1613.
[6] Lv Lin-yuan,Medo Matú?,Chi Ho-yeung,et al.Recommender systems [J].Physics Reports,2012,519(1):1-49.
[7] Guimerà Roger,Marta Sales-pardo,Stanley H E.Missing and spurious interactions and the reconstruction of complex networks [J].Proceedings of the National Academy of Sciences,2009,106(52):22073-22078.
[8] Mark Newman.Clustering and preferential attachment in growing networks [J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2001,64(025102):1-4.
[9] Elizabeth Leich,Petter Holme,Mark Newman.Vertex similarity in networks [J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2006,73(026120):1-10.
[10] Adamic Lada A,Adar Eytan.Friends and neighbors on the Web [J].Social Networks,2003,25(3):211-230.
[11] Lv Lin-yuan,Jin Ci-hang,Zhou Tao.Similarity index based on local paths for link prediction of complex networks [J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2009,80(2):593-598.
[12] Barabasi Albert-laszlo,Albert Reka.Emergence of scaling in random networks [J].Science,1999,286(5439):509-512.
[13] Zhou Tao,Lv Lin-yuan,Zhang Yi-cheng.Predicting missing links via local information [J].The European Physical Journal B,2009,71(4):623-630.
[14] Katz Leo.A new status index derived from sociometric analysis [J].Psychometrika,1953,18(1):39-43.
[15] Liu Zhen,Zhang Qian-ming,Lv Lin-yuan,et al.Link prediction in complex networks:a local na?ve Bayes model [J].Europhysics Letters,2011,96(48007):1-6.
[16] Liu Da-wei,Lv Yuan-na,Yu Zhi-hua.An improved link prediction algorithm for complex networks [J].Journal of Chinese Computer Systems,2016,37(5):1071-1074.
[17] Zeng Shan.Link prediction based on local information considering preferential attachment[J].Physica A Statistical Mechanics & Its Applications,2016,443:537-542.
[18] Newman M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2006,74(3):92-100.
[19] Adamic L A,Glance N.The political blogosphere and the 2004 U.S.election:divided they blog[C].International Workshop on Link Discovery,ACM,2005:36-43.
[20] Von Mering C,Krause R,Snel B,et al.Comparative assessment of large-scale data sets of protein-protein interactions [J].Nature,2002,417(6887):399-403.
[21] Watts Duncan james,Strogatz Steven H.Collective dynamics of ′small-world′ networks [C].Nature,1998:440-442.
[22] Ulanowicz Robert,Heymans Johanna,Egnotovich.Network analysis of trophic dynamics in south florida ecosystems[J].FY 99:The Graminoid Ecosystem,2000,22(5):112-123.
[23] Spring Neil,Mahajan Ratul,Wetherall David.Measuring ISP topologies with rocketfuel [J].Acm Sigcomm Computer Communication Review,2002,32(4):133-145.
[24] Hanley J A,Mcneil B J.The meaning and use of the area under a receiver operating characteristic (ROC) curve [J].Radiology,1982,143(1):29-36.
附中文參考文獻：
[16] 劉大偉,呂元娜,余智華.一種改進的復雜網絡鏈路預測算法[J].小型微型計算機系統(tǒng),2016,37(5):1071-1074.
