基于偏序任務(wù)的社會(huì)網(wǎng)絡(luò)合作算法研究

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

(黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 哈爾濱 150080)(黑龍江省數(shù)據(jù)庫(kù)與并行計(jì)算重點(diǎn)實(shí)驗(yàn)室(黑龍江大學(xué)) 哈爾濱 150080)(acliuyong@sina.com)

?

基于偏序任務(wù)的社會(huì)網(wǎng)絡(luò)合作算法研究

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

(黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 哈爾濱 150080)(黑龍江省數(shù)據(jù)庫(kù)與并行計(jì)算重點(diǎn)實(shí)驗(yàn)室(黑龍江大學(xué)) 哈爾濱 150080)(acliuyong@sina.com)

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

社會(huì)網(wǎng)絡(luò)；合作；偏序關(guān)系；爬山法；分支限界

隨著社會(huì)的發(fā)展，項(xiàng)目的規(guī)模越來(lái)越大，社會(huì)成員間的合作愈顯重要.傳統(tǒng)的合作問(wèn)題[1]研究給定項(xiàng)目P(P中包含若干個(gè)任務(wù))，候選人集合S以及S中每個(gè)人所會(huì)的任務(wù)集合，選擇一個(gè)能完成項(xiàng)目P的團(tuán)隊(duì)，使得某個(gè)目標(biāo)最優(yōu)(例如完成項(xiàng)目時(shí)間最短或者項(xiàng)目花費(fèi)最小).但是，這種方法忽略了團(tuán)隊(duì)內(nèi)部個(gè)體間的合作程度，若團(tuán)隊(duì)內(nèi)個(gè)體間互不熟悉或有矛盾，那么所選擇的團(tuán)隊(duì)未必是一個(gè)最佳團(tuán)隊(duì).

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

然而，已有研究工作在選擇團(tuán)隊(duì)時(shí)只考慮完成項(xiàng)目中的所有任務(wù)，并沒(méi)有考慮任務(wù)間可能具有先后順序，某些任務(wù)只有在前序任務(wù)完成后才能開(kāi)始.例如：在建樓過(guò)程中，如圖1所示，首先要打地基，才能開(kāi)始后續(xù)工作，樓主體結(jié)構(gòu)建成后才能安裝門(mén)窗和管道.沒(méi)有先后順序要求的工作又可以并行進(jìn)行以提升整個(gè)工程的進(jìn)度，如安裝門(mén)窗和管道可以同時(shí)實(shí)施.這種任務(wù)間具有偏序關(guān)系的項(xiàng)目在實(shí)際應(yīng)用中普遍存在.對(duì)于這樣的項(xiàng)目，在構(gòu)建團(tuán)隊(duì)時(shí)，不僅要完成所有任務(wù)，還要根據(jù)任務(wù)間的偏序關(guān)系給出團(tuán)隊(duì)成員的具體任務(wù)分配，使得整個(gè)項(xiàng)目的完成時(shí)間最短.

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

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

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

2) 利用爬山法、分支限界策略及動(dòng)態(tài)規(guī)劃方法提出了一個(gè)求解CSN-TPR問(wèn)題的高效算法HillClimbingTF_BBS.該算法不僅輸出有效的團(tuán)隊(duì)，而且給出團(tuán)隊(duì)成員的具體任務(wù)分配以及每項(xiàng)任務(wù)的開(kāi)始時(shí)間.

3) 真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果表明：HillClimbingTF_BBS算法能有效并高效求解CSN-TPR問(wèn)題，此外，還通過(guò)實(shí)驗(yàn)給出了HillClimbingTF_BBS算法的聯(lián)機(jī)近似比.

1 相關(guān)工作

社會(huì)個(gè)體如何合作高效完成任務(wù)一直是學(xué)術(shù)界的熱點(diǎn)研究?jī)?nèi)容，因?yàn)槠渚哂袠O大的社會(huì)需求和廣泛的應(yīng)用前景.例如：Meetup和Google都已經(jīng)開(kāi)發(fā)了活動(dòng)合作功能，用于安排活動(dòng)時(shí)間和活動(dòng)參與者.

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

然而，已有研究工作并沒(méi)有考慮完成任務(wù)先后順序的限制，本文將針對(duì)帶有偏序關(guān)系的任務(wù)集，定義社會(huì)網(wǎng)絡(luò)合作問(wèn)題，并提出有效算法求解該問(wèn)題.

2 預(yù)備知識(shí)

