孫 勇 譚文安,2

1(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 211106)2 (上海第二工業(yè)大學(xué)計(jì)算機(jī)與信息工程學(xué)院 上海 201209)

支持社會(huì)協(xié)同計(jì)算的跨組織工作流任務(wù)分派算法

孫 勇1譚文安1,2

1(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 211106)2(上海第二工業(yè)大學(xué)計(jì)算機(jī)與信息工程學(xué)院 上海 201209)

(syong@nuaa.edu.cn)

針對(duì)社會(huì)協(xié)同計(jì)算帶來的不可靠性和社會(huì)網(wǎng)絡(luò)所固有的大規(guī)模性問題，提出了支持社會(huì)協(xié)同計(jì)算的跨組織工作流任務(wù)分派優(yōu)化算法.首先，采用了基于工作流任務(wù)子網(wǎng)分層的優(yōu)化模型，將復(fù)雜社會(huì)網(wǎng)絡(luò)圖進(jìn)行有效地劃分，從而簡化了社會(huì)網(wǎng)絡(luò)成員的協(xié)作關(guān)系評(píng)估問題；然后，根據(jù)劃分后網(wǎng)絡(luò)的拓?fù)涮卣?，設(shè)計(jì)了一種基于工作流任務(wù)子網(wǎng)連接點(diǎn)的快速介數(shù)中心性計(jì)算方法，以高效地選取跨組織業(yè)務(wù)項(xiàng)目的領(lǐng)導(dǎo)者；最后，采用基于任務(wù)子網(wǎng)劃分的最短路徑近似算法，實(shí)現(xiàn)了快速查找跨組織業(yè)務(wù)過程的協(xié)作成員；并且，理論證明了支持社會(huì)協(xié)同計(jì)算的工作流分派算法的可行性.實(shí)驗(yàn)結(jié)果表明所提算法大幅降低了社會(huì)協(xié)同計(jì)算的復(fù)雜性，保證了較高的準(zhǔn)確性，解決了工作流任務(wù)成員之間的關(guān)系評(píng)價(jià)和人工團(tuán)隊(duì)組合優(yōu)化的時(shí)效性問題，為社會(huì)協(xié)同計(jì)算的任務(wù)分派提供了一種新的思路.

協(xié)同計(jì)算；團(tuán)隊(duì)組合；任務(wù)分派；跨組織工作流；社會(huì)網(wǎng)絡(luò)

完全自動(dòng)執(zhí)行的業(yè)務(wù)過程難以滿足所有實(shí)際社會(huì)協(xié)同計(jì)算應(yīng)用的需求，復(fù)雜的社會(huì)協(xié)同計(jì)算系統(tǒng)中某些任務(wù)活動(dòng)必須借助跨組織的專業(yè)人工服務(wù)才能圓滿完成[1-2].因此，為有效地解決機(jī)器難以實(shí)現(xiàn)的復(fù)雜問題，社會(huì)協(xié)同計(jì)算系統(tǒng)采用WS-BPEL工作流技術(shù)，通過將人工任務(wù)外包給專家社會(huì)網(wǎng)絡(luò)服務(wù)，實(shí)現(xiàn)社會(huì)成員之間的協(xié)同計(jì)算.在WS-BPEL工作流應(yīng)用中，專家任務(wù)被定義為WS-BPEL工作流控制結(jié)構(gòu)中的一個(gè)活動(dòng)，社會(huì)協(xié)同計(jì)算系統(tǒng)通過調(diào)用專家服務(wù)解決跨組織業(yè)務(wù)中人工任務(wù)的執(zhí)行問題，從而實(shí)現(xiàn)專家服務(wù)與業(yè)務(wù)過程之間的松散融合[1-2]，如圖1所示：

Fig. 1 Cross organizational workflow model based on expert services[2]圖1 基于人工服務(wù)的跨組織工作流應(yīng)用模型[2]

面向?qū)＜疑鐣?huì)化網(wǎng)絡(luò)的協(xié)同計(jì)算模式從企業(yè)內(nèi)部成員交互演變?yōu)榭缃M織之間的協(xié)作，導(dǎo)致組織模型呈現(xiàn)出動(dòng)態(tài)性和不穩(wěn)定性.跨組織工作流系統(tǒng)采用質(zhì)量管理過程技術(shù)，實(shí)現(xiàn)跨組織業(yè)務(wù)質(zhì)量的持續(xù)改進(jìn)，為社會(huì)協(xié)同計(jì)算應(yīng)用提供了有效的計(jì)算機(jī)技術(shù)支持.面向社會(huì)化網(wǎng)絡(luò)的工作流活動(dòng)執(zhí)行前需要分配人工任務(wù)，即在工作流任務(wù)和專家社會(huì)網(wǎng)絡(luò)之間建立映射關(guān)系，跨組織業(yè)務(wù)的任務(wù)分派問題已被證明是NP-hard問題.近年來，工作流任務(wù)分派模型構(gòu)建及其算法優(yōu)化成為了社會(huì)協(xié)同計(jì)算研究領(lǐng)域的難點(diǎn)和熱點(diǎn)問題[2-5]，例如，基于社會(huì)化網(wǎng)絡(luò)的眾包計(jì)算[3-5]和面向?qū)＜疑鐣?huì)網(wǎng)絡(luò)的團(tuán)隊(duì)組合發(fā)現(xiàn)[6-8].研究者通過探索社會(huì)科學(xué)知識(shí)、理論和方法學(xué)，借助基于服務(wù)的跨組織工作流技術(shù)，有效地促進(jìn)了面向社會(huì)網(wǎng)絡(luò)的協(xié)同計(jì)算應(yīng)用[9].

復(fù)雜的社會(huì)協(xié)同計(jì)算項(xiàng)目需要多個(gè)跨組織成員共同完成，跨組織工作流的任務(wù)分派問題是社會(huì)協(xié)同計(jì)算的最基本難點(diǎn)問題.其中，跨組織成員之間的協(xié)同工作效率，不僅依賴于參與者的業(yè)務(wù)執(zhí)行者能力，還取決于參與者之間的合作關(guān)系.執(zhí)行跨組織業(yè)務(wù)的專家成員之間的社會(huì)關(guān)系直接影響著項(xiàng)目進(jìn)度，和睦的社會(huì)關(guān)系有利于跨組織業(yè)務(wù)項(xiàng)目順利地進(jìn)行.在此背景下，社會(huì)網(wǎng)絡(luò)中成員之間的關(guān)系評(píng)估分析變得十分重要.而且，高效地執(zhí)行跨組織業(yè)務(wù)項(xiàng)目要求選擇出項(xiàng)目領(lǐng)導(dǎo)者，以協(xié)調(diào)好不同組織成員之間的關(guān)系，并管理好跨組織項(xiàng)目的進(jìn)度.因此，支持社會(huì)協(xié)同計(jì)算的工作流任務(wù)分派模型的首要任務(wù)是在大規(guī)模社會(huì)網(wǎng)絡(luò)中確立跨組織業(yè)務(wù)應(yīng)用的中心領(lǐng)導(dǎo)者，以管理跨組織業(yè)務(wù)項(xiàng)目的執(zhí)行；然后，為領(lǐng)導(dǎo)者選取合適的項(xiàng)目協(xié)作成員，協(xié)同完成工作流任務(wù).為確?？缃M織業(yè)務(wù)項(xiàng)目的順利進(jìn)行，領(lǐng)導(dǎo)者必須和每個(gè)任務(wù)協(xié)作成員之間具有良好密切的關(guān)系，即項(xiàng)目領(lǐng)導(dǎo)者到任務(wù)協(xié)作成員之間的最短路徑距離盡可能小.

社會(huì)協(xié)同分析算法采用圖數(shù)據(jù)結(jié)構(gòu)來描述社會(huì)網(wǎng)絡(luò)，通過調(diào)用圖的算法，分析社會(huì)成員之間的協(xié)同工作等復(fù)雜計(jì)算問題.社會(huì)成員之間的關(guān)系評(píng)測依賴于社會(huì)成員節(jié)點(diǎn)之間的最短路徑計(jì)算[10-12].然而，社會(huì)網(wǎng)絡(luò)所固有的大規(guī)模性、急劇擴(kuò)張性以及復(fù)雜性等特點(diǎn)，給社會(huì)網(wǎng)絡(luò)成員的關(guān)系評(píng)測算法帶來了嚴(yán)峻的挑戰(zhàn).經(jīng)典的Dijkstra和A*最短路徑算法具有很高的復(fù)雜度，不適用于規(guī)模較大的現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)[10-12].近年來，研究人員提出很多面向大規(guī)模社會(huì)網(wǎng)絡(luò)的最短路徑優(yōu)化近似算法，普遍采用了基于參考點(diǎn)的計(jì)算方法，通過預(yù)先計(jì)算生成的輔助數(shù)據(jù)，提高了后續(xù)算法的執(zhí)行效率.然而，參考點(diǎn)的選擇算法是NP-hard問題[9]，其選取結(jié)果直接影響著最短距離計(jì)算的正確性和效率.而且，從復(fù)雜社會(huì)網(wǎng)絡(luò)中查找跨組織項(xiàng)目的領(lǐng)導(dǎo)者是一個(gè)難點(diǎn)問題，研究者采用了基于介數(shù)中心性的領(lǐng)導(dǎo)者節(jié)點(diǎn)確定方法[7]，因?yàn)榫哂懈呓閿?shù)中心性的候選領(lǐng)導(dǎo)者節(jié)點(diǎn)，總是在多數(shù)社會(huì)成員節(jié)點(diǎn)之間的最短路徑上，因此，提高了所選工作流任務(wù)成員與領(lǐng)導(dǎo)者的高效協(xié)同工作的可能性.但是，目前最高效的介數(shù)中心計(jì)算方法在無權(quán)網(wǎng)絡(luò)中的算法時(shí)間復(fù)雜度為O(m×n)，而在加權(quán)網(wǎng)絡(luò)中的時(shí)間復(fù)雜度為O(m×n+n2×logn)[7-8]，當(dāng)面向大規(guī)模社會(huì)網(wǎng)絡(luò)選取領(lǐng)導(dǎo)者時(shí)，同樣需要耗費(fèi)大量的計(jì)算成本，其效率不高.

