常圣，馬宏，劉樹(shù)新

基于三元組結(jié)構(gòu)的有向網(wǎng)鏈路預(yù)測(cè)方法

常圣，馬宏，劉樹(shù)新

（國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002）

當(dāng)前鏈路預(yù)測(cè)的研究主要集中在無(wú)向網(wǎng)絡(luò)，然而現(xiàn)實(shí)世界中存在大量的有向網(wǎng)絡(luò)，忽略鏈路的方向會(huì)缺失一些重要信息甚至使預(yù)測(cè)失去意義，而直接將無(wú)向網(wǎng)絡(luò)的預(yù)測(cè)方法應(yīng)用于有向網(wǎng)絡(luò)又存在預(yù)測(cè)精度降低的問(wèn)題。為此，提出了一個(gè)基于三元組的有向網(wǎng)絡(luò)鏈路預(yù)測(cè)算法，該算法針對(duì)有向網(wǎng)絡(luò)和無(wú)向網(wǎng)絡(luò)三元組結(jié)構(gòu)的不同，應(yīng)用勢(shì)理論對(duì)三元組進(jìn)行篩選，通過(guò)統(tǒng)計(jì)分析不同三元組閉合的可能性，以網(wǎng)絡(luò)整體三元組閉合指數(shù)作為權(quán)重計(jì)算節(jié)點(diǎn)間的相似性。在9個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，所提方法比基準(zhǔn)方法的預(yù)測(cè)精度提高了4.3%。

鏈路預(yù)測(cè)；有向網(wǎng)絡(luò)；三元組

1 引言

隨著社交網(wǎng)絡(luò)的興起，鏈路預(yù)測(cè)受到越來(lái)越多的關(guān)注。鏈路預(yù)測(cè)是指通過(guò)已知的網(wǎng)絡(luò)信息，預(yù)測(cè)網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間存在連邊的可能性[1]。這種預(yù)測(cè)既包含對(duì)未知連邊（尚未觀測(cè)到的連邊）的預(yù)測(cè)，也包含對(duì)未來(lái)連邊（尚未產(chǎn)生的連邊）的預(yù)測(cè)。網(wǎng)絡(luò)信息包括節(jié)點(diǎn)的屬性和網(wǎng)絡(luò)結(jié)構(gòu)。雖然考慮節(jié)點(diǎn)的屬性可以提高預(yù)測(cè)的準(zhǔn)確性，但多數(shù)情況下節(jié)點(diǎn)的屬性獲取較為困難[2]，并伴有噪聲，引入節(jié)點(diǎn)屬性還會(huì)增加計(jì)算的復(fù)雜度。近年來(lái)，基于網(wǎng)絡(luò)結(jié)構(gòu)的方法受到學(xué)者越來(lái)越多的青睞。基于網(wǎng)絡(luò)結(jié)構(gòu)的方法大體可以分為兩類[2]：基于相似性的方法，概率和統(tǒng)計(jì)方法。概率和統(tǒng)計(jì)方法主要包括層次結(jié)構(gòu)模型[3]和隨機(jī)分塊模型[4]等，此類方法雖然能夠取得不錯(cuò)的預(yù)測(cè)效果，但計(jì)算復(fù)雜度較高，難以應(yīng)用于規(guī)模較大的網(wǎng)絡(luò)。與之相比，基于相似性的方法計(jì)算復(fù)雜度較低，且預(yù)測(cè)精度較好。共同鄰居（CN，common neighbor）指標(biāo)是最簡(jiǎn)單的相似性指標(biāo)，其核心思想認(rèn)為如果兩個(gè)節(jié)點(diǎn)共同鄰居越多，則它們之間存在連邊的可能性越大。受到共同鄰居的啟發(fā)，加入對(duì)節(jié)點(diǎn)度的考慮，產(chǎn)生了很多相似性指標(biāo)，包括Adamic/Adar（AA）[5]、Salton（SA）[6]、Jaccard（JA）[7]和資源分配指標(biāo)（RA）[8]等。此外，具有代表性的相似性指標(biāo)還有Katz[9]指標(biāo)和有重啟的隨機(jī)游走（RWR）[10]等。

