鏈路預測下能源供應鏈網絡合作演化機制研究

張學龍，王軍進

(桂林電子科技大學 商學院，廣西 桂林 541004)

鏈路預測下能源供應鏈網絡合作演化機制研究

張學龍，王軍進

(桂林電子科技大學 商學院，廣西 桂林 541004)

應用供應鏈網絡結構或節點的屬性信息預測未產生鏈接的節點企業合作的可能性是鏈路預測應用供應鏈網絡合作演化分析的關鍵，利用鏈路預測的理論框架和評價方法，借助5種相似性指標對能源供應鏈網絡合作連邊演化進行預測。研究結果表明：當使用供應鏈網絡結構屬性作為單一相似性指標時，RWR指標的預測效果最好；耦合指標預測精確度要比單獨考慮單一指標時有顯著提高；RWR指標和Katz指標耦合效果要優于和CN指標、PA指標、LP指標耦合效果，且RWR指標在耦合算法中起到主導性作用；與直接建立網絡演化模型相比，鏈路預測在分析供應鏈網絡合作演化機制上更為有效。

供應鏈網絡；合作演化；鏈路預測；網絡結構；能源供應鏈；相似性指標；精確度；耦合

預測是所有的科學學科所不能回避的問題。鏈路預測是數據挖掘的研究方向之一，尤其在計算機領域早有較深入的研究，其研究思路主要是基于馬爾可夫鏈和機器學習[1-3]。網絡中的鏈路預測是利用已知的網絡節點以及網絡結構等信息，預測網絡中尚未產生連邊的兩個節點之間鏈接的可能性。這種預測包含了對網絡中實際上存在但尚未被探測到的鏈路預測，即“未知鏈接”預測；也包含了目前不存在和應該存在或者未來可能會存在的鏈路預測，即“未來鏈接”預測。其中，基于相似性(接近程度)的鏈路預測是網絡鏈路預測的主流方法。刻畫節點的相似性有較多方法，最簡單直接的就是利用節點的屬性，網絡中屬性相似的節點之間更容易鏈接[4]。應用節點屬性進行預測的效果良好，如劉宏鯤等[5]利用鏈路預測將結構(共同鄰居數目)和節點屬性(地理位置、人口、GDP和第三產業產值)進行耦合，研究中國城市航空網絡演化機制；O'Madadhain等[6]利用網絡的拓撲結構信息以及節點的屬性建立了一個局部的條件概率模型，應用節點屬性進行鏈路預測；Lin[7]基于節點的屬性定義了節點間的相似性，直接用定義的屬性進行鏈路預測。雖然應用節點外部信息可得到良好的預測效果，但很多情況這些信息非常難獲取，包括信息是保密的、真假難辨等，甚至無法獲得。相對于節點外部信息而言，獲取網絡內部結構信息較為容易也更加可靠。近幾年，內部結構相似性的鏈路預測方法受到越來越多的關注，包括度分布、集聚性質、社團結構、節點中心性、節點間的路徑長度等[8-10]。Liben-Nowell等[11]定義了網絡拓撲結構的相似性方法，將相似性指標分為節點和路徑，并且分析了多種指標在社會合作網絡中的預測效果。周濤等[12]用9種相似性指標對6種現實網絡進行了鏈路預測，進一步驗證了Liben-Nowell等的研究結果，并且提出了兩種精確度更高的指標：資源分配指標和局部路徑指標。Clauset等[13]分析了利用網絡的層次結構進行鏈路預測的方法，該方法在具有明顯層次結構的網絡中表現較好；Roger G等[14]提出了識別錯誤鏈路預測的方法，同時定義了網絡錯誤連邊的概念。

利用鏈路預測方法不僅在各種靜態網絡結構的研究成果眾多，從動態角度揭示網絡演化的機制、各種微觀因素對網絡結構形成的影響成果也較為豐富[15-18]。利用鏈路預測研究網絡演化機制最常用的方法是直接建立演化模型從而預測影響網絡演化的因素。例如Barabási-Albert (BA)[19]模型是基于節點度研究網絡優先連接機制，針對某些影響因素建立對象網絡并研究其統計特征，如果分析所得的統計特征具有和真實網絡接近的性質，那么這些影響因素對網絡的結構就有顯著影響，即這些因素是網絡演化的重要機制，否則認為這些影響因素對網絡結構的影響不顯著。但衡量模擬網絡與真實網絡相似度的影響因素指標可能會表現不一致，以致難以辨析哪些才是影響網絡演化的主導因素，以及這些主導因素在網絡演化過程中分別起到了多大的作用，這在一定程度上制約了演化模型的發展。

