支持社會協同計算的跨組織工作流任務分派算法

孫 勇 譚文安,2

1(南京航空航天大學計算機科學與技術學院 南京 211106)2 (上海第二工業大學計算機與信息工程學院 上海 201209)

支持社會協同計算的跨組織工作流任務分派算法

孫 勇1譚文安1,2

1(南京航空航天大學計算機科學與技術學院 南京 211106)2(上海第二工業大學計算機與信息工程學院 上海 201209)

(syong@nuaa.edu.cn)

針對社會協同計算帶來的不可靠性和社會網絡所固有的大規模性問題，提出了支持社會協同計算的跨組織工作流任務分派優化算法.首先，采用了基于工作流任務子網分層的優化模型，將復雜社會網絡圖進行有效地劃分，從而簡化了社會網絡成員的協作關系評估問題；然后，根據劃分后網絡的拓撲特征，設計了一種基于工作流任務子網連接點的快速介數中心性計算方法，以高效地選取跨組織業務項目的領導者；最后，采用基于任務子網劃分的最短路徑近似算法，實現了快速查找跨組織業務過程的協作成員；并且，理論證明了支持社會協同計算的工作流分派算法的可行性.實驗結果表明所提算法大幅降低了社會協同計算的復雜性，保證了較高的準確性，解決了工作流任務成員之間的關系評價和人工團隊組合優化的時效性問題，為社會協同計算的任務分派提供了一種新的思路.

協同計算；團隊組合；任務分派；跨組織工作流；社會網絡

完全自動執行的業務過程難以滿足所有實際社會協同計算應用的需求，復雜的社會協同計算系統中某些任務活動必須借助跨組織的專業人工服務才能圓滿完成[1-2].因此，為有效地解決機器難以實現的復雜問題，社會協同計算系統采用WS-BPEL工作流技術，通過將人工任務外包給專家社會網絡服務，實現社會成員之間的協同計算.在WS-BPEL工作流應用中，專家任務被定義為WS-BPEL工作流控制結構中的一個活動，社會協同計算系統通過調用專家服務解決跨組織業務中人工任務的執行問題，從而實現專家服務與業務過程之間的松散融合[1-2]，如圖1所示：

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

面向專家社會化網絡的協同計算模式從企業內部成員交互演變為跨組織之間的協作，導致組織模型呈現出動態性和不穩定性.跨組織工作流系統采用質量管理過程技術，實現跨組織業務質量的持續改進，為社會協同計算應用提供了有效的計算機技術支持.面向社會化網絡的工作流活動執行前需要分配人工任務，即在工作流任務和專家社會網絡之間建立映射關系，跨組織業務的任務分派問題已被證明是NP-hard問題.近年來，工作流任務分派模型構建及其算法優化成為了社會協同計算研究領域的難點和熱點問題[2-5]，例如，基于社會化網絡的眾包計算[3-5]和面向專家社會網絡的團隊組合發現[6-8].研究者通過探索社會科學知識、理論和方法學，借助基于服務的跨組織工作流技術，有效地促進了面向社會網絡的協同計算應用[9].

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

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

針對社會網絡所固有的數據大規模性問題，本文采用了基于工作流任務子網分層的優化模型，將復雜社會網絡圖進行有效地劃分，在此基礎上，提出了支持社會協同計算的跨組織工作流分派模型及其高效算法.本文的主要貢獻如下：

1) 基于工作流任務劃分的人工服務社會網絡設計了一種適用于工作流任務子網劃分的參考點選擇策略；

2) 綜合考慮劃分后社會網絡的拓撲特征，提出了基于工作流任務子網劃分的最短路徑近似計算方法，其中包括面向任務子網內部和不同任務子網之間的社會成員關系評測算法；創新性地提出了基于任務子網連接點的快速介數中性計算方法，該方法能夠高效率地優選出項目領導者；

3) 理論證明了所提出的社會協同計算方法的可行性;

4) 使用真實數據集仿真驗證分析了支持復雜社會協同計算的跨組織工作流任務分派算法的有效性.

