基于偏序任務的社會網絡合作算法研究

劉 勇 韓 雪 李金寶 任倩倩 王 楠

(黑龍江大學計算機科學技術學院 哈爾濱 150080)(黑龍江省數據庫與并行計算重點實驗室(黑龍江大學) 哈爾濱 150080)(acliuyong@sina.com)

?

基于偏序任務的社會網絡合作算法研究

劉 勇 韓 雪 李金寶 任倩倩 王 楠

(黑龍江大學計算機科學技術學院 哈爾濱 150080)(黑龍江省數據庫與并行計算重點實驗室(黑龍江大學) 哈爾濱 150080)(acliuyong@sina.com)

針對不同任務之間通常存在偏序關系這種實際情況，提出了基于偏序任務的社會網絡合作問題(collaboration problem in social networks based on tasks with partial ordering relations, CSN-TPR).該問題研究如何從社會網絡中選擇合適的團隊來合作完成具有偏序關系的任務集，使得由通信代價、時間代價和預算代價構成的總體代價性能最優.首先證明了CSN-TPR是NP-hard問題，然后利用爬山法、分支限界策略和動態規劃方法提出了近似算法HillClimbingTF_BBS.HillClimbingTF_BBS算法不僅輸出有效的團隊，而且能給出團隊成員的具體任務分配以及每項任務的開始時間. 真實數據上的實驗結果表明： HillClimbingTF_BBS算法能有效并高效求解CSN-TPR.

社會網絡；合作；偏序關系；爬山法；分支限界

隨著社會的發展，項目的規模越來越大，社會成員間的合作愈顯重要.傳統的合作問題[1]研究給定項目P(P中包含若干個任務)，候選人集合S以及S中每個人所會的任務集合，選擇一個能完成項目P的團隊，使得某個目標最優(例如完成項目時間最短或者項目花費最小).但是，這種方法忽略了團隊內部個體間的合作程度，若團隊內個體間互不熟悉或有矛盾，那么所選擇的團隊未必是一個最佳團隊.

近年來，由于大規模社交網站(如Facebook、Twitter、人人網等)變得非常流行，基于社會網絡的合作問題逐漸成為了數據挖掘領域的熱點研究內容[2-5].基于社會網絡的合作問題定義如下：給定社會網絡G=(V,E)，V中每個個體所會的任務集，以及由若干個任務構成的項目P，要求從V中選擇一個團隊T.在完成項目P的前提下，使團隊T中成員間的通信代價盡可能小.通信代價可以使用最小生成樹、Steiner樹、密度、直徑等多個標準度量[6-7].針對該問題，已經提出了多個問題變體和多種解決方法.

然而，已有研究工作在選擇團隊時只考慮完成項目中的所有任務，并沒有考慮任務間可能具有先后順序，某些任務只有在前序任務完成后才能開始.例如：在建樓過程中，如圖1所示，首先要打地基，才能開始后續工作，樓主體結構建成后才能安裝門窗和管道.沒有先后順序要求的工作又可以并行進行以提升整個工程的進度，如安裝門窗和管道可以同時實施.這種任務間具有偏序關系的項目在實際應用中普遍存在.對于這樣的項目，在構建團隊時，不僅要完成所有任務，還要根據任務間的偏序關系給出團隊成員的具體任務分配，使得整個項目的完成時間最短.

Fig. 1 An example for tasks with partial relations.圖1 偏序任務示例

除了整個項目的完成時間，團隊成員間的合作程度、項目的成本也是影響整個項目的重要因素，是管理者需要考慮的重要問題.因此，為了有效完成項目，最佳的團隊必須綜合考慮團隊的時間代價、通信代價和預算代價3方面因素，使得總體代價最優.每部分代價在總體代價中所占的比重可以根據實際項目的需要由管理者自己選擇.本文主要研究如何從社交網中選擇合適的團隊來合作完成帶有偏序關系的任務集(項目)，使得總體代價最優，其主要貢獻有3點：

1) 提出了基于偏序任務的社會網絡合作問題(collaboration problem in social networks based on tasks with partial ordering relations, CSN-TPR)，并證明了該問題是NP-hard問題.

2) 利用爬山法、分支限界策略及動態規劃方法提出了一個求解CSN-TPR問題的高效算法HillClimbingTF_BBS.該算法不僅輸出有效的團隊，而且給出團隊成員的具體任務分配以及每項任務的開始時間.

3) 真實數據上的實驗結果表明：HillClimbingTF_BBS算法能有效并高效求解CSN-TPR問題，此外，還通過實驗給出了HillClimbingTF_BBS算法的聯機近似比.

1 相關工作

社會個體如何合作高效完成任務一直是學術界的熱點研究內容，因為其具有極大的社會需求和廣泛的應用前景.例如：Meetup和Google都已經開發了活動合作功能，用于安排活動時間和活動參與者.