針對(duì)社會(huì)網(wǎng)絡(luò)所固有的數(shù)據(jù)大規(guī)模性問題，本文采用了基于工作流任務(wù)子網(wǎng)分層的優(yōu)化模型，將復(fù)雜社會(huì)網(wǎng)絡(luò)圖進(jìn)行有效地劃分，在此基礎(chǔ)上，提出了支持社會(huì)協(xié)同計(jì)算的跨組織工作流分派模型及其高效算法.本文的主要貢獻(xiàn)如下：

1) 基于工作流任務(wù)劃分的人工服務(wù)社會(huì)網(wǎng)絡(luò)設(shè)計(jì)了一種適用于工作流任務(wù)子網(wǎng)劃分的參考點(diǎn)選擇策略；

2) 綜合考慮劃分后社會(huì)網(wǎng)絡(luò)的拓?fù)涮卣鳎岢隽嘶诠ぷ髁魅蝿?wù)子網(wǎng)劃分的最短路徑近似計(jì)算方法，其中包括面向任務(wù)子網(wǎng)內(nèi)部和不同任務(wù)子網(wǎng)之間的社會(huì)成員關(guān)系評(píng)測算法；創(chuàng)新性地提出了基于任務(wù)子網(wǎng)連接點(diǎn)的快速介數(shù)中性計(jì)算方法，該方法能夠高效率地優(yōu)選出項(xiàng)目領(lǐng)導(dǎo)者；

3) 理論證明了所提出的社會(huì)協(xié)同計(jì)算方法的可行性;

4) 使用真實(shí)數(shù)據(jù)集仿真驗(yàn)證分析了支持復(fù)雜社會(huì)協(xié)同計(jì)算的跨組織工作流任務(wù)分派算法的有效性.

1 基于工作流任務(wù)的社會(huì)網(wǎng)絡(luò)劃分

通常，專家社會(huì)網(wǎng)絡(luò)中存在著大量能夠勝任各種工作流任務(wù)的專家服務(wù)候選者，因此，跨組織工作流任務(wù)分派應(yīng)用系統(tǒng)可從專家社會(huì)網(wǎng)絡(luò)中搜索出適合的專家服務(wù)，協(xié)同完成跨組織業(yè)務(wù).例如，某個(gè)信息系統(tǒng)集成協(xié)同研究中心要組織完成一個(gè)大型的軟件項(xiàng)目，為了提高軟件項(xiàng)目質(zhì)量，采用跨組織工作流技術(shù)進(jìn)行管理，并將工作流任務(wù)分派到專家網(wǎng)絡(luò)中的社會(huì)成員協(xié)同完成[13].其中，完成工作流任務(wù)的團(tuán)隊(duì)是一個(gè)關(guān)系緊密的整體，工作流任務(wù)要求人工服務(wù)具備軟件工程(SE)、數(shù)據(jù)庫(DB)、Web開發(fā)等專業(yè)知識(shí)技能.跨組織工作流任務(wù)分派框架如圖2所示：

Fig. 2 Expert network graph based on partition with workflow tasks圖2 基于工作流任務(wù)劃分的專家社會(huì)網(wǎng)絡(luò)圖

針對(duì)專家社會(huì)網(wǎng)絡(luò)的大規(guī)模性和復(fù)雜性等特點(diǎn)，從工作流任務(wù)功能出發(fā)，將社會(huì)網(wǎng)絡(luò)進(jìn)行分組描述，構(gòu)建出一種基于任務(wù)子網(wǎng)劃分的社會(huì)網(wǎng)絡(luò)抽象圖模型.首先，任務(wù)子網(wǎng)劃分方法將工作流任務(wù)作為社會(huì)網(wǎng)絡(luò)圖節(jié)點(diǎn)，加入到專家候選者社會(huì)網(wǎng)絡(luò)中；然后，將任務(wù)的專家候選者與相應(yīng)的任務(wù)節(jié)點(diǎn)進(jìn)行連接.通過增加任務(wù)節(jié)點(diǎn)和連接邊，改變了原有社會(huì)網(wǎng)絡(luò)的圖結(jié)構(gòu)，有利于提高工作流任務(wù)分派的計(jì)算效率.假定工作流任務(wù)集為T={ti|1≤i≤l}，任務(wù)ti作為新增節(jié)點(diǎn)加入到原網(wǎng)絡(luò)圖中，將任務(wù)ti的所有候選者節(jié)點(diǎn)與新增的任務(wù)節(jié)點(diǎn)相連，設(shè)置其連接邊為較大的實(shí)數(shù)值D.例如，圖2表示一個(gè)基于任務(wù)劃分的社會(huì)網(wǎng)絡(luò)圖實(shí)例.

假設(shè)跨組織工作流應(yīng)用需要完成p個(gè)任務(wù)，可根據(jù)工作流任務(wù)將社會(huì)網(wǎng)絡(luò)劃分成p個(gè)任務(wù)子網(wǎng)絡(luò)，如果社會(huì)成員能夠完成工作流任務(wù)ti，則將該成員劃分到任務(wù)子網(wǎng)i中，相關(guān)概念和定義如下:

定義1. 任務(wù)子網(wǎng)圖(subgraph).設(shè)任意2圖G=(V,E,W)與GH=(VH,EH,WH)，如果VH?V，EH?VH×VH，則稱圖GH是圖G的任務(wù)子網(wǎng)圖.

定義2. 鄰接節(jié)點(diǎn)(adjacent node).給定圖G中的任意2個(gè)節(jié)點(diǎn)u和v，如果它們之間有邊相連，則稱節(jié)點(diǎn)u為節(jié)點(diǎn)v的鄰接節(jié)點(diǎn)，

Adj(v)={u|(u,v)∈E∧u,v∈V}.

(1)

定義3. 任務(wù)子網(wǎng)連接點(diǎn)(connector).給定社會(huì)網(wǎng)絡(luò)圖G和基于工作流任務(wù)的某一劃分方案P={G1,G2,…,Gp}，對(duì)于Gi中任意節(jié)點(diǎn)u∈Vi與Gj中任意節(jié)點(diǎn)v∈Vj，如果存在節(jié)點(diǎn)v∈Adj(u)，且Vi≠Vj，則稱u是任務(wù)子網(wǎng)圖Gi的連接點(diǎn)，記為u∈CN(Gi)；否則，稱為內(nèi)部節(jié)點(diǎn)，記為u∈IN(Gi).

定義4. 任務(wù)子網(wǎng)連接邊(CEdge).給定社會(huì)網(wǎng)絡(luò)圖G和基于工作流任務(wù)的某一劃分方案P={G1,G2,…,Gp}，對(duì)于劃分方案P中任意相鄰子圖Gi和Gj之間的連接邊可定義為

CEdge(Gi,Gj)={(v,u)|(v,u)∈

E∧(v∈CN(Gj))∧(u∈CN(Gi))}.

(2)

定義5. 任務(wù)子網(wǎng)內(nèi)部邊(IEdge).給定某一劃分方案P={G1,G2,…,Gp}，對(duì)于劃分方案P中任意子圖Gj(1≤j≤p)，構(gòu)造所有任務(wù)子網(wǎng)連接點(diǎn)的內(nèi)部連接邊，邊的權(quán)重等于在該子圖內(nèi)部所計(jì)算出的連接點(diǎn)之間的最短路徑值，稱為任務(wù)子圖內(nèi)部邊，其定義如下：

IEdge(Gi,Gj)={(v,u)|(v,u)∈

E∧(v∈CN(Gj))∧(u∈CN(Gi))}.

(3)

支持社會(huì)協(xié)同計(jì)算的跨組織工作流分派方法采用基于工作流任務(wù)子網(wǎng)劃分的分層優(yōu)化思想，將復(fù)雜的社會(huì)網(wǎng)絡(luò)圖進(jìn)行有效地劃分，依據(jù)劃分后網(wǎng)絡(luò)的拓?fù)涮卣鳎珊喕蝿?wù)分派中社會(huì)成員節(jié)點(diǎn)之間的最短路徑近似計(jì)算和人工服務(wù)組合優(yōu)化的問題，有利于降低大規(guī)模社會(huì)網(wǎng)絡(luò)中人工服務(wù)搜索算法的時(shí)間復(fù)雜度.

2 任務(wù)成員社會(huì)關(guān)系評(píng)測算法

社會(huì)關(guān)系直接影響著跨組織業(yè)務(wù)項(xiàng)目的執(zhí)行質(zhì)量，在社會(huì)網(wǎng)絡(luò)中，運(yùn)用業(yè)務(wù)項(xiàng)目成員節(jié)點(diǎn)之間的最短路徑距離值來描述成員之間的社會(huì)關(guān)系，因此，支持社會(huì)協(xié)同計(jì)算的跨組織工作流任務(wù)分派方法采用社會(huì)網(wǎng)絡(luò)圖的最短路徑近似算法，實(shí)現(xiàn)工作流任務(wù)成員的社會(huì)關(guān)系評(píng)測.本節(jié)主要討論社會(huì)網(wǎng)絡(luò)成員節(jié)點(diǎn)之間的最短路徑快速計(jì)算問題.

2.1 基于參考點(diǎn)的最短路徑近似計(jì)算

定義6. 最短路徑參考點(diǎn).在社會(huì)網(wǎng)絡(luò)圖中，選擇k個(gè)參考點(diǎn)R={u1,u2,…,uk}，任意節(jié)點(diǎn)v到參考點(diǎn)的最短路徑定義為θ(v)={d(v,u1),d(v,u2),…,d(v,uk)}，d(v,ui)為節(jié)點(diǎn)v與第i個(gè)參考點(diǎn)的距離，滿足：

