張 璐， 蔡皖東， 彭 冬

(1. 西安市煙草專賣局 信息中心，陜西 西安 710061；2. 西北工業(yè)大學(xué) 計算機學(xué)院，陜西 西安 710072)

隨著制造網(wǎng)格及Web技術(shù)的發(fā)展，協(xié)同制造領(lǐng)域出現(xiàn)了一些新的網(wǎng)絡(luò)應(yīng)用，如利用Web技術(shù)將專網(wǎng)中的制造節(jié)點的交互進一步擴展到基于互聯(lián)網(wǎng)的交互．將制造節(jié)點的工作狀態(tài)信息通過互聯(lián)網(wǎng)絡(luò)進行交互，使遠程的制造節(jié)點實時交互信息及協(xié)同工作，顯現(xiàn)出越來越大的價值和影響力[1-3]．

信息物理融合系統(tǒng)(Cyber-Physical Systems，CPS)是一個綜合計算、網(wǎng)絡(luò)和物理環(huán)境的多維復(fù)雜系統(tǒng)，通過3C(Computation、Communication、Control)技術(shù)的有機融合與深度協(xié)作，實現(xiàn)大型工程系統(tǒng)的實時感知、動態(tài)控制和信息服務(wù)．基于廣域網(wǎng)的制造網(wǎng)格也是一種信息物理融合系統(tǒng)，網(wǎng)格中參與計算的不同制造節(jié)點可將自身的工作狀態(tài)信息在互聯(lián)網(wǎng)中進行發(fā)布，并可實時地更新自身的狀態(tài)信息．同時，也可以調(diào)用其他制造節(jié)點的工作狀態(tài)信息以實現(xiàn)制造設(shè)備之間的高效協(xié)同控制．在制造網(wǎng)格中，狀態(tài)信息的交互傳播過程中，狀態(tài)匯聚代理發(fā)揮了重要的作用．局部狀態(tài)在狀態(tài)匯聚代理的影響下演化為網(wǎng)絡(luò)制造狀態(tài)．狀態(tài)匯聚代理是指制造網(wǎng)格在協(xié)同制造過程中經(jīng)常為其他節(jié)點提供信息并施加影響的“重要節(jié)點”，它們在制造網(wǎng)格的網(wǎng)絡(luò)制造狀態(tài)形成過程中起著重要的作用，由它們將制造網(wǎng)格協(xié)同制造過程中的協(xié)同信息擴散給受眾節(jié)點，形成信息傳遞的兩級傳播[1]．隨著制造網(wǎng)格協(xié)同程度的不斷深入，人們對制造網(wǎng)格中狀態(tài)匯聚代理的研究也在不斷地深入．

統(tǒng)計數(shù)據(jù)顯示，制造網(wǎng)格的現(xiàn)實應(yīng)用中大部分用戶節(jié)點不經(jīng)常參與信息的制造與傳播，它們做出的控制決策往往參考狀態(tài)匯聚代理發(fā)布的信息．有效地識別廣域網(wǎng)中制造網(wǎng)格的狀態(tài)匯聚代理，通過狀態(tài)匯聚代理發(fā)布引導(dǎo)性信息來影響所在網(wǎng)絡(luò)中用戶節(jié)點的控制決策而非直接使用控制指令控制它們，可以有效地觸發(fā)整個網(wǎng)絡(luò)的協(xié)同性，對于推動信息傳播、提高廣域網(wǎng)中節(jié)點的控制效能具有重要的現(xiàn)實意義．對于狀態(tài)匯聚代理識別問題，國內(nèi)外學(xué)者都進行了大量的研究，提出了多種狀態(tài)匯聚代理的識別算法，主要思路是根據(jù)網(wǎng)絡(luò)拓撲特性，將網(wǎng)絡(luò)抽象成一種圖(無向圖或有向圖)，通過分析節(jié)點之間的結(jié)構(gòu)關(guān)系，計算每個節(jié)點的權(quán)值．節(jié)點的權(quán)值越大，成為狀態(tài)匯聚代理的可能性就越大．由于有向制造網(wǎng)格是一種新興的制造網(wǎng)格，具有與傳統(tǒng)制造網(wǎng)格不同的網(wǎng)絡(luò)拓撲特性．在有向制造網(wǎng)格中，網(wǎng)格節(jié)點構(gòu)成一種有向圖，在分析節(jié)點之間結(jié)構(gòu)關(guān)系時，除了出度(Out-Degree)和入度(In-Degree)外，還需要考慮其他因素，以提高計算精確度．