當(dāng)前鏈路預(yù)測(cè)的研究工作對(duì)于無(wú)向網(wǎng)絡(luò)的關(guān)注遠(yuǎn)遠(yuǎn)高于有向網(wǎng)絡(luò)。然而現(xiàn)實(shí)世界中大部分網(wǎng)絡(luò)是有向的，如食物鏈網(wǎng)絡(luò)中的捕食關(guān)系，如果忽略連邊的方向，可能會(huì)缺失重要的信息甚至失去鏈路預(yù)測(cè)的意義。在有向網(wǎng)絡(luò)中，連邊的方向讓鏈路預(yù)測(cè)變得更加困難。文獻(xiàn)[11-12]曾把部分相似性指標(biāo)（CN、RA、AA等）直接應(yīng)用于有向網(wǎng)絡(luò)，這種方法可能會(huì)造成信息缺失，因?yàn)椴煌较虻倪B邊具有不同的含義，不同的形成機(jī)理在鏈路預(yù)測(cè)的過(guò)程中對(duì)于相似度的影響也是不同的。Narayanan等[11]將局部隨機(jī)游走推廣到了有向網(wǎng)絡(luò)，并取得了較好的預(yù)測(cè)效果，Lichtenwalter等[13]基于隨機(jī)游走提出了PropFlow方法，但是這兩種方法相比局部性方法復(fù)雜度較高，難以應(yīng)用于大型復(fù)雜網(wǎng)絡(luò)。張千明等[14]在2013年提出了勢(shì)理論，并篩選出了具有較高預(yù)測(cè)精度的雙風(fēng)扇子圖（bi-fan）結(jié)構(gòu)。近幾年來(lái)，基于三元組結(jié)構(gòu)的方法受到越來(lái)越多的關(guān)注。文獻(xiàn)[15]統(tǒng)計(jì)了13種三元組的頻次，以此來(lái)計(jì)算節(jié)點(diǎn)間的相似度，如果某個(gè)類型的三元組出現(xiàn)越多，那么這種三元組對(duì)于相似度的貢獻(xiàn)就越高。雖然該方法取得了不錯(cuò)的預(yù)測(cè)精度，但其精度是結(jié)合分類器得到的，指標(biāo)本身對(duì)預(yù)測(cè)精度的貢獻(xiàn)作者并未給出。文獻(xiàn)[16]分別計(jì)算9種非閉合三元組結(jié)構(gòu)的相似性，但是沒(méi)有區(qū)分不同類型三元組的作用，而是直接將結(jié)果構(gòu)成一個(gè)9維特征向量作為監(jiān)督學(xué)習(xí)的輸入。總體來(lái)看，當(dāng)前對(duì)有向網(wǎng)絡(luò)還缺乏深入的研究，多數(shù)方法是對(duì)無(wú)向網(wǎng)絡(luò)算法的直接應(yīng)用，或者結(jié)合機(jī)器學(xué)習(xí)方法來(lái)提高預(yù)測(cè)精度，缺乏對(duì)于網(wǎng)絡(luò)本身內(nèi)部機(jī)制的挖掘，因此，如何量化不同方向連邊和不同結(jié)構(gòu)的作用，從而設(shè)計(jì)一個(gè)有效的有向網(wǎng)絡(luò)鏈路預(yù)測(cè)方法具有十分重要的意義。

基于上述情況，本文提出了一種基于三元組結(jié)構(gòu)的有向網(wǎng)絡(luò)鏈路預(yù)測(cè)方法。該方法根據(jù)有向網(wǎng)絡(luò)和無(wú)向網(wǎng)絡(luò)中三元組結(jié)構(gòu)的差異、應(yīng)用勢(shì)理論，從9個(gè)非閉合三元組中篩選出4個(gè)進(jìn)行相似度計(jì)算，通過(guò)統(tǒng)計(jì)分析不同三元組閉合的可能性，以網(wǎng)絡(luò)整體三元組閉合指數(shù)為權(quán)重計(jì)算節(jié)點(diǎn)間的相似性。通過(guò)在9個(gè)不同性質(zhì)的真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并與基準(zhǔn)方法進(jìn)行比較，證明改進(jìn)后的方法預(yù)測(cè)精度更高。