自2004年團隊構建概念提出后[1]，合作研究迅速成為了一個熱門的研究領域，已經提出很多成熟高效的算法.大部分研究工作僅以團隊完成既定任務為目標，沒有考慮社會成員間的社會關系和以往的合作程度[8].近些年來的研究工作在原有合作問題的基礎上進行了擴展，在完成任務的前提下盡可能降低成員間的通信代價.Lappas等人[2]首次提出了基于社會網絡的合作問題，根據社會成員間以往的合作程度，并利用最小生成樹、Steiner樹、直徑等標準度量通信代價[6-7]，研究如何構建通信代價最小的團隊.Datta等人[3]對社會網絡合作問題加入任務負載平衡的限制.Rangapuram等人[4]和Gajewar等人[9]基于稠密子圖定義通信代價，研究了社會網絡合作問題.Yang等人[10]在構建團隊時除了優化通信代價，也把完成任務的時間作為一個優化目標.Li等人[11]對任務給出了限制條件，規定每個任務所需的人員數，運用劃分的方法求解社會網絡合作問題.Kargar等人[5]綜合考慮通信代價和成員報酬，提出了一個雙目標的組合優化.Farhadi等人[12]和Sozio等人[13]利用社團劃分方法來求解社會網絡合作問題，在劃分后的社團上構建團隊不僅提高了挖掘效率，同時保證了結果的準確性.Anagnostopoulos等人[14]在大規模社會網絡上進行社團劃分，使得團隊構建問題可應用于大規模網絡.Sun等人[15]最近提出了社會網絡上支持任務分組的團隊構建問題并給出了有效的算法.

然而，已有研究工作并沒有考慮完成任務先后順序的限制，本文將針對帶有偏序關系的任務集，定義社會網絡合作問題，并提出有效算法求解該問題.

2 預備知識

本節描述文中所用的符號定義以及本文算法所用的2個樹搜索策略.

2.1 符號定義

G(V,E)表示無向加權圖，其中V為個體集，E為邊集.d(i,i′)表示在圖G中個體i到i′的最短距離.

P(T,R)表示項目(有向無環圖)，T?A表示項目中的任務集，R表示任務之間的偏序關系.k表示項目P中的任務數,即|T|=k.Cc(V′)表示團隊V′的通信代價，即V′中個體構成最小生成樹邊上的權值和.Ct(V′)表示團隊V′的時間代價，即完成項目所需最長時間.Cb(V′)表示團隊V′的預算代價，即每個個體完成相應任務所需薪資總和.

2.2 爬山法與分支限界策略

本文中將采用爬山法解決帶有任務偏序關系的社會網絡合作問題.爬山法是一種深度優先樹搜索算法.初始化時，構造由根節點組成的單元素棧S.在搜索過程中，判斷棧頂元素p是否為目標節點，如果是，則返回目標節點搜索結束；否則彈出棧頂元素p，將p的子節點按照其啟發測度由大到小(或由小到大)的順序壓入棧S，繼續搜索過程.顯然，在深度優先樹搜索過程中，爬山法使用貪心方法確定搜索的方向，是優化的深度優先搜索策略.

本文將采用分支限界法縮小搜索空間，提高算法效率.分支限界法常以廣度優先或以最小耗費(最大效益)優先的方式搜索問題的解空間.每一個活節點只有一次機會成為擴展節點，活節點一旦成為擴展節點，就一次性產生其所有孩子節點.在這些孩子節點中，導致不可行解或導致非最優解的孩子節點被舍棄，其余孩子節點被加入活節點表中.此后，從活節點表中取下一節點成為當前擴展節點，并重復上述節點擴展過程.這個過程一直持續到找到所需的解或活節點表為空時為止.

3 問題定義

在完成具有偏序關系的任務集而構建團隊的前提下，比較合理并且實際的目標是找到的團隊不僅通信代價小，而且所花費時間和預算都盡可能小.

為了找到低通信代價、低預算、高效率的合作團隊，本文給出了基于偏序任務的社會網絡合作問題(CSN-TPR)，定義如下：

定義1. 給定社會網絡G(V,E)，任務域A，每個個體所會的任務集Task(V)={X1,X2,…,Xn}以及項目P(T,R)，目標是找到一個團隊V′?V和對該團隊V′的具體任務分配，使得3個條件成立：

2)V′中個體完成任務的順序應滿足項目P(T,R)中要求的偏序關系R；

3) 總代價αCc(V′)+βCt(V′)+(1-α-β)Cb(V′)最小.

