有向制造網格節點多重鏈接權重計算方法

張 璐， 蔡皖東， 彭 冬

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

隨著制造網格及Web技術的發展，協同制造領域出現了一些新的網絡應用，如利用Web技術將專網中的制造節點的交互進一步擴展到基于互聯網的交互．將制造節點的工作狀態信息通過互聯網絡進行交互，使遠程的制造節點實時交互信息及協同工作，顯現出越來越大的價值和影響力[1-3]．

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

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

筆者重點研究廣域網中面向有向制造網格的狀態匯聚代理識別問題，提出一種基于多重鏈接的有向制造網格節點權重計算方法，能夠有效地識別有向制造網格中的狀態匯聚代理．

1 相關工作

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

2 基于多重鏈接的有向制造網格節點權重計算方法

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

該方法的基本原理如下．

定義1 有向制造網格的有向圖G表示為G= (R，M)，其中，R表示節點關系集合，M表示節點集合．

定義2 有效關聯節點集合E(v)如下式所示:

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

(1)

式中，ζ是非負常數閾值，表示節點v的關聯節點m對節點v反饋的程度門限，超過該閾值且屬于節點v的關聯節點才能看做有效關聯節點．

定義3 由鏈接關系所產生的節點權值WNWL(vi)的計算式為

(2)

式中，WNWL(vi)表示節點vi鏈接關系產生的節點權值，Rrelevant(vi) 為節點vi的所有關聯節點的集合，RRnum(vj) 為節點vj的關聯節點數目，σ是介于0和1之間的阻尼系數，N為網絡圖中的總節點數．

定義4 由節點交互關系所產生的節點權值WNWI(vi)的計算式為

(3)

式中，WNWI(vi)表示節點vi的節點權值，SSIS(vi) 為節點vi的狀態信息集合，S表示所有具有交互情況的狀態集，|S|是集合S的元素數，Rs(vj) 是節點vj針對狀態信息tj的響應次數，Rμ(vj) 為響應平均值，RResp包括用戶轉發、回復、評論和收藏狀態的信息．

定義5 節點綜合權值WNWGe(vi)的計算式為

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

(4)

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

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

(1) 利用網絡垂直搜索工具，從互聯網中采集制造網格的狀態信息數據，提取其中的節點、連接等網絡拓撲信息存入數據庫待處理;

(2) 構建有向網絡圖G=(R，N);

(3) 利用式(1)計算有效關聯節點集合E(v);

(4) 利用式(2)計算由鏈接關系所產生的節點權值WNWL(vi);

(5) 利用式(3)計算由節點交互關系所產生的節點權值WNWI(vi);

(6) 利用式(4)計算節點綜合權值WNWGe(vi);

(7) 計算網絡圖中所有節點的綜合權值，并按綜合權值由大到小排序，選取綜合權值較大的n個節點作為狀態匯聚代理的候選對象．

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

3 實驗結果及分析

由于狀態匯聚代理的識別被量化成網絡中節點權值序列，故在這個序列中排名靠前的可認為是網絡中的狀態匯聚代理．目前還沒有用于衡量狀態匯聚代理識別效果的標準，學術界主要采用算法比較方式來確認狀態匯聚代理的識別效果．

下面對基于多重鏈接算法和基于網絡拓撲特性算法進行3種統計學方法比較，即T-Test檢驗、Kendall tau Rank檢驗和Spearman Rank檢驗．

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

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

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

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

圖1 多重鏈接算法的T-Test檢驗圖2 基于網絡拓撲特性算法的T-Test檢驗

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

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

根據計算結果，多重鏈接算法和基于網絡拓撲特性算法之間的τ值為0.910 7，說明這兩種算法具有很高的一致性．

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

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

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

表1 各算法的斯皮爾曼等級相關系數值表

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

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

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

式中，A表示找到的真實狀態匯聚代理數目；B表示找到的非真實狀態匯聚代理數目；C表示未識別到的真實狀態匯聚代理數目．

由于在狀態匯聚代理識別中還沒有標準來衡量是否發現了全部的狀態匯聚代理，因此在計算準確率和召回率時，通常采用基于經驗的狀態匯聚代理來獲得真實狀態匯聚代理的數目．

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

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

注: 時間測試是在包含1萬個制造節點的仿真數據環境下得到的結果．

筆者采用制造網格拓撲結構中鏈接關系與節點交互相結合的計算方法，降低了網絡節點規模，從而提高了計算速度，同時顯著提高了準確率和召回率．

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

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

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

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

4 總 結

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

從算法的準確率和召回率以及計算時間的實驗結果可以看出，多重鏈接算法不僅在準確率和召回率上表現良好，并且比基于網絡拓撲特性、Topic-based等算法的時間復雜度要低，這對于處理海量網絡數據來說是至關重要的．因此，從狀態匯聚節點識別能力、準確率和召回率以及計算時間等綜合指標來看，多重鏈接算法更具優勢．

[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] 孫鵬崗, 權義寧, 劉俊萍. L-模糊集信任機制的網格計算任務調度方法[J]. 西安電子科技大學學報, 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.