2 基于三元組的有向網(wǎng)鏈路預(yù)測(cè)方法

大多數(shù)基于相似性的鏈路預(yù)測(cè)算法是以三元組作為分析單位的。無(wú)向網(wǎng)絡(luò)中三元組的節(jié)點(diǎn)關(guān)系非常簡(jiǎn)單，需要考慮的未閉合結(jié)構(gòu)只有圖1中的一種情況，所形成的閉合結(jié)構(gòu)也僅有一種。

在有向網(wǎng)絡(luò)中，連邊方向的出現(xiàn)使三元組結(jié)構(gòu)變得復(fù)雜。有共同鄰居且未閉合的三元組有9種，形成新連邊的情況更多。與無(wú)向網(wǎng)絡(luò)相比，有向網(wǎng)絡(luò)中三元組的網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生了較大變化。如果直接將無(wú)向網(wǎng)絡(luò)的預(yù)測(cè)算法應(yīng)用到有向網(wǎng)絡(luò)，那么無(wú)論使用圖1中哪一種結(jié)構(gòu)進(jìn)行預(yù)測(cè)都會(huì)缺失大量的結(jié)構(gòu)信息，也會(huì)混淆出度和入度等概念，顯然這并不符合有向網(wǎng)的連邊機(jī)理和演化規(guī)律。由此產(chǎn)生兩個(gè)問(wèn)題：①使用哪種結(jié)構(gòu)進(jìn)行預(yù)測(cè)能夠獲得較高的預(yù)測(cè)精度；②如何對(duì)每種結(jié)構(gòu)進(jìn)行量化。

2.1 三元組結(jié)構(gòu)的篩選

張千明等[14]在2013年提出了勢(shì)理論，該理論是對(duì)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)等級(jí)的一種描述。對(duì)于節(jié)點(diǎn)和，如果存在指向的連邊，則的勢(shì)能比高一個(gè)單位。如果一個(gè)子圖中每個(gè)節(jié)點(diǎn)的勢(shì)能都能確定，則稱這個(gè)子圖為可定義勢(shì)的。顯然，含有互惠邊的子圖都是不可定義勢(shì)的。圖2展示了一些不可定義勢(shì)和可定義勢(shì)子圖的例子。節(jié)點(diǎn)中的數(shù)字代表節(jié)點(diǎn)的勢(shì)。

勢(shì)理論認(rèn)為，若一條連邊的出現(xiàn)能夠產(chǎn)生更多的可定義勢(shì)子圖，那么它出現(xiàn)的可能性越大[14]。在真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)也表明，使用可定義勢(shì)子圖構(gòu)造的預(yù)測(cè)器具有更高的預(yù)測(cè)精度。本文對(duì)此進(jìn)行了延伸，直接使用勢(shì)理論對(duì)非閉合三元組（S1-S9）進(jìn)行篩選：9種三元組結(jié)構(gòu)中S1-S4是可定義勢(shì)的。同時(shí)考慮到S1-S4的計(jì)算復(fù)雜度比S5-S9低，本文使用S1-S4結(jié)構(gòu)進(jìn)行相似度計(jì)算。

圖1 無(wú)向圖與有向圖中未閉合三元組結(jié)構(gòu)差異

圖2 不可定義勢(shì)和可定義勢(shì)子圖示例

2.2 三元組結(jié)構(gòu)權(quán)重的量化

現(xiàn)實(shí)網(wǎng)絡(luò)中，不同復(fù)雜網(wǎng)絡(luò)之間結(jié)構(gòu)和演化規(guī)律可能有很大不同，如社交網(wǎng)絡(luò)和食物鏈網(wǎng)絡(luò)，不同的三元組形成機(jī)理不同，閉合的概率也不一定相同，顯然賦予不同三元組同樣的權(quán)重是欠妥的。此外，如果賦予不同結(jié)構(gòu)一個(gè)固定的權(quán)重，可能導(dǎo)致在不同性質(zhì)網(wǎng)絡(luò)中預(yù)測(cè)精度差異較大。如果想要同時(shí)提高預(yù)測(cè)精度和指標(biāo)的適用范圍，可以將網(wǎng)絡(luò)的某些自身特性作為預(yù)測(cè)指標(biāo)的一部分?；谝陨峡紤]，本文將一個(gè)網(wǎng)絡(luò)中某種三元組（S1-S9）的閉合指數(shù)（TCI，triad closeness index）定義如下。