能源在我國社會發展中具有重要戰略地位，能源問題已成為影響經濟發展、國家安全等重大戰略性問題。能源供應鏈是由多流程(能源供應、加工、配送等)、多部門(生產部門、運輸部門等)、多資源(人力、物力、技術等)要素構成的開放系統，節點企業的協調和合作影響整個供應鏈的運營效率。自然災害可導致煤電能源供應鏈脫節，重要電路供電中斷。能源供應鏈斷鏈的背后，映射出我國能源供應鏈各個環節需要進行整體規劃，實現相互協調與合作。因此，對于現實中的能源供應鏈的合作演化機制有必要進行深入研究。

隨著能源供應鏈面臨的問題越來越多，供應鏈上節點企業的內外部環境越來越復雜，很多合作問題亟需解決，針對能源供應鏈合作演化，本文提供了一個全新的視角，即利用鏈路預測研究能源供應鏈合作演化機制問題。在分析鏈路預測法和評價指標的基礎上，對能源供應鏈進行實證分析，將供應鏈似然成網絡，在供應鏈網絡中選取5個可以代表能源供應鏈的網絡結構相似性指標，通過計算5種相似性指標的精確度，清晰直觀地對各指標預測精確度進行辨別，找到最佳的預測指標，并將最佳指標和其他4種指標耦合，運用耦合指標算法更加精確地預測“未知鏈接”和“未來鏈接”，為挖掘能源供應鏈合作演化機制的重要驅動因素模型和公平評價模型優劣提供了可能性，鏈路預測在分析供應鏈網絡演化機制上提供了科學的量化方法。

1 問題描述與評價指標

國民生產和生活需要消耗大量的能源，每個節點企業協調一致保障著整個供應鏈的高效運營，一旦供應鏈發生問題，小則導致局部癱瘓，大則引起社會動蕩。上游企業(如煤炭、電力企業)和下游企業(如鋼鐵企業)不僅是供求關系，同時也是一個整體，節點企業之間相互制約和相互合作。供應鏈中的合作是相互合作，不存在方向性，因此可將能源供應鏈節點企業之間的合作關系描述為一個完整無向網絡，節點之間的連線代表企業間合作關系，利用無向網絡一些特征和鏈路預測對其進行合作演化研究。

為了測試相似性指標預測的準確性，一般將已知的連邊E分為兩個部分：訓練集ET和測試集EP。顯然，E=ET∪EP，ET∩EP=?。在此，將屬于U但不屬于E的邊稱為不存在的邊，稱為J，屬于U但不屬于ET的邊為未知邊，稱為H。

衡量鏈路預測算法精確度的指標主要有AU、Precision和RankingScore。這3個指標對預測精確度衡量的側重點不同，其中AUC是最常見的一種衡量指標，它從整體上衡量算法的精確度[20]；Precision只考慮排在前L位的邊是否預測準確[21]；而RankingScore則更多考慮了所預測邊的排序[22]。文中選擇的衡量算法精確度的指標為AUC，AUC是在EP中隨機選擇一條邊的分數值比隨機選擇的一條不存在的邊的分數值高的概率[23]。每次隨機從EP中選一條邊，再從J中隨機選擇一條邊，若EP中選擇邊的分數值大于J中選擇邊的分數，那么就加1分；若兩個分數值相等就加0.5分；若小于就不加分。這樣獨立比較n次，如果有M次EP中的邊分數值大于J分數值，有Z次兩分數值相等，AUC的計算式如式(1)所示。

AUC=(M+0.5Z)/n

(1)

假設所有分數都是隨機產生的，因此AUC≈0.5，當AUC≥0.5時，大于的程度衡量了算法在多大程度上比隨機選擇的方法要精確。為了進一步說明AUC指標的含義，假設由5個節點構成的能源供應鏈網絡，其結構圖如圖1所示。

圖1 5個節點能源供應鏈網絡結構Fig.1 Network structure of five node energy supply chains