定理1. 三角不等式.任取3個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)s,u,t∈V，d(s,t)表示s與t之間的最短路徑距離，則有：

d(s,t)≤d(s,u)+d(u,t)，

(4)

(5)

推論1. 假設(shè)存在路徑πs,t∈SP(s,t)且u∈πs,t，則有：

d(s,t)=d(s,u)+d(u,t).

(6)

推論2. 假設(shè)存在路徑πs,u∈SP(s,u)且t∈πs,u，則有：

(7)

基于參考點(diǎn)的預(yù)先計(jì)算環(huán)節(jié)采用了深度優(yōu)先算法，計(jì)算出參考點(diǎn)K={u1,u2,…,uk-1,uk}與網(wǎng)絡(luò)其他節(jié)點(diǎn)之間的最短路徑距離，根據(jù)三角不等式定理可知：

(8)

(9)

(10)

(11)

(12)

2.2 基于任務(wù)子網(wǎng)劃分的參考點(diǎn)選取

參考點(diǎn)選取是基于參考點(diǎn)的最短路徑近似算法的最重要部分，其選取結(jié)果直接影響著最短距離計(jì)算的正確性和效率.然而，參考點(diǎn)的選擇算法是NP-hard問題[13].為提高最短路徑近似算法的正確性和時(shí)間效率，設(shè)計(jì)了一種適用于社會(huì)工作流任務(wù)分派的參考點(diǎn)選取策略，根據(jù)劃分后社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)特征，選擇任務(wù)子網(wǎng)連接點(diǎn)作為參考點(diǎn)，因?yàn)?，任?個(gè)任務(wù)子網(wǎng)節(jié)點(diǎn)之間的最短路徑必然經(jīng)過任務(wù)子網(wǎng)的連接點(diǎn).如圖3所示，其中，深色點(diǎn)表示任務(wù)子網(wǎng)圖的連接點(diǎn)，虛連接線表示子網(wǎng)之間的連接邊，以圖3中節(jié)點(diǎn)a,b,c,d,e,f為例，它們之間的最短路徑都是經(jīng)過所選的參考點(diǎn)，即任務(wù)子網(wǎng)的連接點(diǎn).

命題1. 在處理不同子網(wǎng)成員的社會(huì)關(guān)系評(píng)測時(shí)，采用基于參考點(diǎn)的最短路徑算法，并以工作流任務(wù)子網(wǎng)連接點(diǎn)作為參考點(diǎn)，稱之為基于任務(wù)子網(wǎng)連接點(diǎn)的最短路徑算法，該算法和Dijkstra最短路徑算法具有相同的準(zhǔn)確度.

證明. 由基于任務(wù)子網(wǎng)的參考點(diǎn)選取示意圖可知，不同工作流任務(wù)子網(wǎng)成員之間的最短路徑必然經(jīng)過任務(wù)子網(wǎng)的連接點(diǎn)，由推論1可得：d(s,t)=d(s,connector)+d(connector,t)，其中s,t是不同任務(wù)子網(wǎng)的2個(gè)節(jié)點(diǎn)，至少有一個(gè)參考點(diǎn)出現(xiàn)在s,t之間的最短路徑時(shí)，則Landmark(s,t)=1.根據(jù)三角不等式可知，在處理不同子網(wǎng)成員的社會(huì)關(guān)系評(píng)測時(shí)，以任務(wù)子網(wǎng)連接點(diǎn)作為參考點(diǎn)的最短路徑算法和Dijkstra最短路徑算法具有相同的準(zhǔn)確度.

證畢.

Fig. 3 Reference point selection based task subgraph partition圖3 基于任務(wù)子網(wǎng)劃分的參考點(diǎn)選取示意圖

2.3 基于任務(wù)子網(wǎng)劃分的數(shù)據(jù)存儲(chǔ)

基于任務(wù)子網(wǎng)連接點(diǎn)的最短路徑算法采用數(shù)據(jù)預(yù)處理環(huán)節(jié)，通過預(yù)先計(jì)算生成的輔助數(shù)據(jù)，提高后續(xù)算法的執(zhí)行效率.不同于文獻(xiàn)[14-16]的存儲(chǔ)方法，本文設(shè)計(jì)了一種基于任務(wù)子網(wǎng)分層的存儲(chǔ)方案.在預(yù)計(jì)算階段，首先，執(zhí)行基于任務(wù)子網(wǎng)連接點(diǎn)的最短路徑生成樹算法，不僅存儲(chǔ)每個(gè)候選節(jié)點(diǎn)vi到子網(wǎng)連接點(diǎn)u之間的最短距離，而且存儲(chǔ)每個(gè)節(jié)點(diǎn)到子網(wǎng)連接點(diǎn)的最短路徑(vi,pu[vi],pu[pu[vi]],…,u)，其中，pu[vi]是vi生成樹的父節(jié)點(diǎn)，通過運(yùn)用父節(jié)點(diǎn)查找算法，可準(zhǔn)確計(jì)算出每一個(gè)節(jié)點(diǎn)到參考點(diǎn)的最短路徑；然后，按照工作流任務(wù)功能進(jìn)行分類，存儲(chǔ)子網(wǎng)參考點(diǎn)到子網(wǎng)內(nèi)部節(jié)點(diǎn)之間的最短路徑、距離以及功能屬性值；最后，存儲(chǔ)高一級(jí)的參考點(diǎn)網(wǎng)絡(luò).

基于任務(wù)子網(wǎng)分層的存儲(chǔ)方案不需要存儲(chǔ)所有節(jié)點(diǎn)到參考點(diǎn)之間的最短路徑信息，只需按任務(wù)功能分類，存儲(chǔ)子網(wǎng)內(nèi)部節(jié)點(diǎn)到相應(yīng)參考點(diǎn)的信息，有效地減少了存儲(chǔ)空間；同時(shí)，在分析2個(gè)節(jié)點(diǎn)之間的最短路徑時(shí)，只需計(jì)算候選者節(jié)點(diǎn)到其任務(wù)子網(wǎng)連接點(diǎn)之間的最短距離，因此，提高了近似算法的計(jì)算效率.

2.4 不同子網(wǎng)成員的社會(huì)關(guān)系評(píng)測

針對(duì)不同子網(wǎng)成員的社會(huì)關(guān)系評(píng)測問題，討論了3種算法：1)采用以任務(wù)子網(wǎng)連接點(diǎn)作為參考點(diǎn)的選取策略，設(shè)計(jì)一種最基本的社會(huì)關(guān)系評(píng)測算法，即基于任務(wù)子網(wǎng)連接點(diǎn)的最短路徑算法(ConnSPT)；2)采用任務(wù)子網(wǎng)分層策略，提出一種基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑算法(LayeredSPT)；3)通過定義任務(wù)子網(wǎng)距離，提出基于任務(wù)子網(wǎng)距離的最短路徑近似算法(LTaskSPT).

2.4.1 基于任務(wù)子網(wǎng)連接點(diǎn)的最短路徑算法

證畢.

根據(jù)命題2分析，基于任務(wù)子網(wǎng)連接點(diǎn)的社會(huì)成員關(guān)系評(píng)測的實(shí)現(xiàn)描述如算法1：

算法1. 基于任務(wù)子網(wǎng)連接點(diǎn)的社會(huì)成員關(guān)系評(píng)測算法.

輸入：工作流任務(wù)Task={ta1,ta2,…,tak}、候選者網(wǎng)絡(luò)圖G=(V,E,W)；

輸出：s,t兩點(diǎn)之間近似距離.

① 計(jì)算節(jié)點(diǎn)s和t到其所屬的任務(wù)子網(wǎng)的連接點(diǎn)集合connList；

② foreachconninconnListdo

③ps→t=ps→conn°pconn→t；

⑤ end for

算法1中ps→conn°pconn→t的符號(hào)°表示ps→conn和pconn→t兩條路徑的連接符，假設(shè)ps→conn={u1,u2,…,ui,ui+1}和pconn→t={v1,v2,…,vj,vj+1}，存在ui+1=v1，且ui+1和v1是子網(wǎng)連接點(diǎn)，則可表示為ps→t=ps→conn°pconn→t.

2.4.2 基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑算法

基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑算法融合了任務(wù)子網(wǎng)分層策略，根據(jù)社會(huì)網(wǎng)絡(luò)的任務(wù)劃分，將原社會(huì)網(wǎng)絡(luò)構(gòu)建為2層網(wǎng)絡(luò)的分層結(jié)構(gòu).其中，特殊節(jié)點(diǎn)作為高一級(jí)抽象網(wǎng)絡(luò)層，通過去除中間節(jié)點(diǎn)進(jìn)行化簡，化簡后的各個(gè)任務(wù)功能網(wǎng)絡(luò)相對(duì)獨(dú)立，任務(wù)子網(wǎng)之間通過少量的邊連接起來，這部分邊的端點(diǎn)稱為子網(wǎng)連接點(diǎn)(connector)以及功能子網(wǎng)內(nèi)部的連接邊共同構(gòu)成高一層網(wǎng)絡(luò)，采用基于任務(wù)子網(wǎng)參考點(diǎn)的分層策略能夠有效地降低最短路徑近似算法的復(fù)雜度.

假設(shè)ps→i Conn為節(jié)點(diǎn)s到其所屬子網(wǎng)i連接點(diǎn)iConn的最短路徑，pj Conn→t為節(jié)點(diǎn)t所屬子網(wǎng)j的連接點(diǎn)jConn到節(jié)點(diǎn)t的最短路徑，pi Conn→j Conn表示任務(wù)子網(wǎng)i的所有連接點(diǎn)和子網(wǎng)j的所有連接點(diǎn)之間的最短路徑，其長度稱為分層子網(wǎng)距離，則有ps→t=ps→i Conn°pi Conn→j Conn°pj Conn→t，基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑近似算法的計(jì)算模型可定義為