圖3 三元組結(jié)構(gòu)的篩選

其中，()獲得節(jié)點(diǎn)、和構(gòu)成的三元組結(jié)構(gòu)，()統(tǒng)計(jì)某種三元組結(jié)構(gòu)在整個(gè)網(wǎng)絡(luò)中出現(xiàn)的頻次，()統(tǒng)計(jì)三元組對(duì)應(yīng)閉合結(jié)構(gòu)的出現(xiàn)頻次。需要注意的是，本文提到的閉合三元組僅指單方向的閉合。如圖4所示，考慮節(jié)點(diǎn)和及其共同鄰居節(jié)點(diǎn)所構(gòu)成的三元組，如果存在由節(jié)點(diǎn)指向節(jié)點(diǎn)的連邊，無(wú)論是否存在由節(jié)點(diǎn)指向的連邊，均稱此三元組為閉合三元組，反之則為未閉合三元組。這樣定義的好處在于，每次計(jì)算時(shí)只考慮一個(gè)方向的連邊，簡(jiǎn)單清晰，且在進(jìn)行矩陣運(yùn)算時(shí)，會(huì)遍歷每個(gè)節(jié)點(diǎn)，“自動(dòng)”計(jì)算另一個(gè)方向連邊的預(yù)測(cè)值。

2.3 預(yù)測(cè)方法

基于2.1節(jié)和2.2節(jié)的考慮，每個(gè)S1-S4結(jié)構(gòu)中共同鄰居節(jié)點(diǎn)對(duì)于相似度的貢獻(xiàn)為

TCI是2.2節(jié)中定義的三元組閉合指數(shù)，()是節(jié)點(diǎn)貢獻(xiàn)函數(shù)。在有向網(wǎng)絡(luò)中，節(jié)點(diǎn)的度數(shù)有出度和入度的區(qū)分。對(duì)于不同的三元組，共同鄰居節(jié)點(diǎn)的出度和入度對(duì)于新連邊的影響程度是不同的。例如，S2結(jié)構(gòu)三元組的出現(xiàn)頻次僅與節(jié)點(diǎn)的入度有關(guān)，而S3結(jié)構(gòu)則僅和的出度相關(guān)。參照RA指標(biāo)，度數(shù)越大，其共同鄰居節(jié)點(diǎn)對(duì)相似度的貢獻(xiàn)越小?；谝陨峡紤]，()等于

圖4 有向網(wǎng)絡(luò)中三元組結(jié)構(gòu)閉合示例

基于此，新的方法（PTI，potential triad index）定義如下。

相似性函數(shù)(,)是遍歷所有的共同鄰居節(jié)點(diǎn)，且僅計(jì)算其中S1-S4結(jié)構(gòu)再求和得到的。可以看出新方法的計(jì)算復(fù)雜度為O(2)，與CN在同一個(gè)量級(jí)，其中，表示網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目。

相似性計(jì)算算法流程如下。

1) input: directed graph G

2) for each Vertex∈G do

3) for each Vertex∈G do

4) for each Vertex∈do

5) if∈.neighbors()

and∈.neighbors()

6) switch(parten(x,y,z)):

7) case S1: s(,)+=TCIS1*f()

8) case S2: s(,)+=TCIS2*f()

9) case S3: s(,)+=TCIS3*f()

10) case S4: s(,)+=TCIS4*f()

11) end if

12) end for

13) end for

14) end for

3 仿真實(shí)驗(yàn)

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

本文選擇的9個(gè)公開(kāi)網(wǎng)絡(luò)數(shù)據(jù)集如下。

1) 電子郵件網(wǎng)絡(luò)（E-mail）[17]：歐洲研究機(jī)構(gòu)的電子郵件網(wǎng)絡(luò)，節(jié)點(diǎn)代表用戶，有向邊代表用戶發(fā)送過(guò)郵件。

