基于三元組結構的有向網鏈路預測方法

常圣，馬宏，劉樹新

基于三元組結構的有向網鏈路預測方法

常圣，馬宏，劉樹新

（國家數字交換系統工程技術研究中心，河南 鄭州 450002）

當前鏈路預測的研究主要集中在無向網絡，然而現實世界中存在大量的有向網絡，忽略鏈路的方向會缺失一些重要信息甚至使預測失去意義，而直接將無向網絡的預測方法應用于有向網絡又存在預測精度降低的問題。為此，提出了一個基于三元組的有向網絡鏈路預測算法，該算法針對有向網絡和無向網絡三元組結構的不同，應用勢理論對三元組進行篩選，通過統計分析不同三元組閉合的可能性，以網絡整體三元組閉合指數作為權重計算節點間的相似性。在9個真實數據集上的實驗表明，所提方法比基準方法的預測精度提高了4.3%。

鏈路預測；有向網絡；三元組

1 引言

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

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

基于上述情況，本文提出了一種基于三元組結構的有向網絡鏈路預測方法。該方法根據有向網絡和無向網絡中三元組結構的差異、應用勢理論，從9個非閉合三元組中篩選出4個進行相似度計算，通過統計分析不同三元組閉合的可能性，以網絡整體三元組閉合指數為權重計算節點間的相似性。通過在9個不同性質的真實數據集上進行實驗，并與基準方法進行比較，證明改進后的方法預測精度更高。

2 基于三元組的有向網鏈路預測方法

大多數基于相似性的鏈路預測算法是以三元組作為分析單位的。無向網絡中三元組的節點關系非常簡單，需要考慮的未閉合結構只有圖1中的一種情況，所形成的閉合結構也僅有一種。

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

2.1 三元組結構的篩選

張千明等[14]在2013年提出了勢理論，該理論是對復雜網絡中節點等級的一種描述。對于節點和，如果存在指向的連邊，則的勢能比高一個單位。如果一個子圖中每個節點的勢能都能確定，則稱這個子圖為可定義勢的。顯然，含有互惠邊的子圖都是不可定義勢的。圖2展示了一些不可定義勢和可定義勢子圖的例子。節點中的數字代表節點的勢。

勢理論認為，若一條連邊的出現能夠產生更多的可定義勢子圖，那么它出現的可能性越大[14]。在真實網絡的實驗也表明，使用可定義勢子圖構造的預測器具有更高的預測精度。本文對此進行了延伸，直接使用勢理論對非閉合三元組（S1-S9）進行篩選：9種三元組結構中S1-S4是可定義勢的。同時考慮到S1-S4的計算復雜度比S5-S9低，本文使用S1-S4結構進行相似度計算。

圖1 無向圖與有向圖中未閉合三元組結構差異

圖2 不可定義勢和可定義勢子圖示例

2.2 三元組結構權重的量化

現實網絡中，不同復雜網絡之間結構和演化規律可能有很大不同，如社交網絡和食物鏈網絡，不同的三元組形成機理不同，閉合的概率也不一定相同，顯然賦予不同三元組同樣的權重是欠妥的。此外，如果賦予不同結構一個固定的權重，可能導致在不同性質網絡中預測精度差異較大。如果想要同時提高預測精度和指標的適用范圍，可以將網絡的某些自身特性作為預測指標的一部分。基于以上考慮，本文將一個網絡中某種三元組（S1-S9）的閉合指數（TCI，triad closeness index）定義如下。

圖3 三元組結構的篩選

其中，()獲得節點、和構成的三元組結構，()統計某種三元組結構在整個網絡中出現的頻次，()統計三元組對應閉合結構的出現頻次。需要注意的是，本文提到的閉合三元組僅指單方向的閉合。如圖4所示，考慮節點和及其共同鄰居節點所構成的三元組，如果存在由節點指向節點的連邊，無論是否存在由節點指向的連邊，均稱此三元組為閉合三元組，反之則為未閉合三元組。這樣定義的好處在于，每次計算時只考慮一個方向的連邊，簡單清晰，且在進行矩陣運算時，會遍歷每個節點，“自動”計算另一個方向連邊的預測值。

2.3 預測方法

基于2.1節和2.2節的考慮，每個S1-S4結構中共同鄰居節點對于相似度的貢獻為

TCI是2.2節中定義的三元組閉合指數，()是節點貢獻函數。在有向網絡中，節點的度數有出度和入度的區分。對于不同的三元組，共同鄰居節點的出度和入度對于新連邊的影響程度是不同的。例如，S2結構三元組的出現頻次僅與節點的入度有關，而S3結構則僅和的出度相關。參照RA指標，度數越大，其共同鄰居節點對相似度的貢獻越小。基于以上考慮，()等于

圖4 有向網絡中三元組結構閉合示例

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

相似性函數(,)是遍歷所有的共同鄰居節點，且僅計算其中S1-S4結構再求和得到的?？梢钥闯鲂路椒ǖ挠嬎銖碗s度為O(2)，與CN在同一個量級，其中，表示網絡中節點的數目。

相似性計算算法流程如下。

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 仿真實驗

3.1 數據集

本文選擇的9個公開網絡數據集如下。

1) 電子郵件網絡（E-mail）[17]：歐洲研究機構的電子郵件網絡，節點代表用戶，有向邊代表用戶發送過郵件。

