賈 珺，胡曉峰，賀筱媛

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

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

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

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

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

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

0 引言

鏈路預(yù)測是研究如何在已知鏈路和節(jié)點屬性等信息條件下，預(yù)測未知的鏈路是否存在、是何類型以及權(quán)重多少等問題[1]。從計算機領(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ò)研究中的熱點領(lǐng)域之一[7]。在實際進行網(wǎng)絡(luò)的鏈路預(yù)測應(yīng)用時，面對具體的網(wǎng)絡(luò)和已有的幾十種成熟預(yù)測方法，如何快速選擇最適合的方法進行預(yù)測，以得到較高精度的預(yù)測結(jié)果，是鏈路預(yù)測應(yīng)用中要解決的首要問題。

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

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

對于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的研究，一直是復(fù)雜網(wǎng)絡(luò)研究的基礎(chǔ)領(lǐng)域[16-18]，而已有的研究更多的是關(guān)注于結(jié)構(gòu)對網(wǎng)絡(luò)整體性能、傳播、同步以及網(wǎng)絡(luò)控制的影響[19-22]。對于不同網(wǎng)絡(luò)結(jié)構(gòu)與具體鏈路預(yù)測方法之間的關(guān)系，則只有對WS和BA兩種模型生成網(wǎng)絡(luò)的參數(shù)與預(yù)測結(jié)果之間關(guān)系的初步研究[23]，還缺乏以現(xiàn)實中實際網(wǎng)絡(luò)結(jié)構(gòu)特征為對象的定量化研究。因此本論文以美國政治博客網(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個實際網(wǎng)絡(luò)為例，通過單網(wǎng)絡(luò)與多網(wǎng)絡(luò)兩類實驗，研究了集聚系數(shù)、同配系數(shù)和網(wǎng)絡(luò)效率等參數(shù)與不同預(yù)測算法結(jié)果之間的相關(guān)關(guān)系，發(fā)現(xiàn)了同配系數(shù)和集聚系數(shù)對預(yù)測算法選擇的關(guān)鍵作用，為今后針對不同網(wǎng)絡(luò)選擇準確率相對較高的預(yù)測方法，提供了定量化的參考依據(jù)。

1 基本概念

1.1 問題描述

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

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

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

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

1) 共同鄰居(CN)

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

(1)

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

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

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

(2)

3)Jaccard

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

(3)

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

4)Adamic-Adar(AA)

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

(4)

5)Katz

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

(5)

6) 平均通勤時間(ACT)

(6)

1.4 準確率評價方法

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

1)AUC

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

(7)

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

2)Precision

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

(8)

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

2 實驗條件

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

2.1 工具與平臺

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

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

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

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

3 實驗與分析

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

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

圖1 實驗對象網(wǎng)絡(luò)度分布圖Fig.1 The degree distributions of experiment networks

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

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

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

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

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

本論文選擇度分布符合冪律特性的metabolic作為單網(wǎng)絡(luò)實驗的對象，按照上述步驟，分別進行實驗。首先進行第1、2、3步實驗。設(shè)定α=0.1，隨機對網(wǎng)絡(luò)進行抽取，并采用6種方法分別進行預(yù)測。重復(fù)進行N=25次實驗中，抽取的訓(xùn)練集網(wǎng)絡(luò)結(jié)構(gòu)特征參數(shù)值中只有同配系數(shù)和集聚系數(shù)在隨機抽取中會發(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ò)實驗中(α=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ò)實驗(α=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ò)實驗(α=0.1)中6種預(yù)測方法的結(jié)果精度(precision)Fig.4 The precision of six prediction algorithms in single network experiment (a=0.1)

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 5個訓(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ù)測方法進行預(yù)測，統(tǒng)計后可得，各預(yù)測結(jié)果的均值如表4所示。

由表4可以看到，不同的網(wǎng)絡(luò)適用不同的鏈路預(yù)測方法，表中的陰影方格是綜合考慮AUC和Precision后的最佳預(yù)測結(jié)果。從這個結(jié)果初步可以看出，當同配系數(shù)為正時，基于局部信息的預(yù)測算法正確率較高，當同配系數(shù)為負時，基于全局信息的預(yù)測算法正確率較高。接下來進行第4步，根據(jù)前面的實驗可以得出，由于網(wǎng)絡(luò)密度、效率和集聚系數(shù)與鏈路數(shù)量的變化成正比，現(xiàn)選擇PoliticalBlogs和Jazz兩個網(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ò)實驗(α=0.1)中6種預(yù)測結(jié)果均值Tab.4 The six algorithms’ accuracy in multi-network experiment

