網(wǎng)絡(luò)結(jié)構(gòu)特征與鏈路預(yù)測算法關(guān)系研究

賈 珺，胡曉峰，賀筱媛

(1.國防大學(xué)信息作戰(zhàn)與指揮訓(xùn)練教研部，北京 100091; 2.軍事科學(xué)院運(yùn)籌所，北京 100091)

網(wǎng)絡(luò)結(jié)構(gòu)特征與鏈路預(yù)測算法關(guān)系研究

賈 珺1,2，胡曉峰1，賀筱媛1

(1.國防大學(xué)信息作戰(zhàn)與指揮訓(xùn)練教研部，北京 100091; 2.軍事科學(xué)院運(yùn)籌所，北京 100091)

以美國航空網(wǎng)絡(luò)、科學(xué)家合作網(wǎng)絡(luò)和線蟲新陳代謝網(wǎng)絡(luò)等5種實(shí)際網(wǎng)絡(luò)為例進(jìn)行了綜合實(shí)驗(yàn)，用結(jié)果數(shù)據(jù)定量化描述了同配系數(shù)、集聚系數(shù)和網(wǎng)絡(luò)效率等網(wǎng)絡(luò)結(jié)構(gòu)特征參數(shù)，與基于局部信息和全局信息的兩類鏈路預(yù)測方法結(jié)果之間的關(guān)系。通過對(duì)結(jié)果的分析，得到了網(wǎng)絡(luò)同配系數(shù)為正且聚集系數(shù)大于閾值(約0.1)時(shí)適用基于局部信息的預(yù)測方法，否則適用基于全局信息的預(yù)測方法；以及集聚系數(shù)、網(wǎng)絡(luò)效率與局部信息預(yù)測方法的結(jié)果成正比，與全局信息預(yù)測方法成反比等結(jié)論。這些結(jié)論為通過網(wǎng)絡(luò)特征參數(shù)進(jìn)行鏈路預(yù)測方法的選擇提供了定量化的參考依據(jù)。

鏈路預(yù)測；同配系數(shù)；集聚系數(shù)；網(wǎng)絡(luò)效率；預(yù)測精度

0 引言

鏈路預(yù)測是研究如何在已知鏈路和節(jié)點(diǎn)屬性等信息條件下，預(yù)測未知的鏈路是否存在、是何類型以及權(quán)重多少等問題[1]。從計(jì)算機(jī)領(lǐng)域的數(shù)據(jù)挖掘[2-3]到社交網(wǎng)絡(luò)中的朋友推薦[4-5]，從恐怖分子網(wǎng)絡(luò)中的威脅發(fā)現(xiàn)到生物領(lǐng)域中的蛋白質(zhì)交互[6]，鏈路預(yù)測的廣泛應(yīng)用已使其成為了復(fù)雜網(wǎng)絡(luò)研究中的熱點(diǎn)領(lǐng)域之一[7]。在實(shí)際進(jìn)行網(wǎng)絡(luò)的鏈路預(yù)測應(yīng)用時(shí)，面對(duì)具體的網(wǎng)絡(luò)和已有的幾十種成熟預(yù)測方法，如何快速選擇最適合的方法進(jìn)行預(yù)測，以得到較高精度的預(yù)測結(jié)果，是鏈路預(yù)測應(yīng)用中要解決的首要問題。

現(xiàn)有的成熟預(yù)測方法，可劃分為有監(jiān)督和無監(jiān)督兩類。其中有監(jiān)督方法一般都是將傳統(tǒng)的機(jī)器學(xué)習(xí)與網(wǎng)絡(luò)特征參數(shù)相結(jié)合，通過構(gòu)建相關(guān)映射函數(shù)來最終實(shí)現(xiàn)對(duì)鏈路的預(yù)測，此類方法在最近的研究與應(yīng)用中越來越受到重視[8-10]。但這類方法有個(gè)重要的條件，就是一般都需要節(jié)點(diǎn)的屬性信息，而這種屬性信息很多時(shí)候是很難獲得的[7]。因此，更簡單和直觀的進(jìn)行鏈路預(yù)測的就是無監(jiān)督方法。具體來說就是通過計(jì)算節(jié)點(diǎn)間的拓?fù)湎嗨菩詠磉M(jìn)行鏈路的預(yù)測。其中常見的包括基于節(jié)點(diǎn)、路徑和隨機(jī)游走等[1,7]，同時(shí)還有針對(duì)整體網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行預(yù)測的[11]。在最近的研究中還出現(xiàn)了通過廣義聚集系數(shù)[15]、網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)[12]以及通過對(duì)網(wǎng)絡(luò)鄰接矩陣進(jìn)行擾動(dòng)[13]等進(jìn)行網(wǎng)絡(luò)預(yù)測的。這些方法一般計(jì)算復(fù)雜度都不高，同時(shí)還能獲得不錯(cuò)的預(yù)測精度。