1 基于工作流任務的社會網絡劃分

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

Fig. 2 Expert network graph based on partition with workflow tasks圖2 基于工作流任務劃分的專家社會網絡圖

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

假設跨組織工作流應用需要完成p個任務，可根據工作流任務將社會網絡劃分成p個任務子網絡，如果社會成員能夠完成工作流任務ti，則將該成員劃分到任務子網i中，相關概念和定義如下:

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

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

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

(1)

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

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

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

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

(2)

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

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

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

(3)

支持社會協同計算的跨組織工作流分派方法采用基于工作流任務子網劃分的分層優化思想，將復雜的社會網絡圖進行有效地劃分，依據劃分后網絡的拓撲特征，可簡化任務分派中社會成員節點之間的最短路徑近似計算和人工服務組合優化的問題，有利于降低大規模社會網絡中人工服務搜索算法的時間復雜度.

2 任務成員社會關系評測算法

社會關系直接影響著跨組織業務項目的執行質量，在社會網絡中，運用業務項目成員節點之間的最短路徑距離值來描述成員之間的社會關系，因此，支持社會協同計算的跨組織工作流任務分派方法采用社會網絡圖的最短路徑近似算法，實現工作流任務成員的社會關系評測.本節主要討論社會網絡成員節點之間的最短路徑快速計算問題.

2.1 基于參考點的最短路徑近似計算

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

定理1. 三角不等式.任取3個網絡節點s,u,t∈V，d(s,t)表示s與t之間的最短路徑距離，則有：

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

(4)

(5)

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

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

(6)

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

(7)

基于參考點的預先計算環節采用了深度優先算法，計算出參考點K={u1,u2,…,uk-1,uk}與網絡其他節點之間的最短路徑距離，根據三角不等式定理可知：

(8)

(9)

(10)

(11)

(12)

2.2 基于任務子網劃分的參考點選取

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

命題1. 在處理不同子網成員的社會關系評測時，采用基于參考點的最短路徑算法，并以工作流任務子網連接點作為參考點，稱之為基于任務子網連接點的最短路徑算法，該算法和Dijkstra最短路徑算法具有相同的準確度.

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

證畢.

Fig. 3 Reference point selection based task subgraph partition圖3 基于任務子網劃分的參考點選取示意圖

2.3 基于任務子網劃分的數據存儲

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

基于任務子網分層的存儲方案不需要存儲所有節點到參考點之間的最短路徑信息，只需按任務功能分類，存儲子網內部節點到相應參考點的信息，有效地減少了存儲空間；同時，在分析2個節點之間的最短路徑時，只需計算候選者節點到其任務子網連接點之間的最短距離，因此，提高了近似算法的計算效率.

2.4 不同子網成員的社會關系評測

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

2.4.1 基于任務子網連接點的最短路徑算法

證畢.

根據命題2分析，基于任務子網連接點的社會成員關系評測的實現描述如算法1：

算法1. 基于任務子網連接點的社會成員關系評測算法.

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

輸出：s,t兩點之間近似距離.

① 計算節點s和t到其所屬的任務子網的連接點集合connList；

② foreachconninconnListdo

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

⑤ end for

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

2.4.2 基于任務子網連接點的分層最短路徑算法

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

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

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

(13)

根據分層最短路徑的近似計算模型分析，基于任務子網連接點的分層最短路徑近似算法的實現步驟如算法2：

算法2. 基于任務子網連接點的分層最短路徑近似算法.

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

輸出：s,t兩點之間近似距離.

① 計算節點s到其所屬的任務子網i的連接點最短路徑ps→i Conn，其中iConn表示子網i的連接點；

② 計算節點t到其所屬任務子網j的連接點最短路徑pt→j Conn，其中jConn表示子網j的連接點；

③ 計算子網連接點之間的最短路徑pi Conn→j Conn；

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

2.4.3 基于任務子網距離的最短路徑近似算法

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

定義7. 任務子網距離.給定任意2個工作流任務子圖SubGH1,SubGH2，則有任務子網距離可定義為