|pi Conn→j Conn|+|pj Conn→t|}.

(13)

根據(jù)分層最短路徑的近似計(jì)算模型分析，基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑近似算法的實(shí)現(xiàn)步驟如算法2：

算法2. 基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑近似算法.

輸入：工作流任務(wù)Task={ta1,ta2,…,tak}、候選者網(wǎng)絡(luò)圖G=(V,E,W)；

輸出：s,t兩點(diǎn)之間近似距離.

① 計(jì)算節(jié)點(diǎn)s到其所屬的任務(wù)子網(wǎng)i的連接點(diǎn)最短路徑ps→i Conn，其中iConn表示子網(wǎng)i的連接點(diǎn)；

② 計(jì)算節(jié)點(diǎn)t到其所屬任務(wù)子網(wǎng)j的連接點(diǎn)最短路徑pt→j Conn，其中jConn表示子網(wǎng)j的連接點(diǎn)；

③ 計(jì)算子網(wǎng)連接點(diǎn)之間的最短路徑pi Conn→j Conn；

④ 融合分層策略的所有最短路徑聯(lián)合:ps→t=ps→i Conn°pi Conn→j Conn°pj Conn→t；

2.4.3 基于任務(wù)子網(wǎng)距離的最短路徑近似算法

基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑近似算法可以提高計(jì)算速度，并且能夠保證較高的正確率.但是，基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑近似算法需要計(jì)算兩任務(wù)子網(wǎng)的所有連接點(diǎn)之間的最短距離，當(dāng)兩任務(wù)子網(wǎng)的連接點(diǎn)太多時(shí)，該近似算法的時(shí)間性能會(huì)受到極大的影響.為進(jìn)一步提高算法的計(jì)算效率，定義了一種任務(wù)子網(wǎng)距離，以任務(wù)子網(wǎng)距離代替連接點(diǎn)之間的最短距離計(jì)算，任務(wù)子網(wǎng)距離定義如下：

定義7. 任務(wù)子網(wǎng)距離.給定任意2個(gè)工作流任務(wù)子圖SubGH1,SubGH2，則有任務(wù)子網(wǎng)距離可定義為

(14)

其中，CN(SubGH1)是子網(wǎng)SubGH1連接點(diǎn)集合，CN(SubGH2)是子網(wǎng)SubGH2連接點(diǎn)集合.

2.5 子網(wǎng)內(nèi)部成員的社會(huì)關(guān)系評(píng)測

基于任務(wù)子網(wǎng)連接點(diǎn)的最短路徑近似算法適用于評(píng)測不同子網(wǎng)的成員關(guān)系，但不能準(zhǔn)確地評(píng)測同一子網(wǎng)內(nèi)部的成員關(guān)系，因此，本節(jié)內(nèi)容主要討論關(guān)于任務(wù)子網(wǎng)內(nèi)部的成員關(guān)系評(píng)測算法，相關(guān)定義如下[16]：

定義8. 最短路徑生成樹.給定任意某一任務(wù)子圖GH=(VH,EH,WH)，基于參考點(diǎn)的本地最短路徑樹是以對(duì)應(yīng)該子網(wǎng)的某一參考點(diǎn)r∈RH為根的生成樹，子網(wǎng)內(nèi)所有節(jié)點(diǎn)v∈VH到根節(jié)點(diǎn)的路徑是r和v的最短路徑，路徑長度是r和v最短距離值.

定義9. 最近公共祖先.給定某一有根樹Tree及樹中2個(gè)節(jié)點(diǎn)u,v，最近公共祖先LCA(Tree,u,v)表示一個(gè)節(jié)點(diǎn)x，滿足x是u,v的祖先且x的深度盡可能大.

根據(jù)定義8和定義9，采用了一種基于最近公共祖先的子網(wǎng)內(nèi)部成員關(guān)系評(píng)測方法.假設(shè)評(píng)測同一任務(wù)子網(wǎng)i成員s到t之間的關(guān)系，首先計(jì)算基于參考點(diǎn)的本地最短路徑樹；然后計(jì)算成員s和t最近公共祖先LCA(Treei,s,t)，則同一子網(wǎng)內(nèi)部成員關(guān)系的估算方法為

(15)

命題3. 給定某一任務(wù)子圖GH=(VH,EH,WH)、子網(wǎng)連接點(diǎn)集合R，?s,t∈VH，則有

(16)

?u∈R,x∈LCA(Treei,s,t)，則有

d(s,u)+d(u,t)=d(s,x)+d(x,t)+2d(u,x).

d(s,u)+d(u,t)≥d(s,x)+d(x,t)，

進(jìn)一步計(jì)算可得

，

則可得

證畢.

為了快速地評(píng)測子網(wǎng)內(nèi)部成員的關(guān)系，根據(jù)命題3分析，子網(wǎng)內(nèi)部成員的關(guān)系評(píng)測算法可計(jì)算為

(17)

其中，x∈LCA(Treei,s,t),u∈R.

根據(jù)式(15)～(17)分析，本文采用了基于最近公共祖先的最短路徑算法，評(píng)測子網(wǎng)內(nèi)部社會(huì)成員關(guān)系.運(yùn)用基于任務(wù)子網(wǎng)分層的存儲(chǔ)方案存儲(chǔ)每個(gè)子網(wǎng)參考點(diǎn)到任務(wù)子網(wǎng)內(nèi)部節(jié)點(diǎn)之間的最短距離和最短路徑.因此，所提出的子網(wǎng)內(nèi)部的任務(wù)成員關(guān)系評(píng)測算法只需直接從分層存儲(chǔ)文件中查詢，即可快速準(zhǔn)確地評(píng)測出同一子網(wǎng)內(nèi)部成員之間的關(guān)系.

3 跨組織工作流任務(wù)分派優(yōu)化算法

為確保跨組織業(yè)務(wù)項(xiàng)目的順利進(jìn)行，要求項(xiàng)目領(lǐng)導(dǎo)者能夠協(xié)調(diào)好不同組織成員之間的關(guān)系，即優(yōu)選出的領(lǐng)導(dǎo)者必須與每個(gè)任務(wù)協(xié)作伙伴成員之間具有良好密切的社會(huì)關(guān)系.因此，在面向大規(guī)模社會(huì)網(wǎng)絡(luò)進(jìn)行協(xié)同計(jì)算時(shí)，跨組織工作流分派優(yōu)化算法需解決2個(gè)問題：1)如何從大規(guī)模專家社會(huì)網(wǎng)絡(luò)中快速地選擇出領(lǐng)導(dǎo)者節(jié)點(diǎn)，從而負(fù)責(zé)分派任務(wù)并協(xié)調(diào)管理任務(wù)協(xié)作伙伴成員之間的交互；2)如何從大規(guī)模專家社會(huì)網(wǎng)絡(luò)中高效率地選擇工作流任務(wù)協(xié)作伙伴，確保任務(wù)協(xié)作成員與領(lǐng)導(dǎo)者之間協(xié)同工作的效率.

傳統(tǒng)帶領(lǐng)導(dǎo)節(jié)點(diǎn)的團(tuán)隊(duì)任務(wù)分派采用了蠻力法(Brute-Force)實(shí)現(xiàn)[6].Brute-Force算法以所有的社會(huì)網(wǎng)絡(luò)成員作為領(lǐng)導(dǎo)候選者；然后，遍歷社會(huì)網(wǎng)絡(luò)中子任務(wù)對(duì)應(yīng)的全部候選者節(jié)點(diǎn)，查詢出與領(lǐng)導(dǎo)者溝通代價(jià)最優(yōu)的子任務(wù)協(xié)作伙伴；最后，通過比較所有的專家服務(wù)組合方案，優(yōu)選出領(lǐng)導(dǎo)者及相應(yīng)任務(wù)協(xié)作成員節(jié)點(diǎn)的團(tuán)隊(duì)組合，其中子任務(wù)協(xié)作成員與領(lǐng)導(dǎo)者之間的協(xié)同交互成本越低越好.

根據(jù)定義10分析，跨組織工作流活動(dòng)執(zhí)行前需要分派人工任務(wù)，即在工作流任務(wù)和專家社會(huì)網(wǎng)絡(luò)之間建立映射關(guān)系，形成協(xié)同成本最優(yōu)的專家團(tuán)隊(duì)組合，從而保證跨組織工作流專家服務(wù)資源的合理配置.實(shí)質(zhì)上，支持社會(huì)協(xié)同計(jì)算的跨組織工作流任務(wù)分派是一個(gè)面向社會(huì)網(wǎng)絡(luò)的團(tuán)隊(duì)組合求解問題.

問題1. 專家團(tuán)隊(duì)組合求解.給定跨組織工作流任務(wù)Task和一個(gè)候選專家社會(huì)網(wǎng)絡(luò)G，支持社會(huì)協(xié)同計(jì)算的跨組織工作流任務(wù)分派模型主要目標(biāo)是：搜尋一組專家團(tuán)隊(duì)成員，團(tuán)隊(duì)成員的所有技能滿足跨組織項(xiàng)目任務(wù)Task的需求，并使得跨組織項(xiàng)目團(tuán)隊(duì)的協(xié)同交互成本最小，形式化定義如下：

(18)

(19)