本節(jié)描述文中所用的符號(hào)定義以及本文算法所用的2個(gè)樹(shù)搜索策略.

2.1 符號(hào)定義

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

P(T,R)表示項(xiàng)目(有向無(wú)環(huán)圖)，T?A表示項(xiàng)目中的任務(wù)集，R表示任務(wù)之間的偏序關(guān)系.k表示項(xiàng)目P中的任務(wù)數(shù),即|T|=k.Cc(V′)表示團(tuán)隊(duì)V′的通信代價(jià)，即V′中個(gè)體構(gòu)成最小生成樹(shù)邊上的權(quán)值和.Ct(V′)表示團(tuán)隊(duì)V′的時(shí)間代價(jià)，即完成項(xiàng)目所需最長(zhǎng)時(shí)間.Cb(V′)表示團(tuán)隊(duì)V′的預(yù)算代價(jià)，即每個(gè)個(gè)體完成相應(yīng)任務(wù)所需薪資總和.

2.2 爬山法與分支限界策略

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

本文將采用分支限界法縮小搜索空間，提高算法效率.分支限界法常以廣度優(yōu)先或以最小耗費(fèi)(最大效益)優(yōu)先的方式搜索問(wèn)題的解空間.每一個(gè)活節(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展節(jié)點(diǎn)，活節(jié)點(diǎn)一旦成為擴(kuò)展節(jié)點(diǎn)，就一次性產(chǎn)生其所有孩子節(jié)點(diǎn).在這些孩子節(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的孩子節(jié)點(diǎn)被舍棄，其余孩子節(jié)點(diǎn)被加入活節(jié)點(diǎn)表中.此后，從活節(jié)點(diǎn)表中取下一節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)，并重復(fù)上述節(jié)點(diǎn)擴(kuò)展過(guò)程.這個(gè)過(guò)程一直持續(xù)到找到所需的解或活節(jié)點(diǎn)表為空時(shí)為止.

3 問(wèn)題定義

在完成具有偏序關(guān)系的任務(wù)集而構(gòu)建團(tuán)隊(duì)的前提下，比較合理并且實(shí)際的目標(biāo)是找到的團(tuán)隊(duì)不僅通信代價(jià)小，而且所花費(fèi)時(shí)間和預(yù)算都盡可能小.

為了找到低通信代價(jià)、低預(yù)算、高效率的合作團(tuán)隊(duì)，本文給出了基于偏序任務(wù)的社會(huì)網(wǎng)絡(luò)合作問(wèn)題(CSN-TPR)，定義如下：

定義1. 給定社會(huì)網(wǎng)絡(luò)G(V,E)，任務(wù)域A，每個(gè)個(gè)體所會(huì)的任務(wù)集Task(V)={X1,X2,…,Xn}以及項(xiàng)目P(T,R)，目標(biāo)是找到一個(gè)團(tuán)隊(duì)V′?V和對(duì)該團(tuán)隊(duì)V′的具體任務(wù)分配，使得3個(gè)條件成立：

2)V′中個(gè)體完成任務(wù)的順序應(yīng)滿(mǎn)足項(xiàng)目P(T,R)中要求的偏序關(guān)系R；

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

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

圖2給出了一個(gè)具體的例子，社會(huì)網(wǎng)絡(luò)G(V,E)如圖2(a)中所示，要完成的項(xiàng)目P(T,R)如圖2(b)中所示.其中，任務(wù)集合T={j1,j2,j3,j4}，偏序關(guān)系R={〈j1,j3〉,〈j1,j4〉,〈j2,j4〉}.每個(gè)個(gè)體所會(huì)任務(wù)集如下：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)}，平衡參數(shù)α=0.3，β=0.4.

Fig. 2 The input for CSN-TPR.圖2 CSN-TPR問(wèn)題的輸入

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

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

定理1. 基于偏序任務(wù)的社會(huì)網(wǎng)絡(luò)合作問(wèn)題CSN-TPR是NP-hard問(wèn)題.