(14)

其中，CN(SubGH1)是子網SubGH1連接點集合，CN(SubGH2)是子網SubGH2連接點集合.

2.5 子網內部成員的社會關系評測

基于任務子網連接點的最短路徑近似算法適用于評測不同子網的成員關系，但不能準確地評測同一子網內部的成員關系，因此，本節內容主要討論關于任務子網內部的成員關系評測算法，相關定義如下[16]：

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

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

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

(15)

命題3. 給定某一任務子圖GH=(VH,EH,WH)、子網連接點集合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)，

進一步計算可得

，

則可得

證畢.

為了快速地評測子網內部成員的關系，根據命題3分析，子網內部成員的關系評測算法可計算為

(17)

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

根據式(15)～(17)分析，本文采用了基于最近公共祖先的最短路徑算法，評測子網內部社會成員關系.運用基于任務子網分層的存儲方案存儲每個子網參考點到任務子網內部節點之間的最短距離和最短路徑.因此，所提出的子網內部的任務成員關系評測算法只需直接從分層存儲文件中查詢，即可快速準確地評測出同一子網內部成員之間的關系.

3 跨組織工作流任務分派優化算法

為確保跨組織業務項目的順利進行，要求項目領導者能夠協調好不同組織成員之間的關系，即優選出的領導者必須與每個任務協作伙伴成員之間具有良好密切的社會關系.因此，在面向大規模社會網絡進行協同計算時，跨組織工作流分派優化算法需解決2個問題：1)如何從大規模專家社會網絡中快速地選擇出領導者節點，從而負責分派任務并協調管理任務協作伙伴成員之間的交互；2)如何從大規模專家社會網絡中高效率地選擇工作流任務協作伙伴，確保任務協作成員與領導者之間協同工作的效率.

傳統帶領導節點的團隊任務分派采用了蠻力法(Brute-Force)實現[6].Brute-Force算法以所有的社會網絡成員作為領導候選者；然后，遍歷社會網絡中子任務對應的全部候選者節點，查詢出與領導者溝通代價最優的子任務協作伙伴；最后，通過比較所有的專家服務組合方案，優選出領導者及相應任務協作成員節點的團隊組合，其中子任務協作成員與領導者之間的協同交互成本越低越好.

根據定義10分析，跨組織工作流活動執行前需要分派人工任務，即在工作流任務和專家社會網絡之間建立映射關系，形成協同成本最優的專家團隊組合，從而保證跨組織工作流專家服務資源的合理配置.實質上，支持社會協同計算的跨組織工作流任務分派是一個面向社會網絡的團隊組合求解問題.

問題1. 專家團隊組合求解.給定跨組織工作流任務Task和一個候選專家社會網絡G，支持社會協同計算的跨組織工作流任務分派模型主要目標是：搜尋一組專家團隊成員，團隊成員的所有技能滿足跨組織項目任務Task的需求，并使得跨組織項目團隊的協同交互成本最小，形式化定義如下：

(18)

(19)

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

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

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

通過觀察工作流任務子網劃分的社會網絡特征，我們發現：任務子網連接點總存在于2個不同任務子網節點之間的最短路徑上，2個子網候選節點的交互必然會經過子網的連接點.因此，領導者與其他任務子網的所有節點之間的最短路徑必然會經過子網連接點.如圖4所示，任務子網GroupA的連接點a在領導節點leader與GroupA中所有節點之間的最短路徑上.

Fig. 4 Example of finding workflow task members圖4 工作流任務協作成員選擇實例

基于劃分后社會網絡特征分析，任務協作伙伴節點必然是任務子網連接點之一，因此，社會協同計算方法在為領導者查找任務協作伙伴時，只需在任務子網連接點集合中搜索，簡化了工作流任務分派算法的復雜度.

命題4. 給定某一任務子圖SubGH=(VH,EH,WH)，已選領導者節點leader?VH，子網連接點集合R?VH,設與領導節點交互成本最優的子任務協作者為mem，則有mem∈R.

