李旗旗，徐 敏

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

鏈路預(yù)測(cè)方法與網(wǎng)絡(luò)結(jié)構(gòu)的相關(guān)性

李旗旗，徐 敏

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

作為數(shù)據(jù)挖掘的一個(gè)分支，鏈路預(yù)測(cè)經(jīng)過多年研究，已經(jīng)提出了多種鏈路預(yù)測(cè)方法?；诰W(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測(cè)方法因?yàn)樵谙嗨平Y(jié)構(gòu)的網(wǎng)絡(luò)中具有普適性，在近年來得到了廣泛關(guān)注。然而，由于每個(gè)復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)不同，鏈路預(yù)測(cè)方法的預(yù)測(cè)準(zhǔn)確度差別較大，同一種鏈路預(yù)測(cè)方法不可能在所有網(wǎng)絡(luò)中都獲得理想的預(yù)測(cè)效果。研究鏈路預(yù)測(cè)方法的準(zhǔn)確度和網(wǎng)絡(luò)結(jié)構(gòu)的相關(guān)性可以在已知一個(gè)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的情況下，選擇合適的鏈路預(yù)測(cè)方法，也可以為鏈路預(yù)測(cè)的改進(jìn)提供理論依據(jù)。通過實(shí)驗(yàn)計(jì)算出常見鏈路預(yù)測(cè)方法在每個(gè)網(wǎng)絡(luò)上的預(yù)測(cè)準(zhǔn)確度，發(fā)現(xiàn)鏈路預(yù)測(cè)方法的預(yù)測(cè)準(zhǔn)確度在不同結(jié)構(gòu)的網(wǎng)絡(luò)中是不同的，結(jié)合網(wǎng)絡(luò)的結(jié)構(gòu)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，并據(jù)此提出了一種簡(jiǎn)單的鏈路預(yù)測(cè)方法選擇方案。

復(fù)雜網(wǎng)絡(luò)；鏈路預(yù)測(cè)；網(wǎng)絡(luò)結(jié)構(gòu)；相似性

0 引 言

自然界中大量的復(fù)雜系統(tǒng)都可以通過各種各樣的網(wǎng)絡(luò)表現(xiàn)出來。一個(gè)典型的網(wǎng)絡(luò)包含了一定數(shù)量的節(jié)點(diǎn)和連接這些節(jié)點(diǎn)的邊，其中節(jié)點(diǎn)表示的是一個(gè)真實(shí)系統(tǒng)中的個(gè)體，而邊則代表了個(gè)體之間的某種關(guān)系。如果兩個(gè)個(gè)體中存在某種關(guān)系，那么對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)之間就存在一條連邊。

今天，在生活中存在各種各樣的復(fù)雜網(wǎng)絡(luò)，比如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)等，每一個(gè)網(wǎng)絡(luò)都有自己獨(dú)特的網(wǎng)絡(luò)結(jié)構(gòu)和屬性。社交網(wǎng)絡(luò)中著名的“六度分離”就是社交網(wǎng)絡(luò)的一個(gè)獨(dú)特網(wǎng)絡(luò)結(jié)構(gòu)。通過網(wǎng)絡(luò)的結(jié)構(gòu)和屬性，可以嘗試去預(yù)測(cè)網(wǎng)絡(luò)在下一個(gè)時(shí)間段的變化，從而為實(shí)際生產(chǎn)提供正確的指導(dǎo)和建議。鏈路預(yù)測(cè)就是一個(gè)很好的選擇。