筆者重點研究廣域網(wǎng)中面向有向制造網(wǎng)格的狀態(tài)匯聚代理識別問題，提出一種基于多重鏈接的有向制造網(wǎng)格節(jié)點權(quán)重計算方法，能夠有效地識別有向制造網(wǎng)格中的狀態(tài)匯聚代理．

1 相關(guān)工作

國內(nèi)外學(xué)者提出了多種制造網(wǎng)格狀態(tài)匯聚代理的識別算法，主要通過分析制造網(wǎng)格拓撲特性來計算網(wǎng)格節(jié)點權(quán)值，或者根據(jù)信息內(nèi)容來判斷其用戶的重要性，進而識別狀態(tài)匯聚代理．文獻[4]提出了一種基于狀態(tài)信息內(nèi)容分析的有向制造網(wǎng)格重要用戶分析方法，通過分析大量的有向制造網(wǎng)格的狀態(tài)信息內(nèi)容來判斷其用戶的重要性，但需要耗費大量的時間用于內(nèi)容清理和分析，效率較低．文獻[5]提出一種狀態(tài)匯聚代理識別方法，通過對有向制造網(wǎng)格中網(wǎng)格節(jié)點的對比來判斷用戶的重要性，并通過這些用戶對整個網(wǎng)絡(luò)所做的貢獻來計算用戶權(quán)值．該文采用了余弦定理計算不同制造節(jié)點狀態(tài)信息的相似性，復(fù)雜性較高，開銷大．文獻[6]提出了一種基于有向制造網(wǎng)格中節(jié)點交互信息的計算識別狀態(tài)匯聚代理的方法，根據(jù)制造網(wǎng)格中節(jié)點的用戶關(guān)系、節(jié)點及其用戶的分布以及在信息交互的過程中各種用戶群體所起到的作用進行權(quán)重計算．該算法主要基于制造主題進行分析，召回率不高．文獻[7]研究了如何對節(jié)點影響力進行定量分析，通過因子圖建模，提出了3種學(xué)習(xí)算法，但文中用到的LDA和因子圖降低了其效率．文獻[8]根據(jù)有向制造網(wǎng)格節(jié)點之間的交互信息和拓撲信息，利用線性回歸模型預(yù)測節(jié)點之間的影響力大小，結(jié)果表明交互信息起主導(dǎo)作用，拓撲信息作用較?。摲椒▋H利用了一種領(lǐng)域制造網(wǎng)格的數(shù)據(jù)，結(jié)論是否適合于其他領(lǐng)域的制造網(wǎng)格還待進一步驗證．

2 基于多重鏈接的有向制造網(wǎng)格節(jié)點權(quán)重計算方法

為了克服現(xiàn)有制造網(wǎng)格節(jié)點權(quán)重計算方法準確率及召回率低、時間復(fù)雜度高的不足，筆者提出了一種基于多重鏈接的有向制造網(wǎng)格節(jié)點權(quán)重計算方法．該方法首先將有向制造網(wǎng)格抽象成一種有向網(wǎng)絡(luò)圖G= (R，N)，每個制造節(jié)點構(gòu)成網(wǎng)絡(luò)中的節(jié)點，制造節(jié)點之間的關(guān)系構(gòu)成節(jié)點之間的邊．由于每個制造節(jié)點所擁有的關(guān)聯(lián)節(jié)點(關(guān)聯(lián)程度)不同，因此各個制造節(jié)點具有不同的權(quán)值．節(jié)點權(quán)值越大，說明該節(jié)點的影響力越大，成為狀態(tài)匯聚節(jié)點的可能性也就越大．在計算節(jié)點權(quán)重時，考慮到節(jié)點擁有的關(guān)聯(lián)節(jié)點數(shù)量以及節(jié)點鏈接關(guān)系和交互關(guān)系等多方面因素，提高了計算效率以及準確率．