注：表中加框的為網(wǎng)絡(luò)對應(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可以看到，當抽取比率為0.5時，Jazz的聚集系數(shù)與PoliticalBlogs的相同；當抽取比率為0.7時，Jazz的網(wǎng)絡(luò)效率與PoliticalBlogs的相同；當抽取比率為0.8時，Jazz的網(wǎng)絡(luò)密度與PoliticalBlogs的相同；當抽取比率為0.9時，網(wǎng)絡(luò)的同配系數(shù)為負。按照相對應(yīng)的抽取比率，從0.5開始，分別生成新的網(wǎng)絡(luò)，然后使用6種預(yù)測方法分別進行預(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)則并不明顯，甚至有時還成反比。當抽取比率大于0.8(新網(wǎng)絡(luò)的集聚系數(shù)大約小于0.1、同配系數(shù)小于0)時，基于全局信息的預(yù)測算法精度開始優(yōu)于基于局部信息的優(yōu)化算法。這再一次證明了同配系數(shù)和集聚系數(shù)這兩個參數(shù)對于預(yù)測算法的選擇起著至關(guān)重要的作用。

3.3 結(jié)論與分析

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

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

這一結(jié)論主要是因為同配系數(shù)和聚集系數(shù)從不同角度反映了網(wǎng)絡(luò)中節(jié)點之間的鏈接情況，若同配系數(shù)大于零，說明同類節(jié)點存在鏈接的概率更大，小于零則反之；當聚集系數(shù)較大時，說明節(jié)點間互相連接情況較多，較小時則相反。因此可以得出，基于局部信息的相似性算法更加依賴網(wǎng)絡(luò)的聚集性，因此在保證同配系數(shù)為正的情況下，網(wǎng)絡(luò)聚集系數(shù)越高基于局部信息的預(yù)測結(jié)果會越好；而對于全局信息的相似性算法則是依賴更多的長路徑，因此在保證同配系數(shù)為負的情況下，集聚系數(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ù)值降低時，局部預(yù)測算法的預(yù)測精度也同樣降低。這一結(jié)論是由于基于局部信息的相似性預(yù)測算法，主要是通過節(jié)點的鄰居和度等信息進行節(jié)點對的相似性計算，而減少網(wǎng)絡(luò)鏈路數(shù)量過程中，必然降低節(jié)點度和減少節(jié)點鄰居，這在降低網(wǎng)絡(luò)集聚系數(shù)、網(wǎng)絡(luò)密度的同時，也降低了相似性算法中節(jié)點對的值，因此必然降低預(yù)測精度。而在全局預(yù)測算法中，計算主要使用的是各種長度的路徑。在不同的網(wǎng)絡(luò)中，更低的集聚系數(shù)或者網(wǎng)絡(luò)效率意味著網(wǎng)絡(luò)中相對存在著更多更長的路徑，而這種長路徑的存在會導(dǎo)致預(yù)測算法結(jié)果的增大。因此使得聚集系數(shù)和網(wǎng)絡(luò)效率與預(yù)測結(jié)果之間呈現(xiàn)出反比。這一情況在圖4或表5、6中也可以看到，由于鏈路數(shù)量的減少，降低了集聚系數(shù)和網(wǎng)絡(luò)效率，同時使得網(wǎng)絡(luò)中長路徑相對增加，使得Katz算法的結(jié)果下降趨勢明顯小于其他兩種算法。

4 結(jié)論

本文通過CN、Jaccard、PA、AA、Katz和ACT 6種預(yù)測方法在PoliticalBlogs、 USAir、NetScience、metabolic和Jazz等5種實際網(wǎng)絡(luò)上的兩類實驗，發(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ù)之間相互影響，是否能通過一個單一的網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)確定預(yù)測方法還需要進行更進一步的實驗。在預(yù)測方法的選擇方面，本文的預(yù)測方法僅僅局限于無監(jiān)督方法中常見的局部和全局信息兩類，對于一些中觀角度出發(fā)的基于社團結(jié)構(gòu)和廣義聚集系數(shù)等還未進行相關(guān)關(guān)系的分析。這也是導(dǎo)致實驗中某些網(wǎng)絡(luò)的最佳預(yù)測結(jié)果并不令人滿意的原因。同時，現(xiàn)在更多的預(yù)測方法是通過引入機器學(xué)習(xí)的有監(jiān)督方法，逐步通過回饋調(diào)整預(yù)測算法中的某些參數(shù)，使預(yù)測結(jié)果達到最佳。如何將兩者關(guān)系與有監(jiān)督方法相結(jié)合，通過提高機器學(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.

(責任編輯 耿金花)

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-)，男，陜西西安人，博士研究生，助理研究員，主要研究方向為軍事運籌學(xué)。

TP391.9

A