在上面的問題定義中，所找團隊V′?V要滿足3個條件：1)V′中所有個體被分配的任務集合可以覆蓋項目P(T,R)中的任務集T.2)對T中任意任務Ti和Tj，如果在偏序關系R中Ti在Tj之前，那么Ti的完成時間應早于Tj的開始時間.注意：本文算法不僅找到所需團隊，而且可以確定任務對團隊成員的具體分配以及每個任務的開始和完成時間.3)本文綜合考慮團隊的通信代價Cc(V′)、時間代價Ct(V′)和預算代價Cb(V′)，使得總代價盡可能小.其中，Cc(V′)可用最小生成樹或直徑等標準衡量[6-7]，Ct(V′)是項目最后的完成時間，Cb(V′)是團隊成員完成任務的薪資總和.α,β是平衡各部分代價的參數，根據具體的項目由管理者來確定.由于不同代價的度量范圍不同，本文將社會圖中權值統一為1～10范圍內的數，個體完成任務的時間和所需薪資都統一為1～10范圍內的數，這樣可以用平衡參數計算總代價.

圖2給出了一個具體的例子，社會網絡G(V,E)如圖2(a)中所示，要完成的項目P(T,R)如圖2(b)中所示.其中，任務集合T={j1,j2,j3,j4}，偏序關系R={〈j1,j3〉,〈j1,j4〉,〈j2,j4〉}.每個個體所會任務集如下：X1={(j1,4,3),(j2,2,3),(j3,5,1)}，X2={(j3,2,2),(j4,1,5)}，X3={(j1,4,2),(j2,3,3)}，X4={(j3,3,2)}，X5={(j4,2,2)}，平衡參數α=0.3，β=0.4.

Fig. 2 The input for CSN-TPR.圖2 CSN-TPR問題的輸入

表1對上面的例子給出了2個候選團隊，每個任務的具體分配以及任務開始和完成時間.在團隊Team1中，任務j1由個體3來完成，薪資為4;任務j2由個體1來完成，薪資為2;任務j3由個體2來完成，薪資為2;任務j4由個體5來完成，薪資為2，所以預算代價Cb(V′)=4+2+2+2=10.個體3，1，2，5在社會網絡(如圖2(a)所示)中構成的最小生成樹權為1+1+2=4，所以通信代價Cc(V′)=4.整個項目的最后結束時間是5，所以Ct(V′)=5.因此總代價為0.3×4+0.4×5+(1-0.3-0.4)×10=6.2.用類似的方法可計算團隊Team2的總代價為8.3.注意：在任務分配時，多個任務可以分配給同一個個體，如Team2中任務j1和j2都分配給了個體1.這時任務j1和j2不能像Team1那樣同時被執行，必須有先后順序.在計算個體1，4，2構成的最小生成樹時，盡管個體4和個體1，個體4和個體2不直接相連，但可以計算個體4和個體1的最短路徑d(4,1)=5，個體4和個體2的最短路徑d(4,2)=4.個體1，4，2構成的最小生成樹的權為d(4,2)+d(1,2)=7.因此，Team2中的通信代價為7.

Table 1 Two Selected Teams for the Problem Shown in the Fig.2

定理1. 基于偏序任務的社會網絡合作問題CSN-TPR是NP-hard問題.

證明. 如果項目中的各個任務獨立，沒有偏序關系，同時忽略時間代價和預算代價，只考慮通信代價(通過設置平衡參數α=1，β=0,總代價就是通信代價)，那么本文所提出的問題CSN-TPR等價于Lappas等人在文獻[2]中提出的原始社會網絡合作問題Mst-Tf.也就是說，對Mst-Tf問題的任何一個實例，通過取α=1，β=0，就可以在多項式時間內變換成CSN-TPR問題的一個實例.因此，Mst-Tf問題可以在多項式時間內規約到CSN-TPR問題.因為Mst-Tf問題是NP-hard[2]，所以CSN-TPR問題也是NP-hard.

證畢.

4 算 法

針對CSN-TPR問題，本文采用爬山法進行任務樹搜索，利用分支限界策略進行剪支，提出了HillClimbingTF_BBS算法.由于在CSN-TPR問題中，任務集具有嚴格的偏序關系，所以時間代價的計算不能單純地進行串行累加計算，本文應用動態規劃方法來計算時間代價.

4.1 HillClimbingTF_BBS算法

根據任務間的偏序關系，可建立一棵搜索樹.例如：根據圖2(b)的偏序關系可建立搜索樹如圖3所示.利用爬山法進行樹結構搜索，每步分支都選擇當前所有可擴展分支中使得總代價最小的節點去擴展.設當前構建的部分團隊為V′,則每步分支都應選擇使總代價C(V′∪i)=αCc(V′∪i)+βCt(V′∪i)+(1-α-β)Cb(V′∪i)最小的節點i去擴展.

Fig. 3 Searching tree for the tasks.圖3 任務的搜索樹

當任務數過多、偏序關系過于復雜而且社會網絡節點過多時，算法的執行效率會由于搜索樹的結構過大而降低.在算法中加入分支限界策略，對不可能產生最優解的分支提前剪支可以極大地提升算法效率.