證明. 如果項(xiàng)目中的各個(gè)任務(wù)獨(dú)立，沒(méi)有偏序關(guān)系，同時(shí)忽略時(shí)間代價(jià)和預(yù)算代價(jià)，只考慮通信代價(jià)(通過(guò)設(shè)置平衡參數(shù)α=1，β=0,總代價(jià)就是通信代價(jià))，那么本文所提出的問(wèn)題CSN-TPR等價(jià)于Lappas等人在文獻(xiàn)[2]中提出的原始社會(huì)網(wǎng)絡(luò)合作問(wèn)題Mst-Tf.也就是說(shuō)，對(duì)Mst-Tf問(wèn)題的任何一個(gè)實(shí)例，通過(guò)取α=1，β=0，就可以在多項(xiàng)式時(shí)間內(nèi)變換成CSN-TPR問(wèn)題的一個(gè)實(shí)例.因此，Mst-Tf問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)規(guī)約到CSN-TPR問(wèn)題.因?yàn)镸st-Tf問(wèn)題是NP-hard[2]，所以CSN-TPR問(wèn)題也是NP-hard.

證畢.

4 算 法

針對(duì)CSN-TPR問(wèn)題，本文采用爬山法進(jìn)行任務(wù)樹(shù)搜索，利用分支限界策略進(jìn)行剪支，提出了HillClimbingTF_BBS算法.由于在CSN-TPR問(wèn)題中，任務(wù)集具有嚴(yán)格的偏序關(guān)系，所以時(shí)間代價(jià)的計(jì)算不能單純地進(jìn)行串行累加計(jì)算，本文應(yīng)用動(dòng)態(tài)規(guī)劃方法來(lái)計(jì)算時(shí)間代價(jià).

4.1 HillClimbingTF_BBS算法

根據(jù)任務(wù)間的偏序關(guān)系，可建立一棵搜索樹(shù).例如：根據(jù)圖2(b)的偏序關(guān)系可建立搜索樹(shù)如圖3所示.利用爬山法進(jìn)行樹(shù)結(jié)構(gòu)搜索，每步分支都選擇當(dāng)前所有可擴(kuò)展分支中使得總代價(jià)最小的節(jié)點(diǎn)去擴(kuò)展.設(shè)當(dāng)前構(gòu)建的部分團(tuán)隊(duì)為V′,則每步分支都應(yīng)選擇使總代價(jià)C(V′∪i)=αCc(V′∪i)+βCt(V′∪i)+(1-α-β)Cb(V′∪i)最小的節(jié)點(diǎn)i去擴(kuò)展.

Fig. 3 Searching tree for the tasks.圖3 任務(wù)的搜索樹(shù)

當(dāng)任務(wù)數(shù)過(guò)多、偏序關(guān)系過(guò)于復(fù)雜而且社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)過(guò)多時(shí)，算法的執(zhí)行效率會(huì)由于搜索樹(shù)的結(jié)構(gòu)過(guò)大而降低.在算法中加入分支限界策略，對(duì)不可能產(chǎn)生最優(yōu)解的分支提前剪支可以極大地提升算法效率.

如圖4所示，本文采用爬山法進(jìn)行深度優(yōu)先搜索，當(dāng)擴(kuò)展到葉節(jié)點(diǎn)j4時(shí)，記錄當(dāng)前的一個(gè)總代價(jià)值cost=6.6；當(dāng)回溯到另一分枝考慮j2節(jié)點(diǎn)時(shí)，若當(dāng)前團(tuán)隊(duì)的代價(jià)值cost=6.8，表示再向下擴(kuò)展節(jié)點(diǎn)時(shí)，總代價(jià)不可能小于6.8，所以此分枝不可能產(chǎn)生最優(yōu)解，通過(guò)分支限界法將此分枝裁剪掉.

Fig. 4 The pruned searching tree.圖4 被裁剪的搜索樹(shù)

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

算法1.leader選取算法.

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

輸出:leader.

①max_power=0；

② fori∈Vdo

③Degree=節(jié)點(diǎn)i在圖G中的度數(shù)；

④CoverRatio=10×i所會(huì)任務(wù)數(shù)/任務(wù)總數(shù)；

⑤TaskTime=10/i做所會(huì)任務(wù)平均時(shí)間；

⑥i_power=γ×Degree+μ×CoverRatio+

(1-γ-μ)×TaskTime；

⑦ ifi_power>max_powerthen

⑧max_power=i_power；

⑨leader=i；

⑩ end if

利用爬山法進(jìn)行樹(shù)結(jié)構(gòu)搜索過(guò)程中，需要計(jì)算團(tuán)隊(duì)的通信代價(jià).本文采用最小生成樹(shù)的權(quán)值作為通信代價(jià)[2].為快速計(jì)算通信代價(jià)，本文對(duì)圖G中每個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短距離預(yù)先計(jì)算并存儲(chǔ).求解CSN-TPR問(wèn)題的HillClimbingTF_BBS算法偽代碼如算法2所示：