可以看出，無監(jiān)督方法主要是從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的微觀、中觀和宏觀角度出發(fā)，進(jìn)行鏈路預(yù)測的。因此不同預(yù)測方法所產(chǎn)生的結(jié)果與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之間可能會(huì)存在著某些內(nèi)在的聯(lián)系。在鏈路預(yù)測應(yīng)用時(shí)，就可以利用這種聯(lián)系，通過已知的網(wǎng)絡(luò)結(jié)構(gòu)，選擇相對(duì)適用的鏈路預(yù)測方法，得到較好的預(yù)測結(jié)果。

對(duì)于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究，一直是復(fù)雜網(wǎng)絡(luò)研究的基礎(chǔ)領(lǐng)域[16-18]，而已有的研究更多的是關(guān)注于結(jié)構(gòu)對(duì)網(wǎng)絡(luò)整體性能、傳播、同步以及網(wǎng)絡(luò)控制的影響[19-22]。對(duì)于不同網(wǎng)絡(luò)結(jié)構(gòu)與具體鏈路預(yù)測方法之間的關(guān)系，則只有對(duì)WS和BA兩種模型生成網(wǎng)絡(luò)的參數(shù)與預(yù)測結(jié)果之間關(guān)系的初步研究[23]，還缺乏以現(xiàn)實(shí)中實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)特征為對(duì)象的定量化研究。因此本論文以美國政治博客網(wǎng)絡(luò)(PoliticalBlogs)、美國航空網(wǎng)絡(luò)(USAir)、科學(xué)家合作網(wǎng)絡(luò)(NetScience)[27]、線蟲新陳代謝網(wǎng)絡(luò)(metabolic)[28]和爵士樂手網(wǎng)絡(luò)(Jazz)[26]等5個(gè)實(shí)際網(wǎng)絡(luò)為例，通過單網(wǎng)絡(luò)與多網(wǎng)絡(luò)兩類實(shí)驗(yàn)，研究了集聚系數(shù)、同配系數(shù)和網(wǎng)絡(luò)效率等參數(shù)與不同預(yù)測算法結(jié)果之間的相關(guān)關(guān)系，發(fā)現(xiàn)了同配系數(shù)和集聚系數(shù)對(duì)預(yù)測算法選擇的關(guān)鍵作用，為今后針對(duì)不同網(wǎng)絡(luò)選擇準(zhǔn)確率相對(duì)較高的預(yù)測方法，提供了定量化的參考依據(jù)。

1 基本概念

1.1 問題描述

為了檢驗(yàn)預(yù)測函數(shù)fi的準(zhǔn)確率，通常的做法是將已知網(wǎng)絡(luò)的鏈路集E分為訓(xùn)練集ET和測試集EP，使ET∪EP=E且ET∩EP=Φ，使用預(yù)測函數(shù)可得到一個(gè)結(jié)果集ER，然后通過專門的評(píng)價(jià)算法g對(duì)ER和EP進(jìn)行比較，最終得到一個(gè)衡量算法準(zhǔn)確率的值PScorefi。

1.2 網(wǎng)絡(luò)結(jié)構(gòu)特征參數(shù)

常見的網(wǎng)絡(luò)結(jié)構(gòu)有規(guī)則、隨機(jī)、小世界和無標(biāo)度等。為了描述不同網(wǎng)絡(luò)結(jié)構(gòu)的特征，人們建立了一系列的特征參數(shù)，這些參數(shù)從不同的側(cè)面將不同結(jié)構(gòu)的網(wǎng)絡(luò)區(qū)分開來。為了達(dá)到研究的目的，本論文選用了網(wǎng)絡(luò)密度(d)、冪指數(shù)(α)、聯(lián)通集團(tuán)數(shù)量(nc)、同配系數(shù)(r)、網(wǎng)絡(luò)效率(e)和集聚系數(shù)(C)等6項(xiàng)常見的網(wǎng)絡(luò)整體指標(biāo)，作為衡量網(wǎng)絡(luò)結(jié)構(gòu)特征的參數(shù)。

1.3 典型鏈路預(yù)測算法

1) 共同鄰居(CN)

共同鄰居是最基本的相似性指標(biāo)，對(duì)于網(wǎng)絡(luò)中不存在鏈接的節(jié)點(diǎn)對(duì)x和y，它兩個(gè)之間具有鏈接的可能性值取決于兩個(gè)節(jié)點(diǎn)鄰居的數(shù)量，數(shù)量越多，可能性越大。用公式可以表示為

(1)

其中，Sxy即為節(jié)點(diǎn)對(duì)x和y之間存在鏈路的定量化表示。

2) 優(yōu)先鏈接(PA)

PA這一指標(biāo)相對(duì)與其他指標(biāo)考慮的因素也較少，因而計(jì)算復(fù)雜度較低，具體來說對(duì)于網(wǎng)絡(luò)中不存在鏈接的節(jié)點(diǎn)對(duì)x和y，它兩個(gè)之間具有鏈接的可能性值取決于兩個(gè)節(jié)點(diǎn)度的乘積。用公式可以表示為

(2)

3)Jaccard