如圖4所示，本文采用爬山法進行深度優先搜索，當擴展到葉節點j4時，記錄當前的一個總代價值cost=6.6；當回溯到另一分枝考慮j2節點時，若當前團隊的代價值cost=6.8，表示再向下擴展節點時，總代價不可能小于6.8，所以此分枝不可能產生最優解，通過分支限界法將此分枝裁剪掉.

Fig. 4 The pruned searching tree.圖4 被裁剪的搜索樹

在圖4中，每個節點都對應著一個完成該任務的個體，然而root所對應的個體應如何選擇？本文將root節點所對應的個體設定為整個團隊的leader.在實際應用中leader通常由管理層指定，無需選擇.但CSN-TPR問題定義中沒有給出leader，需要選取leader.選取leader通常需要考慮3方面因素：1)該個體認識的成員相對較多，也就是圖G中度較大的節點；2)所會任務相對較多；3)完成所會任務的平均時間相對較短.為了將這3方面因素都考慮到leader的選取中，本文又引入平衡參數γ和μ(γ,μ∈[0,1],γ+μ≤1)來平衡這3方面因素，leader選取算法偽代碼如算法1所示：

算法1.leader選取算法.

輸入:G(V,E)，Task(V)={X1,X2,…,Xn}，γ，μ；

輸出:leader.

①max_power=0；

② fori∈Vdo

③Degree=節點i在圖G中的度數；

④CoverRatio=10×i所會任務數/任務總數；

⑤TaskTime=10/i做所會任務平均時間；

⑥i_power=γ×Degree+μ×CoverRatio+

(1-γ-μ)×TaskTime；

⑦ ifi_power>max_powerthen

⑧max_power=i_power；

⑨leader=i；

⑩ end if

利用爬山法進行樹結構搜索過程中，需要計算團隊的通信代價.本文采用最小生成樹的權值作為通信代價[2].為快速計算通信代價，本文對圖G中每個節點到其他節點的最短距離預先計算并存儲.求解CSN-TPR問題的HillClimbingTF_BBS算法偽代碼如算法2所示：

算法2. HillClimbingTF_BBS算法.

輸入:G(V,E),Task(V)={X1,X2,…,Xn},P(T,R)；

輸出:Team，Allocation.

① 初始化優先級隊列Q[0],Q[1],…,Q[k]=?，初始化Team，Allocation，V′=?；

② 使用算法1選取leader；

③leader放入Q[0]；

④Team,Allocation=HillClimbing_BBS(0,V′)；

⑤ returnTeam,Allocation.

在算法2中，步驟①為初始化工作.因為在搜索樹的每一層都需要1個優先級隊列，存儲當前任務的所有后繼任務和完成后繼任務的最優個體以及對應的代價，所以初始化k+1個優先級隊列Q[0],Q[1],…,Q[k]，其中k為任務數.Team記錄算法選擇的優化團隊，Allocation記錄為優化團隊成員分配的任務以及對應的時間和預算等信息，V′記錄當前構建的部分團隊.步驟③調用遍歷任務搜索樹的遞歸算法HillClimbing_BBS，其偽代碼如算法3所示：

算法3. HillClimbing_BBS算法.

輸入:h，V′；

輸出:Team，Allocation.

① ifh=kthen /*k為任務數*/

②Node=Q[h].Pop( )；

③V′=V′∪Node；

④ ifC(V′)

⑤mincost=C(V′),Team=V′；

⑥ 在Allocation中記錄Node的任務、時間和預算分配；

⑦ end if

⑧h=h-1；

⑨ HillClimbing_BBS(h,V′Node)；

⑩ end if

擴展*/

節點)；

4.2 動態規劃求解時間代價

完成每項任務的人員一旦確定，完成每項任務的時間也就確定了.圖5(a)給出了一個偏序任務集，每項任務的執行時間在任務旁邊列出.

Fig. 5 Tasks with partial relation and weighted graph.圖5 任務偏序集和對應的加權圖

由于任務之間具有嚴格的偏序關系，某些任務的開始執行必須在所有前驅任務完成之后，如圖5(a)中j4的開始時間應為j1和j2中最后完成的時間，所以時間代價不能是最長任務的執行時間.又由于有些任務沒有先后順序可以并行執行，如圖5(a)中j1和j2，所以時間代價也不應該是每項任務執行時間之和.對于具有偏序關系的任務集合，時間代價應為整個項目最后完成的時間.對圖5(a)中的偏序任務集，因為j1和j2可以同時執行，j1和j2完成后才可以執行j4，所以整個項目的完成時間為3+2=5，圖5(a)中的偏序任務集的時間代價等于5.