圖1表示一個完整的供應鏈網絡結構，實線表示訓練集，虛線表示測試集。該網絡中包含5個節點，該網絡在理論上存在的連邊數是5×(5-1)/2=10，其中7條是已知的，剩下3條為不存在的邊。為了驗證鏈路預測算法的精確性，需要在7條已知邊中選擇部分構成EP，假如選擇邊{2,4}和{2,5}作為測試邊，如圖1(b)所示，則剩下的5條已知邊則構成ET。在鏈路預測方法中，只應用ET中邊的信息，上述中的EP中的邊僅是隨機從已知邊中選取的，若再進行下一次驗證精確性選擇，則測試邊不一定是{2,4}和{2,5}，而是ET中的任何邊都可能被選出作為測試邊，ET中的邊只是暫時被“待定”。根據鏈路預測算法得到剩下5條未知邊的得分值分別為s25=4，s24=4.5，s14=3.8，s34=4.6，s35=4，那么在計算AUC時需將未知邊按照其得分排序：s14

由此可以說明，當選擇EP中的邊個數發生變化時，AUC值會相應地變化，即使EP完全相同時，AUC值也會不同。因為AUC計算公式中的n是抽樣次數，抽樣方式有多種類型，如隨機抽樣、逐項遍歷、滾雪球抽樣等，由5個節點構成的能源供應鏈中n=6，其含義是測試邊和不存在的邊比較了6次。而在文中利用計算機程序計算AUC值時，比較的邊(預測邊和不存在邊的比較)是隨機抽取的，因此即便EP中信息完全一樣，抽樣次數和抽樣比較對象不同導致AUC值變化，為了使得到的AUC越接近真實值，抽樣次數n越大越好。

2 能源供應鏈網絡合作演化分析

本文運用鏈路預測對能源供應鏈合作演化進行研究，將能源供應鏈網絡中節點內外部信息量化，對量化后的數據進行劃分，再利用相似性指標對預測進行得分，最后使用AUC評價指標對預測的精確性進行對比分析。

2.1 能源供應鏈網絡結構

一個簡單無向無權網絡，由點和邊構成，需要滿足以下4個條件：

1)節點自身不可以與自身連接；

2)節點間最多只有一條連線，不可出現多條連邊；

3)連邊不具有方向性；

4)連邊只代表節點間關系，代表的是合作的關系，沒有對應的權重。

本文分析的能源供應鏈由20個節點企業構成，將其分別編號為1,2,…,20，其節點鏈接表示其長期合作情況，如表1所示。

表1 各節點企業合作連接情況

由表1中所示的節點企業的合作情況，將其合作轉化成連邊。在使用計算機分析時，用鄰居矩陣來刻畫網絡，假設能源供應鏈網絡的鄰居矩陣為A，由上表可知A是一個20×20的方陣，如果節點vx、vy有合作關系，那么A的第x行y列上的元素就為1，否則為0。為了方便研究，在滿足構建條件的同時，作出如下假設：

1)傳統的供應鏈管理是按照上下游關系將供應鏈中企業分為制造商、分銷商、零售商等，而本文研究不考慮企業的類型，只是將企業作為網絡中的一個節點；其次，一般供應鏈的末端都是消費者，為了方便統計，將零售商作為整個網絡的邊界點；

2)企業間有相互的合作關系，則彼此之間存在一條連線，合作是指長期的合作，短期的或者偶爾的合作將不作為連線標準，同時認為合作是相互的，不考慮連邊的方向性；

3)將供應鏈企業合作關系抽象為無向網絡，忽略企業間上下游的關系，默認企業間的傳遞信息是對稱的，所以沒有對邊進行賦值。

2.2 基于網絡結構相似性的指標

利用節點間的相似性進行鏈路預測時，兩個節點之間相似性越大，它們之間存在鏈接的可能性就會越大。相似性也為一種接近的程度。基于網絡結構相似性可分為基于局部信息的相似性、基于路徑的相似性和基于隨機游走的相似性。

基于局部信息的最簡單的相似性指標是共同鄰居的相似性指標CN[24](common neighbors)，又稱為結構等價(structural equivalence)，即兩個節點如果有很多的共同鄰居節點，那么這兩個節點相似。在鏈路預測中應用CN指標的基本假設是兩個未鏈接的節點如果有更多的共同鄰居，則它們更傾向于連邊。CN指標是對于網絡中的節點vx，定義其鄰居集合為Γ(x)，則兩個節點vx和vy的相似性就定義為兩者共同的鄰居數，即

(2)