Jaccard是完全利用網(wǎng)絡(luò)節(jié)點(diǎn)的局部信息進(jìn)行鏈路預(yù)測的。具體來說對(duì)于網(wǎng)絡(luò)圖中不存在鏈接的節(jié)點(diǎn)對(duì)x和y，它兩個(gè)之間具有鏈接的可能性值取決于兩個(gè)節(jié)點(diǎn)鄰居的交集與鄰居的并集之間的比值。用公式可以表示為

(3)

其中，Sxy即為節(jié)點(diǎn)對(duì)x和y之間存在鏈路的概率，可以證明0≤Sxy≤1。

4)Adamic-Adar(AA)

AA是通過計(jì)算共同鄰居的節(jié)點(diǎn)情況來進(jìn)行鏈路預(yù)測的，但是其基本思想是共同鄰居的數(shù)量越多，同時(shí)每個(gè)共同鄰居節(jié)點(diǎn)的度越低，則兩點(diǎn)之間存在鏈接的可能性越大，反之如果共同鄰居越少，同時(shí)共同鄰居節(jié)點(diǎn)的度越大，則可能性越低。用公式可以表示為

(4)

5)Katz

S=βA+β2A2+β3A3+…+βLAL

(5)

6) 平均通勤時(shí)間(ACT)

(6)

1.4 準(zhǔn)確率評(píng)價(jià)方法

通過鏈路預(yù)測算法得出相應(yīng)的結(jié)果后，就需要對(duì)預(yù)測結(jié)果的準(zhǔn)確率進(jìn)行檢驗(yàn)。常見的評(píng)判算法準(zhǔn)確率的指標(biāo)有AUC、Precision和RankingScore3種。本論文選用AUC和Precision兩個(gè)值進(jìn)行算法精度的評(píng)價(jià)。

1)AUC

AUC指標(biāo)主要是從全局角度考慮預(yù)測的正確率。具體的計(jì)算方法是從測試集EP中隨機(jī)選取一條鏈路，然后再隨機(jī)選擇一條不存在的鏈路，比較這兩個(gè)鏈路在結(jié)果集ER中的結(jié)果值，如果測試集中鏈路的值大于不存在的鏈路，那么比較的結(jié)果值即為1；若兩個(gè)值相等，則比較結(jié)果記為0.5；若測試集中鏈路的值小于不存在的鏈路，則結(jié)果記為0。獨(dú)立的比較n次，若其中有n′次結(jié)果為1，n″次結(jié)果為0.5，n″′次結(jié)果為0，則最終的AUC值可記為

(7)

由式(7)可以看出AUC的取值范圍是0≤AUC≤1，若AUC≤0.5說明預(yù)測算法的正確率還不如隨機(jī)選擇的正確率高。

2)Precision

Precision主要考慮的是前L個(gè)預(yù)測結(jié)果的正確率。具體來說就是將預(yù)測結(jié)果集按照預(yù)測得到的值進(jìn)行排序，取前L個(gè)預(yù)測結(jié)果與測試結(jié)果集進(jìn)行比對(duì)，如果有l(wèi)個(gè)相同，則預(yù)測結(jié)果的正確率為兩個(gè)數(shù)的比值。用式(8)可以表示為

(8)

同理，對(duì)于不同的預(yù)測方法，若AUC值基本相同，則Precision值越高的，預(yù)測精度越高(本論文的所有算法中L=100)。

2 實(shí)驗(yàn)條件

對(duì)于網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)和鏈路預(yù)測算法之間關(guān)系的分析，需要搭建完整有效的實(shí)驗(yàn)環(huán)境。那么如何選擇能夠滿足研究要求的工具和平臺(tái)，以及有代表性的數(shù)據(jù)集，就成為了實(shí)驗(yàn)準(zhǔn)備最基本的兩個(gè)環(huán)節(jié)。下面分別介紹這兩部分的情況。

2.1 工具與平臺(tái)

現(xiàn)有成熟的復(fù)雜網(wǎng)絡(luò)分析工具包括C語言編寫的igraph、C++的Boost Graph Library(BGL)、DotNet平臺(tái)下的QuickGraph以及Python下的networkx等。其中networkx是目前應(yīng)用最廣泛也是最專業(yè)的復(fù)雜網(wǎng)絡(luò)分析工具包之一。它能夠創(chuàng)建和操縱復(fù)雜網(wǎng)絡(luò)，并對(duì)復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)、功能和動(dòng)力學(xué)進(jìn)行研究，同時(shí)networkx還提供了目前相對(duì)最完整的復(fù)雜網(wǎng)絡(luò)分析算法集[24]。但由于networkx是使用Python語言編寫的，因此其執(zhí)行效率要遠(yuǎn)低于前幾種基于C或C++的工具包。

鑒于本實(shí)驗(yàn)主要關(guān)注的是算法的精度和準(zhǔn)確度，對(duì)效率的要求并不高。同時(shí)，由于在計(jì)算網(wǎng)絡(luò)結(jié)構(gòu)時(shí)，需要對(duì)網(wǎng)絡(luò)度分布的冪律進(jìn)行擬合，而這方面現(xiàn)在最權(quán)威的分析工具是Python下的powerlaw分析包[25]。因此，本實(shí)驗(yàn)的基礎(chǔ)平臺(tái)采用Python2.7，IDE采用pywin32-219，網(wǎng)絡(luò)分析工具采用2014年9月發(fā)布的networkx-1.9.1。

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