復(fù)雜網(wǎng)絡(luò)中的鏈路預(yù)測(cè)通過計(jì)算網(wǎng)絡(luò)中尚未連邊的兩個(gè)節(jié)點(diǎn)之間在未來產(chǎn)生連邊的概率達(dá)到預(yù)測(cè)的目的[1]。其研究思路和方法主要基于馬爾可夫鏈和機(jī)器學(xué)習(xí)。Sarukkai使用馬爾可夫鏈對(duì)網(wǎng)絡(luò)進(jìn)行了鏈路預(yù)測(cè)和路徑分析[2]。之后學(xué)者對(duì)基于馬爾可夫鏈的鏈路預(yù)測(cè)方法進(jìn)行了擴(kuò)展，但是在這其中的很多方法都用到了網(wǎng)絡(luò)的節(jié)點(diǎn)信息。不少研究表明，使用節(jié)點(diǎn)信息進(jìn)行鏈路預(yù)測(cè)可以獲得比較好的結(jié)果[3]，但是現(xiàn)實(shí)中很多網(wǎng)絡(luò)都難以獲得節(jié)點(diǎn)信息，而且即使獲得了節(jié)點(diǎn)信息，也不能保證信息的可靠性。因此，國(guó)內(nèi)外學(xué)者越來越關(guān)注基于網(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測(cè)方法[4]。相比節(jié)點(diǎn)屬性信息，網(wǎng)絡(luò)的結(jié)構(gòu)更加可靠。然而，鏈路預(yù)測(cè)方法在某種程度上都有自己的局限性，并不能在所有網(wǎng)絡(luò)上都有很好的預(yù)測(cè)準(zhǔn)確度，所以對(duì)于一個(gè)已知網(wǎng)絡(luò)，如何尋找到一個(gè)合適的鏈路預(yù)測(cè)方法是很重要的。

1 鏈路預(yù)測(cè)方法

用G(V,E)表示一個(gè)無向網(wǎng)絡(luò)，其中V表示節(jié)點(diǎn)集，E表示邊集。G[t,t1]表示G在[t,t1]時(shí)間段的情況，那么在(t1,t2]時(shí)間段G的情況就是G(t1,t2]。鏈路預(yù)測(cè)關(guān)注的就是如何預(yù)測(cè)網(wǎng)絡(luò)G從[t,t1]到(t1,t2]的變化。

鏈路預(yù)測(cè)經(jīng)過多年的研究，提出了各種各樣的方法。選擇其中常用的10種方法，為了能更好地介紹這些方法，首先介紹一些在文章中使用的符號(hào)。其中，x,y表示節(jié)點(diǎn)，N表示網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量。kx和ky表示節(jié)點(diǎn)x和y的度數(shù)，Γ(x)和Γ(y)分別表示節(jié)點(diǎn)x和y的鄰居節(jié)點(diǎn)集合。

基于局部信息的相似性方法是指僅通過節(jié)點(diǎn)的局部信息(如節(jié)點(diǎn)的度和最近鄰等)就可以計(jì)算出相似度的方法。這種方法的優(yōu)勢(shì)在于時(shí)間復(fù)雜度低，適用于大型的網(wǎng)絡(luò)應(yīng)用。

1.1 共同鄰居(CN)

共同鄰居是一種比較簡(jiǎn)單的鏈路預(yù)測(cè)方法，其基本假設(shè)為：如果兩個(gè)尚未連邊的節(jié)點(diǎn)有更多的共同鄰居，那么它們更傾向于連邊。這種假設(shè)很容易理解，比如在社交網(wǎng)絡(luò)中，如果兩個(gè)陌生人有很多共同的朋友，那么他們將來成為朋友的概率也很大[5]。又比如，Newman等發(fā)現(xiàn)在科學(xué)家合作網(wǎng)絡(luò)中，如果兩個(gè)科學(xué)家的共同合作伙伴很多，那么他們將來也很有可能會(huì)合作[6]。其定義為：

sxy=Γ(x)∩Γ(y)

(1)

1.2 Salton

該方法是基于CN方法并且考慮連邊兩個(gè)端點(diǎn)節(jié)點(diǎn)度的影響[7]。它的定義為：

(2)

1.3 Jaccard

100多年前被提出，用于計(jì)算集合的相似度[8]。它的定義為：

(3)

1.4 大度節(jié)點(diǎn)有利(Hub Promoted Index,HPI)

HPI方法[9]的定義為：

(4)

由于分母只有度比較小的節(jié)點(diǎn)決定，所以度比較大的節(jié)點(diǎn)更容易和其他節(jié)點(diǎn)形成較高的相似性。

1.5 大度節(jié)點(diǎn)不利(Hub Depressed Index,HDI)

其定義與HPI相似，只是分母取節(jié)點(diǎn)度數(shù)的較大值[10]。

(5)

1.6 Adamic-Adar(AA)

其思想是度小的共同鄰居節(jié)點(diǎn)的貢獻(xiàn)大于度大的共同鄰居節(jié)點(diǎn)[11]。例如，在微博網(wǎng)絡(luò)中，受關(guān)注較多的人往往是某個(gè)領(lǐng)域的專家或者名人，因此共同關(guān)注他們的人之間可能并不擁有特別相似的興趣。相反，如果兩個(gè)人共同關(guān)注了一個(gè)粉絲很少的人(非專家)，那么說明這兩個(gè)人確實(shí)具有相同的興趣愛好或者重疊的社交圈，因此有更高概率相連。

(6)

1.7 Resource-Allocation(RA)

考慮網(wǎng)絡(luò)中沒有直接相連的兩個(gè)節(jié)點(diǎn)x和y，從x可以傳遞一些資源到y(tǒng)，而在此過程中，它們的共同鄰居就成為傳遞的媒介[12]。

假設(shè)每個(gè)媒介都有一個(gè)單位的資源并且平均分配傳給它的鄰居，則y可以接收到的資源就可以定義為節(jié)點(diǎn)x和y的相似度，即:

(7)

當(dāng)網(wǎng)絡(luò)的平均度較小時(shí)，RA和AA區(qū)別不大；但是當(dāng)平均度較大時(shí)，就有很大區(qū)別了。

1.8 局部路徑(Local Path,LP)

LP方法在CN方法的基礎(chǔ)上考慮了三階路徑的影響，其定義為：

(8)

1.9 Katz

Katz方法考慮了網(wǎng)絡(luò)的所有路徑[13]，其定義為：

(9)

其中，β用來調(diào)節(jié)高階路徑的貢獻(xiàn)。當(dāng)β值很小時(shí)，高階路徑的貢獻(xiàn)也就很小了，此時(shí)Katz的預(yù)測(cè)結(jié)果接近于局部路徑方法。

2 實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)方法