2) 論文引用網(wǎng)絡(luò)（Kohonen）[18]：Kohonen network也被稱為自組織映射（SOM），是一種展示和分析多維數(shù)據(jù)的方法。該網(wǎng)絡(luò)是與SOM相關(guān)的論文引用網(wǎng)絡(luò)。

3) 論文引用網(wǎng)絡(luò)（SmaGri）[18]：與Small等相關(guān)的論文引用網(wǎng)絡(luò)。

4) 食物鏈網(wǎng)絡(luò)（FWMW）[19]：紅樹(shù)林河口濕季的食物鏈網(wǎng)絡(luò)，包含97種生物、1 492條有向邊。

5) 線蟲(chóng)代謝網(wǎng)絡(luò)（CElegans）[20]：該數(shù)據(jù)集是秀麗隱桿線蟲(chóng)的代謝網(wǎng)絡(luò)。節(jié)點(diǎn)是代謝物（如蛋白質(zhì)），連邊是代謝物之間的相互作用。

6) 政治博客網(wǎng)絡(luò)（PB）[21]：這是美國(guó)政治博客之間的超鏈接網(wǎng)絡(luò)。對(duì)于博客A和B，由A指向B的有向邊表示同方向的超鏈接。原網(wǎng)絡(luò)是含有自環(huán)的和多連邊的，本文會(huì)忽略這些特殊情況。

7) 論文引用網(wǎng)絡(luò)（Scimet）[18]：以“科學(xué)計(jì)量學(xué)”為主的論文引用網(wǎng)絡(luò)。

8) 維基百科（Wikivote）[22]：這是維基百科中用戶選舉管理員的投票網(wǎng)絡(luò)。節(jié)點(diǎn)代表用戶，邊代表投票。原網(wǎng)絡(luò)的連邊是有正負(fù)邊兩種情況的，本文也對(duì)其進(jìn)行歸一化處理。

9) Gnutella網(wǎng)絡(luò)（Gnutella）[23]：Gnutella是一種文件共享網(wǎng)絡(luò)，節(jié)點(diǎn)表示網(wǎng)絡(luò)拓?fù)渲械闹鳈C(jī)，連邊表示主機(jī)的連接關(guān)系。

表1列出了9個(gè)網(wǎng)絡(luò)中4種三元組結(jié)構(gòu)的樣本數(shù)以及閉合指數(shù)，可以看出，三元組S4在所有三元組中閉合指數(shù)最低，S1的閉合指數(shù)最高。不同網(wǎng)絡(luò)的閉合指數(shù)相差較大，E-mail網(wǎng)絡(luò)中4種三元組指數(shù)比例差不多，SmaGri網(wǎng)絡(luò)中S1閉合指數(shù)最高，Gnutella網(wǎng)絡(luò)4種結(jié)構(gòu)閉合指數(shù)都很低。由此可以看出，不同網(wǎng)絡(luò)的演化規(guī)律可能有很大差別。此外，出現(xiàn)頻次和閉合指數(shù)并沒(méi)有直接的關(guān)系，出現(xiàn)頻次最高的S2和S3閉合指數(shù)并不是最高的。

表1最后一行表示4種三元組結(jié)構(gòu)在9個(gè)網(wǎng)絡(luò)中的平均閉合指數(shù)，為了進(jìn)一步簡(jiǎn)化計(jì)算，不必每次統(tǒng)計(jì)整個(gè)網(wǎng)絡(luò)的三元組閉合情況，同時(shí)仍能夠保持較好的預(yù)測(cè)精度，建議PCI寫(xiě)為

表1 數(shù)據(jù)集中4種三元組結(jié)構(gòu)及閉合指數(shù)

稱將式(5)固定閉合概率代入式(4)得到的相似度為FPTI（fixed potential triad index）。