其中，xj i是布爾變量，當(dāng)工作流任務(wù)tj選擇第i個(gè)專家時(shí)xj i=1，否則xj i=0.跨組織項(xiàng)目是由多個(gè)子任務(wù)組成，實(shí)際上面向工作流任務(wù)分派算法針對(duì)每一個(gè)子任務(wù)，專家社會(huì)網(wǎng)絡(luò)存在著大量候選專家.以2006年的DBLP數(shù)據(jù)集為例，DBLP存在著4 802個(gè)關(guān)于Web問題的研究專家，5 140個(gè)專家從事DW方面的研究，其中大量專家之間存在著相互關(guān)系，他們形成了復(fù)雜的大規(guī)模社會(huì)網(wǎng)絡(luò).因此，從該網(wǎng)絡(luò)中選取出項(xiàng)目領(lǐng)導(dǎo)者，以及計(jì)算出所有任務(wù)候選專家到領(lǐng)導(dǎo)者節(jié)點(diǎn)之間的最短路徑，都需要大量的計(jì)算時(shí)間.

基于蠻力法的團(tuán)隊(duì)任務(wù)分派算法能夠查找出交互成本最優(yōu)的解決方案，但產(chǎn)生了大量的計(jì)算成本，不適用于復(fù)雜社會(huì)網(wǎng)絡(luò).為了提高算法的性能，Juang等人[7]采用社會(huì)計(jì)算的重要概念介數(shù)中心性(betweenness centrality)，提出了2種選擇領(lǐng)導(dǎo)者節(jié)點(diǎn)的算法：BCinDijkstra和SSinDijkstra[7]，在此基礎(chǔ)上，從社會(huì)網(wǎng)絡(luò)中選擇與領(lǐng)導(dǎo)節(jié)點(diǎn)交互成本最優(yōu)的每個(gè)任務(wù)協(xié)作伙伴成員，即距離領(lǐng)導(dǎo)者節(jié)點(diǎn)最近的任務(wù)子網(wǎng)候選者節(jié)點(diǎn).基于介數(shù)中心性方法確定的領(lǐng)導(dǎo)者節(jié)點(diǎn)具有高的介數(shù)中心性，因此總是在多數(shù)社會(huì)成員節(jié)點(diǎn)之間的最短路徑上，提高了所選工作流任務(wù)成員與領(lǐng)導(dǎo)者的高效協(xié)同工作的可能性.

介數(shù)中心性是Freeman[17]于1977年提出的，用于衡量社會(huì)成員節(jié)點(diǎn)的社會(huì)地位和交互協(xié)調(diào)性.2001年，Brandes[18]提出了一種快速介數(shù)中心性的計(jì)算方法，主要思路為：首先任取一個(gè)節(jié)點(diǎn)開始，通過Dijkstra計(jì)算經(jīng)過節(jié)點(diǎn)的最短路徑數(shù)；然后反向累加計(jì)算節(jié)點(diǎn)的介數(shù)中心性[19].在大規(guī)模社會(huì)網(wǎng)絡(luò)中[20-21]，Brandes算法在計(jì)算節(jié)點(diǎn)之間的最短路徑時(shí)，需要耗費(fèi)大量的計(jì)算成本，其效率不高.而且，在沒有進(jìn)行任務(wù)子網(wǎng)劃分的原始社會(huì)網(wǎng)絡(luò)中，搜索相應(yīng)工作流任務(wù)的團(tuán)隊(duì)協(xié)作伙伴成員，必須遍歷整個(gè)社會(huì)網(wǎng)絡(luò)圖，才能查詢出合適的子任務(wù)協(xié)作伙伴.

通過觀察工作流任務(wù)子網(wǎng)劃分的社會(huì)網(wǎng)絡(luò)特征，我們發(fā)現(xiàn)：任務(wù)子網(wǎng)連接點(diǎn)總存在于2個(gè)不同任務(wù)子網(wǎng)節(jié)點(diǎn)之間的最短路徑上，2個(gè)子網(wǎng)候選節(jié)點(diǎn)的交互必然會(huì)經(jīng)過子網(wǎng)的連接點(diǎn).因此，領(lǐng)導(dǎo)者與其他任務(wù)子網(wǎng)的所有節(jié)點(diǎn)之間的最短路徑必然會(huì)經(jīng)過子網(wǎng)連接點(diǎn).如圖4所示，任務(wù)子網(wǎng)GroupA的連接點(diǎn)a在領(lǐng)導(dǎo)節(jié)點(diǎn)leader與GroupA中所有節(jié)點(diǎn)之間的最短路徑上.

Fig. 4 Example of finding workflow task members圖4 工作流任務(wù)協(xié)作成員選擇實(shí)例

基于劃分后社會(huì)網(wǎng)絡(luò)特征分析，任務(wù)協(xié)作伙伴節(jié)點(diǎn)必然是任務(wù)子網(wǎng)連接點(diǎn)之一，因此，社會(huì)協(xié)同計(jì)算方法在為領(lǐng)導(dǎo)者查找任務(wù)協(xié)作伙伴時(shí)，只需在任務(wù)子網(wǎng)連接點(diǎn)集合中搜索，簡化了工作流任務(wù)分派算法的復(fù)雜度.

命題4. 給定某一任務(wù)子圖SubGH=(VH,EH,WH)，已選領(lǐng)導(dǎo)者節(jié)點(diǎn)leader?VH，子網(wǎng)連接點(diǎn)集合R?VH,設(shè)與領(lǐng)導(dǎo)節(jié)點(diǎn)交互成本最優(yōu)的子任務(wù)協(xié)作者為mem，則有mem∈R.

證明. 假設(shè)mem∈VH是任務(wù)子網(wǎng)SubGH所選出的任務(wù)協(xié)作者，且mem?R.由于leader?VH,不同任務(wù)子網(wǎng)成員之間的最短路徑必然經(jīng)過連接點(diǎn)，因此，存在連接點(diǎn)conn∈R，且conn在leader與mem節(jié)點(diǎn)之間的最短路徑上.

根據(jù)推論1可得到:d(leader,mem)=d(leader,conn)+d(conn,mem)，且d(conn,mem)≥0.

則d(leader,mem)≥d(leader,conn)，可推出mem不是協(xié)作交互成本最低的項(xiàng)目協(xié)作伙伴.

因此，只有當(dāng)mem∈R時(shí)，候選節(jié)點(diǎn)mem才是團(tuán)隊(duì)最優(yōu)的任務(wù)協(xié)作者.

證畢.

由命題4分析可知，社會(huì)協(xié)同計(jì)算應(yīng)用只需在工作流任務(wù)子網(wǎng)連接點(diǎn)集合中搜索子任務(wù)協(xié)作伙伴，減少了任務(wù)協(xié)作伙伴的搜索時(shí)間，提高了社會(huì)協(xié)同計(jì)算的時(shí)間效率.而且，從命題4的結(jié)論反推，逆向思考可知，距離所有任務(wù)子網(wǎng)連接點(diǎn)越近的社會(huì)成員節(jié)點(diǎn)，越有可能被選作為領(lǐng)導(dǎo)者節(jié)點(diǎn)，因?yàn)?，社?huì)協(xié)同計(jì)算模型要求所選取的領(lǐng)導(dǎo)者必須與每個(gè)任務(wù)協(xié)作伙伴成員之間具有良好密切的社會(huì)關(guān)系.受此啟發(fā)，根據(jù)工作流任務(wù)劃分后的社會(huì)網(wǎng)絡(luò)特征，在借鑒Brandes算法思想的基礎(chǔ)上，本文創(chuàng)新性提出了一種基于任務(wù)子網(wǎng)連接點(diǎn)的快速介數(shù)中心性算法，用于快速地搜索領(lǐng)導(dǎo)者節(jié)點(diǎn).

定義11. 基于任務(wù)子網(wǎng)連接點(diǎn)的介數(shù)中心性.令σ(s,t)表示節(jié)點(diǎn)對(duì)(s,t)的最短路徑數(shù)量，σ(s,t|v)表示節(jié)點(diǎn)對(duì)(s,t)的最短路徑通過v的數(shù)量，子網(wǎng)連接點(diǎn)conn∈R，則基于子網(wǎng)連接點(diǎn)的介數(shù)中心性可定義為

(20)

其中，若conn=t，則σ(conn,t)=1;若v∈r,t，則σ(conn,t|v)=0.

由定義11可知，經(jīng)過節(jié)點(diǎn)的最短路徑數(shù)量決定了其在社會(huì)網(wǎng)絡(luò)中的介數(shù)中心性值.首先，基于任務(wù)子網(wǎng)連接點(diǎn)的快速介數(shù)中心性算法任取一個(gè)任務(wù)子網(wǎng)連接點(diǎn)conn，并將conn定義為源節(jié)點(diǎn)，采用Dijkstra最短路徑算法，遍歷基于任務(wù)子網(wǎng)劃分的候選者網(wǎng)絡(luò)圖，計(jì)算經(jīng)過候選節(jié)點(diǎn)的最短路徑數(shù).在以節(jié)點(diǎn)conn開始的最短路徑中，候選節(jié)點(diǎn)w的父節(jié)點(diǎn)可表示為

Pconn(w)={u:(u,w)∈E,d(conn,w)=

d(conn,u)+d(u,w)}，

(21)

則有

(22)

因?yàn)榈竭_(dá)節(jié)點(diǎn)u的最短路徑也通過邊(u,w)到達(dá)節(jié)點(diǎn)w，在進(jìn)行Dijkstra算法遍歷時(shí)，可根據(jù)式(21)(22)，計(jì)算出從任務(wù)子網(wǎng)連接點(diǎn)出發(fā)經(jīng)過每個(gè)節(jié)點(diǎn)最短路徑數(shù)量.Dijkstra算法復(fù)雜度為O(m+nlogn)，因此，采用基于任務(wù)子網(wǎng)連接點(diǎn)的快速介數(shù)中心性算法分析時(shí)，經(jīng)過社會(huì)網(wǎng)絡(luò)圖中候選節(jié)點(diǎn)的最短路徑數(shù)量的統(tǒng)計(jì)時(shí)間復(fù)雜度為O(Rnum×m+Rnum×nlogn).