局部信息相似性指標除了共同鄰居的相似性指標以外，還有基于偏好連接相似性[25](PA)指標。偏好連接是指優先連接，即一條新邊連接到節點vx的概率正比于該節點的度kx的大小。新鏈接節點vx和vy的概率正比于兩個節點度的乘積。由此兩個節點間的偏好連接相似性定義為

(3)

局部信息的相似性指標的優勢就在于計算復雜度較低，但是由于利用信息有限，預測精度受到了限制。周濤等[26]在共同鄰居的基礎上考慮三階路徑的因素，提出了基于局部路徑相似性指標(localpath，LP)。其定義為

(4)

式中：α為可調參數，A表示網絡的鄰接矩陣，(A3)xy表示節點vx和vy之間的長度為3的路徑數目。當α=0時，LP指標退化為CN指標。CN指標本質上是考慮了二階路徑數目，當然LP指標也可以擴展到為更高階形式，但是當階數無窮大的時候，LP就會相當于考慮網絡全部路徑的Katz指標[27]。

Katz指標考慮了網絡的所有路徑，其定義為

(5)

式中：(Ai)xy表示連接節點vx和vy之間長度為i的路徑數。由式(5)可知，當可調參數α很小時，高階路徑的貢獻也很小，使得Katz指標的預測效果接近于LP指標。

有相當數量的相似性指標是基于隨機游走的，譬如有重啟的隨機游走指標[28](Randomwalkwithrestart，RWR)。RWR指標假設隨機游走粒子在每走一步的時候都以一定概率返回初始位置。設粒子返回概率為ρ，P為網絡概率返回矩陣，其元素Pixy=axy/kx表示節點vx處的粒子下一步到節點vy的概率，如果兩者相連axy=1，否則axy=0。某粒子初始時刻在節點vx處，那么t+1時刻該粒子到達網絡每個節點概率向量為

(6)

式中：ex表示一個一維列向量且僅有第x個元素為1，其他元素都為0。不難得到式(6)的穩定解為

(7)

式中：πxy為節點vx出發的粒子最終有多少概率走到節點vy，由此定義RWR相似性為

(8)

2.3 相似性算法精確度分析

表1中所示該能源供應鏈共66條連邊，不存在自環(沒有單獨的點)，而20個節點的網絡在理論上的鏈接邊數為20×[(20-1)/2]=190條，當前已知鏈接數為66，未知鏈接數為190-66=124。假設測試集比例為10%，訓練集則為90%，對測試集和訓練集進行一次性劃分，在劃分的同時需要保證訓練集的連通性。測試集中的測試邊的數目為66×10%≈7，最精確的方法是將所有的測試邊和不存在的邊都進行比較，共有比較次數為7×124=868次，因為計算機程序代碼設計的是隨機抽樣，為了使得AUC盡可能接近真實值，本文采取抽樣次數為200 000次，并進行200次獨立實驗，計算出的AUC值等于200 000次抽樣200次獨立實驗的平均數。

計算AUC值的過程類似于伯努利實驗，200 000次隨機抽樣的結果不相互影響，忽略比較得分相等的情況下，計算AUC值時得分為1的概率為p，則得分為0的概率為1-p。如此地進行n次抽樣得到的AUC值為M/n，抽樣次數越多AUC值越接近p。那么，最佳的抽樣次數是能夠接受的概率無限接近于p的最小n值。設LP指標和Katz指標中可調參數α=0.001，RWR指標中的粒子返回概率ρ=0.95，5種相似性算法在能源供應鏈中預測的AUC值平均值和方差如表2所示。

由表2看出，當單獨以5種指標作為相似性算法時，RWR指標的精確度AUC為0.795 2是最高的，說明通過RWR指標進行能源供應鏈節點企業合作預測更符合網絡特征，對于合作演化的機制具有較高的精確性，而且平均方差σ=0.007 1，在5種指標中也是最小的，意味著200組獨立實驗計算的AUC值波動幅度最小，提高了實驗的準確性和可靠性；利用路徑相似指標的LP指標預測效果好于Katz指標，也就是在該能源供應鏈網絡中考慮局部路徑的效果明顯好于考慮全部路徑，其中LP指標預測效果也是5組指標中精確度第2的指標；基于局部信息相似指標的PA指標預測的精確度大于CN指標的精確度，但是PA指標的實驗數據方差較大，也就是再次進行實驗時可能導致PA指標平均精確度值變化較大；CN指標預在能源供應鏈中預測合作的效果最差，和其他4個指標相比，精確度之差相差甚大。在此特別說明的是，表2中精確度的平均值并不是絕對的，也就是說，假如再一次進行200組獨立實驗時，計算的結果可能會發生改變，但是通過各自方差可知變化浮動不會太大。

