鏈路預(yù)測下能源供應(yīng)鏈網(wǎng)絡(luò)合作演化機(jī)制研究

張學(xué)龍，王軍進(jìn)

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

鏈路預(yù)測下能源供應(yīng)鏈網(wǎng)絡(luò)合作演化機(jī)制研究

張學(xué)龍，王軍進(jìn)

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

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

供應(yīng)鏈網(wǎng)絡(luò)；合作演化；鏈路預(yù)測；網(wǎng)絡(luò)結(jié)構(gòu)；能源供應(yīng)鏈；相似性指標(biāo)；精確度；耦合

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

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

能源在我國社會發(fā)展中具有重要戰(zhàn)略地位，能源問題已成為影響經(jīng)濟(jì)發(fā)展、國家安全等重大戰(zhàn)略性問題。能源供應(yīng)鏈?zhǔn)怯啥嗔鞒?能源供應(yīng)、加工、配送等)、多部門(生產(chǎn)部門、運(yùn)輸部門等)、多資源(人力、物力、技術(shù)等)要素構(gòu)成的開放系統(tǒng)，節(jié)點(diǎn)企業(yè)的協(xié)調(diào)和合作影響整個供應(yīng)鏈的運(yùn)營效率。自然災(zāi)害可導(dǎo)致煤電能源供應(yīng)鏈脫節(jié)，重要電路供電中斷。能源供應(yīng)鏈斷鏈的背后，映射出我國能源供應(yīng)鏈各個環(huán)節(jié)需要進(jìn)行整體規(guī)劃，實(shí)現(xiàn)相互協(xié)調(diào)與合作。因此，對于現(xiàn)實(shí)中的能源供應(yīng)鏈的合作演化機(jī)制有必要進(jìn)行深入研究。

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

1 問題描述與評價指標(biāo)

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

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

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

AUC=(M+0.5Z)/n

(1)

假設(shè)所有分?jǐn)?shù)都是隨機(jī)產(chǎn)生的，因此AUC≈0.5，當(dāng)AUC≥0.5時，大于的程度衡量了算法在多大程度上比隨機(jī)選擇的方法要精確。為了進(jìn)一步說明AUC指標(biāo)的含義，假設(shè)由5個節(jié)點(diǎn)構(gòu)成的能源供應(yīng)鏈網(wǎng)絡(luò)，其結(jié)構(gòu)圖如圖1所示。

圖1 5個節(jié)點(diǎn)能源供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 Network structure of five node energy supply chains

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

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

2 能源供應(yīng)鏈網(wǎng)絡(luò)合作演化分析

本文運(yùn)用鏈路預(yù)測對能源供應(yīng)鏈合作演化進(jìn)行研究，將能源供應(yīng)鏈網(wǎng)絡(luò)中節(jié)點(diǎn)內(nèi)外部信息量化，對量化后的數(shù)據(jù)進(jìn)行劃分，再利用相似性指標(biāo)對預(yù)測進(jìn)行得分，最后使用AUC評價指標(biāo)對預(yù)測的精確性進(jìn)行對比分析。

2.1 能源供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)

一個簡單無向無權(quán)網(wǎng)絡(luò)，由點(diǎn)和邊構(gòu)成，需要滿足以下4個條件：

1)節(jié)點(diǎn)自身不可以與自身連接；

2)節(jié)點(diǎn)間最多只有一條連線，不可出現(xiàn)多條連邊；

3)連邊不具有方向性；

4)連邊只代表節(jié)點(diǎn)間關(guān)系，代表的是合作的關(guān)系，沒有對應(yīng)的權(quán)重。

本文分析的能源供應(yīng)鏈由20個節(jié)點(diǎn)企業(yè)構(gòu)成，將其分別編號為1,2,…,20，其節(jié)點(diǎn)鏈接表示其長期合作情況，如表1所示。

表1 各節(jié)點(diǎn)企業(yè)合作連接情況

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

1)傳統(tǒng)的供應(yīng)鏈管理是按照上下游關(guān)系將供應(yīng)鏈中企業(yè)分為制造商、分銷商、零售商等，而本文研究不考慮企業(yè)的類型，只是將企業(yè)作為網(wǎng)絡(luò)中的一個節(jié)點(diǎn)；其次，一般供應(yīng)鏈的末端都是消費(fèi)者，為了方便統(tǒng)計(jì)，將零售商作為整個網(wǎng)絡(luò)的邊界點(diǎn)；

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

3)將供應(yīng)鏈企業(yè)合作關(guān)系抽象為無向網(wǎng)絡(luò)，忽略企業(yè)間上下游的關(guān)系，默認(rèn)企業(yè)間的傳遞信息是對稱的，所以沒有對邊進(jìn)行賦值。

2.2 基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的指標(biāo)

利用節(jié)點(diǎn)間的相似性進(jìn)行鏈路預(yù)測時，兩個節(jié)點(diǎn)之間相似性越大，它們之間存在鏈接的可能性就會越大。相似性也為一種接近的程度。基于網(wǎng)絡(luò)結(jié)構(gòu)相似性可分為基于局部信息的相似性、基于路徑的相似性和基于隨機(jī)游走的相似性。

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

(2)

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

(3)

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