該方法的基本原理如下．

定義1 有向制造網(wǎng)格的有向圖G表示為G= (R，M)，其中，R表示節(jié)點關(guān)系集合，M表示節(jié)點集合．

定義2 有效關(guān)聯(lián)節(jié)點集合E(v)如下式所示:

E(v)={m|m∈Rrelevant(v)∩Rresponse(v)>ζ} ,

(1)

式中，ζ是非負常數(shù)閾值，表示節(jié)點v的關(guān)聯(lián)節(jié)點m對節(jié)點v反饋的程度門限，超過該閾值且屬于節(jié)點v的關(guān)聯(lián)節(jié)點才能看做有效關(guān)聯(lián)節(jié)點．

定義3 由鏈接關(guān)系所產(chǎn)生的節(jié)點權(quán)值WNWL(vi)的計算式為

(2)

式中，WNWL(vi)表示節(jié)點vi鏈接關(guān)系產(chǎn)生的節(jié)點權(quán)值，Rrelevant(vi) 為節(jié)點vi的所有關(guān)聯(lián)節(jié)點的集合，RRnum(vj) 為節(jié)點vj的關(guān)聯(lián)節(jié)點數(shù)目，σ是介于0和1之間的阻尼系數(shù)，N為網(wǎng)絡(luò)圖中的總節(jié)點數(shù)．

定義4 由節(jié)點交互關(guān)系所產(chǎn)生的節(jié)點權(quán)值WNWI(vi)的計算式為

(3)

式中，WNWI(vi)表示節(jié)點vi的節(jié)點權(quán)值，SSIS(vi) 為節(jié)點vi的狀態(tài)信息集合，S表示所有具有交互情況的狀態(tài)集，|S|是集合S的元素數(shù)，Rs(vj) 是節(jié)點vj針對狀態(tài)信息tj的響應(yīng)次數(shù)，Rμ(vj) 為響應(yīng)平均值，RResp包括用戶轉(zhuǎn)發(fā)、回復(fù)、評論和收藏狀態(tài)的信息．

定義5 節(jié)點綜合權(quán)值WNWGe(vi)的計算式為

WNWGe(vi)=(1-ε) (WNWL(vi)+ε)WNWI(vi) ,

(4)

式中，參數(shù)ε(ε∈[0， 1])主要決定鏈接關(guān)系和節(jié)點交互關(guān)系兩個因子在節(jié)點權(quán)值計算中所處的地位．當(dāng)ε較小時，節(jié)點權(quán)值主要由鏈接關(guān)系決定，特別當(dāng)ε=0 時，則完全由鏈接關(guān)系計算權(quán)值．

綜上所述，該方法的具體算法描述如下:

(1) 利用網(wǎng)絡(luò)垂直搜索工具，從互聯(lián)網(wǎng)中采集制造網(wǎng)格的狀態(tài)信息數(shù)據(jù)，提取其中的節(jié)點、連接等網(wǎng)絡(luò)拓撲信息存入數(shù)據(jù)庫待處理;

(2) 構(gòu)建有向網(wǎng)絡(luò)圖G=(R，N);

(3) 利用式(1)計算有效關(guān)聯(lián)節(jié)點集合E(v);

(4) 利用式(2)計算由鏈接關(guān)系所產(chǎn)生的節(jié)點權(quán)值WNWL(vi);

(5) 利用式(3)計算由節(jié)點交互關(guān)系所產(chǎn)生的節(jié)點權(quán)值WNWI(vi);

(6) 利用式(4)計算節(jié)點綜合權(quán)值WNWGe(vi);

(7) 計算網(wǎng)絡(luò)圖中所有節(jié)點的綜合權(quán)值，并按綜合權(quán)值由大到小排序，選取綜合權(quán)值較大的n個節(jié)點作為狀態(tài)匯聚代理的候選對象．