為了比較每一種方法的準(zhǔn)確度，實(shí)驗(yàn)中選取了7組提取自真實(shí)網(wǎng)絡(luò)的數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果通過AUC值進(jìn)行評(píng)價(jià)。

2.1 數(shù)據(jù)集

USAir：網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)機(jī)場(chǎng)，如果在兩個(gè)機(jī)場(chǎng)之間存在一條直達(dá)航線，那么兩個(gè)機(jī)場(chǎng)之間存在一條連邊。

NS：這個(gè)網(wǎng)絡(luò)是由M.Newman在2006年收集的，其中包含了在網(wǎng)絡(luò)科學(xué)領(lǐng)域的科學(xué)家發(fā)表的論文。網(wǎng)絡(luò)中的節(jié)點(diǎn)表示科學(xué)家，兩個(gè)節(jié)點(diǎn)之間存在連邊說明兩個(gè)科學(xué)家合作發(fā)表過論文。

Power：美國(guó)西部電網(wǎng)，是由Watts和Strogatz收集的。節(jié)點(diǎn)表示變電站或者換流站，連邊表示它們之間有高壓線。

Router：Internet路由層次網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)表示一個(gè)路由器，如果兩個(gè)路由器之間可以直接進(jìn)行數(shù)據(jù)包交換，則它們之間存在一條連邊。

Yeast：蛋白質(zhì)相互作用網(wǎng)絡(luò)，節(jié)點(diǎn)表示蛋白質(zhì)，邊表示它們之間的相互作用。

Wiki-vote：維基百科中的活躍用戶可以被提名為管理員，當(dāng)一個(gè)用戶被提名時(shí)，維基百科會(huì)組織選舉，獲得支持最多的用戶晉升為管理員。用戶表示節(jié)點(diǎn)，選舉行為對(duì)應(yīng)于網(wǎng)絡(luò)中的邊，如果用戶A給用戶B投票，那么就有一條邊從A指向B。

Facebook：Facebook數(shù)據(jù)集是通過其應(yīng)用從調(diào)查的參與者中收集到的，節(jié)點(diǎn)表示用戶，邊表示兩個(gè)用戶之間的好友關(guān)系。

2.2 評(píng)價(jià)方法

一個(gè)時(shí)間序列中的預(yù)測(cè)意味著要將數(shù)據(jù)集按照時(shí)間戳分為訓(xùn)練集和測(cè)試集，其中訓(xùn)練集視為已知的信息，測(cè)試集視為未知信息，這個(gè)集合中的所有信息都不能被用來預(yù)測(cè)[14]。為了保證在抽樣后訓(xùn)練集仍然保持連通，實(shí)驗(yàn)中采用的劃分策略是，在隨機(jī)抽樣的基礎(chǔ)上加入網(wǎng)絡(luò)連通性判斷機(jī)制，即首先在給定的網(wǎng)絡(luò)中選取一條邊，然后判斷這條邊的兩個(gè)節(jié)點(diǎn)在刪除這條邊之后是否仍然可以連通，如果可以則將該邊加入測(cè)試集，否則放棄，然后重新隨機(jī)抽取一條邊。