我們使用動態規劃方法計算偏序任務集的時間代價.對于任何偏序任務集，可以構造一個帶有源點和終點的加權圖.例如：對圖5(a)中的偏序任務集，構造的加權圖如圖5(b)所示.這時，求偏序任務集的時間代價就等價于在加權圖中計算從源點S到終點T的最長路徑長度.例如，計算圖5(a)中的偏序任務集的時間代價等價于計算圖5(b)中從源點S到終點T的最長路徑長度.

設L(u,v)表示加權圖中從節點u到節點v的最長路徑長度.對于圖5(b)中的加權圖顯然有：

L(S,T)=max{0+L(j1,T),0+L(j2,T)}，

L(j1,T)=max{1+L(j3,T),1+L(j4,T)}，

L(j2,T)=max{3+L(j4,T)}.

容易驗證在有向加權圖中求從源點到終點的最長路徑長度問題滿足最優子結構，重疊子問題條件，因而可用動態規劃進行求解.

設Gw表示從任務的偏序集構造的帶有源點S和終點T的加權圖.l表示從源點S到達終點T的最多邊數.令L(u,T)表示從節點u到終點T的最長路徑長度；next(u)表示從節點u到終點T的最長路徑上u的后繼節點.令LV(i)表示最多經過i條邊到達終點T的節點集合.動態規劃方法計算時間代價的偽代碼如算法4所示：

算法4. 計算時間代價的算法.

輸入:Gw； /*加權圖*/

輸出: 源點S到終點T的最長路徑長度length.

① fori=2 tol

② foru∈LV(i)

⑤ end for

⑥ end for

⑦length=0,u=S；

⑧ fori=1 tol

⑨length=length+d(u,next(u))；

⑩u=next(u)；

4.3 算法復雜度分析

HillClimbingTF_BBS算法預先計算圖G中每個節點到其他節點的最短距離，可以對每個節點調用DIJKSTRA算法或者直接使用FLOYD算法，時間復雜性為O(n3)，其中n為圖G中節點數.

在計算個體i加入當前團隊V′的總代價時，需要計算通信代價、預算代價、時間代價.通信代價可以使用Prim算法計算最小生成樹獲得，時間復雜性為O(k2)，其中k為任務數;計算預算代價只需對所有成員的薪資累加求和，時間復雜性為O(k);計算時間代價需要在偏序任務集對應的加權圖上計算源點到終點的最長路徑，使用動態規劃方法的時間復雜性為O(n′+e′)，其中n′為加權圖上的節點數,e′為加權圖上的邊數.因為n′=k+2，e′≤k2+2k，所以計算時間代價的時間復雜性最多為O(k2).因此，計算一次總體代價的時間復雜性為O(k2).

令p表示會某個任務的平均人數.HillClimbingTF_BBS算法在遍歷搜索樹中的某個節點時，需要對會該任務的所有人計算總體代價，因此遍歷搜索樹中某個節點的平均時間復雜性為O(pk2).顯然，搜索樹中的節點數最多為k!,所以HillClimbingTF_BBS算法遍歷整個搜索樹的時間復雜性為O(k!pk2).加上計算最短距離的預處理時間，算法HillClimbingTF_BBS的時間復雜性為O(n3+k!pk2).

在實際應用中，最短距離計算可以計算一次存儲起來，不需要每次都計算.任務數k通常是一個比較小的值,而且，由于采用了分支限界策略，被搜索的節點數通常要遠遠小于k!.因而算法HillClimbingTF_BBS在實際應用中會有很高的效率.

5 實驗結果與分析

5.1 實驗設置

偏序任務集為模擬生成的有向無環圖，具體生成過程如下:1)設定偏序圖中的任務數k和偏序邊數e.當任務數為k時，從任務域A中隨機選擇k個任務作為偏序圖的結點(不同的節點可以具有相同的任務).2)從這k個節點中隨機選擇一對不同的節點u和v，再隨機確定邊的方向，例如u→v.如果邊u→v加入偏序圖中沒有形成回路，則添加邊u→v到偏序圖中;如果邊u→v加入偏序圖中形成回路，則放棄邊u→v.重復上述過程，直到偏序圖中包含了e條邊.在后面的實驗中，如果沒有明確說明邊數e，則邊數e默認取k-1.

為了使得通信代價、時間代價和預算代價具有可比性，本文將邊上權值、完成任務時間和薪資的數值單位均統一到1～10之間的數.具體過程如下：如果DBLP合作網絡邊上的權值ω(i,i′)在[0,0.1)區間，則設置ω(i,i′)=1;如果ω(i,i′)在[0.1,0.2)區間，則設置ω(i,i′)=2.以此類推，如果ω(i,i′)在[0.9,1)區間，則設置ω(i,i′)=10.個體完成各任務的時間和所需薪資從1～10中均勻隨機生成.