新方法從計算效率和精確度兩個方面改進了現(xiàn)有方法．首先，通過定義有效關(guān)聯(lián)節(jié)點集合，將沒有或擁有少量關(guān)聯(lián)節(jié)點的節(jié)點排除掉，它們成為狀態(tài)匯聚代理的可能性極小，因為狀態(tài)匯聚代理或高權(quán)值節(jié)點必然擁有大量的關(guān)聯(lián)節(jié)點，這樣就可大幅度減小網(wǎng)絡(luò)圖規(guī)模，有利于提高計算效率．其次，在計算節(jié)點權(quán)值時，不僅考慮了由關(guān)聯(lián)節(jié)點產(chǎn)生的鏈接關(guān)系，還考慮了狀態(tài)信息的發(fā)布、轉(zhuǎn)發(fā)、回復(fù)以及收藏等所產(chǎn)生的節(jié)點交互關(guān)系，因此提高了計算精確度．

3 實驗結(jié)果及分析

由于狀態(tài)匯聚代理的識別被量化成網(wǎng)絡(luò)中節(jié)點權(quán)值序列，故在這個序列中排名靠前的可認為是網(wǎng)絡(luò)中的狀態(tài)匯聚代理．目前還沒有用于衡量狀態(tài)匯聚代理識別效果的標準，學(xué)術(shù)界主要采用算法比較方式來確認狀態(tài)匯聚代理的識別效果．

下面對基于多重鏈接算法和基于網(wǎng)絡(luò)拓撲特性算法進行3種統(tǒng)計學(xué)方法比較，即T-Test檢驗、Kendall tau Rank檢驗和Spearman Rank檢驗．

(1) 數(shù)據(jù)集．從煙草工業(yè)制造集成化信息系統(tǒng)及商業(yè)物流銷售集成化信息系統(tǒng)中抽取原始的數(shù)據(jù)，生成煙草制造網(wǎng)格所需的原始數(shù)據(jù)集，為本課題研究的驗證過程提供所需的數(shù)據(jù)支持．

(2) 網(wǎng)絡(luò)分析工具．采用自行研制的網(wǎng)絡(luò)分析工具對所采集的數(shù)據(jù)集進行分析，該工具實現(xiàn)了多重鏈接、基于網(wǎng)絡(luò)拓撲特性、Topic-based、PageRank、HITS、TwitterRank、InfluenceRank等多種算法，可以對這些算法的性能進行對比實驗分析．該工具運行在一臺PC機上， CPU為Intel 酷睿i5 3350P，主頻為 3.1 GHz，內(nèi)存為 4 GB．

(3) T-Test檢驗．T-Test檢驗也稱student-t檢驗，主要用于檢驗樣本空間較小 (n<30)、總體標準差σ未知的正態(tài)分布數(shù)據(jù)．

首先使用多重鏈接算法和基于網(wǎng)絡(luò)拓撲特性算法分別對 10 000 個制造網(wǎng)格節(jié)點進行狀態(tài)匯聚代理識別，得到前100位節(jié)點權(quán)值排名靠前的制造節(jié)點，然后對這100個節(jié)點使用T-Test檢驗，得到這些節(jié)點的P分布．圖1和圖2分別給出了多重鏈接算法和基于網(wǎng)絡(luò)拓撲特性算法的T-Test檢驗的P分布．圖中直線標識了P=0.05 (即5%)的分割線，可以看出，節(jié)點的P值主要集中在該直線以下，即通過T-Test檢驗發(fā)現(xiàn)，兩種算法計算的節(jié)點領(lǐng)袖權(quán)值具有較高的可信度，能夠代表網(wǎng)絡(luò)中的狀態(tài)匯聚代理．

圖1 多重鏈接算法的T-Test檢驗圖2 基于網(wǎng)絡(luò)拓撲特性算法的T-Test檢驗

(4) Kendall-tau檢驗．在統(tǒng)計學(xué)中，肯德爾相關(guān)系數(shù)(Kendall-tau)是用來測量兩個隨機變量相關(guān)性的統(tǒng)計值，用希臘字母τ表示其值．肯德爾檢驗是一個無參數(shù)假設(shè)檢驗，它使用計算得到的相關(guān)系數(shù)去檢驗兩個隨機變量的統(tǒng)計依賴性．τ的取值范圍在 -1 到1之間．當(dāng)τ=1 時，表示兩個隨機變量擁有一致的等級相關(guān)性；當(dāng)τ=-1 時，表示兩個隨機變量擁有完全相反的等級相關(guān)性；當(dāng)τ=0 時，表示兩個隨機變量是相互獨立的．τ的計算公式為