算法2. HillClimbingTF_BBS算法.

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

輸出:Team，Allocation.

① 初始化優(yōu)先級(jí)隊(duì)列Q[0],Q[1],…,Q[k]=?，初始化Team，Allocation，V′=?；

② 使用算法1選取leader；

③leader放入Q[0]；

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

⑤ returnTeam,Allocation.

在算法2中，步驟①為初始化工作.因?yàn)樵谒阉鳂?shù)的每一層都需要1個(gè)優(yōu)先級(jí)隊(duì)列，存儲(chǔ)當(dāng)前任務(wù)的所有后繼任務(wù)和完成后繼任務(wù)的最優(yōu)個(gè)體以及對(duì)應(yīng)的代價(jià)，所以初始化k+1個(gè)優(yōu)先級(jí)隊(duì)列Q[0],Q[1],…,Q[k]，其中k為任務(wù)數(shù).Team記錄算法選擇的優(yōu)化團(tuán)隊(duì)，Allocation記錄為優(yōu)化團(tuán)隊(duì)成員分配的任務(wù)以及對(duì)應(yīng)的時(shí)間和預(yù)算等信息，V′記錄當(dāng)前構(gòu)建的部分團(tuán)隊(duì).步驟③調(diào)用遍歷任務(wù)搜索樹(shù)的遞歸算法HillClimbing_BBS，其偽代碼如算法3所示：

算法3. HillClimbing_BBS算法.

輸入:h，V′；

輸出:Team，Allocation.

① ifh=kthen /*k為任務(wù)數(shù)*/

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

③V′=V′∪Node；

④ ifC(V′)

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

⑥ 在Allocation中記錄Node的任務(wù)、時(shí)間和預(yù)算分配；

⑦ end if

⑧h=h-1；

⑨ HillClimbing_BBS(h,V′N(xiāo)ode)；

⑩ end if

擴(kuò)展*/

節(jié)點(diǎn))；

4.2 動(dòng)態(tài)規(guī)劃求解時(shí)間代價(jià)

完成每項(xiàng)任務(wù)的人員一旦確定，完成每項(xiàng)任務(wù)的時(shí)間也就確定了.圖5(a)給出了一個(gè)偏序任務(wù)集，每項(xiàng)任務(wù)的執(zhí)行時(shí)間在任務(wù)旁邊列出.

Fig. 5 Tasks with partial relation and weighted graph.圖5 任務(wù)偏序集和對(duì)應(yīng)的加權(quán)圖

由于任務(wù)之間具有嚴(yán)格的偏序關(guān)系，某些任務(wù)的開(kāi)始執(zhí)行必須在所有前驅(qū)任務(wù)完成之后，如圖5(a)中j4的開(kāi)始時(shí)間應(yīng)為j1和j2中最后完成的時(shí)間，所以時(shí)間代價(jià)不能是最長(zhǎng)任務(wù)的執(zhí)行時(shí)間.又由于有些任務(wù)沒(méi)有先后順序可以并行執(zhí)行，如圖5(a)中j1和j2，所以時(shí)間代價(jià)也不應(yīng)該是每項(xiàng)任務(wù)執(zhí)行時(shí)間之和.對(duì)于具有偏序關(guān)系的任務(wù)集合，時(shí)間代價(jià)應(yīng)為整個(gè)項(xiàng)目最后完成的時(shí)間.對(duì)圖5(a)中的偏序任務(wù)集，因?yàn)閖1和j2可以同時(shí)執(zhí)行，j1和j2完成后才可以執(zhí)行j4，所以整個(gè)項(xiàng)目的完成時(shí)間為3+2=5，圖5(a)中的偏序任務(wù)集的時(shí)間代價(jià)等于5.

我們使用動(dòng)態(tài)規(guī)劃方法計(jì)算偏序任務(wù)集的時(shí)間代價(jià).對(duì)于任何偏序任務(wù)集，可以構(gòu)造一個(gè)帶有源點(diǎn)和終點(diǎn)的加權(quán)圖.例如：對(duì)圖5(a)中的偏序任務(wù)集，構(gòu)造的加權(quán)圖如圖5(b)所示.這時(shí)，求偏序任務(wù)集的時(shí)間代價(jià)就等價(jià)于在加權(quán)圖中計(jì)算從源點(diǎn)S到終點(diǎn)T的最長(zhǎng)路徑長(zhǎng)度.例如，計(jì)算圖5(a)中的偏序任務(wù)集的時(shí)間代價(jià)等價(jià)于計(jì)算圖5(b)中從源點(diǎn)S到終點(diǎn)T的最長(zhǎng)路徑長(zhǎng)度.