實(shí)驗(yàn)數(shù)據(jù)的選擇在很大程度上影響著實(shí)驗(yàn)結(jié)果。為了使本論文的研究更具有普適性和實(shí)際應(yīng)用價(jià)值，本論文采用美國政治博客網(wǎng)絡(luò)(PoliticalBlogs)、美國航空網(wǎng)絡(luò)(USAir)、科學(xué)家合作網(wǎng)絡(luò)(NetScience)、線蟲新陳代謝網(wǎng)絡(luò)(metabolic)和爵士樂手網(wǎng)絡(luò)(Jazz)等5種典型的實(shí)際網(wǎng)絡(luò)。這幾種網(wǎng)絡(luò)歸屬于不同的領(lǐng)域，其規(guī)模和形成機(jī)理都不一致，具體的網(wǎng)絡(luò)結(jié)構(gòu)特征參數(shù)值如表1所示。5種網(wǎng)絡(luò)的度分布如圖1所示。

3 實(shí)驗(yàn)與分析

在已有實(shí)驗(yàn)工具、平臺(tái)和數(shù)據(jù)基礎(chǔ)上，需要對(duì)實(shí)驗(yàn)進(jìn)行合理設(shè)計(jì)，才能達(dá)到系統(tǒng)研究結(jié)構(gòu)特征與預(yù)測方法關(guān)系的目標(biāo)。本論文將實(shí)驗(yàn)分為兩大部分，一是首先對(duì)某一單獨(dú)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，考察其結(jié)構(gòu)特征參數(shù)值的變化與預(yù)測方法之間的關(guān)系；然后是多網(wǎng)絡(luò)實(shí)驗(yàn)，具體又分為兩種情況。一是考察多個(gè)網(wǎng)絡(luò)不同結(jié)構(gòu)參數(shù)值與預(yù)測方法之間的關(guān)系；二是考察多個(gè)網(wǎng)絡(luò)相近參數(shù)值與預(yù)測方法之間的關(guān)系。在以上實(shí)驗(yàn)基礎(chǔ)上，通過對(duì)結(jié)果數(shù)據(jù)的深入分析，找到網(wǎng)絡(luò)結(jié)構(gòu)特征參數(shù)值與預(yù)測方法之間可能存在的聯(lián)系。

表1 實(shí)驗(yàn)對(duì)象網(wǎng)絡(luò)結(jié)構(gòu)特征參數(shù)統(tǒng)計(jì)Tab.1 the Structure Features of Experiment Networks

圖1 實(shí)驗(yàn)對(duì)象網(wǎng)絡(luò)度分布圖Fig.1 The degree distributions of experiment networks

3.1 單網(wǎng)絡(luò)結(jié)構(gòu)特征與預(yù)測算法關(guān)系實(shí)驗(yàn)

單網(wǎng)絡(luò)的結(jié)構(gòu)特征與預(yù)測算法關(guān)系實(shí)驗(yàn)，主要可分為以下幾個(gè)步驟：

第2步：按照α將對(duì)象網(wǎng)絡(luò)隨機(jī)分為訓(xùn)練集EP和測試集ET，計(jì)算EP的結(jié)構(gòu)參數(shù)，并按照指定的鏈路預(yù)測算法進(jìn)行預(yù)測，計(jì)算結(jié)果正確率。

第3步：重復(fù)第二步N次，記錄結(jié)構(gòu)參數(shù)變化與結(jié)果正確率之間的關(guān)系，并同時(shí)求出在這一比率下結(jié)構(gòu)參數(shù)的均值和結(jié)果正確率的均值。

第4步：改變?chǔ)?，重?fù)第2、3步，記錄不同α下的結(jié)構(gòu)參數(shù)值和結(jié)果正確率。

本論文選擇度分布符合冪律特性的metabolic作為單網(wǎng)絡(luò)實(shí)驗(yàn)的對(duì)象，按照上述步驟，分別進(jìn)行實(shí)驗(yàn)。首先進(jìn)行第1、2、3步實(shí)驗(yàn)。設(shè)定α=0.1，隨機(jī)對(duì)網(wǎng)絡(luò)進(jìn)行抽取，并采用6種方法分別進(jìn)行預(yù)測。重復(fù)進(jìn)行N=25次實(shí)驗(yàn)中，抽取的訓(xùn)練集網(wǎng)絡(luò)結(jié)構(gòu)特征參數(shù)值中只有同配系數(shù)和集聚系數(shù)在隨機(jī)抽取中會(huì)發(fā)生比較明顯的變化，其余都基本與平均值一致。各參數(shù)平均值如表2所示。(同配系數(shù)和集聚系數(shù)的變化情況如圖2所示。)

表2 metabolic訓(xùn)練集網(wǎng)絡(luò)特征參數(shù)均值 (a=0.1)Tab.2 The features’ mean values of metabolic training set at the rate of 0.1