τ=(ne-nd)/((n0-n1)(n0-n2))1/2．

根據(jù)計算結(jié)果，多重鏈接算法和基于網(wǎng)絡(luò)拓撲特性算法之間的τ值為0.910 7，說明這兩種算法具有很高的一致性．

(5) Spearman Rank檢驗．在統(tǒng)計學(xué)中，斯皮爾曼等級相關(guān)系數(shù)(Spearman Rank)用來估計兩個變量X、Y之間的相關(guān)性，其中變量間的相關(guān)性可以使用單調(diào)函數(shù)來描述，并用希臘字母ρ表示其值．如果兩個變量取值的兩個集合中均不存在相同的兩個元素，那么，當(dāng)其中一個變量可以表示為另一個變量的單調(diào)函數(shù) (即兩個變量的變化趨勢相同)時，兩個變量之間的ρ值范圍在 -1 到1之間．

假設(shè)兩個隨機變量分別為X、Y(也可以看做是兩個集合)，它們的元素個數(shù)均為N，兩個隨機變量取的第i(1≤i≤N) 個值分別用Xi、Yi表示．對X、Y進行排序(同時為升序或降序)，得到兩個元素排行集合x、y，其中元素xi、yi分別為Xi在X中的排行以及Yi在Y中的排行．將集合x、y中的元素對應(yīng)相減，得到一個排行差分集合d，其中，di=xi-yi，1≤i≤N．隨機變量X、Y之間的ρ值可以由x、y或者d計算得到，其計算式為

表1給出了7種算法之間的斯皮爾曼等級相關(guān)系數(shù)值．從表1可以看出，多重鏈接算法和基于網(wǎng)絡(luò)拓撲特性算法具有較高的斯皮爾曼等級相關(guān)系數(shù)值，序列一致性較高，說明多重鏈接算法和基于網(wǎng)絡(luò)拓撲特性算法在狀態(tài)匯聚代理識別上表現(xiàn)出較好的能力．

表1 各算法的斯皮爾曼等級相關(guān)系數(shù)值表

注：A表示Topological；B表示Topic；C表示多重鏈接；D表示PageRank；E表示HITS；F表示TwitterRank；G表示InfluenceRank．

(6) 準確率與召回率．使用準確率和召回率(查全率)來評價狀態(tài)匯聚代理識別算法的性能，其中準確率和召回率分別使用P和R表示：

P=A/(A+B) ,R=A/(A+C) ,

式中，A表示找到的真實狀態(tài)匯聚代理數(shù)目；B表示找到的非真實狀態(tài)匯聚代理數(shù)目；C表示未識別到的真實狀態(tài)匯聚代理數(shù)目．

由于在狀態(tài)匯聚代理識別中還沒有標準來衡量是否發(fā)現(xiàn)了全部的狀態(tài)匯聚代理，因此在計算準確率和召回率時，通常采用基于經(jīng)驗的狀態(tài)匯聚代理來獲得真實狀態(tài)匯聚代理的數(shù)目．

表2是以處理10 000個制造節(jié)點為基準測試的．從表2中可以看出，單純分析網(wǎng)絡(luò)節(jié)點(如入度、出度等鏈接關(guān)系分析算法)可以降低節(jié)點分析時間，但準確率和召回率不高．考慮節(jié)點內(nèi)容(如ThreadRank、InfluenceRank及TwitterRank等算法)后能夠提高節(jié)點分析的召回率和準確率，但是會大大降低系統(tǒng)效率．

表2 各種算法的召回率、準確率及平均節(jié)點處理時間對照

注: 時間測試是在包含1萬個制造節(jié)點的仿真數(shù)據(jù)環(huán)境下得到的結(jié)果．