候選節(jié)點(diǎn)v的介數(shù)中心性表示經(jīng)過節(jié)點(diǎn)v的最短路徑數(shù)量比例，其值越高，則節(jié)點(diǎn)v就越重要，對(duì)工作流任務(wù)子網(wǎng)連接點(diǎn)的影響也越大.為了簡化計(jì)算，將通過節(jié)點(diǎn)v最短路徑的數(shù)量比例定義為節(jié)點(diǎn)依賴度:

(23)

根據(jù)式(20)～(23)分析，根據(jù)節(jié)點(diǎn)依賴度的定義，可推導(dǎo)出命題5.

命題5. 假定工作流任務(wù)子網(wǎng)連接點(diǎn)conn∈R，在社會(huì)網(wǎng)絡(luò)中conn經(jīng)過節(jié)點(diǎn)v到其他成員節(jié)點(diǎn)存在著最短路徑，則可知節(jié)點(diǎn)v的介數(shù)中心性可滿足：

ζ(conn|v)=

(24)

證明. 根據(jù)式(23)，可知：

因?yàn)?/p>

σ(conn,t|v,w)=

則有

整理可得

根據(jù)節(jié)點(diǎn)模型依賴度定義，可知

ζ(conn,t|v,w)=ζ(conn,w|v)×ζ(conn,t|w),

因此，

又因?yàn)?/p>

for (v,w)∈Pconn(w)，

fort=w，

則有

即

證畢.

由命題5分析可知，領(lǐng)導(dǎo)節(jié)點(diǎn)計(jì)算方法為

(25)

基于任務(wù)子網(wǎng)連接點(diǎn)的快速介數(shù)中心性算法以任務(wù)子網(wǎng)連接點(diǎn)conn∈R為源點(diǎn)，首先進(jìn)行正向計(jì)算，采用Dijkstra算法生成最短路徑樹，通過節(jié)點(diǎn)w的前驅(qū)節(jié)點(diǎn)v計(jì)算w的最短路徑數(shù)目；然后進(jìn)行反向搜索，從最短路徑生成樹的葉節(jié)點(diǎn)反向遍歷所有節(jié)點(diǎn)，通過節(jié)點(diǎn)w計(jì)算其父節(jié)點(diǎn)v的介數(shù)中心性，具體實(shí)現(xiàn)見算法3.

算法3. 基于任務(wù)子網(wǎng)連接點(diǎn)的介數(shù)中心性算法.

輸入：工作流任務(wù)Task={ta1,ta2,…,tak}、候選者網(wǎng)絡(luò)圖G=(V,E,W)；

輸出：Top-k領(lǐng)導(dǎo)者節(jié)點(diǎn)集.

① 基于任務(wù)的社會(huì)網(wǎng)絡(luò)劃分：GH=(VH,EH,WH)←(V,E,W)；

② foreachconn∈Rdo*遍歷所有子網(wǎng)連接點(diǎn)*

③ 最短路徑計(jì)算：Dijkstra(conn)；

④ 存儲(chǔ)w前驅(qū)節(jié)點(diǎn)：P[w]←v；

⑤ 統(tǒng)計(jì)通過w的最短路徑數(shù)量：σ[w]←σ[w]+σ[v]；

⑥ 將從起點(diǎn)到當(dāng)前點(diǎn)的距離壓入棧：S←v；

⑦ end for

⑧ 初始化：ζ[v]←0；

⑨ whileS≠null do

⑩ 出棧：w←S；

基于任務(wù)子網(wǎng)連接點(diǎn)的介數(shù)中心性算法的時(shí)間復(fù)雜度為O(Rnum×m+Rnum×nlogn).當(dāng)基于任務(wù)劃分的社會(huì)網(wǎng)絡(luò)中連接點(diǎn)非常少時(shí)，相比Brandes算法，所提出的領(lǐng)導(dǎo)者評(píng)價(jià)算法具有良好的時(shí)間性能.

在確定領(lǐng)導(dǎo)者后，根據(jù)命題4，支持社會(huì)協(xié)同計(jì)算的工作流分派方法的具體實(shí)現(xiàn)步驟如算法4.

算法4. 支持社會(huì)協(xié)同計(jì)算的工作流任務(wù)分派算法.

輸入：工作流任務(wù)Task={ta1,ta2,…,tak}、候選者網(wǎng)絡(luò)圖GH=(VH,EH,WH)←(V,E,W)；

輸出：跨組織工作流協(xié)同計(jì)算解決方案wSolution.

① 基于任務(wù)子網(wǎng)連接點(diǎn)的介數(shù)中心性算法：leader←getLeader(GH)；

② 將選取的leader加入解決方案中：wSolution.add(leader);

③ 分析leader所勝任的工作流任務(wù)：taskList←getCapbility(leader)；

④ 基于子網(wǎng)劃分的任務(wù)協(xié)作者遍歷搜索算法；

⑤ foreachTaskinrequiredTasksdo*遍歷跨組織工作流所有任務(wù)*

⑥ ifTaskinTaskListthen

⑦ continue；

⑧ end if

⑨ 獲取工作流任務(wù)子網(wǎng)對(duì)應(yīng)的所有連接點(diǎn)：memList←getConnectors(Task)；

⑩ formeminmemListdo*遍歷任務(wù)子網(wǎng)連接點(diǎn)*

支持社會(huì)協(xié)同計(jì)算的工作流任務(wù)分派算法包括2部分：基于快速中心性計(jì)算的領(lǐng)導(dǎo)者選擇和子任務(wù)團(tuán)隊(duì)協(xié)作成員查詢.根據(jù)算法3的分析已知，領(lǐng)導(dǎo)者節(jié)點(diǎn)確定算法的時(shí)間復(fù)雜度為O(Rnum×m+Rnum×nlogn)；在進(jìn)行子任務(wù)團(tuán)隊(duì)協(xié)作成員評(píng)估分析時(shí)，需計(jì)算最短路徑d(mem,leader)，采用Dijkstra最短路徑算法，計(jì)算所有子任務(wù)協(xié)作成員的時(shí)間復(fù)雜度為O(l×Rnum+l×nlogn)，其中l(wèi)表示工作流任務(wù)的數(shù)量.綜上分析，支持社會(huì)協(xié)同計(jì)算的工作流任務(wù)分派算法的時(shí)間復(fù)雜度為O(Rnum×(l+m)+(l+Rnum)×nlogn)，其中m?Rnum?l.

4 仿真實(shí)驗(yàn)

4.1 數(shù)據(jù)準(zhǔn)備與分析

Table 1 DBLP Data Analysis

假定面向?qū)＜疑鐣?huì)網(wǎng)絡(luò)的跨組織業(yè)務(wù)應(yīng)用需要6個(gè)不同研究方向的專家服務(wù)，以協(xié)同完成跨組織工作流的所有任務(wù)，其中包括算法(AL)、軟件工程(SE)、數(shù)據(jù)庫系統(tǒng)(DB)以及Web程序設(shè)計(jì)(Web)等方面的專家，如圖5所示：

Fig. 5 Cross-organizational workflow application for expert tasks圖5 面向人工任務(wù)的跨組織工作流應(yīng)用實(shí)例

仿真實(shí)驗(yàn)首先按照文獻(xiàn)[6]方法生成了DBLP專家社會(huì)網(wǎng)絡(luò)圖，然后采用了本文第1節(jié)闡述的基于任務(wù)的社會(huì)網(wǎng)絡(luò)劃分方法，根據(jù)每個(gè)候選者節(jié)點(diǎn)的功能角色劃分出不同任務(wù)子網(wǎng)，劃分后專家社會(huì)網(wǎng)絡(luò)如圖6和圖7所示.

Fig. 6 Graph grouped by task types圖6 基于任務(wù)的子網(wǎng)劃分

Fig. 7 Graph classified by connectors圖7 基于連接點(diǎn)的成員分類

圖6中不同顏色表示不同任務(wù)子網(wǎng).社會(huì)協(xié)同計(jì)算的相關(guān)算法都涉及到基于任務(wù)子網(wǎng)連接點(diǎn)的分析方法.因此，在工作流任務(wù)子網(wǎng)劃分圖的基礎(chǔ)上，可視化仿真實(shí)驗(yàn)根據(jù)任務(wù)子網(wǎng)連接點(diǎn)對(duì)所有的社會(huì)成員節(jié)點(diǎn)進(jìn)行了分類，如圖7所示.其中，所有紅色圖形都表示工作流任務(wù)子網(wǎng)連接點(diǎn)，不同圖案表示不同任務(wù)候選者節(jié)點(diǎn).由可視化分析實(shí)驗(yàn)可知，工作流任務(wù)子網(wǎng)連接點(diǎn)存在于2個(gè)不同子網(wǎng)之間，而且，其數(shù)量遠(yuǎn)小于非連接點(diǎn).

4.2 社會(huì)關(guān)系評(píng)測算法分析

本節(jié)仿真實(shí)驗(yàn)分析了本文所提出的社會(huì)關(guān)系評(píng)測算法，驗(yàn)證了該算法在社會(huì)網(wǎng)絡(luò)環(huán)境下解決社會(huì)工作流任務(wù)分派問題的可行性，其中，共設(shè)計(jì)了2個(gè)實(shí)驗(yàn)：實(shí)驗(yàn)1主要是分析了不同子網(wǎng)社會(huì)成員之間的關(guān)系評(píng)測算法；實(shí)驗(yàn)2則主要是分析了子網(wǎng)內(nèi)部社會(huì)成員之間的關(guān)系評(píng)測算法.根據(jù)最短路徑近似算法獲取社會(huì)成員的關(guān)系評(píng)價(jià)值，采用式(26)評(píng)估最短路徑近似算法的正確率.

(26)

實(shí)驗(yàn)1. 不同任務(wù)子網(wǎng)社會(huì)成員的關(guān)系評(píng)測算法分析驗(yàn)證.