設(shè)L(u,v)表示加權(quán)圖中從節(jié)點(diǎn)u到節(jié)點(diǎn)v的最長(zhǎng)路徑長(zhǎng)度.對(duì)于圖5(b)中的加權(quán)圖顯然有：

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)}.

容易驗(yàn)證在有向加權(quán)圖中求從源點(diǎn)到終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度問(wèn)題滿(mǎn)足最優(yōu)子結(jié)構(gòu)，重疊子問(wèn)題條件，因而可用動(dòng)態(tài)規(guī)劃進(jìn)行求解.

設(shè)Gw表示從任務(wù)的偏序集構(gòu)造的帶有源點(diǎn)S和終點(diǎn)T的加權(quán)圖.l表示從源點(diǎn)S到達(dá)終點(diǎn)T的最多邊數(shù).令L(u,T)表示從節(jié)點(diǎn)u到終點(diǎn)T的最長(zhǎng)路徑長(zhǎng)度；next(u)表示從節(jié)點(diǎn)u到終點(diǎn)T的最長(zhǎng)路徑上u的后繼節(jié)點(diǎn).令LV(i)表示最多經(jīng)過(guò)i條邊到達(dá)終點(diǎn)T的節(jié)點(diǎn)集合.動(dòng)態(tài)規(guī)劃方法計(jì)算時(shí)間代價(jià)的偽代碼如算法4所示：

算法4. 計(jì)算時(shí)間代價(jià)的算法.

輸入:Gw； /*加權(quán)圖*/

輸出: 源點(diǎn)S到終點(diǎn)T的最長(zhǎng)路徑長(zhǎng)度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 算法復(fù)雜度分析

HillClimbingTF_BBS算法預(yù)先計(jì)算圖G中每個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短距離，可以對(duì)每個(gè)節(jié)點(diǎn)調(diào)用DIJKSTRA算法或者直接使用FLOYD算法，時(shí)間復(fù)雜性為O(n3)，其中n為圖G中節(jié)點(diǎn)數(shù).

在計(jì)算個(gè)體i加入當(dāng)前團(tuán)隊(duì)V′的總代價(jià)時(shí)，需要計(jì)算通信代價(jià)、預(yù)算代價(jià)、時(shí)間代價(jià).通信代價(jià)可以使用Prim算法計(jì)算最小生成樹(shù)獲得，時(shí)間復(fù)雜性為O(k2)，其中k為任務(wù)數(shù);計(jì)算預(yù)算代價(jià)只需對(duì)所有成員的薪資累加求和，時(shí)間復(fù)雜性為O(k);計(jì)算時(shí)間代價(jià)需要在偏序任務(wù)集對(duì)應(yīng)的加權(quán)圖上計(jì)算源點(diǎn)到終點(diǎn)的最長(zhǎng)路徑，使用動(dòng)態(tài)規(guī)劃方法的時(shí)間復(fù)雜性為O(n′+e′)，其中n′為加權(quán)圖上的節(jié)點(diǎn)數(shù),e′為加權(quán)圖上的邊數(shù).因?yàn)閚′=k+2，e′≤k2+2k，所以計(jì)算時(shí)間代價(jià)的時(shí)間復(fù)雜性最多為O(k2).因此，計(jì)算一次總體代價(jià)的時(shí)間復(fù)雜性為O(k2).

令p表示會(huì)某個(gè)任務(wù)的平均人數(shù).HillClimbingTF_BBS算法在遍歷搜索樹(shù)中的某個(gè)節(jié)點(diǎn)時(shí)，需要對(duì)會(huì)該任務(wù)的所有人計(jì)算總體代價(jià)，因此遍歷搜索樹(shù)中某個(gè)節(jié)點(diǎn)的平均時(shí)間復(fù)雜性為O(pk2).顯然，搜索樹(shù)中的節(jié)點(diǎn)數(shù)最多為k!,所以HillClimbingTF_BBS算法遍歷整個(gè)搜索樹(shù)的時(shí)間復(fù)雜性為O(k!pk2).加上計(jì)算最短距離的預(yù)處理時(shí)間，算法HillClimbingTF_BBS的時(shí)間復(fù)雜性為O(n3+k!pk2).