筆者采用制造網(wǎng)格拓撲結(jié)構(gòu)中鏈接關(guān)系與節(jié)點交互相結(jié)合的計算方法，降低了網(wǎng)絡(luò)節(jié)點規(guī)模，從而提高了計算速度，同時顯著提高了準確率和召回率．

從圖3和圖4可以得出，在測試數(shù)據(jù)集上，多重鏈接、基于網(wǎng)絡(luò)拓撲特性及Topic-based等算法都具有較好的準確率和召回率，與TwitterRank算法基本相當(dāng)，比常見的出度和出度/入度結(jié)合算法更好．在測試數(shù)據(jù)集上，出度和出度/入度結(jié)合算法的召回率和準確率都比較低．

圖3 不同算法識別狀態(tài)匯聚代理的召回率圖4 不同算法識別狀態(tài)匯聚代理的準確率

圖5 不同算法在計算時間上的比較

從圖5可以看出，出度和出度/入度結(jié)合兩種算法的計算時間要比其他算法優(yōu)異．因為在計算過程中，這兩種算法沒有考慮其他的附加條件，所以算法比較簡單，但召回率和準確率都比較低．而其他狀態(tài)匯聚代理識別算法由于考慮了更多的修正因素，因此時間復(fù)雜度稍高．相比之下，多重鏈接算法具有折中的時間復(fù)雜度．

4 總 結(jié)

采用T-Test、Kendall-tau和斯皮爾曼等級相關(guān)系數(shù)這3種統(tǒng)計學(xué)檢驗標準，對不同的狀態(tài)匯聚代理識別算法進行了對比實驗．實驗結(jié)果表明，多重鏈接算法具有較高的狀態(tài)匯聚代理識別能力，與基于網(wǎng)絡(luò)拓撲特性、Topic-based等算法具有一致性．

從算法的準確率和召回率以及計算時間的實驗結(jié)果可以看出，多重鏈接算法不僅在準確率和召回率上表現(xiàn)良好，并且比基于網(wǎng)絡(luò)拓撲特性、Topic-based等算法的時間復(fù)雜度要低，這對于處理海量網(wǎng)絡(luò)數(shù)據(jù)來說是至關(guān)重要的．因此，從狀態(tài)匯聚節(jié)點識別能力、準確率和召回率以及計算時間等綜合指標來看，多重鏈接算法更具優(yōu)勢．

[1] Wang Z Z, Qu T, Chen Q X, et.al. Resource Model and Service Match Algorithm for Mould Manufacturing Grid[J]. International Journal of Computer Integrated Manufacturing, 2012, 25(11): 1011-1028.

[2] Tao F, Zhang L, Lu K, et al. Research on Manufacturing Grid Resource Service Optimal-selection and Composition Framework[J]. Enterprise Information Systems, 2012, 6(2): 237-264.

[3] 孫鵬崗, 權(quán)義寧, 劉俊萍. L-模糊集信任機制的網(wǎng)格計算任務(wù)調(diào)度方法[J]. 西安電子科技大學(xué)學(xué)報, 2008, 35(1): 110-115.

Sun Penggang, Quan Yining, Liu Junping. Task Scheduling Based on Trust Mechanism of the L-fuzzy Set in Grid Computing[J]. Journal of Xidian University, 2008, 35(1): 110-115.

[4] Brink R V, Rusinowska A, Steffen F. Measuring Power and Satisfaction in Societies with Opinion Leaders: an Axiomatization[J]. Social Choice and Welfare, 2013, 41(3): 671-683.

[5] Nakajima S, Tatemura J. Discovering Import-ant Bloggers Based on Analyzing Blog Threads[C]//The 14th International World Wide Web Conference. Piscataway: IEEE, 2005: 2397879.

[6] Song X, Chi Y, Hino K. Identifying Opinion Leaders in the Blogosphere[C]//Conference on Information and Knowledge Management. New York: ACM, 2011: 971-974.

[7] Weng J, Lim E P, Jiang J. Twitterrank: Finding Topic-sensitive Influential Twitterers[C]//Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. New York: ACM, 2010: 261-270.

[8] Tang J, Sun J, Wang C, et al. Social Influence Analysis in Large-scale Networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 807-816.