3.2 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)度量指標(biāo)采用AUC（area under the receiver operating characteristic curve）指標(biāo)[24]。其具體含義是正確預(yù)測(cè)測(cè)試集中邊的值大于不存在邊的概率。AUC的計(jì)算通常采用隨機(jī)抽樣的方式進(jìn)行估計(jì)。每次隨機(jī)從測(cè)試集中選取一條邊，并隨機(jī)選一條不存在邊，如果測(cè)試集中的邊分?jǐn)?shù)值較大，就加1分，相等就加0.5分。AUC可以計(jì)算為

其中，1表示測(cè)試集中的邊分?jǐn)?shù)大于不存在的邊分?jǐn)?shù)的次數(shù)，2代表分?jǐn)?shù)值相等的次數(shù)。

3.3 基準(zhǔn)方法

3.4 預(yù)測(cè)結(jié)果

PTI關(guān)注3.3節(jié)中提到的評(píng)價(jià)指標(biāo)AUC，并與表2中擴(kuò)展后的9種相似性指標(biāo)進(jìn)行對(duì)比。每個(gè)結(jié)果都是100次獨(dú)立實(shí)驗(yàn)結(jié)果的平均值，每次獨(dú)立實(shí)驗(yàn)都對(duì)應(yīng)一個(gè)隨機(jī)的訓(xùn)練集和測(cè)試集。每個(gè)數(shù)據(jù)集中最優(yōu)的結(jié)果加陰影以突出顯示。

表2 基于局部的鏈路預(yù)測(cè)算法

表3 AUC結(jié)果對(duì)比

從表3的預(yù)測(cè)結(jié)果可以看出，對(duì)于同一個(gè)網(wǎng)絡(luò)，前9種基準(zhǔn)指標(biāo)的預(yù)測(cè)精度相差不大，而對(duì)于不同的網(wǎng)絡(luò)，預(yù)測(cè)精度顯著不同。一般而言，如果一個(gè)網(wǎng)絡(luò)具有較高的集聚系數(shù)，那么基于局部相似性的預(yù)測(cè)指標(biāo)將得到較好的預(yù)測(cè)的結(jié)果。例如，效果最差的Gnutella網(wǎng)絡(luò)，其集聚系數(shù)僅有0.007 2，這意味著沒(méi)有多少鄰居節(jié)點(diǎn)進(jìn)行相似度計(jì)算，自然預(yù)測(cè)精度不高?？傮w來(lái)說(shuō)，PTI表現(xiàn)最好。除了FWMW食物鏈網(wǎng)絡(luò)，PTI在其余8個(gè)網(wǎng)絡(luò)中均取得了最高的預(yù)測(cè)精度。而在FWMW網(wǎng)絡(luò)中，PTI的預(yù)測(cè)精確度也和表現(xiàn)最優(yōu)的CN非常接近?？梢钥吹?，除了FWMW食物鏈網(wǎng)絡(luò)和Gnutella點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)以外，PTI在其他網(wǎng)絡(luò)的AUC都達(dá)到了0.85以上，在E-mail和Wikivote網(wǎng)絡(luò)甚至達(dá)到了0.95以上。此外，在無(wú)向網(wǎng)絡(luò)表現(xiàn)較好的RA和AA[2]在有向網(wǎng)絡(luò)中并沒(méi)有體現(xiàn)出明顯優(yōu)勢(shì)。這說(shuō)明簡(jiǎn)單地將無(wú)向網(wǎng)絡(luò)預(yù)測(cè)算法應(yīng)用到有向網(wǎng)絡(luò)中，并不完全適應(yīng)有向網(wǎng)絡(luò)的一些特性，如在有向網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)有出度和入度的不同，無(wú)向網(wǎng)絡(luò)中的算法會(huì)混淆這些特性，這可能是無(wú)向網(wǎng)絡(luò)中算法在有向網(wǎng)絡(luò)中區(qū)分度不大且表現(xiàn)不是很好的原因之一。

表3中FPTI代表固定閉合概率的方法，可以看出，簡(jiǎn)化后的方法與原始方法的AUC相差很小，但每次計(jì)算時(shí)不用統(tǒng)計(jì)整個(gè)網(wǎng)絡(luò)的三元組閉合指數(shù)，降低了計(jì)算復(fù)雜度。在對(duì)AUC要求不是非?？量痰膱?chǎng)合，可以考慮使用FPTI代替PTI使用。

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