圖2 單網(wǎng)絡(luò)實(shí)驗(yàn)中(α=0.1)同配系數(shù)與集聚系數(shù)變化情況Fig.2 The changing values of training set’s assortativity and clustering in single network experiment (a=0.1)

圖3 單網(wǎng)絡(luò)實(shí)驗(yàn)(α=0.1)中6種預(yù)測方法的結(jié)果精度(AUC)Fig.3 The AUC of six prediction algorithms in single network experiment (a=0.1)

圖4 單網(wǎng)絡(luò)實(shí)驗(yàn)(α=0.1)中6種預(yù)測方法的結(jié)果精度(precision)Fig.4 The precision of six prediction algorithms in single network experiment (a=0.1)

通過實(shí)驗(yàn)，6種預(yù)測方法分別獲得的預(yù)測精度值如圖3所示。

由圖4可以看到，6種預(yù)測方法最終的預(yù)測精度基本上是圍繞各自的一個(gè)平均值在上下震動(dòng)，只是震動(dòng)幅度不太一致。但明顯可以看出Katz的預(yù)測精度要好于其他算法。

由圖5可以看到，平均聚集系數(shù)、平均網(wǎng)絡(luò)效率、網(wǎng)絡(luò)密度(上面3個(gè))與訓(xùn)練集中的鏈路數(shù)量變化成正比，平均聯(lián)通集團(tuán)數(shù)量與其變化成反比，同配性和冪律則基本不變。6種預(yù)測方法的預(yù)測結(jié)果如圖6所示。

由圖6可以看到，綜合考慮兩類指標(biāo)可以看出6種預(yù)測算法中Katz和ACT的預(yù)測精度要好于另一類算法，說明基于全局信息的算法更適用于此種網(wǎng)絡(luò)的預(yù)測，同時(shí)預(yù)測精度的變化說明聚集系數(shù)、網(wǎng)絡(luò)密度和網(wǎng)絡(luò)效率等結(jié)構(gòu)參數(shù)與CN、Jaccard等局部算法的預(yù)測結(jié)果呈正比，與Katz和ACT的預(yù)測結(jié)果成反比。下面使用多網(wǎng)絡(luò)實(shí)驗(yàn)，測試不同網(wǎng)絡(luò)結(jié)構(gòu)特征參數(shù)與不同預(yù)測算法間的關(guān)系。

3.2 多網(wǎng)絡(luò)結(jié)構(gòu)特征與預(yù)測算法關(guān)系實(shí)驗(yàn)

對(duì)多個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)特征參數(shù)與預(yù)測算法之間的關(guān)系進(jìn)行實(shí)驗(yàn)，主要可以分為以下幾個(gè)步驟：

第1步：設(shè)定網(wǎng)絡(luò)分解比率α，按照這一比率對(duì)多個(gè)對(duì)象網(wǎng)絡(luò)進(jìn)行分解，并記錄訓(xùn)練集的相關(guān)結(jié)構(gòu)特征參數(shù)值。

第2步：按照給定的鏈路預(yù)測算法，對(duì)所有對(duì)象網(wǎng)絡(luò)進(jìn)行預(yù)測，記錄預(yù)測結(jié)果。

第3步：重復(fù)第1、2兩步N次，求出每個(gè)訓(xùn)練集結(jié)構(gòu)特征參數(shù)和預(yù)測結(jié)果的平均值。

第4步：指定某個(gè)結(jié)構(gòu)特征參數(shù)值，改變對(duì)象網(wǎng)絡(luò)，使其訓(xùn)練集的這一結(jié)構(gòu)特征參數(shù)值與指定數(shù)值基本相等，然后進(jìn)行預(yù)測實(shí)驗(yàn)，記錄預(yù)測結(jié)果。

根據(jù)上述步驟，設(shè)定網(wǎng)絡(luò)分解比率α=0.1，按照上面的第3步重復(fù)進(jìn)行N=50次實(shí)驗(yàn)，得到各網(wǎng)絡(luò)按照比率為0.1進(jìn)行抽取后的訓(xùn)練集網(wǎng)絡(luò)，其特征參數(shù)均值結(jié)果如表3所示。

圖5 單網(wǎng)絡(luò)實(shí)驗(yàn)(變化)中網(wǎng)絡(luò)特征參數(shù)變化Fig.5 The structure features' values in single network experiment with different ratio

圖6 單網(wǎng)絡(luò)實(shí)驗(yàn)(α變化)中6種預(yù)測結(jié)果的精度Fig.6 The accuracy of three algorithms in single network experiment with different ratio α

表3 5個(gè)訓(xùn)練集(α=0.1)網(wǎng)絡(luò)特征參數(shù)均值Tab.3 The averages of five networks training set’s structure features’ mean value (α=0.1)

5種網(wǎng)絡(luò)分別按照6種典型鏈路預(yù)測方法進(jìn)行預(yù)測，統(tǒng)計(jì)后可得，各預(yù)測結(jié)果的均值如表4所示。