在實(shí)際應(yīng)用中，最短距離計(jì)算可以計(jì)算一次存儲(chǔ)起來(lái)，不需要每次都計(jì)算.任務(wù)數(shù)k通常是一個(gè)比較小的值,而且，由于采用了分支限界策略，被搜索的節(jié)點(diǎn)數(shù)通常要遠(yuǎn)遠(yuǎn)小于k!.因而算法HillClimbingTF_BBS在實(shí)際應(yīng)用中會(huì)有很高的效率.

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)設(shè)置

偏序任務(wù)集為模擬生成的有向無(wú)環(huán)圖，具體生成過(guò)程如下:1)設(shè)定偏序圖中的任務(wù)數(shù)k和偏序邊數(shù)e.當(dāng)任務(wù)數(shù)為k時(shí)，從任務(wù)域A中隨機(jī)選擇k個(gè)任務(wù)作為偏序圖的結(jié)點(diǎn)(不同的節(jié)點(diǎn)可以具有相同的任務(wù)).2)從這k個(gè)節(jié)點(diǎn)中隨機(jī)選擇一對(duì)不同的節(jié)點(diǎn)u和v，再隨機(jī)確定邊的方向，例如u→v.如果邊u→v加入偏序圖中沒(méi)有形成回路，則添加邊u→v到偏序圖中;如果邊u→v加入偏序圖中形成回路，則放棄邊u→v.重復(fù)上述過(guò)程，直到偏序圖中包含了e條邊.在后面的實(shí)驗(yàn)中，如果沒(méi)有明確說(shuō)明邊數(shù)e，則邊數(shù)e默認(rèn)取k-1.

為了使得通信代價(jià)、時(shí)間代價(jià)和預(yù)算代價(jià)具有可比性，本文將邊上權(quán)值、完成任務(wù)時(shí)間和薪資的數(shù)值單位均統(tǒng)一到1～10之間的數(shù).具體過(guò)程如下：如果DBLP合作網(wǎng)絡(luò)邊上的權(quán)值ω(i,i′)在[0,0.1)區(qū)間，則設(shè)置ω(i,i′)=1;如果ω(i,i′)在[0.1,0.2)區(qū)間，則設(shè)置ω(i,i′)=2.以此類(lèi)推，如果ω(i,i′)在[0.9,1)區(qū)間，則設(shè)置ω(i,i′)=10.個(gè)體完成各任務(wù)的時(shí)間和所需薪資從1～10中均勻隨機(jī)生成.

所有算法用C++編寫(xiě)，在VC++ 6.0環(huán)境下編譯.所有實(shí)驗(yàn)都在AMD Athlon II X4、2 GHz的CPU、8 GB內(nèi)存的臺(tái)式機(jī)上運(yùn)行.

5.2 不同算法比較

本組實(shí)驗(yàn)比較不同算法產(chǎn)生團(tuán)隊(duì)的總代價(jià).由于現(xiàn)有的算法不能直接求解CSN-TPR問(wèn)題.我們構(gòu)造如下對(duì)比算法:

1) CoverSteiner[2].在忽略偏序關(guān)系的基礎(chǔ)上執(zhí)行CoverSteiner算法求得通信代價(jià)小的團(tuán)隊(duì)，將所得團(tuán)隊(duì)中的中間連接節(jié)點(diǎn)去掉，只保留完成任務(wù)的個(gè)體，再將處理后的團(tuán)隊(duì)根據(jù)任務(wù)偏序關(guān)系進(jìn)行時(shí)間和薪資的分配，并計(jì)算總代價(jià).

2) BaseTime.只考慮時(shí)間因素求時(shí)間代價(jià)最小的團(tuán)隊(duì)，所獲團(tuán)隊(duì)再計(jì)算總代價(jià).

3) BaseBudget.只考慮薪酬因素求預(yù)算代價(jià)最小的團(tuán)隊(duì)，所獲團(tuán)隊(duì)再計(jì)算總代價(jià).

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

以上算法計(jì)算通信代價(jià)都以最小生成樹(shù)為衡量標(biāo)準(zhǔn).

在固定平衡參數(shù)條件下，分別選取帶有不同任務(wù)數(shù)的偏序任務(wù)比較不同算法產(chǎn)生團(tuán)隊(duì)的總代價(jià)，實(shí)驗(yàn)結(jié)果如圖6所示.為了排除偶然性，對(duì)每個(gè)任務(wù)數(shù)都隨機(jī)生成10組偏序任務(wù)進(jìn)行實(shí)驗(yàn)，結(jié)果取均值.