使用AUC來衡量鏈路預(yù)測(cè)方法的準(zhǔn)確度。AUC是指ROC曲線下的面積，在信號(hào)探測(cè)理論中，ROC曲線用來評(píng)價(jià)某種分類器的分類效果[15]。這種方法同樣可以用來衡量鏈路預(yù)測(cè)方法的準(zhǔn)確度。

對(duì)所有未觀察到的連邊進(jìn)行排名，AUC的值可以理解為：在測(cè)試集中隨機(jī)選擇一條連邊的得分高于隨機(jī)選擇的一條不存在的邊的概率。在算法的實(shí)現(xiàn)中，通常是計(jì)算每個(gè)未觀察到的連邊的得分，而不是給出一個(gè)有序的列表，因?yàn)楹笳咝枰蟮臅r(shí)間復(fù)雜度。然后，每次從測(cè)試集中隨機(jī)選取一條連邊，再隨機(jī)從不存在的連邊中選取一條連邊，比較它們的得分。如果在n次實(shí)驗(yàn)中，有n'次前者的分?jǐn)?shù)更高，n''次兩者分?jǐn)?shù)相同，那么AUC的值為：

(10)

從表達(dá)式中可以看出，隨機(jī)選擇法的AUC值約為0.5，所以一個(gè)鏈路預(yù)測(cè)算法的AUC值大于0.5的程度就是該算法比隨機(jī)算法精確的程度。在實(shí)驗(yàn)中，為了減少隨機(jī)抽樣對(duì)結(jié)果的影響，AUC的計(jì)算采取多次計(jì)算求平均值的方法。

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

實(shí)驗(yàn)中計(jì)算了每個(gè)鏈路預(yù)測(cè)方法在所有7個(gè)網(wǎng)絡(luò)數(shù)據(jù)集上的預(yù)測(cè)準(zhǔn)確度，結(jié)果顯示為AUC值。表1是每種鏈路預(yù)測(cè)方法的準(zhǔn)確度。

表1 鏈路預(yù)測(cè)方法的準(zhǔn)確度(AUC值)

可以看出，10種鏈路預(yù)測(cè)方法基本上都給出了好于隨機(jī)選擇方法的預(yù)測(cè)效果，并且基于共同鄰居的方法(CN、Salton、Jaccard、HPI、HDI、AA、RA)預(yù)測(cè)準(zhǔn)確度相差不多，在CN基礎(chǔ)上考慮連邊的兩個(gè)端點(diǎn)度的影響整體表現(xiàn)不如CN，AA和RA方法的準(zhǔn)確度相比于其他方法有較小的提升。

但是也可以看出一些特例，比如在Power和Router網(wǎng)絡(luò)中，除了Katz，其他方法的預(yù)測(cè)準(zhǔn)確度都比較一般；在Facebook和Wiki-vote網(wǎng)絡(luò)中，Katz方法在β=0.01時(shí)AUC值很低，在β=0.001時(shí)預(yù)測(cè)效果很好。

針對(duì)實(shí)驗(yàn)結(jié)果的一些現(xiàn)象，將根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)分析這些現(xiàn)象的原因。表2是在實(shí)驗(yàn)中使用的網(wǎng)絡(luò)的一些結(jié)構(gòu)信息。

表2 網(wǎng)絡(luò)結(jié)構(gòu)信息

Salton、Jaccard等方法在USAir和Wiki-vote上的預(yù)測(cè)效果和CN有比較明顯的差距，可能的原因是這兩個(gè)網(wǎng)絡(luò)中存在比較明顯的“富人俱樂部現(xiàn)象”，即度數(shù)大的節(jié)點(diǎn)相對(duì)于度數(shù)小的節(jié)點(diǎn)更容易和其他度數(shù)大的節(jié)點(diǎn)形成連邊，而Salton等方法懲罰了連邊中兩個(gè)端點(diǎn)的度數(shù)，在一定程度上對(duì)預(yù)測(cè)結(jié)果起到了消極作用。