2) 論文引用網絡（Kohonen）[18]：Kohonen network也被稱為自組織映射（SOM），是一種展示和分析多維數據的方法。該網絡是與SOM相關的論文引用網絡。

3) 論文引用網絡（SmaGri）[18]：與Small等相關的論文引用網絡。

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

5) 線蟲代謝網絡（CElegans）[20]：該數據集是秀麗隱桿線蟲的代謝網絡。節點是代謝物（如蛋白質），連邊是代謝物之間的相互作用。

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

7) 論文引用網絡（Scimet）[18]：以“科學計量學”為主的論文引用網絡。

8) 維基百科（Wikivote）[22]：這是維基百科中用戶選舉管理員的投票網絡。節點代表用戶，邊代表投票。原網絡的連邊是有正負邊兩種情況的，本文也對其進行歸一化處理。

9) Gnutella網絡（Gnutella）[23]：Gnutella是一種文件共享網絡，節點表示網絡拓撲中的主機，連邊表示主機的連接關系。

表1列出了9個網絡中4種三元組結構的樣本數以及閉合指數，可以看出，三元組S4在所有三元組中閉合指數最低，S1的閉合指數最高。不同網絡的閉合指數相差較大，E-mail網絡中4種三元組指數比例差不多，SmaGri網絡中S1閉合指數最高，Gnutella網絡4種結構閉合指數都很低。由此可以看出，不同網絡的演化規律可能有很大差別。此外，出現頻次和閉合指數并沒有直接的關系，出現頻次最高的S2和S3閉合指數并不是最高的。

表1最后一行表示4種三元組結構在9個網絡中的平均閉合指數，為了進一步簡化計算，不必每次統計整個網絡的三元組閉合情況，同時仍能夠保持較好的預測精度，建議PCI寫為

表1 數據集中4種三元組結構及閉合指數

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

3.2 評價指標

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

其中，1表示測試集中的邊分數大于不存在的邊分數的次數，2代表分數值相等的次數。

3.3 基準方法

3.4 預測結果

PTI關注3.3節中提到的評價指標AUC，并與表2中擴展后的9種相似性指標進行對比。每個結果都是100次獨立實驗結果的平均值，每次獨立實驗都對應一個隨機的訓練集和測試集。每個數據集中最優的結果加陰影以突出顯示。

表2 基于局部的鏈路預測算法

表3 AUC結果對比

從表3的預測結果可以看出，對于同一個網絡，前9種基準指標的預測精度相差不大，而對于不同的網絡，預測精度顯著不同。一般而言，如果一個網絡具有較高的集聚系數，那么基于局部相似性的預測指標將得到較好的預測的結果。例如，效果最差的Gnutella網絡，其集聚系數僅有0.007 2，這意味著沒有多少鄰居節點進行相似度計算，自然預測精度不高。總體來說，PTI表現最好。除了FWMW食物鏈網絡，PTI在其余8個網絡中均取得了最高的預測精度。而在FWMW網絡中，PTI的預測精確度也和表現最優的CN非常接近?？梢钥吹?，除了FWMW食物鏈網絡和Gnutella點對點網絡以外，PTI在其他網絡的AUC都達到了0.85以上，在E-mail和Wikivote網絡甚至達到了0.95以上。此外，在無向網絡表現較好的RA和AA[2]在有向網絡中并沒有體現出明顯優勢。這說明簡單地將無向網絡預測算法應用到有向網絡中，并不完全適應有向網絡的一些特性，如在有向網絡中，每個節點有出度和入度的不同，無向網絡中的算法會混淆這些特性，這可能是無向網絡中算法在有向網絡中區分度不大且表現不是很好的原因之一。

表3中FPTI代表固定閉合概率的方法，可以看出，簡化后的方法與原始方法的AUC相差很小，但每次計算時不用統計整個網絡的三元組閉合指數，降低了計算復雜度。在對AUC要求不是非?？量痰膱龊?，可以考慮使用FPTI代替PTI使用。

4 結束語

鏈路預測作為數據挖掘的方向之一，近幾年發展迅猛，學者對于無向網絡進行了系統全面深入的研究，而有向網絡的研究尚處于起步階段。本文在這方面做出了一些嘗試，針對有向網絡特點提出了基于三元組的鏈路預測方法，并引入了三元組閉合指數進行相似度計算。在9個真實網絡的實驗中，新方法在AUC上基本都優于基準方法。這說明基于三元組的預測方法更適合有向網絡，能夠在一定程度上體現有向網絡的連邊機理。然而，本文僅考慮了9種三元組中的4個，其余5種結構對于相似度的影響未詳細分析，考慮并不全面。同時，本文僅關注了有向網絡，對于加權網絡或者動態網絡的分析是下一步的工作。

[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] 呂琳媛, 周濤. 鏈路預測[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的鏈路預測優化算法[J].通信學報, 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? ），男，河南鄭州人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為鏈路預測。

馬宏（1968? ），男，江蘇東臺人，國家數字交換系統工程技術研究中心研究員，主要研究方向為社會網絡分析、電信網關防護。

劉樹新（1987? ），男，山東濰坊人，博士，國家數字交換系統工程技術研究中心助理研究員，主要研究方向為復雜網絡、網絡信息挖掘。

TP393

A

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

2018?12?11；

2019?05?21

常圣，724986365@qq.com

國家自然科學基金資助項目（No.61803384）

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

常圣，馬宏，劉樹新. 基于三元組結構的有向網鏈路預測方法[J]. 網絡與信息安全學報, 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.