所有算法用C++編寫，在VC++ 6.0環境下編譯.所有實驗都在AMD Athlon II X4、2 GHz的CPU、8 GB內存的臺式機上運行.

5.2 不同算法比較

本組實驗比較不同算法產生團隊的總代價.由于現有的算法不能直接求解CSN-TPR問題.我們構造如下對比算法:

1) CoverSteiner[2].在忽略偏序關系的基礎上執行CoverSteiner算法求得通信代價小的團隊，將所得團隊中的中間連接節點去掉，只保留完成任務的個體，再將處理后的團隊根據任務偏序關系進行時間和薪資的分配，并計算總代價.

2) BaseTime.只考慮時間因素求時間代價最小的團隊，所獲團隊再計算總代價.

3) BaseBudget.只考慮薪酬因素求預算代價最小的團隊，所獲團隊再計算總代價.

α=0.3,β=0.4，γ=0.3，μ=0.4Fig. 6 Comparison of HillClimbingTF_BBS and other algorithms w.r.t different Task_number.圖6 不同任務數下HillClimbingTF_BBS和其他算法的比較

以上算法計算通信代價都以最小生成樹為衡量標準.

在固定平衡參數條件下，分別選取帶有不同任務數的偏序任務比較不同算法產生團隊的總代價，實驗結果如圖6所示.為了排除偶然性，對每個任務數都隨機生成10組偏序任務進行實驗，結果取均值.

從圖6可以看出，HillClimbingTF_BBS算法所求總代價明顯低于其他算法.尤其當任務數增多時，HillClimbingTF_BBS算法的優勢更顯著.這是由于其他算法只考慮某一方面代價的優化，而HillClimb-ingTF_BBS算法同時考慮通信代價、時間代價和預算代價3方面的優化.

5.3 偏序程度對不同算法的影響

本組實驗考察偏序程度對不同算法的影響.在固定任務數k=8條件下，分別選取不同數目的偏序邊從而生成不同的偏序任務，比較不同算法產生團隊的總代價，實驗結果如圖7所示.為了排除偶然性，當偏序邊數固定時，隨機生成10組偏序任務進行實驗，結果取均值.

k=8,α=0.3,β=0.4，γ=0.3，μ=0.4Fig. 7 Comparison of HillClimbingTF_BBS and other algorithms w.r.t different Edge_number.圖7 不同偏序程度下HillClimbingTF_BBS和其他算法的比較

從圖7可以看出，隨著偏序程度復雜化(偏序邊數增多)，HillClimbingTF_BBS算法所求總代價明顯低于其他算法.例如：當偏序邊數從7增加到9時，HillClimbingTF_BBS算法所求的總代價只增加了3個單位左右，而其他算法所求的總代價卻增加了10單位以上.這是由于其他算法只考慮某一方面代價的優化，沒有考慮任務之間的偏序關系.當任務集合固定時，所構造的團隊也固定了.但當偏序程度變復雜時，時間上的可協調性受到更多限制，因此時間代價明顯增大，總代價也隨之增大.而HillClimbingTF_BBS算法同時考慮通信代價、時間代價和預算代價3方面的優化.當任務集合固定而偏序程度變復雜時，HillClimbingTF_BBS算法會考慮偏序關系優化總代價，從而會選擇不同的團隊，因而總代價增加得較緩慢,這說明Hill-ClimbingTF_BBS算法更適合處理偏序程度復雜化的任務集合.

當固定任務數k取4,6,10條件下變化偏序邊數目時，也得到了與實驗圖7類似的實驗結果.

5.4 任務數對分項代價影響

本組實驗考察在不同任務數條件下產生團隊的各分項代價以及總代價的變化.將平衡參數值固定，分別選取帶有不同任務數的偏序任務進行代價值比較，為了排除偶然性，對每個任務數都隨機生成10組偏序任務進行實驗，結果取均值.

實驗結果如圖8所示，平衡參數一定，隨著任務數的增多，各分項代價以及總代價都會相應增大.這是因為隨著任務數的增多，任務偏序關系趨向于復雜化，所找到的團隊人數增多，由此通信代價和預算代價就會相應增大，而時間上的可協調性也受到更多限制，因此時間代價也會相應增大，總代價也隨之增大.

α=0.3,β=0.4，γ=0.3，μ=0.4Fig. 8 Cost of each part of HillClimbingTF_BBS w.r.t different Task_number.圖8 不同任務數條件下HillClimbingTF_BBS算法各分項代價

5.5 不同平衡參數對算法的影響

本組實驗考察不同參數的變化對團隊的分項代價和總代價的影響.在圖9(a)中，固定了參數β，γ，μ的值，改變參數α的值，考察各分項代價和總代價的變化.隨著α的增大，通信代價逐漸減小，預算代價逐漸增大.這是由于α的增大，通信代價在總代價中的比重逐漸增大，而預算在總代價中的比重則逐漸減小，為了使得總代價最小化，對占比重較大的通信代價限制會更嚴格，通信代價便逐漸減小，而預算代價限制則相對放寬，預算代價便逐漸增大.