證明. 假設mem∈VH是任務子網SubGH所選出的任務協作者，且mem?R.由于leader?VH,不同任務子網成員之間的最短路徑必然經過連接點，因此，存在連接點conn∈R，且conn在leader與mem節點之間的最短路徑上.

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

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

因此，只有當mem∈R時，候選節點mem才是團隊最優的任務協作者.

證畢.

由命題4分析可知，社會協同計算應用只需在工作流任務子網連接點集合中搜索子任務協作伙伴，減少了任務協作伙伴的搜索時間，提高了社會協同計算的時間效率.而且，從命題4的結論反推，逆向思考可知，距離所有任務子網連接點越近的社會成員節點，越有可能被選作為領導者節點，因為，社會協同計算模型要求所選取的領導者必須與每個任務協作伙伴成員之間具有良好密切的社會關系.受此啟發，根據工作流任務劃分后的社會網絡特征，在借鑒Brandes算法思想的基礎上，本文創新性提出了一種基于任務子網連接點的快速介數中心性算法，用于快速地搜索領導者節點.

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

(20)

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

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

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

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

(21)

則有

(22)

因為到達節點u的最短路徑也通過邊(u,w)到達節點w，在進行Dijkstra算法遍歷時，可根據式(21)(22)，計算出從任務子網連接點出發經過每個節點最短路徑數量.Dijkstra算法復雜度為O(m+nlogn)，因此，采用基于任務子網連接點的快速介數中心性算法分析時，經過社會網絡圖中候選節點的最短路徑數量的統計時間復雜度為O(Rnum×m+Rnum×nlogn).

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

(23)

根據式(20)～(23)分析，根據節點依賴度的定義，可推導出命題5.

命題5. 假定工作流任務子網連接點conn∈R，在社會網絡中conn經過節點v到其他成員節點存在著最短路徑，則可知節點v的介數中心性可滿足：

ζ(conn|v)=

(24)

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

因為

σ(conn,t|v,w)=

則有

整理可得

根據節點模型依賴度定義，可知

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

因此，

又因為

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

fort=w，

則有

即

證畢.

由命題5分析可知，領導節點計算方法為

(25)

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

算法3. 基于任務子網連接點的介數中心性算法.

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

輸出：Top-k領導者節點集.

① 基于任務的社會網絡劃分：GH=(VH,EH,WH)←(V,E,W)；

② foreachconn∈Rdo*遍歷所有子網連接點*

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

④ 存儲w前驅節點：P[w]←v；

⑤ 統計通過w的最短路徑數量：σ[w]←σ[w]+σ[v]；

⑥ 將從起點到當前點的距離壓入棧：S←v；

⑦ end for

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

⑨ whileS≠null do

⑩ 出棧：w←S；

基于任務子網連接點的介數中心性算法的時間復雜度為O(Rnum×m+Rnum×nlogn).當基于任務劃分的社會網絡中連接點非常少時，相比Brandes算法，所提出的領導者評價算法具有良好的時間性能.

在確定領導者后，根據命題4，支持社會協同計算的工作流分派方法的具體實現步驟如算法4.

算法4. 支持社會協同計算的工作流任務分派算法.

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

輸出：跨組織工作流協同計算解決方案wSolution.

① 基于任務子網連接點的介數中心性算法：leader←getLeader(GH)；

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

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

④ 基于子網劃分的任務協作者遍歷搜索算法；

⑤ foreachTaskinrequiredTasksdo*遍歷跨組織工作流所有任務*

⑥ ifTaskinTaskListthen

⑦ continue；

⑧ end if

⑨ 獲取工作流任務子網對應的所有連接點：memList←getConnectors(Task)；

⑩ formeminmemListdo*遍歷任務子網連接點*

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

4 仿真實驗

4.1 數據準備與分析

Table 1 DBLP Data Analysis

假定面向專家社會網絡的跨組織業務應用需要6個不同研究方向的專家服務，以協同完成跨組織工作流的所有任務，其中包括算法(AL)、軟件工程(SE)、數據庫系統(DB)以及Web程序設計(Web)等方面的專家，如圖5所示：

