有向制造網(wǎng)格節(jié)點(diǎn)多重鏈接權(quán)重計(jì)算方法

張 璐， 蔡皖東， 彭 冬

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

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

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

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

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

1 相關(guān)工作

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

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

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

該方法的基本原理如下．

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

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

(4)

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

下面對(duì)基于多重鏈接算法和基于網(wǎng)絡(luò)拓?fù)涮匦运惴ㄟM(jìn)行3種統(tǒng)計(jì)學(xué)方法比較，即T-Test檢驗(yàn)、Kendall tau Rank檢驗(yàn)和Spearman Rank檢驗(yàn)．

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

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

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

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

圖1 多重鏈接算法的T-Test檢驗(yàn)圖2 基于網(wǎng)絡(luò)拓?fù)涮匦运惴ǖ腡-Test檢驗(yàn)

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

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

根據(jù)計(jì)算結(jié)果，多重鏈接算法和基于網(wǎng)絡(luò)拓?fù)涮匦运惴ㄖg的τ值為0.910 7，說(shuō)明這兩種算法具有很高的一致性．

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

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

表1給出了7種算法之間的斯皮爾曼等級(jí)相關(guān)系數(shù)值．從表1可以看出，多重鏈接算法和基于網(wǎng)絡(luò)拓?fù)涮匦运惴ň哂休^高的斯皮爾曼等級(jí)相關(guān)系數(shù)值，序列一致性較高，說(shuō)明多重鏈接算法和基于網(wǎng)絡(luò)拓?fù)涮匦运惴ㄔ跔顟B(tài)匯聚代理識(shí)別上表現(xiàn)出較好的能力．

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

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

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

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

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

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

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

表2 各種算法的召回率、準(zhǔn)確率及平均節(jié)點(diǎn)處理時(shí)間對(duì)照

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

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

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

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

圖5 不同算法在計(jì)算時(shí)間上的比較

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

4 總 結(jié)

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

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

[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-模糊集信任機(jī)制的網(wǎng)格計(jì)算任務(wù)調(diào)度方法[J]. 西安電子科技大學(xué)學(xué)報(bào), 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.