Power和Router網(wǎng)絡(luò)的聚類系數(shù)很小，說明節(jié)點(diǎn)之間的緊密程度很低，它們的平均度很小也說明了這一點(diǎn)。因此，這兩個(gè)網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)之間的共同鄰居節(jié)點(diǎn)個(gè)數(shù)也很少，無法為這兩個(gè)節(jié)點(diǎn)是否相似提供足夠的證據(jù)，這也就是為什么基于共同鄰居的方法預(yù)測(cè)結(jié)果都不好的原因。基于路徑的預(yù)測(cè)算法受這個(gè)問題的影響較小，可以看到LP和Katz的預(yù)測(cè)結(jié)果都不錯(cuò)。唯一值得注意的是，LocalP對(duì)于Power的預(yù)測(cè)結(jié)果不是很好，這是因?yàn)長(zhǎng)P只是考慮了三階路徑，而Power網(wǎng)絡(luò)不僅稀疏而且直徑很大，僅考慮三階路徑性能提升有限。

Katz由于考慮了全路徑，所以它在所有的網(wǎng)絡(luò)上都有比較好的表現(xiàn)，當(dāng)然這也意味著Katz方法的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)高于其他方法。在Wiki-vote和Facebook中，Katz在參數(shù)β=0.01時(shí)出現(xiàn)了比較明顯的異常情況，這恰好體現(xiàn)了Katz方法的一個(gè)明顯問題。根據(jù)Katz的公式可以看到，其時(shí)間復(fù)雜度相當(dāng)高，這對(duì)于稍微大型的網(wǎng)絡(luò)都是無法接受的，但是在β小于鄰接矩陣最大特征值的倒數(shù)的情況下，Katz的公式可以根據(jù)級(jí)數(shù)收斂轉(zhuǎn)化為：

S=(I-βA)-1-I

(11)

而矩陣求逆的時(shí)間復(fù)雜度為O(N3)量級(jí)，從而大大減少了時(shí)間開支。Facebook和Wiki-vote的鄰接矩陣的最大特征值均小于0.01而大于0.001，而實(shí)驗(yàn)中使用的是轉(zhuǎn)化之后的公式，因此導(dǎo)致Katz預(yù)測(cè)結(jié)果的異常。

另外，Yeast網(wǎng)絡(luò)的聚類系數(shù)同樣很小，但是CN、AA等方法也得到了比較不錯(cuò)的預(yù)測(cè)效果，可能的原因有兩個(gè)：

(1)Yeast和Power、Router相比平均度較大，根據(jù)聚類系數(shù)的定義，節(jié)點(diǎn)的度數(shù)會(huì)在一定程度上抑制包含該節(jié)點(diǎn)的三角形的個(gè)數(shù)對(duì)聚類系數(shù)的貢獻(xiàn)。如果一個(gè)節(jié)點(diǎn)的度很大，即使包含它的三角形個(gè)數(shù)很多，也會(huì)表現(xiàn)出較低的聚類系數(shù)；

(2)Yeast網(wǎng)絡(luò)中度數(shù)較小的節(jié)點(diǎn)都有比較大的聚類系數(shù)，由于度數(shù)較大的節(jié)點(diǎn)聚類系數(shù)較小，導(dǎo)致整體的聚類系數(shù)較小，但是節(jié)點(diǎn)對(duì)之間有足夠的共同鄰居節(jié)點(diǎn)來證明它們之間的相似性。

根據(jù)上述分析，對(duì)于一個(gè)結(jié)構(gòu)已知的網(wǎng)絡(luò)，一種簡(jiǎn)單的鏈路預(yù)測(cè)方法推薦方案描述如下：

(1)對(duì)于聚類系數(shù)和平均度較小的網(wǎng)絡(luò)，采用基于路徑的方法，其中Katz方法在大多數(shù)情況下獲得了較好的效果。需要注意的是，Katz方法在使用之前要計(jì)算β的取值上限，LP方法雖然僅考慮了局部路徑，但是沒有參數(shù)的限制。

(2)對(duì)于聚類系數(shù)和平均度較大的網(wǎng)絡(luò)，基于共同鄰居的方法能夠獲得較好的結(jié)果，并且在時(shí)間復(fù)雜度上要優(yōu)于基于路徑的方法。

(3)在基于共同鄰居的方法中，CN、AA和RA可以作為優(yōu)先選擇的方法，AA和RA在異配性比較強(qiáng)的網(wǎng)絡(luò)中會(huì)顯示出比CN更好的預(yù)測(cè)效果。

4 結(jié)束語(yǔ)