由表4可以看到，不同的網(wǎng)絡(luò)適用不同的鏈路預(yù)測方法，表中的陰影方格是綜合考慮AUC和Precision后的最佳預(yù)測結(jié)果。從這個(gè)結(jié)果初步可以看出，當(dāng)同配系數(shù)為正時(shí)，基于局部信息的預(yù)測算法正確率較高，當(dāng)同配系數(shù)為負(fù)時(shí)，基于全局信息的預(yù)測算法正確率較高。接下來進(jìn)行第4步，根據(jù)前面的實(shí)驗(yàn)可以得出，由于網(wǎng)絡(luò)密度、效率和集聚系數(shù)與鏈路數(shù)量的變化成正比，現(xiàn)選擇PoliticalBlogs和Jazz兩個(gè)網(wǎng)絡(luò)，減少Jazz網(wǎng)絡(luò)的鏈路數(shù)量，使其結(jié)構(gòu)特征參數(shù)逐漸逼近PoliticalBlogs，Jazz的網(wǎng)絡(luò)密度、集聚系數(shù)、網(wǎng)絡(luò)效率和同配系數(shù)隨著鏈路數(shù)量減少，其變化如圖7所示。

表 4 多網(wǎng)絡(luò)實(shí)驗(yàn)(α=0.1)中6種預(yù)測結(jié)果均值Tab.4 The six algorithms’ accuracy in multi-network experiment

注：表中加框的為網(wǎng)絡(luò)對(duì)應(yīng)的最優(yōu)預(yù)測結(jié)果。

圖7 Jazz網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)均值變化情況Fig.7 The changing of Jazz’s structure features’ mean values

由圖7可以看到，當(dāng)抽取比率為0.5時(shí)，Jazz的聚集系數(shù)與PoliticalBlogs的相同；當(dāng)抽取比率為0.7時(shí)，Jazz的網(wǎng)絡(luò)效率與PoliticalBlogs的相同；當(dāng)抽取比率為0.8時(shí)，Jazz的網(wǎng)絡(luò)密度與PoliticalBlogs的相同；當(dāng)抽取比率為0.9時(shí)，網(wǎng)絡(luò)的同配系數(shù)為負(fù)。按照相對(duì)應(yīng)的抽取比率，從0.5開始，分別生成新的網(wǎng)絡(luò)，然后使用6種預(yù)測方法分別進(jìn)行預(yù)測，具體的預(yù)測結(jié)果如圖8所示。

圖8 新Jazz網(wǎng)絡(luò)預(yù)測結(jié)果變化情況Fig.8 The changing of Jazz’s prediction’s result

圖9 網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)與預(yù)測算法選擇關(guān)系Fig.9 The relationship between structure features and prediction algorithms

由圖8可以看出，隨著網(wǎng)絡(luò)密度、集聚系數(shù)、網(wǎng)絡(luò)效率等的降低，基于局部信息的預(yù)測算法(CN、Jaccard、AA等)明顯與這些參數(shù)的變化成正比，而基于全局信息的預(yù)測算法(Katz、ACT)則并不明顯，甚至有時(shí)還成反比。當(dāng)抽取比率大于0.8(新網(wǎng)絡(luò)的集聚系數(shù)大約小于0.1、同配系數(shù)小于0)時(shí)，基于全局信息的預(yù)測算法精度開始優(yōu)于基于局部信息的優(yōu)化算法。這再一次證明了同配系數(shù)和集聚系數(shù)這兩個(gè)參數(shù)對(duì)于預(yù)測算法的選擇起著至關(guān)重要的作用。

3.3 結(jié)論與分析

根據(jù)前面的實(shí)驗(yàn)結(jié)果，可以初步得到以下結(jié)論：

結(jié)論1：同配系數(shù)的正負(fù)和聚集系數(shù)的高低兩個(gè)因素是選擇局部或全局算法的關(guān)鍵。由表4可以看出當(dāng)某個(gè)網(wǎng)絡(luò)的同配系數(shù)大于零時(shí)，基于局部信息的預(yù)測算法(AA等)結(jié)果較好；而當(dāng)同配系數(shù)小于零時(shí)，基于全局信息的預(yù)測算法(Katz)結(jié)果較好。同時(shí)根據(jù)表4和圖8還可以看出，當(dāng)聚集系數(shù)較大時(shí)，局部信息的預(yù)測算法結(jié)果較好，當(dāng)聚集系數(shù)小于閾值(0.1)時(shí)，即使同配系數(shù)為正，基于全局信息的預(yù)測算法結(jié)果都要優(yōu)于局部信息的預(yù)測算法。因此同配系數(shù)、集聚系數(shù)與預(yù)測算法選擇之間的關(guān)系可如圖9所示。

這一結(jié)論主要是因?yàn)橥湎禂?shù)和聚集系數(shù)從不同角度反映了網(wǎng)絡(luò)中節(jié)點(diǎn)之間的鏈接情況，若同配系數(shù)大于零，說明同類節(jié)點(diǎn)存在鏈接的概率更大，小于零則反之；當(dāng)聚集系數(shù)較大時(shí)，說明節(jié)點(diǎn)間互相連接情況較多，較小時(shí)則相反。因此可以得出，基于局部信息的相似性算法更加依賴網(wǎng)絡(luò)的聚集性，因此在保證同配系數(shù)為正的情況下，網(wǎng)絡(luò)聚集系數(shù)越高基于局部信息的預(yù)測結(jié)果會(huì)越好；而對(duì)于全局信息的相似性算法則是依賴更多的長路徑，因此在保證同配系數(shù)為負(fù)的情況下，集聚系數(shù)越低則預(yù)測精度越高。