從圖6可以看出，HillClimbingTF_BBS算法所求總代價(jià)明顯低于其他算法.尤其當(dāng)任務(wù)數(shù)增多時(shí)，HillClimbingTF_BBS算法的優(yōu)勢(shì)更顯著.這是由于其他算法只考慮某一方面代價(jià)的優(yōu)化，而HillClimb-ingTF_BBS算法同時(shí)考慮通信代價(jià)、時(shí)間代價(jià)和預(yù)算代價(jià)3方面的優(yōu)化.

5.3 偏序程度對(duì)不同算法的影響

本組實(shí)驗(yàn)考察偏序程度對(duì)不同算法的影響.在固定任務(wù)數(shù)k=8條件下，分別選取不同數(shù)目的偏序邊從而生成不同的偏序任務(wù)，比較不同算法產(chǎn)生團(tuán)隊(duì)的總代價(jià)，實(shí)驗(yàn)結(jié)果如圖7所示.為了排除偶然性，當(dāng)偏序邊數(shù)固定時(shí)，隨機(jī)生成10組偏序任務(wù)進(jìn)行實(shí)驗(yàn)，結(jié)果取均值.

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可以看出，隨著偏序程度復(fù)雜化(偏序邊數(shù)增多)，HillClimbingTF_BBS算法所求總代價(jià)明顯低于其他算法.例如：當(dāng)偏序邊數(shù)從7增加到9時(shí)，HillClimbingTF_BBS算法所求的總代價(jià)只增加了3個(gè)單位左右，而其他算法所求的總代價(jià)卻增加了10單位以上.這是由于其他算法只考慮某一方面代價(jià)的優(yōu)化，沒(méi)有考慮任務(wù)之間的偏序關(guān)系.當(dāng)任務(wù)集合固定時(shí)，所構(gòu)造的團(tuán)隊(duì)也固定了.但當(dāng)偏序程度變復(fù)雜時(shí)，時(shí)間上的可協(xié)調(diào)性受到更多限制，因此時(shí)間代價(jià)明顯增大，總代價(jià)也隨之增大.而HillClimbingTF_BBS算法同時(shí)考慮通信代價(jià)、時(shí)間代價(jià)和預(yù)算代價(jià)3方面的優(yōu)化.當(dāng)任務(wù)集合固定而偏序程度變復(fù)雜時(shí)，HillClimbingTF_BBS算法會(huì)考慮偏序關(guān)系優(yōu)化總代價(jià)，從而會(huì)選擇不同的團(tuán)隊(duì)，因而總代價(jià)增加得較緩慢,這說(shuō)明Hill-ClimbingTF_BBS算法更適合處理偏序程度復(fù)雜化的任務(wù)集合.

當(dāng)固定任務(wù)數(shù)k取4,6,10條件下變化偏序邊數(shù)目時(shí)，也得到了與實(shí)驗(yàn)圖7類(lèi)似的實(shí)驗(yàn)結(jié)果.

5.4 任務(wù)數(shù)對(duì)分項(xiàng)代價(jià)影響

本組實(shí)驗(yàn)考察在不同任務(wù)數(shù)條件下產(chǎn)生團(tuán)隊(duì)的各分項(xiàng)代價(jià)以及總代價(jià)的變化.將平衡參數(shù)值固定，分別選取帶有不同任務(wù)數(shù)的偏序任務(wù)進(jìn)行代價(jià)值比較，為了排除偶然性，對(duì)每個(gè)任務(wù)數(shù)都隨機(jī)生成10組偏序任務(wù)進(jìn)行實(shí)驗(yàn)，結(jié)果取均值.

實(shí)驗(yàn)結(jié)果如圖8所示，平衡參數(shù)一定，隨著任務(wù)數(shù)的增多，各分項(xiàng)代價(jià)以及總代價(jià)都會(huì)相應(yīng)增大.這是因?yàn)殡S著任務(wù)數(shù)的增多，任務(wù)偏序關(guān)系趨向于復(fù)雜化，所找到的團(tuán)隊(duì)人數(shù)增多，由此通信代價(jià)和預(yù)算代價(jià)就會(huì)相應(yīng)增大，而時(shí)間上的可協(xié)調(diào)性也受到更多限制，因此時(shí)間代價(jià)也會(huì)相應(yīng)增大，總代價(jià)也隨之增大.

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

5.5 不同平衡參數(shù)對(duì)算法的影響

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

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