Fig. 5 Cross-organizational workflow application for expert tasks圖5 面向人工任務的跨組織工作流應用實例

仿真實驗首先按照文獻[6]方法生成了DBLP專家社會網絡圖，然后采用了本文第1節闡述的基于任務的社會網絡劃分方法，根據每個候選者節點的功能角色劃分出不同任務子網，劃分后專家社會網絡如圖6和圖7所示.

Fig. 6 Graph grouped by task types圖6 基于任務的子網劃分

Fig. 7 Graph classified by connectors圖7 基于連接點的成員分類

圖6中不同顏色表示不同任務子網.社會協同計算的相關算法都涉及到基于任務子網連接點的分析方法.因此，在工作流任務子網劃分圖的基礎上，可視化仿真實驗根據任務子網連接點對所有的社會成員節點進行了分類，如圖7所示.其中，所有紅色圖形都表示工作流任務子網連接點，不同圖案表示不同任務候選者節點.由可視化分析實驗可知，工作流任務子網連接點存在于2個不同子網之間，而且，其數量遠小于非連接點.

4.2 社會關系評測算法分析

本節仿真實驗分析了本文所提出的社會關系評測算法，驗證了該算法在社會網絡環境下解決社會工作流任務分派問題的可行性，其中，共設計了2個實驗：實驗1主要是分析了不同子網社會成員之間的關系評測算法；實驗2則主要是分析了子網內部社會成員之間的關系評測算法.根據最短路徑近似算法獲取社會成員的關系評價值，采用式(26)評估最短路徑近似算法的正確率.

(26)

實驗1. 不同任務子網社會成員的關系評測算法分析驗證.

按表1和基于任務的社會網絡劃分方法構建了不同規模的DBLP專家網絡，隨機選取2個任務子網，采用本文提出的近似最短路徑算法，計算出不同子網之間的所有節點的最短距離值.實驗1采用柱狀圖分析了基于任務子網連接點的最短路徑計算方法(ConnSPT)、基于任務子網連接點的分層最短路徑計算方法(LayeredSPT)以及基于任務子網距離的最短路徑近似計算方法(LTaskSPT)的正確率，如圖8所示.

Fig. 8 Correctness verification of different group member relation圖8 不同子網的社會關系評測算法正確率分析

通過觀察圖8可知，基于任務子網連接點的最短路徑算法的準確率為1；基于任務子網連接點的分層最短路徑算法也有較好的準確率，其準確率的平均值達到了0.97；基于任務子網距離的最短路徑近似算法的正確率相對較差，其準確率的平均值為0.72.實驗結果表明ConnSPT算法的正確率最好，而LTaskSPT算法的正確率是3種近似算法中相對較差的.

算法的時間性能是評價面向復雜社會網絡的成員關系評測算法可行性的重要指標.為檢驗所提近似算法在不同網絡規模下的性能，仿真實驗采用6種不同規模的社會網絡分析了所提算法的性能，如圖9和10所示.

Fig. 9 Performance evaluation of group member relation圖9 不同子網的社會關系評測算法性能分析

通過觀察圖9可知，本文提出的3種不同任務子網社會成員的社會關系評測算法的時間性能明顯優于精確的最短路徑計算方法.而且，隨著專家候選者的數量不斷增多時，所提算法的性能優勢表現得更加顯著.實驗結果表明，精確的最短路徑算法的時間花費遠大于所提近似算法的時間花費.

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

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

由圖10可知，基于任務子網距離的最短路徑近似算法的性能效率最優，基于任務子網連接點的分層最短路徑算法次之，而基于任務子網連接點的最短路徑算法效率相對差一些.與算法準確率實驗表現出的情況剛好相反，因此，我們可以根據業務的需要，選擇適合的社會關系評測方法.

實驗2. 子網內部社會成員關系評測算法分析.