按表1和基于任務(wù)的社會(huì)網(wǎng)絡(luò)劃分方法構(gòu)建了不同規(guī)模的DBLP專家網(wǎng)絡(luò)，隨機(jī)選取2個(gè)任務(wù)子網(wǎng)，采用本文提出的近似最短路徑算法，計(jì)算出不同子網(wǎng)之間的所有節(jié)點(diǎn)的最短距離值.實(shí)驗(yàn)1采用柱狀圖分析了基于任務(wù)子網(wǎng)連接點(diǎn)的最短路徑計(jì)算方法(ConnSPT)、基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑計(jì)算方法(LayeredSPT)以及基于任務(wù)子網(wǎng)距離的最短路徑近似計(jì)算方法(LTaskSPT)的正確率，如圖8所示.

Fig. 8 Correctness verification of different group member relation圖8 不同子網(wǎng)的社會(huì)關(guān)系評(píng)測算法正確率分析

通過觀察圖8可知，基于任務(wù)子網(wǎng)連接點(diǎn)的最短路徑算法的準(zhǔn)確率為1；基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑算法也有較好的準(zhǔn)確率，其準(zhǔn)確率的平均值達(dá)到了0.97；基于任務(wù)子網(wǎng)距離的最短路徑近似算法的正確率相對(duì)較差，其準(zhǔn)確率的平均值為0.72.實(shí)驗(yàn)結(jié)果表明ConnSPT算法的正確率最好，而LTaskSPT算法的正確率是3種近似算法中相對(duì)較差的.

算法的時(shí)間性能是評(píng)價(jià)面向復(fù)雜社會(huì)網(wǎng)絡(luò)的成員關(guān)系評(píng)測算法可行性的重要指標(biāo).為檢驗(yàn)所提近似算法在不同網(wǎng)絡(luò)規(guī)模下的性能，仿真實(shí)驗(yàn)采用6種不同規(guī)模的社會(huì)網(wǎng)絡(luò)分析了所提算法的性能，如圖9和10所示.

Fig. 9 Performance evaluation of group member relation圖9 不同子網(wǎng)的社會(huì)關(guān)系評(píng)測算法性能分析

通過觀察圖9可知，本文提出的3種不同任務(wù)子網(wǎng)社會(huì)成員的社會(huì)關(guān)系評(píng)測算法的時(shí)間性能明顯優(yōu)于精確的最短路徑計(jì)算方法.而且，隨著專家候選者的數(shù)量不斷增多時(shí)，所提算法的性能優(yōu)勢表現(xiàn)得更加顯著.實(shí)驗(yàn)結(jié)果表明，精確的最短路徑算法的時(shí)間花費(fèi)遠(yuǎn)大于所提近似算法的時(shí)間花費(fèi).

圖10是為了更加清晰地分析所提算法的性能效率，刪除了描述精確最短路徑算法的性能曲線，主要展示了本文所提出的3種最短路徑近似算法的時(shí)間性能.

Fig. 10 Details of Fig. 9圖10 圖9中算法性能的詳細(xì)表示

由圖10可知，基于任務(wù)子網(wǎng)距離的最短路徑近似算法的性能效率最優(yōu)，基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑算法次之，而基于任務(wù)子網(wǎng)連接點(diǎn)的最短路徑算法效率相對(duì)差一些.與算法準(zhǔn)確率實(shí)驗(yàn)表現(xiàn)出的情況剛好相反，因此，我們可以根據(jù)業(yè)務(wù)的需要，選擇適合的社會(huì)關(guān)系評(píng)測方法.

實(shí)驗(yàn)2. 子網(wǎng)內(nèi)部社會(huì)成員關(guān)系評(píng)測算法分析.

采用與實(shí)驗(yàn)1同樣的方法，設(shè)置了不同規(guī)模的DBLP專家網(wǎng)絡(luò)，任取一子網(wǎng)，采用本文所提的子網(wǎng)內(nèi)部社會(huì)成員關(guān)系評(píng)測算法，計(jì)算子網(wǎng)內(nèi)部不同節(jié)點(diǎn)的最短路徑距離值.實(shí)驗(yàn)2采用柱狀圖分析了基于最近公共祖先的最短路徑算法(LCASPT)和基于任務(wù)子網(wǎng)連接點(diǎn)的最短路徑算法(ConnSPT)的正確率.如圖11所示，基于最近公共祖先的最短路徑算法正確率接近1；基于任務(wù)子網(wǎng)連接點(diǎn)的分層最短路徑算法也有較好的正確率，正確率在0.6上下，不適用于同一子網(wǎng)關(guān)系評(píng)測.

為檢驗(yàn)子網(wǎng)內(nèi)部社會(huì)成員關(guān)系評(píng)測算法的時(shí)間性能，仿真實(shí)驗(yàn)比較了基于最近公共祖先的最短路徑算法(LCASPT)和精確的最短路徑算法(Exact)的性能，如圖12所示.其中，虛線條表示采用的LCASPT算法，而實(shí)線條表示Exact算法的性能.觀察圖12可知，基于最近公共祖先的最短路徑近似算法的性能明顯優(yōu)于精確的最短路徑算法.

實(shí)驗(yàn)1和實(shí)驗(yàn)2驗(yàn)證分析了本文提出的社會(huì)關(guān)系評(píng)測算法，實(shí)驗(yàn)結(jié)果表明，本文提出的社會(huì)成員評(píng)測算法具有良好的時(shí)間性能，保證了較高的精確度，為面向大規(guī)模社會(huì)網(wǎng)絡(luò)的跨組織工作流任務(wù)分派提供了技術(shù)支持.

4.3 支持社會(huì)協(xié)同計(jì)算的工作流任務(wù)分派算法分析

仿真實(shí)驗(yàn)進(jìn)一步通過分析社會(huì)工作流的協(xié)同模型算法，驗(yàn)證了所提出的算法在復(fù)雜社會(huì)網(wǎng)絡(luò)環(huán)境下解決工作流多任務(wù)外包問題的可行性.為此，設(shè)計(jì)了3個(gè)方面實(shí)驗(yàn)，其中，實(shí)驗(yàn)3主要驗(yàn)證了基于任務(wù)子網(wǎng)連接點(diǎn)的介數(shù)中心性算法的性能效率，即分析領(lǐng)導(dǎo)者選取算法的效率問題；實(shí)驗(yàn)4分析了基于子網(wǎng)劃分的任務(wù)協(xié)作者遍歷搜索算法的性能效率；實(shí)驗(yàn)5驗(yàn)證了面向社會(huì)工作流的協(xié)同計(jì)算模型算法的正確性.

實(shí)驗(yàn)3. 基于任務(wù)子網(wǎng)連接點(diǎn)的介數(shù)中心性算法的性能效率分析.

社會(huì)化網(wǎng)絡(luò)為工作流任務(wù)提供了大量的專家候選者以及他們之間的社會(huì)關(guān)系信息.然而，社會(huì)網(wǎng)絡(luò)所固有的復(fù)雜性和大規(guī)模性也給工作流協(xié)同模型算法的計(jì)算效率帶來了挑戰(zhàn).為分析領(lǐng)導(dǎo)者選取算法的可行性，實(shí)驗(yàn)3通過分析比較Kargar和An[6]以及Juang等人[7]提出的領(lǐng)導(dǎo)者選擇算法，驗(yàn)證所提出的基于任務(wù)子網(wǎng)的快速介數(shù)中性算法(ConnBC)的性能效率.實(shí)驗(yàn)3中以圖5工作流為例，工作流業(yè)務(wù)包括了6個(gè)任務(wù)，通過選取不同規(guī)模的實(shí)驗(yàn)數(shù)據(jù)來分析算法性能，其中候選者節(jié)點(diǎn)規(guī)模集合為{300,600,900,1 200,1 500,1 800}.每次實(shí)驗(yàn)執(zhí)行10次，取其平均值作為實(shí)驗(yàn)結(jié)果.如圖13所示，所提算法ConnBC具有更好的時(shí)間性能，而且，隨著候選者數(shù)據(jù)量增大，表現(xiàn)則更加明顯.

Fig. 13 Performance evaluation of leader selection圖13 領(lǐng)導(dǎo)者選取算法性能分析

Fig. 14 Performance evaluation of group member discovery圖14 任務(wù)協(xié)作者搜索算法性能分析

實(shí)驗(yàn)4. 基于子網(wǎng)劃分的任務(wù)協(xié)作者遍歷搜索算法性能分析.

為分析任務(wù)協(xié)作者搜索算法效率，實(shí)驗(yàn)4分析了Kargar和An[6]以及Juang等人[7]提出的算法，并與所提出的基于任務(wù)子網(wǎng)劃分的任務(wù)協(xié)作者搜索算法(ConnBC)進(jìn)行了比較，主要是通過比較所有算法在協(xié)作伙伴選擇時(shí)遍歷的候選節(jié)點(diǎn)個(gè)數(shù)，當(dāng)遍歷候選節(jié)點(diǎn)數(shù)越少，表明其算法更優(yōu).實(shí)驗(yàn)4與實(shí)驗(yàn)3采用了同樣的數(shù)據(jù)選取方法，如圖14所示.其中，基于網(wǎng)絡(luò)劃分的任務(wù)協(xié)作者搜索算法是用實(shí)線線條表示，具有更好的性能，而且，隨著專家候選者數(shù)據(jù)量的不斷增大，表現(xiàn)更加明顯.

實(shí)驗(yàn)5. 社會(huì)工作流任務(wù)分派算法的正確性驗(yàn)證.