表2 5種相似性算法預測精確度和方差

Table 2 The prediction accuracy and variance of five kinds of similarity algorithms

算法名稱精確度方差共同鄰居(CN)0．73740．0093偏好連接(PA)0．75930．0104局部路徑(LP)0．76030．0090全部路徑(Katz)0．74650．0095重啟的隨機游走(RWR)0．79520．0071

為了豐富算法的選擇，將5種指標算法進行相互結合，以便觀察兩種指標耦合后預測效果好還是單獨利用相似性指標效果好。本文設計的是：經過計算后的精確度最高的RWR指標與其他4種指標分別耦合從而進行鏈路預測，也就是將基于隨機游走的指標與路徑相似性指標、局部信息相似性指標進行耦合。采用的是最簡單的線性方式，即

(9)

式中：sRWR是基于RWR指標，sQT是基于其他4種結構性指標，參數x∈[0,1]，當x=1時，算法回歸到sRWR，當x=0時，算法回歸到sQT。

式(9)中實際上是對計算機程序中指標算法的得分進行重新計算，為了統一標準，將每種相似性指標得分值作歸一化處理，即每組數據都除以組別數據中的最大值。值得注意的是，所有算法最后的鏈接邊的得分都是在訓練集的基礎上計算出來的，也就是在訓練集和測試集劃分后，原網絡的鏈接情況就是去掉測試集中的邊剩下訓練集的邊，測試集中邊和不存在鏈接一樣不存在了，預測的時候只可以應用訓練集中的信息。

參數x的區間為[0.1,0.95]，步長為0.05，分別計算4種耦合指標算法的精確度結果如表3。

表3 耦合后精確度計算結果

根據表3數據，確定耦合后算法精確度變化趨勢如圖2所示。圖3展現了4種耦合算法隨著參數x變化，預測精確度的變化情況。

(a) RWR+CN

(b)RWR+PA

(c) RWR+LP

(d)RWR+Katz 圖2 耦合算法精確度隨著參數的變化情況Fig.2 The accuracy of coupling algorithms change with the parameter

對比圖2(a)～2(d)，可以得出：

1)將RWR指標與其他各4個指標相互耦合后預測能源供應鏈網絡鏈路合作演化效果總比單獨考慮其他4個指標預測效果要好，同時存在最優參數使得耦合指標算法預測精確度要高于單獨考慮RWR指標。

2)觀察圖2(b)和圖2(c)可知，RWR指標分別耦合PA指標、LP指標后精確度變化趨勢幾乎是相同的，在單獨考慮PA指標、LP指標時，其精確度就幾乎相等，因此可以認為在能源供應鏈網絡鏈路合作預測時，PA指標和LP指標是等價的，預測效果是相近的。

3)當RWR+Katz耦合后，其精確度在單獨考慮RWR指標時的精確度上下波動，而RWR與其他3個指標耦合精確度都有隨著參數的增大而增大的趨勢，也就是說，RWR+Katz耦合效果明顯優于RWR指標與其他3個指標。

為了更為清晰地進一步觀察3種耦合算法的預測效果，總結表3和圖2中數據于表4中。

從表4預測精度對比得出，耦合算法的最優精確度都比5種單獨指標精確度要高，但耦合算法只比利用RWR指標預測的精確度略微提高，分別提高了1.547%、0.792%、1.300%、1.207%。同時最優參數x*分別為0.95、0.85，說明了RWR指標在耦合算法中起到了決定性作用，對節點企業合作連邊產生了較大的作用。盡管相比RWR指標耦合算法精確度提高不是很明顯，但是不可以忽略耦合對象指標在耦合算法所起到的作用。

表4 耦合算法預測的精確度對比

Table 4 Accuracy comparison of prediction by coupling algorithms

耦合算法最優參數精確度提高率/%(與RWR相比)提高率/%(與耦合對象相比)RWR+CN0．950．80751．5479．506RWR+PA0．850．80150．7925．558RWR+LP0．850．80821．3006．300RWR+Katz0．850．80481．2077．810