結(jié)論2：集聚系數(shù)和網(wǎng)絡(luò)效率與局部預(yù)測算法的結(jié)果成正比，與全局預(yù)測算法的結(jié)果成反比。由圖5、圖6和圖8可以看出，通過減少訓(xùn)練網(wǎng)絡(luò)的鏈路數(shù)量，使得集聚系數(shù)和網(wǎng)絡(luò)效率等參數(shù)值降低時(shí)，局部預(yù)測算法的預(yù)測精度也同樣降低。這一結(jié)論是由于基于局部信息的相似性預(yù)測算法，主要是通過節(jié)點(diǎn)的鄰居和度等信息進(jìn)行節(jié)點(diǎn)對(duì)的相似性計(jì)算，而減少網(wǎng)絡(luò)鏈路數(shù)量過程中，必然降低節(jié)點(diǎn)度和減少節(jié)點(diǎn)鄰居，這在降低網(wǎng)絡(luò)集聚系數(shù)、網(wǎng)絡(luò)密度的同時(shí)，也降低了相似性算法中節(jié)點(diǎn)對(duì)的值，因此必然降低預(yù)測精度。而在全局預(yù)測算法中，計(jì)算主要使用的是各種長度的路徑。在不同的網(wǎng)絡(luò)中，更低的集聚系數(shù)或者網(wǎng)絡(luò)效率意味著網(wǎng)絡(luò)中相對(duì)存在著更多更長的路徑，而這種長路徑的存在會(huì)導(dǎo)致預(yù)測算法結(jié)果的增大。因此使得聚集系數(shù)和網(wǎng)絡(luò)效率與預(yù)測結(jié)果之間呈現(xiàn)出反比。這一情況在圖4或表5、6中也可以看到，由于鏈路數(shù)量的減少，降低了集聚系數(shù)和網(wǎng)絡(luò)效率，同時(shí)使得網(wǎng)絡(luò)中長路徑相對(duì)增加，使得Katz算法的結(jié)果下降趨勢(shì)明顯小于其他兩種算法。

4 結(jié)論

本文通過CN、Jaccard、PA、AA、Katz和ACT 6種預(yù)測方法在PoliticalBlogs、 USAir、NetScience、metabolic和Jazz等5種實(shí)際網(wǎng)絡(luò)上的兩類實(shí)驗(yàn)，發(fā)現(xiàn)并證明了網(wǎng)絡(luò)的同配系數(shù)、集聚系數(shù)和網(wǎng)絡(luò)效率與不同類型的預(yù)測方法結(jié)果精度之間的關(guān)系，為今后鏈路預(yù)測應(yīng)用中方法的選擇提供了定量化的參考依據(jù)。

但還是要看到，以上的結(jié)論還是比較粗略的。這是由于在網(wǎng)絡(luò)特征結(jié)構(gòu)方面，本文所選擇的同配系數(shù)、集聚系數(shù)和網(wǎng)絡(luò)效率等參數(shù)之間相互影響，是否能通過一個(gè)單一的網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)確定預(yù)測方法還需要進(jìn)行更進(jìn)一步的實(shí)驗(yàn)。在預(yù)測方法的選擇方面，本文的預(yù)測方法僅僅局限于無監(jiān)督方法中常見的局部和全局信息兩類，對(duì)于一些中觀角度出發(fā)的基于社團(tuán)結(jié)構(gòu)和廣義聚集系數(shù)等還未進(jìn)行相關(guān)關(guān)系的分析。這也是導(dǎo)致實(shí)驗(yàn)中某些網(wǎng)絡(luò)的最佳預(yù)測結(jié)果并不令人滿意的原因。同時(shí)，現(xiàn)在更多的預(yù)測方法是通過引入機(jī)器學(xué)習(xí)的有監(jiān)督方法，逐步通過回饋調(diào)整預(yù)測算法中的某些參數(shù)，使預(yù)測結(jié)果達(dá)到最佳。如何將兩者關(guān)系與有監(jiān)督方法相結(jié)合，通過提高機(jī)器學(xué)習(xí)的效率最終提高預(yù)測精度，也是下一步需要深入研究的內(nèi)容。

[1]Al Hasan M,Zaki M J.A survey of link prediction in social networks[M].Social network data analytics,Springer US,2011:243-275.

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

[3]Getoor L,Diehl C P.Link mining:a survey[J].ACM Sigkdd Explorations Newsletter,2005,7(2):3-12.

[4]Liben-Nowell D,Kleinberg J.The link prediction problem for social networks[J].Journal of the American Society for Information Science and Technology,2007,58(7):1019-1031.

[5]Dong Y,Tang J,Wu S,et al.Link prediction and recommendation across heterogeneous social networks[C]// 2012 IEEE 12th International Conference on Data Mining.2012:181-190.