鏈路預(yù)測(cè)作為數(shù)據(jù)挖掘的方向之一，近幾年發(fā)展迅猛，學(xué)者對(duì)于無(wú)向網(wǎng)絡(luò)進(jìn)行了系統(tǒng)全面深入的研究，而有向網(wǎng)絡(luò)的研究尚處于起步階段。本文在這方面做出了一些嘗試，針對(duì)有向網(wǎng)絡(luò)特點(diǎn)提出了基于三元組的鏈路預(yù)測(cè)方法，并引入了三元組閉合指數(shù)進(jìn)行相似度計(jì)算。在9個(gè)真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)中，新方法在AUC上基本都優(yōu)于基準(zhǔn)方法。這說(shuō)明基于三元組的預(yù)測(cè)方法更適合有向網(wǎng)絡(luò)，能夠在一定程度上體現(xiàn)有向網(wǎng)絡(luò)的連邊機(jī)理。然而，本文僅考慮了9種三元組中的4個(gè)，其余5種結(jié)構(gòu)對(duì)于相似度的影響未詳細(xì)分析，考慮并不全面。同時(shí)，本文僅關(guān)注了有向網(wǎng)絡(luò)，對(duì)于加權(quán)網(wǎng)絡(luò)或者動(dòng)態(tài)網(wǎng)絡(luò)的分析是下一步的工作。

[1] LYU L, ZHOU T. Link prediction in complex networks: a survey[J]. Physica A: Statistical Mechanics And Its Applications, 2011, 390(6): 1150-1170.

[2] 呂琳媛, 周濤. 鏈路預(yù)測(cè)[M]. 北京: 教育出版社, 2013.

LYU L Y, ZHOU T. Link prediction[M]. Beijing: Higher Education Press, 2013.

[3] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008, 453: 98-101.

[4] GUIMERA R, SALES-PARDO M. Missing and spurious interactions and the reconstruction of complex networks[J]. Proc Natl Sci Acad USA, 2009, 106(52): 22073-22078.

[5] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social Networks, 2003, 25(3): 211-230.

[6] SALTON G, MCGILL M J. Introduction to modern information retrieval[M]. Auckland: MuGraw-Hill, 1983.

[7] JACCARD P. Etude comparative de la distribution floraledansune portion des Alpes et des Jura[J]. Bulletin de la SociétéVaudoise des Science Naturelles, 1901, 37: 547-579.

[8] ZHOU T, LYU L, ZHANG Y C. Predicting missing links via local information[J]. EurPhys J B, 2009, 71(4): 623-630.

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

[10] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. ComputNetw& ISDN Syst, 1998, 30(1-7): 107-117.

[11] NARAYANAN A, SHI E, RUBINSTEIN B I P. Link prediction by de-anonymization: how we won the kaggle social network challenge[C]//The 2011 International Joint Conference on Neural Networks (IJCNN). 2011: 1825-1834.

[12] CORLETTE D, SHIPMAN F M. Link prediction applied to an open large-scale online social network[C]//The 21st ACM Conference on Hypertext and Hypermedia. 2010: 135-140.

[13] LICHTENWALTER R N, LUSSIER J T, CHAWLA N V. New perspectives and methods in link prediction[C]//The 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2010: 243-252.

[14] ZHANG Q M, LYU L, WANG W Q, et al. Potential theory for directed networks[J]. PloS One, 2013, 8(2): e55437.

[15] AGHABOZORGI F, KHAYYAMBASHI M R. A new similarity measure for link prediction based on local structures in social networks[J]. Physica A: Statistical Mechanics and its Applications, 2018, 501: 12-23.

[16] BüTüN E, KAYA M, ALHAJJ R. Extension of neighbor-based link prediction methods for directed, weighted and temporal social networks[J]. Information Sciences, 2018.

[17] YIN H, BENSON A R, LESKOVEC J, et al. Local higher-order graph clustering[C]//The 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017: 555-564.

[18] YAO Y, ZHANG R, YANG F, et al. Link prediction in complex networks based on the interactions among paths[J]. Physica A: Statistical Mechanics and its Applications, 2018.