相比單獨考慮其他4種指標，預測精確度分別提高了9.506%、5.558%、6.300%、7.810%，有顯著提高。耦合算法提高了耦合中原本精確度較小的指標預測的效果，其中幫助CN提高了接近10%的精確度，說明了耦合算法達到了提高指標在能源供應鏈網絡中預測合作連邊的目的，也為鏈路預測中各類指標結合提高了可能性。

上述研究結論并不說明CN指標在能源供應鏈網絡預測合作連邊中不重要，文獻[12]比較了9種基于共同鄰居的局部接近性算法，結果顯示CN指標表現較好，而且對航空網絡的預測比較準確，AUC可達到0.9以上。本文是應用鏈路預測方法研究能源供應鏈網絡中節點企業合作演化機制，由于計算程序中的隨機性，因此各指標精確度對所有供應鏈網絡預測不可一概而論。

3 結論

能源供應鏈的合作問題凸顯出合作演化機制研究的重要性，一般研究能源供應鏈網絡合作演化機制的常用方法直接應用演化模型來推測影響供應鏈網絡合作演化的因素，但由于可比較的結構特征量太多，不同的模型之間難以進行定量地比較，而鏈路預測方法推測網絡演化的機制規避了傳統方法的缺陷。本文應用基于網絡結構的鏈路預測方法，研究能源供應鏈網絡合作演化機制，研究結果表明：

1)在5種相似性指標中，RWR指標預測供應鏈網絡合作的效果最好；

2)耦合其他4種指標時，耦合后的預測效果會優于單獨考慮時，達到了耦合指標的目的；

3)RWR指標和Katz指標耦合效果要優于和CN指標、PA指標、LP指標耦合效果；

4)RWR指標在耦合算法中起到主導性作用，耦合對象指標在耦合中則是不可忽略的。

由于鏈路預測能夠計算預測方法的準確度，能夠清晰直觀地利用量化結果對各種因素進行辨別為供應鏈網絡合作演化機制研究提供了分析工具和全新的視角，推動復雜網絡演化模型的理論研究。

為開拓鏈路預測，針對供應鏈網絡結構的研究視角，增加供應鏈網絡結構屬性；將結構屬性與外部屬性相耦合等方面將是進一步研究內容，使得后續供應鏈網絡合作演化機制研究更加全面和更具有深度。

[1]SARUKKAI R R. Link prediction and path analysis using Markov chains[J]. Computer networks, 2000, 33(1/2/3/4/5/6): 377-386.

[2]ZHU Jianhan, HONG Jun, HUGHES J G. Using Markov chains for link prediction in adaptive web sites[M]//BUSTARD D, LIU Weiru, STERRITT R. Soft-Ware 2002: Computing in An Imperfect World. Berlin Heidelberg: Springer, 2002: 60-73.

[3]POPESCUL A, UNGAR L H. Statistical relational learning for link prediction[C]//Proceedings of Workshop on Learning Statistical Models from Relational Data. New York: ACM Press, 2003: 81-87.

[4]KOLACZYK E E. Some implications of path-based sampling on the Internet[C]//Proceedings of a Workshop on Statistics of Networks. Washington: National Academies Press, 2007: 207-226.

[5]劉宏鯤, 呂琳媛, 周濤. 利用鏈路預測推斷網絡演化機制[J]. 中國科學: 物理學 力學 天文學, 2011, 41(7): 816-823. LIU Hongkun, LYU Linyuan, ZHOU Tao. Uncovering the network evolution mechanism by link prediction[J]. Scientia sinica: physica, mechanica & astronomica, 2011, 41(7): 816-823.

[6]O'MADADHAIN J, HUTCHINS J, SMYTH P. Prediction and ranking algorithms for event-based network data[J]. ACM SIGKDD explorations newsletter, 2005, 7(2): 23-30.

[7]LIN Dekang. An information-theoretic definition of Similarity[C]//Proceedings of the Fifteenth International Conference on Machine Learning. San Francisco: Morgan Kaufmann Publishers, 1998: 296-304.

[8]呂琳媛. 復雜網絡鏈路預測[J]. 電子科技大學學報, 2010, 39(5): 651-661. Lü Linyuan. Link prediction on complex networks[J]. Journal of university of electronic science and technology of China, 2010, 39(5): 651-661.

[9]Lü Linyuan, ZHOU Tao. Link prediction in complex networks: a survey[J]. Physica A: statistical mechanics and its applications, 2011, 390(6): 1150-1170.

[10]GETOOR L, DIEHL C P. Link mining: a survey[J]. ACM SIGKDD explorations newsletter, 2005, 7(2): 3-12.