[6]Cannistraci C V,Alanis-Lobato G,Ravasi T.From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J].Scientific Reports,2013,3(4):1613.

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

[8]Al Hasan M,Chaoji V,Salem S,et al.Link prediction using supervised learning[J]//Proc of Sdm Workshop Link Analysis Counterrorism & Security,2005,30(9):798-805.

[9]Miller K,Jordan M I,Griffiths T L.Nonparametric latent feature models for link prediction[J]//Advances in Neural Information Processing Systems.2009:1276-1284.

[10]Fire M,Tenenboim L,Lesser O,et al.Link prediction in social networks using computationally efficient topological features[C].Privacy,Security,Risk and Trust (PASSAT) and 2011 IEEE Third Inernational Conference on Social Computing (SocialCom),2011 IEEE Third International Conference on.IEEE,2011:73-80.

[11] Clauset A,Moore C,Newman M E J.Hierarchical structure and the prediction of missing links in networks[J].Nature,2008,453(7191):98-101.

[12] Ding J,Jiao L,Wu J,et al.Prediction of missing links based on multi-resolution community division[J].Physica A:Statistical Mechanics and Its Applications,2015,417:76-85.

[13] Lü L,Pan L,Zhou T,et al.Toward link predictability of complex networks[J].Proceedings of the National Academy of Sciences,2015,112(8):2325-2330.

[14] Liu H K,Ln L Y，Zhou T.Uncovering the network evolution mechanism by link prediction[J].Sci Sin Phys Mech Astron,201l,41:816-823

[15] Huang Z.Link prediction based on graph topology:the predictive value of generalized clustering coefficient[J].Social Science Electronic Publishing,2010:1634014.

[16] Milward H B,Provan K G.Measuring network structure[J].Public Administration,1998,76(2):387-407.

[17] Newman M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.

[18] Newman M J.The structure of scientic collaboration networks[J].Proc of the National Acad of Sciences,2001,98(2):404-409.

[19] Lazer D,Friedman A.The network structure of exploration and exploitation[J].Administrative Science Quarterly,2007,52(4):667-694.

[20] Reagans R,McEvily B.Network structure and knowledge transfer:the effects of cohesion and range[J].Administrative Science Quarterly,2003,48(2):240-267.

[21] Wagner C S,Leydesdorff L.Network structure,self-organization,and the growth of international collaboration in science[J].Research Policy,2005,34(10):1608-1618.

[22] Jalili M,Sichani O A,Yu X.Optimal pinning controllability of complex networks:dependence on network structure[J].Physical Review E,2015,91(1):012803.

[23] Ahn M W,Jung W S.Accuracy test for link prediction in terms of similarity index:the case of WS and BA models[J].Physica A:Statistical Mechanics and Its Applications,2015.

[24] Schult D A,Swart P J.Exploring network structure,dynamics,and function using NetworkX[C].Proceedings of the 7th Python in Science Conferences,2008:11-16.

[25] Alstott J,Bullmore E,Plenz D.Powerlaw:a python package for analysis of heavy-tailed distributions[J].PLoS One,2014,9(1):e85777.

[26] Gleiser P M,Danon L.Community structure in jazz[J].Aduances in Complex Systems,2003,6(4):565-573.

[27] Newman M E J.Finding community structure in networks using the eigenvectors of matrics[J].Physical Review E,2006,74(3):036104.

[28] Watts D J,Strogatz S H.Collective dynamics of small-world networks[J].Nature,1998,393(6684):440-442.

(責(zé)任編輯 耿金花)

On the Relationship Between Network Structure Features and Link Prediction Algorithms

JIA Jun1,2,HU Xiaofeng1,HE Xiaoyuan

(1.The Department of Information Operation Command Training,National Defense University,Beijing 100091,China; 2.The Department of Graduate,National Defense University,Beijing 100091,China)

This paper experimented with five virtual networks,such as the Air network of US,the Coauthorship network of Scientists,the Neural network of the nematode C,etc.and quantified the relationship between the network structure features and the link prediction algorithms by the experiment’s data.The network structure features could be measured by assortativity coefficient,clustering coefficient,etc.and the link prediction algorithms could be divided into local-information based and global-information based.After analyzed the data,we found that if the value of network’s assortativity coefficient is positive and the value of network’s clustering coefficient is greater than the threshold which is about 0.1,the local-information based would be the better choice,otherwise the global-information based would be better.And the clustering coefficient and the network efficiency is proportional to the result of link prediction algorithms based local information and is reverse proportional to the result of algorithms based global information.These conclusions provide quantitative basis for selecting the right algorithm.

link prediction; assortativity coefficient; clustering coefficient; network efficiency; accuracy of prediction

1672-3813(2017)01-0028-10；

10.13306/j.1672-3813.2017.01.005

2015-04-07；

2015-10-11

國家自然科學(xué)基金 (U1435218,61174035,61273189,61374179)

賈珺(1981-)，男，陜西西安人，博士研究生，助理研究員，主要研究方向?yàn)檐娛逻\(yùn)籌學(xué)。

TP391.9

A