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

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

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

鏈路預(yù)測(cè)下能源供應(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ù)測(cè)未產(chǎn)生鏈接的節(jié)點(diǎn)企業(yè)合作的可能性是鏈路預(yù)測(cè)應(yīng)用供應(yīng)鏈網(wǎng)絡(luò)合作演化分析的關(guān)鍵，利用鏈路預(yù)測(cè)的理論框架和評(píng)價(jià)方法，借助5種相似性指標(biāo)對(duì)能源供應(yīng)鏈網(wǎng)絡(luò)合作連邊演化進(jìn)行預(yù)測(cè)。研究結(jié)果表明：當(dāng)使用供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)屬性作為單一相似性指標(biāo)時(shí)，RWR指標(biāo)的預(yù)測(cè)效果最好；耦合指標(biāo)預(yù)測(cè)精確度要比單獨(dú)考慮單一指標(biāo)時(shí)有顯著提高；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ù)測(cè)在分析供應(yīng)鏈網(wǎng)絡(luò)合作演化機(jī)制上更為有效。

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

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

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

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

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

1 問(wèn)題描述與評(píng)價(jià)指標(biāo)

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

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

衡量鏈路預(yù)測(cè)算法精確度的指標(biāo)主要有AU、Precision和RankingScore。這3個(gè)指標(biāo)對(duì)預(yù)測(cè)精確度衡量的側(cè)重點(diǎn)不同，其中AUC是最常見(jiàn)的一種衡量指標(biāo)，它從整體上衡量算法的精確度[20]；Precision只考慮排在前L位的邊是否預(yù)測(cè)準(zhǔn)確[21]；而RankingScore則更多考慮了所預(yù)測(cè)邊的排序[22]。文中選擇的衡量算法精確度的指標(biāo)為AUC，AUC是在EP中隨機(jī)選擇一條邊的分?jǐn)?shù)值比隨機(jī)選擇的一條不存在的邊的分?jǐn)?shù)值高的概率[23]。每次隨機(jī)從EP中選一條邊，再?gòu)腏中隨機(jī)選擇一條邊，若EP中選擇邊的分?jǐn)?shù)值大于J中選擇邊的分?jǐn)?shù)，那么就加1分；若兩個(gè)分?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時(shí)，大于的程度衡量了算法在多大程度上比隨機(jī)選擇的方法要精確。為了進(jìn)一步說(shuō)明AUC指標(biāo)的含義，假設(shè)由5個(gè)節(jié)點(diǎn)構(gòu)成的能源供應(yīng)鏈網(wǎng)絡(luò)，其結(jié)構(gòu)圖如圖1所示。

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

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

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

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

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

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

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

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

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

3)連邊不具有方向性；

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

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

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

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

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

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

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

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

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