(4)

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

Katz指標(biāo)考慮了網(wǎng)絡(luò)的所有路徑，其定義為

(5)

式中：(Ai)xy表示連接節(jié)點(diǎn)vx和vy之間長度為i的路徑數(shù)。由式(5)可知，當(dāng)可調(diào)參數(shù)α很小時，高階路徑的貢獻(xiàn)也很小，使得Katz指標(biāo)的預(yù)測效果接近于LP指標(biāo)。

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

(6)

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

(7)

式中：πxy為節(jié)點(diǎn)vx出發(fā)的粒子最終有多少概率走到節(jié)點(diǎn)vy，由此定義RWR相似性為

(8)

2.3 相似性算法精確度分析

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

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

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

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

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重啟的隨機(jī)游走(RWR)0．79520．0071

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

(9)

式中：sRWR是基于RWR指標(biāo)，sQT是基于其他4種結(jié)構(gòu)性指標(biāo)，參數(shù)x∈[0,1]，當(dāng)x=1時，算法回歸到sRWR，當(dāng)x=0時，算法回歸到sQT。

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

參數(shù)x的區(qū)間為[0.1,0.95]，步長為0.05，分別計(jì)算4種耦合指標(biāo)算法的精確度結(jié)果如表3。

表3 耦合后精確度計(jì)算結(jié)果

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

(a) RWR+CN

(b)RWR+PA

(c) RWR+LP

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

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

1)將RWR指標(biāo)與其他各4個指標(biāo)相互耦合后預(yù)測能源供應(yīng)鏈網(wǎng)絡(luò)鏈路合作演化效果總比單獨(dú)考慮其他4個指標(biāo)預(yù)測效果要好，同時存在最優(yōu)參數(shù)使得耦合指標(biāo)算法預(yù)測精確度要高于單獨(dú)考慮RWR指標(biāo)。

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

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

為了更為清晰地進(jìn)一步觀察3種耦合算法的預(yù)測效果，總結(jié)表3和圖2中數(shù)據(jù)于表4中。

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

表4 耦合算法預(yù)測的精確度對比

Table 4 Accuracy comparison of prediction by coupling algorithms

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

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

上述研究結(jié)論并不說明CN指標(biāo)在能源供應(yīng)鏈網(wǎng)絡(luò)預(yù)測合作連邊中不重要，文獻(xiàn)[12]比較了9種基于共同鄰居的局部接近性算法，結(jié)果顯示CN指標(biāo)表現(xiàn)較好，而且對航空網(wǎng)絡(luò)的預(yù)測比較準(zhǔn)確，AUC可達(dá)到0.9以上。本文是應(yīng)用鏈路預(yù)測方法研究能源供應(yīng)鏈網(wǎng)絡(luò)中節(jié)點(diǎn)企業(yè)合作演化機(jī)制，由于計(jì)算程序中的隨機(jī)性，因此各指標(biāo)精確度對所有供應(yīng)鏈網(wǎng)絡(luò)預(yù)測不可一概而論。

3 結(jié)論

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

1)在5種相似性指標(biāo)中，RWR指標(biāo)預(yù)測供應(yīng)鏈網(wǎng)絡(luò)合作的效果最好；

2)耦合其他4種指標(biāo)時，耦合后的預(yù)測效果會優(yōu)于單獨(dú)考慮時，達(dá)到了耦合指標(biāo)的目的；

3)RWR指標(biāo)和Katz指標(biāo)耦合效果要優(yōu)于和CN指標(biāo)、PA指標(biāo)、LP指標(biāo)耦合效果；

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

由于鏈路預(yù)測能夠計(jì)算預(yù)測方法的準(zhǔn)確度，能夠清晰直觀地利用量化結(jié)果對各種因素進(jìn)行辨別為供應(yīng)鏈網(wǎng)絡(luò)合作演化機(jī)制研究提供了分析工具和全新的視角，推動復(fù)雜網(wǎng)絡(luò)演化模型的理論研究。

為開拓鏈路預(yù)測，針對供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)的研究視角，增加供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)屬性；將結(jié)構(gòu)屬性與外部屬性相耦合等方面將是進(jìn)一步研究內(nèi)容，使得后續(xù)供應(yīng)鏈網(wǎng)絡(luò)合作演化機(jī)制研究更加全面和更具有深度。

[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]劉宏鯤, 呂琳媛, 周濤. 利用鏈路預(yù)測推斷網(wǎng)絡(luò)演化機(jī)制[J]. 中國科學(xué): 物理學(xué) 力學(xué) 天文學(xué), 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]呂琳媛. 復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測[J]. 電子科技大學(xué)學(xué)報, 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.

張學(xué)龍，男，1978年生，副教授，博士，主要研究方向?yàn)楣?yīng)鏈管理、工業(yè)工程、決策分析。

王軍進(jìn)，男，1990年生，碩士研究生，主要研究方向?yàn)楣?yīng)鏈管理。

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.

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

王軍進(jìn). 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

張學(xué)龍，王軍進(jìn). 鏈路預(yù)測下能源供應(yīng)鏈網(wǎng)絡(luò)合作演化機(jī)制研究[J]. 智能系統(tǒng)學(xué)報， 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.