[19] BAIRD D, LUCZKOVICH J, CHRISTIAN R R. Assessment of spatial and temporal variability in ecosystem attributes of the st marks national wildlife refuge, apalachee bay, florida[J]. Estuarine, Coastal and Shelf Science, 1998, 47(3): 329-349.

[20] WATTS D J, STROGATZ S H. Collective dynamics of “small-world” networks[J]. Nature, 1998, 393(6684): 440.

[21] ADAMIC L A, GLANCE N. The political blogosphere and the 2004 US election: divided they blog[C]//The 3rd International Workshop on Link discovery. 2005: 36-43.

[22] LESKOVEC J, HUTTENLOCHER D, KLEINBERG J. Predicting positive and negative links in online social networks[C]//The 19th International Conference on World Wide Web. 2010: 641-650.

[23] LESKOVEC J, KLEINBERG J, FALOUTSOS C. Graph evolution: densification and shrinking diameters[J]. ACM Transactions on Knowledge Discovery from Data (TKDD). 2007, 1(1): 2.

[24] HANELY J A, MCNEIL B J. The meaning and use of the area under a receiver operating characteristic (ROC) curve[J]. Radiology, 1982, 143: 29-36.

[25] 吳祖峰, 梁棋, 劉嶠, 等. 基于AdaBoost的鏈路預(yù)測(cè)優(yōu)化算法[J].通信學(xué)報(bào), 2014, 35(3): 116-123.

WU Z F, LIANG Q, LIU Q, et al. Modified link prediction algrithm based on AdaBoost [J]. Journal on Communications, 2014, 35(3): 116-123.

[26] SORENSEN T. A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons[J]. BiolSkr, 1948, 5(4): 1-34.

[27] RAVASZ E, SOMERA A L, MONGRU D A, et al. Hierarchical organization of modularity in metabolic networks[J]. Science, 2002, 297(5586): 1553-1555.

[28] LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks[J]. Phys Rev E, 2006, 73: 026120.

[29] DEVI S J, SINGH B. Analysis of link prediction in directed and weighted social network structure[C]//The International Symposium on Intelligent Systems Technologies and Applications. 2017: 1-13.

New method for link prediction in directed networks based on triad patterns

CHANG Sheng, MA Hong, LIU Shuxin

National Digital Switching System Engineering & Technological R & D Center, Zhengzhou 450002,China

Almost all current studies on link prediction problem focus on undirected networks. Unfortunately, many complex networks in the real world are directed. Ignoring the direction of a link will overlook some important information or even make the prediction meaningless. Directly applying the methods for undirected networks to directed networks will reduce the accuracy of prediction. A new method for link prediction in directed networks based on triad patterns was proposed. The proposed metric compare the difference of triad structures between undirected and directed networks and use potential theory to filter the triad patterns. By statistics of triad closeness in various networks, new method calculate the similarity between nodes using the triad closeness index of a network as the weight for different triad patterns. Experiments on nine real networks show that accuracy of proposed method is 4.3% better than benchmark methods.

link prediction, directed networks, triad patterns

常圣（1988? ），男，河南鄭州人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士生，主要研究方向?yàn)殒溌奉A(yù)測(cè)。

馬宏（1968? ），男，江蘇東臺(tái)人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心研究員，主要研究方向?yàn)樯鐣?huì)網(wǎng)絡(luò)分析、電信網(wǎng)關(guān)防護(hù)。

劉樹(shù)新（1987? ），男，山東濰坊人，博士，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心助理研究員，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、網(wǎng)絡(luò)信息挖掘。

TP393

A

10.11959/j.issn.2096?109x.2019049

2018?12?11；

2019?05?21

常圣，724986365@qq.com

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61803384）

The National Natural Science Foundation of China (No.61803384)

常圣，馬宏，劉樹(shù)新. 基于三元組結(jié)構(gòu)的有向網(wǎng)鏈路預(yù)測(cè)方法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2019, 5(5): 39-47.

CHANG S, MA H, LIU S X. New method for link prediction in directed networks based on triad patterns [J]. Chinese Journal of Network and Information Security, 2019,5(5): 39-47.