基于局部信息的最簡(jiǎn)單的相似性指標(biāo)是共同鄰居的相似性指標(biāo)CN[24](common neighbors)，又稱(chēng)為結(jié)構(gòu)等價(jià)(structural equivalence)，即兩個(gè)節(jié)點(diǎn)如果有很多的共同鄰居節(jié)點(diǎn)，那么這兩個(gè)節(jié)點(diǎn)相似。在鏈路預(yù)測(cè)中應(yīng)用CN指標(biāo)的基本假設(shè)是兩個(gè)未鏈接的節(jié)點(diǎn)如果有更多的共同鄰居，則它們更傾向于連邊。CN指標(biāo)是對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)vx，定義其鄰居集合為Γ(x)，則兩個(gè)節(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的概率正比于兩個(gè)節(jié)點(diǎn)度的乘積。由此兩個(gè)節(jié)點(diǎn)間的偏好連接相似性定義為

(3)

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

(4)

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

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

(5)

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

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

(6)

式中：ex表示一個(gè)一維列向量且僅有第x個(gè)元素為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)(沒(méi)有單獨(dú)的點(diǎn))，而20個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)在理論上的鏈接邊數(shù)為20×[(20-1)/2]=190條，當(dāng)前已知鏈接數(shù)為66，未知鏈接數(shù)為190-66=124。假設(shè)測(cè)試集比例為10%，訓(xùn)練集則為90%，對(duì)測(cè)試集和訓(xùn)練集進(jìn)行一次性劃分，在劃分的同時(shí)需要保證訓(xùn)練集的連通性。測(cè)試集中的測(cè)試邊的數(shù)目為66×10%≈7，最精確的方法是將所有的測(cè)試邊和不存在的邊都進(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值的過(guò)程類(lèi)似于伯努利實(shí)驗(yàn)，200 000次隨機(jī)抽樣的結(jié)果不相互影響，忽略比較得分相等的情況下，計(jì)算AUC值時(shí)得分為1的概率為p，則得分為0的概率為1-p。如此地進(jìn)行n次抽樣得到的AUC值為M/n，抽樣次數(shù)越多AUC值越接近p。那么，最佳的抽樣次數(shù)是能夠接受的概率無(wú)限接近于p的最小n值。設(shè)LP指標(biāo)和Katz指標(biāo)中可調(diào)參數(shù)α=0.001，RWR指標(biāo)中的粒子返回概率ρ=0.95，5種相似性算法在能源供應(yīng)鏈中預(yù)測(cè)的AUC值平均值和方差如表2所示。

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

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

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

算法名稱(chēng)精確度方差共同鄰居(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é)合，以便觀(guān)察兩種指標(biāo)耦合后預(yù)測(cè)效果好還是單獨(dú)利用相似性指標(biāo)效果好。本文設(shè)計(jì)的是：經(jīng)過(guò)計(jì)算后的精確度最高的RWR指標(biāo)與其他4種指標(biāo)分別耦合從而進(jìn)行鏈路預(yù)測(cè)，也就是將基于隨機(jī)游走的指標(biāo)與路徑相似性指標(biāo)、局部信息相似性指標(biāo)進(jìn)行耦合。采用的是最簡(jiǎn)單的線(xiàn)性方式，即

(9)

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

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

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

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

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

(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

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

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

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

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

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

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

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

Table 4 Accuracy comparison of prediction by coupling algorithms

耦合算法最優(yōu)參數(shù)精確度提高率/%(與RWR相比)提高率/%(與耦合對(duì)象相比)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ù)測(cè)精確度分別提高了9.506%、5.558%、6.300%、7.810%，有顯著提高。耦合算法提高了耦合中原本精確度較小的指標(biāo)預(yù)測(cè)的效果，其中幫助CN提高了接近10%的精確度，說(shuō)明了耦合算法達(dá)到了提高指標(biāo)在能源供應(yīng)鏈網(wǎng)絡(luò)中預(yù)測(cè)合作連邊的目的，也為鏈路預(yù)測(cè)中各類(lèi)指標(biāo)結(jié)合提高了可能性。

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

3 結(jié)論

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

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

2)耦合其他4種指標(biāo)時(shí)，耦合后的預(yù)測(cè)效果會(huì)優(yōu)于單獨(dú)考慮時(shí)，達(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)性作用，耦合對(duì)象指標(biāo)在耦合中則是不可忽略的。

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

為開(kāi)拓鏈路預(yù)測(cè)，針對(duì)供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)的研究視角，增加供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)屬性；將結(jié)構(gòu)屬性與外部屬性相耦合等方面將是進(jìn)一步研究?jī)?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ù)測(cè)推斷網(wǎng)絡(luò)演化機(jī)制[J]. 中國(guó)科學(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ù)測(cè)[J]. 電子科技大學(xué)學(xué)報(bào), 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.

國(guó)家自然科學(xué)基金項(xiàng)目(71662007)；廣西哲學(xué)社會(huì)科學(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ù)測(cè)下能源供應(yīng)鏈網(wǎng)絡(luò)合作演化機(jī)制研究[J]. 智能系統(tǒng)學(xué)報(bào)， 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.