支持社會(huì)協(xié)同計(jì)算的跨組織工作流任務(wù)分派方法通過將跨組織工作流任務(wù)外包到候選者社會(huì)網(wǎng)絡(luò)中，從候選者網(wǎng)絡(luò)中查找到領(lǐng)導(dǎo)者節(jié)點(diǎn)及任務(wù)協(xié)作伙伴，并保證協(xié)同交互成本最低.通過比較Kargar和An[6]提出的BruteForce算法，Juang等人[7]提出BCPruning算法和SSPruning算法，及所提算法(Proposed)，驗(yàn)證了所提算法的正確性，如圖15所示.其中，Proposed算法是用實(shí)線條表示，其交互成本幾乎與BruteForce接近，表明Proposed算法能夠選出關(guān)系密切的專家服務(wù)組合.

Fig. 15 Correctness verification of social workflow task allocation圖15 社會(huì)工作流的任務(wù)分派算法正確性驗(yàn)證

實(shí)驗(yàn)結(jié)果表明本文所提出的跨組織工作流任務(wù)分派算法，大幅降低了工作流任務(wù)分派的時(shí)間成本，并能保持較高的算法精度，適用于大規(guī)模社會(huì)網(wǎng)絡(luò)的協(xié)同計(jì)算問題.但存在2點(diǎn)不足：1)算法結(jié)果還不夠精確，應(yīng)更進(jìn)一步提高；2)當(dāng)工作流任務(wù)子網(wǎng)連接點(diǎn)數(shù)目很多時(shí)，所提算法的時(shí)間效率仍會(huì)不理想，應(yīng)設(shè)計(jì)出不同的應(yīng)對(duì)解決方案.

5 結(jié) 論

復(fù)雜社會(huì)網(wǎng)絡(luò)所固有的大規(guī)模性特征給支持社會(huì)協(xié)同計(jì)算應(yīng)用的算法性能提出了更高的要求.針對(duì)面向大規(guī)模社會(huì)網(wǎng)絡(luò)的跨組織工作流人工任務(wù)分派問題，提出了一種支持社會(huì)協(xié)同計(jì)算的跨組織工作流分派優(yōu)化算法，采用了基于工作流任務(wù)子網(wǎng)的分層優(yōu)化思想，有效地劃分復(fù)雜社會(huì)網(wǎng)絡(luò)圖，簡化了最短路徑的近似計(jì)算問題；并依據(jù)劃分后人工服務(wù)社會(huì)網(wǎng)絡(luò)的拓?fù)涮卣?，改進(jìn)了快速介數(shù)中心性算法，設(shè)計(jì)了一種新穎的基于任務(wù)子網(wǎng)連接點(diǎn)的快速介數(shù)中心性計(jì)算方法，高效地選取跨組織業(yè)務(wù)項(xiàng)目的領(lǐng)導(dǎo)者；然后，采用基于任務(wù)子網(wǎng)劃分的最短路徑近似算法，實(shí)現(xiàn)了快速查找跨組織業(yè)務(wù)項(xiàng)目的協(xié)作成員；理論證明和仿真實(shí)驗(yàn)表明所提出分派方法具有良好的算法性能，并保持較高的算法精度，有效地解決了跨組織工作流任務(wù)成員之間的關(guān)系評(píng)價(jià)和人工服務(wù)組合優(yōu)化的時(shí)效性問題，適用于復(fù)雜的大規(guī)模社會(huì)網(wǎng)絡(luò)協(xié)同計(jì)算.

[1]Skopik F, Schall D, Dustdar S, et al. Modeling and mining of dynamic trust in complex service-oriented systems[J]. Information Systems, 2010, 35(7): 735-757

[2]Schall D, Satzger B, Psaier H. Crowdsourcing tasks to social networks in BPEL4People[J]. World Wide Web-Internet and Web Information Systems, 2014, 17(1): 1-32

[3]Feng Jianhong, Li Guoliang, Feng Jianhua. A survey on crowdsourcing[J]. Chinese Journal of Computers, 2015, 38(9): 1713-1726 (in Chinese)(馮劍紅, 李國良, 馮建華. 眾包技術(shù)研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(9): 1713-1726 )

[4]Kittur A, Nickerson J V, Michael S B. The future of crowd work[C]Proc of ACM Int Conf on Computer Supported Cooperative Work. New York: ACM, 2013: 1301-1318

[5]Gradiraju U, Demartini G D, Kawase R, et al. Human beyond the machine: Challenges and opportunities of microtask crowdsourcing[J]. IEEE Intelligent Systems, 2015, 30(4): 81-85

[6]Kargar M, An A. Discovering top-kteams of experts withwithout a leader in social networks[C]Proc of the 20th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2011: 985-994

[7]Juang Mingchin, Huang Chenche, Huang Jiunlong. Efficient algorithms for team formation with a leader in social networks[J]. Journal of Supercomputing, 2013, 66(2): 721-737

[8]Wang Xinyu, Zhao Zhou, Ng W. USTF: A unified system for team formation[J]. IEEE Trans on Big Data, 2016, 2(1): 70-84

[9]Yu Yan, Wang Ying, Liu Xingmei, et al. Workflow task assignment strategy based on social context[J]. Journal of Software, 2015, 26(3): 562-573 (in Chinese)(余陽, 王潁, 劉醒梅, 等. 基于社會(huì)關(guān)系的工作流任務(wù)分派策略研究[J]. 軟件學(xué)報(bào), 2015, 26(3): 562-573

[10]Gorge S, Bergmann R. Social workflows—Vision and potential study[J]. Information Systems, 2015, 50(1): 1-19

[11]Dorn C, Taylor R N, Dustdar S. Flexible social workflows: Collaborations as human architecture[J]. IEEE Internet Computing, 2012, 16(2): 72-77

[12]Tang Jintao, Wang Ting, Wang Ji. Shortest path approximate algorithm for complex network analysis[J]. Journal of Software, 2011, 22(10): 2279-2290 (in Chinese)(唐晉韜, 王挺, 王戟. 適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J]. 軟件學(xué)報(bào), 2011, 22(10): 2279-2290)

[13]Sun Huanliang, Jin Mingyu, Liu Junling, et al. Methods for team formation problem with grouping task in social networks[J]. Journal of Computer Research and Development, 2015, 52(11): 2535-2544 (in Chinese)(孫煥良, 金洺宇, 劉俊嶺, 等. 社會(huì)網(wǎng)絡(luò)上支持任務(wù)分組的團(tuán)隊(duì)形成方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(11): 2535-2544)

[14]Gubichev A, Bedathur S, Seufert S, et al. Fast and accurate estimation of shortest paths in large graphs[C]Proc of the 19th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2010: 499-508

[15]Tretyakov K, Armascervantes A, Garciabanuelos L, et al. Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs[C]Proc of the 20th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2011: 1785-1794

[16]Qiao Miao, Cheng Hong, Chang Lijun, et al. Approximate shortest distance computing: A query-dependent local landmark scheme[J]. IEEE Trans on Knowledge and Data Engineering, 2014, 26(1): 55-68

[17]Freeman L. A set of measures of centrality based upon betweenness[J]. Stoichiometry, 1977, 40(1): 35-41

[18]Brandes U. A faster algorithm for betweenness centrality[J]. Journal of Mathematical Sociology, 2001, 25(2): 163-177

[19]Kolaczyk E D, Chua D B, Barthelemy M. Group between-ness and co-betweenness: Inter-related notions of coalition centrality[J]. Social Networks, 2009, 31(3): 190-203

[20]Meng Xiaofeng, Li Yong, Zhu Jianhua. Social computing in the era of big data: Opportunities and challenges[J]. Journal of Computer Research and Developent, 2013, 50(12): 2483-2491 (in Chinese)(孟小峰, 李勇, 祝建華. 社會(huì)計(jì)算: 大數(shù)據(jù)時(shí)代的機(jī)遇與挑戰(zhàn)[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(12): 2483-2491)

[21]Kucherbaev P, Daniel F, Tranquillini S, et al. Crowdsourcing processes: A survey of approaches and opportunities[J]. IEEE Internet Computing, 2016, 20(2): 50-56

Sun Yong, born in 1977. PhD. Lecturer. Member of CCF. His main research interests include cooperative computing, service computing, social workflow scheduling, intelligent infor-mation systems and software engineering.

Tan Wenan, born in 1965. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include soft-ware engineering, process engineering and development environment, enterprise dynamic modeling, trusted service computation and enterprise intelligent information systems.

Cross-Organizational Workflow Task Allocation Algorithms for Socially Aware Collaborative Computing

Sun Yong1and Tan Wenan1,2

1(SchoolofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,Nanjing211106)2(CollegeofComputerandInformation,ShanghaiPolytechnicUniversity,Shanghai201209)

Recently, human-interactions are substantial part of Web service-oriented collaborations and cross-organizational business processes. Social networks can help to process crowdsourced workflow tasks among humans in a more effective manner. However, it is challenging to identify a group of prosperous collaborative partners with a leader to work on joint cross-organizational workflow tasks in a prompt and efficient way, especially when the number of alternative candidates is large in collaborative networks. Therefore, in this paper, a new and efficient algorithm has been proposed to find an optimal group in social networks so as to process crowdsourced workflow tasks. Firstly, a set of new concepts has been defined to remodel the social graph; then, a sub-graph connector-based betweenness centrality algorithm has been enhanced to efficiently identify the leader who serves as the host manager of the joint workflow tasks; finally, an efficient algorithm is proposed to find the workflow task members associated with the selected leader by confining the searching space in the set of connector nodes. Theoretical analysis and extensive experiments are conducted for validation purpose; and the experimental results on real data show that our algorithms outperform several existing algorithms in terms of computation time in dealing with the increasing number of workflow task executing candidates.

collaborative computing; team formation; task allocation; cross-organizational workflow; social network

2016-07-13；

2016-12-28

國家自然科學(xué)基金項(xiàng)目(61672022,61272036);安徽省高校自然科學(xué)基金重點(diǎn)項(xiàng)目(KJ2017A414) This work was supported by the National Natural Science Foundation of China (61672022, 61272036) and the Key Project of University Natural Science Foundation of Anhui Province (KJ2017A414).

TP391.1