[11]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.

[12]ZHOU Tao, Lü Linyuan, ZHANG Yicheng. Predicting missing links via local information[J]. The European physical journal B, 2009, 71(4): 623-630.

[13]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.

[14]GUIMERà R, SALES-PARDO M. Missing and spurious interactions and the reconstruction of complex networks[J]. Proceedings of the national academy of sciences of the United States of America, 2009, 106(52): 22073-22078.

[15]ADAMIC L A, HUBERMAN B A. Power-law distribution of the world wide web[J]. Science, 2000, 287(5461): 2115.

[16]NEWMAN M E J. The structure of scientific collaboration networks[J]. Proceedings of the national academy of sciences of the United States of America, 2001, 98(2): 404-409.

[17]ALBERT R, BARABáSI A L. Statistical mechanics of complex networks[J]. Reviews of modern physics, 2002, 74(1): 47-97.

[18]DOROGOVTSEV S N, MENDES J F F. Evolution of networks[J]. Advances in physics, 2002, 51(4): 1079-1187.

[19]BARABáSI A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.

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

[21] HERLOCKER J L, KONSTAN J A, TERVEEN L G, et al. Evaluating collaborative filtering recommender systems[J]. ACM transactions on information systems, 2004, 22(1): 5-53.

[22]ZHOU Tao, REN Jie, MEDO M, et al. Bipartite network projection and personal recommendation[J]. Physical review E, 2007, 76(4): 046115.

[23]FAWCETT T. An introduction to ROC analysis[J]. Pattern recognition letters, 2006, 27(8): 861-874.

[24]LORRAIN F, WHITE H C. Structural equivalence of individuals in social networks[J]. The journal of mathematical sociology, 1971, 1(1): 49-80.

[25]XIE Yanbo, ZHOU Tao, WANG Binghong. Scale-free networks without growth[J]. Physica A: statistical mechanics and its applications, 2008, 387(7): 1683-1688.

[26]Lü Linyuan, JIN Cihang, ZHOU Tao. Similarity index based on local paths for link prediction of complex networks[J]. Physical review E, 2009, 80(4): 046122.

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

[28]BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer networks and ISDN systems, 1998, 30(1): 107-117.

張學龍，男，1978年生，副教授，博士，主要研究方向為供應鏈管理、工業工程、決策分析。

王軍進，男，1990年生，碩士研究生，主要研究方向為供應鏈管理。

On the evolution cooperation mechanism of energysupply chain networks under link prediction

ZHANG Xuelong， WANG Junjin

(School of Business, Guilin University of Electronic Technology, Guilin 541004, China)

Using attribute information of a given network structure or nodes of a supply chain to predict the possibility of cooperation with an unlinked enterprise is key to link prediction being applied to supply chain networks. As such, we predicted side-connected evolutions of network cooperation in energy supply chains by utilizing a theoretical framework and evaluation method for link prediction and five similarity indexes. Our results show that when the attribute of the network structure of a supply chain is used as a single similarity index, the predictive effect of the RWR index is the best. Further, the prediction accuracy of the coupling index is remarkably higher than the single index. Here, the coupling effect between the RWR index and the Katz index is superior to the coupling effects between RWR and CN, PA and LP index. Further, the RWR index plays a leading role in the coupling algorithm. Compared with directly setting up a model for network evolution, link prediction is more effective in analyzing the cooperation evolution mechanism of supply chain networks.

supply chain network; cooperation evolution; link prediction; network structure; energy supply chain; similarity index; accuracy; coupling

2016-05-03.

日期：2017-01-11.

國家自然科學基金項目(71662007)；廣西哲學社會科學研究課題(15BJY016)；桂林電子科技大學研究生教育創新計劃項目(2016YJCX61).

王軍進. E-mail：1204703207@qq.com.

10.11992/tis.201605003

http://www.cnki.net/kcms/detail/23.1538.tp.20170111.1705.018.html

TP391；F273

A

1673-4785(2017)02-0221-08

張學龍，王軍進. 鏈路預測下能源供應鏈網絡合作演化機制研究[J]. 智能系統學報， 2017, 12(2): 221-228.

英文引用格式：ZHANG Xuelong， WANG Junjin. On the evolution cooperation mechanism of energy supply chain networks under link prediction[J]. CAAI transactions on intelligent systems, 2017, 12(2): 221-228.