在圖10(a)中，固定了參數(shù)α，β，γ的值，改變參數(shù)μ的值，考察各分項(xiàng)代價(jià)和總代價(jià)的變化.隨著μ值的增大，所找團(tuán)隊(duì)通信代價(jià)逐漸減小，時(shí)間代價(jià)逐漸增大.這是由于當(dāng)μ值逐漸增大時(shí)，使得選取leader時(shí)社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)度數(shù)所占比重逐漸增大，所以由leader開(kāi)始擴(kuò)展的節(jié)點(diǎn)相對(duì)較多，所找團(tuán)隊(duì)通信代價(jià)逐漸減小，而由于可選個(gè)體的增多，團(tuán)隊(duì)在時(shí)間協(xié)調(diào)性上受到一定限制，時(shí)間代價(jià)則相應(yīng)增大.

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

Fig. 10 Impact of the variation of μ and γ on cost.圖10 參數(shù)μ和γ的變化對(duì)代價(jià)的影響

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 不同任務(wù)數(shù)條件下HillClimbingTF和HillClimbingTF_BBS運(yùn)行時(shí)間

為了驗(yàn)證分支限界策略的有效性，本節(jié)進(jìn)行如下對(duì)比實(shí)驗(yàn)：選擇沒(méi)有加入分支限界策略的HillClimbingTF算法與HillClimbingTF_BBS算法進(jìn)行比較.在固定平衡參數(shù)條件下，分別選取帶有不同任務(wù)數(shù)的偏序任務(wù)進(jìn)行算法效率對(duì)比，為了排除偶然性，對(duì)相同任務(wù)數(shù)分別取10個(gè)不同的偏序任務(wù)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果取均值.如圖11所示，隨著任務(wù)數(shù)的增多，HillClimbingTF算法的效率大幅下降，而HillClimbingTF_BBS算法則具有很好的擴(kuò)展性.因?yàn)槿蝿?wù)數(shù)的增多使得搜索樹(shù)的分支呈指數(shù)增長(zhǎng)，HillClimbingTF算法的運(yùn)行時(shí)間也隨之大幅度增長(zhǎng);而加入分支限界策略的HillClimbingTF_BBS算法提前減去不可能產(chǎn)生最優(yōu)結(jié)果的分支，使得搜索范圍大大降低，提升了算法效率.

5.7 聯(lián)機(jī)近似比

為了證明HillClimbingTF_BBS算法的有效性，本節(jié)通過(guò)實(shí)驗(yàn)給出算法的聯(lián)機(jī)近似比.對(duì)于具體的CSN-TPR問(wèn)題，我們很容易計(jì)算最優(yōu)團(tuán)隊(duì)總代價(jià)的下界.設(shè)V*是最優(yōu)團(tuán)隊(duì).首先使用算法CoverSteiner[2]求得通信代價(jià)最小的團(tuán)隊(duì)V1，顯然有Cc(V1)

設(shè)V為HillClimbingTF_BBS算法求得的團(tuán)隊(duì)，則聯(lián)機(jī)近似比為

圖12顯示了當(dāng)任務(wù)數(shù)變化時(shí)本文算法輸出團(tuán)隊(duì)的總代價(jià)以及最優(yōu)團(tuán)隊(duì)總代價(jià)的下界.實(shí)驗(yàn)結(jié)果表明HillClimbingTF_BBS算法的聯(lián)機(jī)近似比約為1.6，由此驗(yàn)證了HillClimbingTF_BBS算法的有效性.

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

6 結(jié)束語(yǔ)

本文首次提出了基于偏序任務(wù)的社會(huì)網(wǎng)絡(luò)合作問(wèn)題CSN-TPR，并證明了此問(wèn)題為NP-hard問(wèn)題.為了解決該問(wèn)題，本文提出了一個(gè)高效的近似算法HillClimbingTF_BBS.實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的有效性和高效率.

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

(孫煥良, 金洺宇, 劉俊嶺, 等. 社交網(wǎng)絡(luò)上支持任務(wù)分組的團(tuán)隊(duì)形成方法[J]. 計(jì)算機(jī)研究與發(fā)展, 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

國(guó)家自然科學(xué)基金項(xiàng)目(61370222,61300225)；黑龍江省自然科學(xué)基金項(xiàng)目(F201430)；黑龍江省高校科技創(chuàng)新團(tuán)隊(duì)建設(shè)計(jì)劃項(xiàng)目(2013TD012)；黑龍江省教育廳科技研究項(xiàng)目(12531476)；哈爾濱科技創(chuàng)新人才研究專(zhuān)項(xiàng)資金項(xiàng)目(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).