在圖9(b)中，固定了參數α，γ，μ的值，改變參數β的值，考察各分項代價和總代價的變化.隨著β的增大，時間代價逐漸減小，預算代價逐漸增大.這是由于β的增大，使得時間代價在總代價中的比重逐漸增大，而預算在總代價中的比重則逐漸減小，為了使得總代價最小化，對占比重較大的時間代價限制會更嚴格，時間代價便逐漸減小，而預算代價限制則相對放寬，預算代價便逐漸增大.

在圖10(a)中，固定了參數α，β，γ的值，改變參數μ的值，考察各分項代價和總代價的變化.隨著μ值的增大，所找團隊通信代價逐漸減小，時間代價逐漸增大.這是由于當μ值逐漸增大時，使得選取leader時社會網絡中節點度數所占比重逐漸增大，所以由leader開始擴展的節點相對較多，所找團隊通信代價逐漸減小，而由于可選個體的增多，團隊在時間協調性上受到一定限制，時間代價則相應增大.

在圖10(b)中，固定了參數α，β，μ的值，改變參數γ的值，考察各分項代價和總代價的變化.隨著γ值的增大，所找團隊通信代價逐漸減小，預算代價逐漸減小.這是由于參數γ控制了leader的任務覆蓋率，隨著γ值的增大，leader所會技能增多，相對地在所找到的團隊中leader所做任務數相對地增多，團隊人數相對地減小，總體的通信代價則會降低.由于團隊人數減少，每個團隊內成員可能做多個任務，影響了任務的可并行性，使得時間代價增大.

Fig. 10 Impact of the variation of μ and γ on cost.圖10 參數μ和γ的變化對代價的影響

5.6 分支限界策略的有效性

α=0.3,β=0.4，γ=0.3，μ=0.4Fig. 11 Running time of HillClimbingTF and HillClimbingTF_BBS w.r.t different Task_number.圖11 不同任務數條件下HillClimbingTF和HillClimbingTF_BBS運行時間

為了驗證分支限界策略的有效性，本節進行如下對比實驗：選擇沒有加入分支限界策略的HillClimbingTF算法與HillClimbingTF_BBS算法進行比較.在固定平衡參數條件下，分別選取帶有不同任務數的偏序任務進行算法效率對比，為了排除偶然性，對相同任務數分別取10個不同的偏序任務進行實驗，實驗結果取均值.如圖11所示，隨著任務數的增多，HillClimbingTF算法的效率大幅下降，而HillClimbingTF_BBS算法則具有很好的擴展性.因為任務數的增多使得搜索樹的分支呈指數增長，HillClimbingTF算法的運行時間也隨之大幅度增長;而加入分支限界策略的HillClimbingTF_BBS算法提前減去不可能產生最優結果的分支，使得搜索范圍大大降低，提升了算法效率.

5.7 聯機近似比

為了證明HillClimbingTF_BBS算法的有效性，本節通過實驗給出算法的聯機近似比.對于具體的CSN-TPR問題，我們很容易計算最優團隊總代價的下界.設V*是最優團隊.首先使用算法CoverSteiner[2]求得通信代價最小的團隊V1，顯然有Cc(V1)

設V為HillClimbingTF_BBS算法求得的團隊，則聯機近似比為

圖12顯示了當任務數變化時本文算法輸出團隊的總代價以及最優團隊總代價的下界.實驗結果表明HillClimbingTF_BBS算法的聯機近似比約為1.6，由此驗證了HillClimbingTF_BBS算法的有效性.

α=0.3,β=0.4，γ=0.3，μ=0.4Fig. 12 Total cost of HillClimbingTF_BBS and lower ound.圖12 HillClimbingTF_BBS算法總代價和總代價下界

6 結束語

本文首次提出了基于偏序任務的社會網絡合作問題CSN-TPR，并證明了此問題為NP-hard問題.為了解決該問題，本文提出了一個高效的近似算法HillClimbingTF_BBS.實驗結果驗證了該算法的有效性和高效率.

[1]Chen S J, Lin L. Modeling team member characteristics for the formation of a multifunctional team in concurrent engineering[J]. IEEE Trans on Engineering Management, 2004, 51(2): 111-124

[2]Lappas T, Liu K, Terzi E. Finding a team of experts in social networks[C] //Proc of the 15th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2009: 467-476