文中介紹了10種鏈路預(yù)測(cè)方法，并且在7個(gè)真實(shí)網(wǎng)絡(luò)中比較了它們的預(yù)測(cè)準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明，對(duì)于平均度和聚類系數(shù)較小的網(wǎng)絡(luò)，基于共同鄰居的方法往往不能給出一個(gè)很好的預(yù)測(cè)效果，但是Katz可以獲得很好的預(yù)測(cè)準(zhǔn)確度。

同時(shí)還發(fā)現(xiàn)，社交網(wǎng)絡(luò)的鄰接矩陣的最大特征值的倒數(shù)往往較小。在這種情況下，對(duì)Katz方法的參數(shù)值的選取有一定限制，此時(shí)可以考慮使用基于局部路徑的方法。可以看到，在鏈路預(yù)測(cè)中，獲得一個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)對(duì)于尋找一個(gè)合適的鏈路預(yù)測(cè)方法很有幫助。

[1] 呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)[J].電子科技大學(xué)學(xué)報(bào),2010,39(5):651-661.

[2] Sarukkai R R.Link prediction and path analysis using Markov chains[J].Computer Networks,2000,33(1-6):377-386.

[3] 劉大偉,呂元娜,余智華.一種改進(jìn)的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)算法[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(5):1071-1074.

[4] 傅穎斌,陳羽中.基于鏈路預(yù)測(cè)的微博用戶關(guān)系分析[J].計(jì)算機(jī)科學(xué),2014,41(2):201-205.

[5] 丁兆云,賈 焰,周 斌,等.社交網(wǎng)絡(luò)影響力研究綜述[J].計(jì)算機(jī)科學(xué),2014,41(1):48-53.

[6] Newman M E J. Clustering and preferential attachment in growing networks[J].Physical Review E,2001,64(2):025102.

[7] Salton G,Mcgill M J.Introduction to modern information retrieval[M].[s.l.]:McGraw-Hill,1983.

[8] Jaccard P.Etude de la distribution florale dans une portion des Alpes et du Jura[J].Bulletin De La Societe Vaudoise Des Sciences Naturelles,1901,37(142):547-579.

[9] Ravasz E,Somera A L,Mongru D A,et al.Hierarchical organization of modularity in metabolic networks[J].Science,2002,297(5586):1551.

[10] Zhou T,Lu L,Zhang Y C.Predicting missing links via local information[J].Physics of Condensed Matter,2009,71(4):623-630.

[11] Adamic L A,Adar E.Friends and neighbors on the web[J].Social Networks,2003,25(3):211-230.

[12] Ou Q,Jin Y D,Zhou T,et al.Power-law strength-degree correlation from resource-allocation dynamics on weighted networks[J].Physical Review E,2007,75:021102.

[13] Katz L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.

[14] Lü L,Zhou T.Link prediction in complex networks:a survey[J].Physica A Statistical Mechanics & Its Applications,2011,390(6):1150-1170.

[15] Fawcett T.Introduction to ROC analysis[J].Pattern Recognition Letters,2006,27(8):861-874.

CorrelationbetweenLinkPredictionMethodandNetworkStructure

LI Qi-qi，XU Min

(School of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics,Nanjing 211106，China)

As a branch of data mining,link prediction has been studied many years in the computer field,and a variety of link prediction methods are proposed.The link prediction method based on network structure has been widely concerned in recent years,because it is common in the network with similar structure.However,due to the different structure of complex networks,the prediction accuracy of the link prediction method is different,and the same link prediction method can’t get the desired results in all networks.Analyzing the correlation of network structure and the accuracy of link prediction method can help to choose a right link prediction method for a given network,and provide the theoretical basis for improving link prediction.The prediction accuracy of the link prediction method is calculated by the experiment,and the results show that it exists difference in the different network structure.Analyzing experimental results combined with the network structure,a simple selection of link prediction method is proposed.

complex networks；link prediction；network structure；similarity

TP393

A

1673-629X(2017)12-0057-04

10.3969/j.issn.1673-629X.2017.12.013

2016-12-11

2017-04-19 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-08-01

國(guó)家“973”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目(2014CB744900)

李旗旗(1991-)，男，碩士研究生，CCF會(huì)員(E200041166G)，研究方向?yàn)闄C(jī)器學(xué)習(xí)、鏈路預(yù)測(cè)；徐 敏，博士，副教授，研究方向?yàn)槟Ｊ阶R(shí)別、機(jī)器學(xué)習(xí)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1557.078.html