采用與實驗1同樣的方法，設置了不同規模的DBLP專家網絡，任取一子網，采用本文所提的子網內部社會成員關系評測算法，計算子網內部不同節點的最短路徑距離值.實驗2采用柱狀圖分析了基于最近公共祖先的最短路徑算法(LCASPT)和基于任務子網連接點的最短路徑算法(ConnSPT)的正確率.如圖11所示，基于最近公共祖先的最短路徑算法正確率接近1；基于任務子網連接點的分層最短路徑算法也有較好的正確率，正確率在0.6上下，不適用于同一子網關系評測.

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

實驗1和實驗2驗證分析了本文提出的社會關系評測算法，實驗結果表明，本文提出的社會成員評測算法具有良好的時間性能，保證了較高的精確度，為面向大規模社會網絡的跨組織工作流任務分派提供了技術支持.

4.3 支持社會協同計算的工作流任務分派算法分析

仿真實驗進一步通過分析社會工作流的協同模型算法，驗證了所提出的算法在復雜社會網絡環境下解決工作流多任務外包問題的可行性.為此，設計了3個方面實驗，其中，實驗3主要驗證了基于任務子網連接點的介數中心性算法的性能效率，即分析領導者選取算法的效率問題；實驗4分析了基于子網劃分的任務協作者遍歷搜索算法的性能效率；實驗5驗證了面向社會工作流的協同計算模型算法的正確性.

實驗3. 基于任務子網連接點的介數中心性算法的性能效率分析.

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

Fig. 13 Performance evaluation of leader selection圖13 領導者選取算法性能分析

Fig. 14 Performance evaluation of group member discovery圖14 任務協作者搜索算法性能分析

實驗4. 基于子網劃分的任務協作者遍歷搜索算法性能分析.

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

實驗5. 社會工作流任務分派算法的正確性驗證.

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

Fig. 15 Correctness verification of social workflow task allocation圖15 社會工作流的任務分派算法正確性驗證

實驗結果表明本文所提出的跨組織工作流任務分派算法，大幅降低了工作流任務分派的時間成本，并能保持較高的算法精度，適用于大規模社會網絡的協同計算問題.但存在2點不足：1)算法結果還不夠精確，應更進一步提高；2)當工作流任務子網連接點數目很多時，所提算法的時間效率仍會不理想，應設計出不同的應對解決方案.

5 結 論

復雜社會網絡所固有的大規模性特征給支持社會協同計算應用的算法性能提出了更高的要求.針對面向大規模社會網絡的跨組織工作流人工任務分派問題，提出了一種支持社會協同計算的跨組織工作流分派優化算法，采用了基于工作流任務子網的分層優化思想，有效地劃分復雜社會網絡圖，簡化了最短路徑的近似計算問題；并依據劃分后人工服務社會網絡的拓撲特征，改進了快速介數中心性算法，設計了一種新穎的基于任務子網連接點的快速介數中心性計算方法，高效地選取跨組織業務項目的領導者；然后，采用基于任務子網劃分的最短路徑近似算法，實現了快速查找跨組織業務項目的協作成員；理論證明和仿真實驗表明所提出分派方法具有良好的算法性能，并保持較高的算法精度，有效地解決了跨組織工作流任務成員之間的關系評價和人工服務組合優化的時效性問題，適用于復雜的大規模社會網絡協同計算.

[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)(馮劍紅, 李國良, 馮建華. 眾包技術研究綜述[J]. 計算機學報, 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)(余陽, 王潁, 劉醒梅, 等. 基于社會關系的工作流任務分派策略研究[J]. 軟件學報, 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)(唐晉韜, 王挺, 王戟. 適合復雜網絡分析的最短路徑近似算法[J]. 軟件學報, 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)(孫煥良, 金洺宇, 劉俊嶺, 等. 社會網絡上支持任務分組的團隊形成方法[J]. 計算機研究與發展, 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)(孟小峰, 李勇, 祝建華. 社會計算: 大數據時代的機遇與挑戰[J]. 計算機研究與發展, 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

國家自然科學基金項目(61672022,61272036);安徽省高校自然科學基金重點項目(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