[3]Datta S, Majumder A, Naidu K. Capacitated team formation problem on social networks[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 1005-1013

[4]Rangapuram S S, Hler T, Hein M. Towards realistic team formation in social networks based on densest subgraphs[C] //Proc of the 24th Int Conf on World Wide Web. New York: ACM, 2013: 1077-1087

[5]Kargar M, An A, Zihayat M. Efficient Bi-Objective Team Formation in Social Networks[M]. Berlin: Springer, 2012: 483-498

[6]Arkin E M, Refael H. Minimum-diameter covering problems[J]. Networks, 1997, 36(3): 147-155

[7]Duin C W, Volgenant A, Vo? S. Solving group Steiner problems as Steiner problems[J]. European Journal of Operational Research, 2004, 154(1): 323-329

[8]Baykasoglu A, Dereli T, Das S. Project team selection using fuzzy optimization approach[J]. Cybernetics and Systems, 2007, 38(2): 155-185

[9]Gajewar A, Sarma A D. Multi-skill collaborative teams based on densest subgraphs[C] //Proc of the 12th SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2012: 165-176

[10]Yang D N, Chen Y L, Lee W C, et. al. On social-temporal group query with acquaintance constraint[J]. Proceedings of VLDB Endowment, 2011, 4(6): 397-408

[11]Li C T, Shan M K. Team formation for generalized tasks in expertise social networks[C] //Proc of IEEE Int Conf on Social Computing. Piscataway, NJ: IEEE, 2010: 9-16

[12]Farhadi F, Hoseini E, Hashemi S M. TeamFinder: A co-clustering based framework for finding an effective team of experts in social networks[C] //Proc of IEEE Int Conf on Data Mining Workshops. Piscataway, NJ: IEEE, 2012: 107-114

[13]Sozio M, Gionis A. The community-search problem and how to plan a successful cocktail party[C] //Proc of the 16th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2010: 939-948

[14]Anagnostopoulos A, Becchetti L, Castillo C, et. al. Power in unity: Forming teams in large-scale community systems[C] //Proc of the 19th ACM Int Conf on Information & Knowledge Management. New York: ACM, 2010: 599-608

[15]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)

Liu Yong, born in 1975. Associate professor at Heilongjiang University. Member of China Computer Federation. His main research interests include data mining and social network.

Han Xue, born in 1991. Graduate student at Heilongjiang University. His main research interests include data mining and social network.

Li Jinbao, born in 1969. Professor and PhD supervisor at Heilongjiang University. Senior member of China Computer Federation. His main research interests include sensor network, mobile social network and big data.

Ren Qianqian, born in 1980. Associate professor at Heilongjiang University. Her main research interests include database and information processing.

Wang Nan, born in 1980. PhD candidate at Heilongjiang University. Her main research interests include sensor network and social network.

Collaboration Algorithm in Social Networks Based on Tasks with Partial Relation

Liu Yong, Han Xue, Li Jinbao, Ren Qianqian, and Wang Nan

(SchoolofComputerScienceandTechnology,HeilongjiangUniversity,Harbin150080)(KeyLaboratoryofDatabaseandParallelComputingofHeilongjiangProvince(HeilongjiangUniversity),Harbin150080)

The collaboration problem in social networks has attracted lots of interests among the data mining community. Previous work focused on finding a team with the lowest communication cost to complete all tasks in a project. However, tasks in the realistic projects usually have partial ordering relations. Existing methods cannot deal with partial ordering relations, and thus are not capable of obtaining an effective team. In this paper, we study how to complete the tasks with partial ordering relations effectively, and propose a novel collaboration problem in social networks, named CSN-TPR (collaboration problem in social networks based on tasks with partial ordering relations). Specifically, we investigate how to select an appropriate team in social networks to complete the tasks with partial ordering relations so as to minimize the total cost which is composed of communication cost, time cost and budget cost. We firstly prove that CSN-TPR is NP-hard, and then adopt hill-climbing method, branch and bound strategy and dynamic programming method to propose an approximation algorithm called HillClimbingTF_BBS. HillClimbingTF_BBS can not only acquire an effective team, but also obtain the task allocation of each team member and the start time of each task. The experimental results on real data show that HillClimbingTF_BBS can solve CSN-TPR effectively and efficiently.

social networks; collaboration; partial relation; hill-climbing; branch and bound

2015-06-30；

2016-03-22

國家自然科學基金項目(61370222,61300225)；黑龍江省自然科學基金項目(F201430)；黑龍江省高校科技創新團隊建設計劃項目(2013TD012)；黑龍江省教育廳科技研究項目(12531476)；哈爾濱科技創新人才研究專項資金項目(2012RFQXG096)

任倩倩(rqian99@163.com)

TP311.1

This work was supported by the National Natural Science Foundation of China (61370222, 61300225), the Natural Science Foundation of Heilongjiang Province of China (F201430), the University Science & Technology Innovation Team Project of Heilongjiang Province (2013TD012), the Science & Technology Project of Department of Education of Heilongjiang Province (12531476), and the Innovation Talents Project of Science and Technology Bureau of Harbin (2012RFQXG096).