孫煥良，富珊珊，劉俊嶺,，于　戈，許鴻斐.沈陽建筑大學(xué) 信息與控制工程學(xué)院，沈陽 068.東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 0006

?

社會網(wǎng)絡(luò)中弱關(guān)系團(tuán)隊(duì)形成問題研究*

孫煥良1+，富珊珊1，劉俊嶺1,2，于戈2，許鴻斐2
1.沈陽建筑大學(xué) 信息與控制工程學(xué)院，沈陽 110168
2.東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110006

SUN Huanliang,FU Shanshan,LIU Junling,et al.Team formation with weak ties in social networks.Journal of Frontiers of Computer Science and Technology,2016,10(6):773-785.

摘要：隨著在線社會網(wǎng)絡(luò)的迅速發(fā)展，社會網(wǎng)絡(luò)的團(tuán)隊(duì)形成問題逐漸成為研究熱點(diǎn)?，F(xiàn)有的社會網(wǎng)絡(luò)中團(tuán)隊(duì)形成問題目標(biāo)是尋找一個(gè)成員間溝通代價(jià)最小的團(tuán)隊(duì)。然而，實(shí)際應(yīng)用中團(tuán)隊(duì)成員間的不緊密關(guān)系使得團(tuán)隊(duì)的觀點(diǎn)多樣化、多角度、無偏見，可以廣泛應(yīng)用于形成專家評審團(tuán)隊(duì)、大眾評審團(tuán)等?；诖诵枨螅瑢⑸鐣W(xué)的弱關(guān)系概念引入團(tuán)隊(duì)形成問題中，提出了一種社會網(wǎng)絡(luò)中弱關(guān)系團(tuán)隊(duì)形成問題。該問題旨在尋找成員間為弱關(guān)系，同時(shí)滿足技能、經(jīng)驗(yàn)值要求的一個(gè)團(tuán)隊(duì)，為NP-hard問題。提出了3類算法解決該問題，分別為貪心算法、精確算法、α-近似算法，每類算法有各自的特點(diǎn)與適用范圍。利用ACM和DBLP兩類真實(shí)的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，綜合評估了各類算法的效率與求解質(zhì)量，證明了提出算法的有效性。

關(guān)鍵詞：社會網(wǎng)絡(luò)；團(tuán)隊(duì)形成；弱關(guān)系；貪心算法；精確算法；近似算法

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(06)-0773-13

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

隨著在線社交網(wǎng)絡(luò)平臺的興起，大量用戶通過互加好友或相互關(guān)注等方式，在平臺中建立起社交關(guān)系，形成了具有大規(guī)模結(jié)點(diǎn)的在線社會網(wǎng)絡(luò)。基于社會網(wǎng)絡(luò)，研究人員開展了社區(qū)發(fā)現(xiàn)[1-2]、影響力分析[3-4]、團(tuán)隊(duì)形成等研究工作[5-10]。

社會網(wǎng)絡(luò)中的團(tuán)隊(duì)形成問題是找出一個(gè)能夠滿足給定任務(wù)需求且關(guān)系緊密的一組專家[5-9]?，F(xiàn)有的社會網(wǎng)絡(luò)中團(tuán)隊(duì)形成問題均強(qiáng)調(diào)專家間的關(guān)系緊密性，緊密性可降低成員間的溝通代價(jià)，有利于任務(wù)的順利完成。然而，實(shí)際應(yīng)用中存在大量要求成員間為“不緊密”關(guān)系的需求，這種成員間的“不緊密”關(guān)系稱為弱關(guān)系[11]。美國社會學(xué)家Granovetter指出了弱關(guān)系具有許多優(yōu)點(diǎn)[11]，包括弱關(guān)系中的成員可以多角度看問題，無偏見性，以及弱關(guān)系具有高效能的傳播效率。弱關(guān)系的這些優(yōu)點(diǎn)可以滿足某些應(yīng)用領(lǐng)域團(tuán)隊(duì)形成需求。例如，在項(xiàng)目評審中，如果評審專家整體具有高經(jīng)驗(yàn)值的同時(shí)，相互間具有弱關(guān)系，可以使得評審結(jié)果無偏見性；另外，交易糾紛解決與電視節(jié)目評選廣泛采用大眾評審團(tuán)機(jī)制，如“淘寶網(wǎng)”采用大眾評審來解決一些買賣雙方的問題，若評審團(tuán)中成員間具有弱關(guān)系，則有利于避免評判結(jié)果的趨同性，從而保證評判結(jié)果的公平性。在傳播效率方面，如社交平臺上的廣告投放，將有限的資源投放在高影響力弱關(guān)系的結(jié)點(diǎn)上，可以避免信息在關(guān)系緊密結(jié)點(diǎn)上的局部傳播，使得信息傳播更加廣泛，從而有效提升廣告投放效果。

基于以上應(yīng)用需求，本文提出了一種社會網(wǎng)絡(luò)中弱關(guān)系團(tuán)隊(duì)形成問題。該問題旨在尋找一組既能滿足任務(wù)技能需求又具有弱關(guān)系約束的整體經(jīng)驗(yàn)值最高的團(tuán)隊(duì)。弱關(guān)系可以采用網(wǎng)絡(luò)中的結(jié)點(diǎn)間跳數(shù)或邊權(quán)和來度量，技能由關(guān)鍵字表示，技能的經(jīng)驗(yàn)值為關(guān)鍵字上的分值。

運(yùn)行實(shí)例1圖1為一個(gè)社會網(wǎng)絡(luò)示例圖，圖中結(jié)點(diǎn)代表評審專家，邊表示專家間關(guān)系。每個(gè)結(jié)點(diǎn)包括表示技能的關(guān)鍵字及經(jīng)驗(yàn)值，如表示a1關(guān)鍵字上的經(jīng)驗(yàn)值為10。給定一個(gè)任務(wù)P={(a1，2)，(a2，1)，(a3，2)}，其中(a1，2)表示關(guān)鍵字a1需要2人。弱關(guān)系可以采用兩點(diǎn)間最短路徑上邊權(quán)和或跳數(shù)來定義，在本實(shí)例中采用跳數(shù)來定義，設(shè)結(jié)點(diǎn)間跳數(shù)大于1時(shí)為弱關(guān)系。

Fig.1　An example of expert social network圖1　專家社會網(wǎng)絡(luò)示例

對于實(shí)例1，可求得一組滿足任務(wù)需求的弱關(guān)系團(tuán)隊(duì)T1={v1，v2，v5，v7，v9}，其中v1、v7完成子任務(wù)(a1，2)，v2完成子任務(wù)(a2，1)，而v5、v9則完成子任務(wù)(a3，2)，團(tuán)隊(duì)T1成員的總經(jīng)驗(yàn)值為38。還可求得一組弱關(guān)系團(tuán)隊(duì)為T2={v1，v3，v5，v7，v9}，子任務(wù)(a1，2)同樣由v1、v7完成，v5完成子任務(wù)(a2，1)，子任務(wù)(a3，2)則由v3、v9完成，團(tuán)隊(duì)T2中成員總經(jīng)驗(yàn)值為42。除了T1、T2外，還有其他團(tuán)隊(duì)滿足實(shí)例1要求，并未列出。然而在所有滿足任務(wù)需求的弱關(guān)系團(tuán)隊(duì)中，T2的總經(jīng)驗(yàn)值最高，則T2是弱關(guān)系團(tuán)隊(duì)查詢的一個(gè)結(jié)果。

弱關(guān)系團(tuán)隊(duì)查詢需要遍歷所有成員的組合進(jìn)行成員間弱關(guān)系約束檢查，同時(shí)還需計(jì)算團(tuán)隊(duì)總經(jīng)驗(yàn)值。當(dāng)團(tuán)隊(duì)規(guī)模較大時(shí)，如大眾評審團(tuán)可達(dá)到幾百人，搜索過程代價(jià)較高，該問題為NP-hard問題。因此，如何快速高效地搜索到社會網(wǎng)絡(luò)中高質(zhì)量的弱關(guān)系團(tuán)隊(duì)具有挑戰(zhàn)性?；谏鲜瞿繕?biāo)，本文提出3類算法實(shí)現(xiàn)弱關(guān)系團(tuán)隊(duì)查詢，分別為貪心算法、精確算法、α-近似算法。其中，貪心算法具有最高的搜索效率；精確算法可獲得精確解，適用于小規(guī)模的應(yīng)用需求；α-近似算法可以在保證算法運(yùn)行效率的同時(shí)求得滿足α近似率的解。

綜上所述，本文的主要貢獻(xiàn)如下:

（1）將社會學(xué)中弱關(guān)系概念引入到團(tuán)隊(duì)形成問題中，提出了弱關(guān)系團(tuán)隊(duì)形成問題，并給出了相關(guān)定義及度量方法，證明了該問題為NP-hard問題。

（2）提出了3類算法求解該弱關(guān)系團(tuán)隊(duì)形成問題，分別為貪心算法、精確算法和α-近似算法。

（3）實(shí)驗(yàn)采用真實(shí)的數(shù)據(jù)集測試了不同參數(shù)下算法的運(yùn)行效率，并對查詢結(jié)果的質(zhì)量和團(tuán)隊(duì)影響力進(jìn)行了分析。

2　相關(guān)工作

傳統(tǒng)的團(tuán)隊(duì)形成問題只需找出能夠提供所需技能的成員集合，不考慮成員間的溝通代價(jià)，團(tuán)隊(duì)查詢?yōu)榧蠑?shù)據(jù)上的組合優(yōu)化問題[12-13]。這類問題通常采用模擬退火[12]、分支限界[13]等策略進(jìn)行求解。

伴隨著社交網(wǎng)絡(luò)的興起，基于社交網(wǎng)絡(luò)的團(tuán)隊(duì)形成問題得到廣泛研究。為了使團(tuán)隊(duì)各成員間合作高效，團(tuán)隊(duì)形成問題更傾向于尋找一組聯(lián)系緊密的專家團(tuán)隊(duì)?，F(xiàn)有的研究工作分為以下3類：不同溝通代價(jià)度量的團(tuán)隊(duì)形成問題[5-7]，考慮團(tuán)隊(duì)內(nèi)各成員工作量平衡的團(tuán)隊(duì)形成問題[7-8]、人員花費(fèi)與溝通花費(fèi)相結(jié)合的雙目標(biāo)問題[9]。

在溝通代價(jià)度量方面，Lappas等人[5]首次在團(tuán)隊(duì)形成問題中考慮成員間的社會關(guān)系，提出了兩種溝通代價(jià)評價(jià)方法——直徑和最小生成樹評價(jià)方法。Kargar等人[6]提出了一種在社會網(wǎng)絡(luò)中考慮團(tuán)隊(duì)領(lǐng)導(dǎo)者的top-k專家團(tuán)隊(duì)發(fā)現(xiàn)問題，并提出了距離之和與領(lǐng)導(dǎo)者距離兩種溝通代價(jià)評價(jià)方法。Datta等人[7]則提出了新的溝通代價(jià)評價(jià)方法，即瓶頸代價(jià)評價(jià)方法。

在考慮團(tuán)隊(duì)內(nèi)各成員工作量平衡關(guān)系方面，文獻(xiàn)[8]同時(shí)考慮了成員間溝通成本及團(tuán)隊(duì)成員的工作量。Datta等人[7]提出了能力約束的概念，即為每個(gè)專家限定了最大能力范圍，分配給各專家的任務(wù)不能超過該約束。Kargar等人[9]在原有的團(tuán)隊(duì)形成問題中加入成員花費(fèi)，將該問題轉(zhuǎn)化為同時(shí)考慮成員花費(fèi)與溝通花費(fèi)的雙目標(biāo)求解問題。

以上團(tuán)隊(duì)形成問題均以獲得緊密關(guān)系團(tuán)隊(duì)成員為目標(biāo)，而本文提出弱關(guān)系團(tuán)隊(duì)形成問題中希望成員間具有弱關(guān)系。因此，現(xiàn)有的團(tuán)隊(duì)形成問題研究方法難以適用于本問題的研究。

社會學(xué)中的弱關(guān)系理論指出社會網(wǎng)絡(luò)中大部分關(guān)系屬于弱關(guān)系，并提出弱關(guān)系雖然不如強(qiáng)關(guān)系堅(jiān)固，卻具有低成本和高效能的傳播效率，弱關(guān)系間的成員看法具有多樣性[11]。人類學(xué)家Dunbar于2009年提出著名的鄧巴數(shù)字[14]，即150定律。根據(jù)該定律，在每個(gè)人能夠維持的150個(gè)成員的社交網(wǎng)絡(luò)中，強(qiáng)關(guān)系約30個(gè)，弱關(guān)系約120個(gè)。本文將社會學(xué)中的弱關(guān)系理論引入團(tuán)隊(duì)形成問題中，并將150定律作為弱關(guān)系參數(shù)設(shè)置的理論基礎(chǔ)。

與弱關(guān)系相關(guān)的另一類相關(guān)工作是圖結(jié)構(gòu)中的獨(dú)立集問題。圖結(jié)構(gòu)中的獨(dú)立集問題是指圖中兩兩互不相鄰的結(jié)點(diǎn)構(gòu)成的集合，而圖中包含結(jié)點(diǎn)最多的獨(dú)立集稱為最大獨(dú)立集[15]。最大獨(dú)立集問題是圖論中經(jīng)典的組合優(yōu)化問題，為高效地解決該問題，采用啟發(fā)式算法[16]或近似算法[17]來提高運(yùn)行效率。獨(dú)立子集中的結(jié)點(diǎn)只要求結(jié)點(diǎn)間不直接相連，而本文所定義的弱關(guān)系來源于社會學(xué)相關(guān)理論，定義弱關(guān)系為大于某一跳數(shù)或邊權(quán)和大于某個(gè)給定值。

3　問題定義

給定一個(gè)無向帶權(quán)圖G=(V，E)，其中V為結(jié)點(diǎn)集，E?V×V是圖G的邊集。本文結(jié)點(diǎn)集中的一個(gè)結(jié)點(diǎn)代表一名專家，邊表示兩個(gè)專家vi與vj具有合作關(guān)系，邊上的權(quán)值表示專家vi與vj間關(guān)系強(qiáng)弱，邊權(quán)值越大，vi與vj關(guān)系越弱。A={a1，a2，…，an}，表示包含n個(gè)技能的集合。每個(gè)結(jié)點(diǎn)vi∈V表示為{，＜ai2，wi2＞，…，}，其中結(jié)點(diǎn)vi第j個(gè)關(guān)鍵字aij∈A，其對應(yīng)的分值為wij，表示該專家的經(jīng)驗(yàn)值。結(jié)點(diǎn)vi擁有的關(guān)鍵字集合表示為Q(vi)={ai1，ai2，…，aik}。為了方便算法描述，將具有k個(gè)關(guān)鍵字的結(jié)點(diǎn)vi按關(guān)鍵字分解為k個(gè)三元組，表示為{，＜vi，ai2，wi2＞，…，}。每個(gè)三元組稱為候選元素，可以完成與任務(wù)關(guān)鍵字相對應(yīng)的子任務(wù)。將所有結(jié)點(diǎn)按此方式拆分并存入同一個(gè)候選元素集U中，則結(jié)點(diǎn)集合V可轉(zhuǎn)化為候選元素集合U。對于集合U中第i個(gè)元素，用U[i].v、U[i].a、U[i].w分別表示元素U[i]中的結(jié)點(diǎn)、關(guān)鍵字和經(jīng)驗(yàn)值。

定義1（技能的結(jié)點(diǎn)候選集）對于任意一個(gè)技能ai∈A，S(ai)={v|ai∈Q(v)}表示所有包含技能ai的候選集；而對于子集T?V，如果T擁有技能ai，則在T中至少存在一個(gè)結(jié)點(diǎn)v，使得ai∈Q(v)。

定義3（弱關(guān)系約束）給定圖G=(V，E)及弱關(guān)系約束h。若存在子集T?V，對于T中任意兩個(gè)結(jié)點(diǎn)v、v′都有dist(v，v')≥h，則稱T滿足弱關(guān)系約束h。其中，dist()是社會網(wǎng)絡(luò)上的距離函數(shù)，其返回值為結(jié)點(diǎn)間的跳數(shù)或結(jié)點(diǎn)間最短路徑上邊權(quán)和。

本文根據(jù)鄧巴數(shù)字中弱關(guān)系與強(qiáng)關(guān)系的比例[14]，結(jié)合具體數(shù)據(jù)集對弱關(guān)系約束參數(shù)h進(jìn)行設(shè)定，詳見第5章實(shí)驗(yàn)結(jié)果與分析部分。

問題1（弱關(guān)系團(tuán)隊(duì)發(fā)現(xiàn)問題）給定圖G=(V，E)和任務(wù)約束P，弱關(guān)系約束h。弱關(guān)系團(tuán)隊(duì)發(fā)現(xiàn)就是從圖G中找到子集T?V，滿足P與h約束，并且使得團(tuán)隊(duì)的總經(jīng)驗(yàn)值WT(P)最大。

定理1社會網(wǎng)絡(luò)中的弱關(guān)系團(tuán)隊(duì)發(fā)現(xiàn)問題是一個(gè)NP-hard問題。

4　查詢處理算法

下面研究弱關(guān)系團(tuán)隊(duì)形成問題查詢處理算法。第4.1節(jié)介紹處理該問題的貪心算法；第4.2節(jié)提出兩種精確算法；第4.3節(jié)介紹一種α-近似算法。

本文所提出的各種算法均需要進(jìn)行弱關(guān)系與關(guān)鍵字約束檢查，為方便表達(dá)，將這一檢查過程提取出一個(gè)過程表示，如過程1。給定一個(gè)當(dāng)前未滿足成員數(shù)要求的弱關(guān)系團(tuán)隊(duì)T及當(dāng)前需要檢查的候選元素C[i]，判斷C[i]是否加入T，需要檢查C[i]的關(guān)鍵字是否為對應(yīng)未完成任務(wù)，并且檢查C[i]與T中現(xiàn)有元素是否為弱關(guān)系。步驟1～2，判斷T中是否已找到滿足子任務(wù)C[i].a需求的人數(shù)，若已滿足人數(shù)需求，則返回0；步驟3～5，判斷結(jié)點(diǎn)C[i].v是否與T中所有結(jié)點(diǎn)滿足弱關(guān)系，若有一個(gè)結(jié)點(diǎn)不滿足弱關(guān)系，則返回0；步驟6，若經(jīng)上述判斷，結(jié)點(diǎn)C[i].v與T中所有結(jié)點(diǎn)均滿足弱關(guān)系約束，且子任務(wù)C[i].a所需人數(shù)還未滿足，則返回1。

過程1 IsInsert(T,C[i])

1.if|TC[i].a∩S(C[i].a)|≥kC[i].athen

2.return 0;//子任務(wù)C[i].a已滿足人數(shù)需求

3.for j=1 to|T|do

4.if dist(C[i].v,T[j].v)≤h then

5.return0;//結(jié)點(diǎn)C[i].v與T[j].v不滿足弱關(guān)系約束

6.return 1;

進(jìn)行弱關(guān)系團(tuán)隊(duì)查詢時(shí)，需要檢查兩個(gè)結(jié)點(diǎn)距離是否大于弱關(guān)系約束h。本文將社會網(wǎng)絡(luò)圖中的結(jié)點(diǎn)距離進(jìn)行預(yù)計(jì)算并存儲，當(dāng)需要檢查結(jié)點(diǎn)距離時(shí)訪問預(yù)計(jì)算結(jié)果即可。如果圖中有n個(gè)結(jié)點(diǎn)，則需計(jì)算并存儲n2結(jié)點(diǎn)對距離。根據(jù)鄧巴定律，一個(gè)圖中強(qiáng)關(guān)系只占20%，因此本文只保存距離小于弱關(guān)系約束h的關(guān)系對，即強(qiáng)關(guān)系的結(jié)點(diǎn)對，對比將所有結(jié)點(diǎn)間關(guān)系進(jìn)行存儲的數(shù)據(jù)量大幅度減少。將這些關(guān)系對采用倒排索引存儲，當(dāng)需要檢查某一對結(jié)點(diǎn)是否為弱關(guān)系時(shí)，則訪問該索引。

4.1貪心算法

貪心算法是解決NP-hard問題的常用方法，本文首先采用貪心算法進(jìn)行弱關(guān)系團(tuán)隊(duì)查詢。弱關(guān)系團(tuán)隊(duì)形成問題的目標(biāo)是最大化成員分?jǐn)?shù)，因此優(yōu)先搜索高分值的關(guān)鍵字傾向得到較優(yōu)解。預(yù)先建立關(guān)鍵字候選元素排序表C，C中各關(guān)鍵字候選元素按分值從大到小排序，貪心算法即從排序表中分值最大的元素開始依次向后搜索，直至求得滿足弱關(guān)系和關(guān)鍵字約束的團(tuán)隊(duì)為止。

令候選集總數(shù)為N，團(tuán)隊(duì)人數(shù)為K，算法中第一個(gè)元素最多需要選擇N次，后面K-1個(gè)元素最多進(jìn)行N-1次判斷，因此Greedy算法總的時(shí)間復(fù)雜度為O(N2)。

4.2精確算法

4.2.1回溯搜索算法

回溯搜索算法基本思想為首先利用4.1節(jié)提出的貪心算法求得一個(gè)初始解T，然后利用初始解T構(gòu)造最優(yōu)解搜索空間樹，并在該搜索空間樹上將T中元素按經(jīng)驗(yàn)值從小到大進(jìn)行逐一回溯替換。當(dāng)求得一組解優(yōu)于當(dāng)前解時(shí)，再對最優(yōu)解搜索空間樹進(jìn)行更新，直到將解空間內(nèi)所有結(jié)點(diǎn)替換結(jié)束為止。

若對整個(gè)解空間樹進(jìn)行回溯，則會造成許多無效搜索，本文結(jié)合兩種優(yōu)化搜索策略以提高回溯法搜索效率。第一種策略利用弱關(guān)系和關(guān)鍵字約束剪去不滿足約束的子樹；第二個(gè)策略是確定最優(yōu)團(tuán)隊(duì)中每個(gè)元素在搜索列表中的下界位置，從而縮減搜索空間。定理2給出最優(yōu)弱關(guān)系團(tuán)隊(duì)中元素的下界位置求解方法。

證明略。

由定理2可求得最優(yōu)弱關(guān)系團(tuán)隊(duì)中每個(gè)元素的下界位置，將每個(gè)元素在C中下界位置存入下界列表Lower，Lower[i](1≤i≤K)表示最優(yōu)團(tuán)隊(duì)中第i個(gè)元素在C中的下界位置。如實(shí)例1中，由Greedy算法求得初始解T總經(jīng)驗(yàn)值為38，根據(jù)定理2可求得Lower= {2，3，7，10，12}。假設(shè)在回溯搜索樹中，結(jié)點(diǎn)i代表元素C[i]，若該結(jié)點(diǎn)作為團(tuán)隊(duì)中第j個(gè)元素進(jìn)行擴(kuò)展時(shí)，其所代表的元素在C中位置i已超過Lower[j]，則可斷定以結(jié)點(diǎn)i為根的子樹中不含有最優(yōu)解，因此可將該子樹剪去。

算法1描述了回溯搜索算法細(xì)節(jié)。步驟1調(diào)用算法1求得弱關(guān)系團(tuán)隊(duì)T；步驟3～6選定T中需要替換的結(jié)點(diǎn)T[i]，對T[i]以下所有元素進(jìn)行替換；步驟4 將C[T[i].s+1]作為T[i]的替換元素，并用s記錄該元素位置；步驟6調(diào)用過程2對T中T[i]及以后元素進(jìn)行替換。

如過程2所示，步驟1將T中當(dāng)前要替換的元素位置賦給j；步驟2～5如果當(dāng)前加入元素C[s]在C中位置未超過Lower[j]，調(diào)用過程1判斷C[s]結(jié)點(diǎn)是否與T滿足弱關(guān)系及關(guān)鍵字約束，若滿足將C[s]加入T，并將C[s+1]當(dāng)作T[j+1]元素的替換元素進(jìn)行判斷，否則將C[s+1]繼續(xù)作為元素T[j]的替換元素進(jìn)行判斷；步驟6～11，若當(dāng)前位置s超過Lower[j]，則說明繼續(xù)對T中第j個(gè)元素進(jìn)行替換已找不到最優(yōu)解，此時(shí)若j未超過需要替換的i，則從T中第j-1個(gè)元素開始替換，否則遞歸結(jié)束；步驟12～17，若經(jīng)過替換獲得一組滿足要求團(tuán)隊(duì)T，如果T優(yōu)于Tbest，則用T替換Tbest，并更新Lower。

算法1 ExactBB

輸出：最優(yōu)弱關(guān)系團(tuán)隊(duì)Tbest。

過程2 Replace(T,s,i)

回溯搜索算法雖然利用Greedy算法對解空間進(jìn)行了縮減，同時(shí)利用縮減策略降低了查詢代價(jià)，但在解空間內(nèi)仍需替換大量的結(jié)點(diǎn)，導(dǎo)致運(yùn)行效率低。在搜索空間內(nèi)的組合替換仍然是NP-hard問題。因此下面將提出一種基于動態(tài)規(guī)劃思想的精確算法。

4.2.2動態(tài)規(guī)劃搜索算法

本文所提出的團(tuán)隊(duì)形成問題，如不考慮弱關(guān)系約束，本質(zhì)上是求解集合中的一個(gè)分值和最高的子集，則問題轉(zhuǎn)換為0-1背包問題，可以考慮采用0-1背包問題求解方法求解。但是加入弱關(guān)系約束后不滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，則0-1背包問題的方法不再適用。然而可以保存所有滿足關(guān)鍵字與弱關(guān)系約束的解，每一個(gè)解為一個(gè)背包，這樣問題即轉(zhuǎn)換為多維背包問題。因此，可以采用求解多維背包問題的動態(tài)規(guī)劃思想，保留多個(gè)滿足弱關(guān)系的候選解，利用候選解的關(guān)系設(shè)計(jì)剪枝條件，從而以空間換時(shí)間提高搜索效率?；诖怂枷?，提出了基于動態(tài)規(guī)劃搜索的精確算法。

算法首先創(chuàng)建一個(gè)二維數(shù)組g[K][S]來存儲候選可行解，二維數(shù)組的行表示背包的容量，即團(tuán)隊(duì)成員數(shù)，列表示背包的一個(gè)解，并按解的優(yōu)劣排序。此二維數(shù)組g[K][S]隨新元素的加入動態(tài)更新，g[i][j]表示當(dāng)前i個(gè)成員團(tuán)隊(duì)第j個(gè)最優(yōu)解。設(shè)g[i][j].w為候選解g[i][j]總經(jīng)驗(yàn)值。

求解過程訪問候選元素，當(dāng)前加入元素C[s]時(shí)，更新g的第i行，且該行的有序解是由以下3種情況的有序解合并所得：

（1）未加入C[s]時(shí)，第i行中的解g[i][j]；

（2）當(dāng)C[s]與g[i-1][j]滿足弱關(guān)系和關(guān)鍵字約束時(shí)，在g[i-1][j]基礎(chǔ)上加入C[s]，所得解為g[i-1][j]+ C[s]；

（3）當(dāng)C[s]與g[i][j]中元素c擁有相同結(jié)點(diǎn)時(shí)，若g[i][j]中技能C[s].a未達(dá)到成員數(shù)要求，則以C[s]替換c，替換后所得解用R(C[s]，c)表示。

當(dāng)候選元素表C中所有元素訪問結(jié)束后，g[K][1]一定為最優(yōu)弱關(guān)系團(tuán)隊(duì)。定理3給出不需訪問C中所有元素即可判斷g[K][1]是否為最優(yōu)解的條件。

定理3設(shè)已求得一組弱關(guān)系團(tuán)隊(duì)g[K][1]，當(dāng)前要加入元素分值為w，若對任意i(0≤i

證明假設(shè)g[K][1]不是最優(yōu)解，則有g(shù)[K-1][j].w+ w>g[K][1].w(1≤j≤S)。又由對于?i(0≤i

定理3說明將當(dāng)前各行的最優(yōu)解與加入元素C [s]進(jìn)行逐一比較，若加入C[s]后不優(yōu)于解g[K][1]，則g[K][1]為最優(yōu)解，提前終止對C中元素的訪問。

當(dāng)團(tuán)隊(duì)所需人數(shù)增多時(shí)，解空間所要保存的弱關(guān)系組合隨之增多，空間需求量增大，運(yùn)行效率降低。然而在所保存的解中，有大量的中間結(jié)果不為最優(yōu)解的一部分，則可以為每一行求得一個(gè)最小值作為g[i][j].w下界，若第i行解小于相應(yīng)的下界值，則不加入解空間內(nèi)，從而減少了解的數(shù)量。定理4給出了g[i][j].w下界計(jì)算方法。

例如，對于實(shí)例1，假設(shè)團(tuán)隊(duì)T中已加入2個(gè)元素，當(dāng)前要加入元素為C[6]，則剩余3個(gè)元素所能取到的最大值是在不考慮弱關(guān)系及關(guān)鍵字約束下，以C[6]開始的連續(xù)3個(gè)元素，即C[6]、C[7]、C[8]，經(jīng)驗(yàn)值之和為19。又因?yàn)橛蠫reedy算法求得弱關(guān)系團(tuán)隊(duì)經(jīng)驗(yàn)值為38，所以若C[6]為BT中第3個(gè)元素，則團(tuán)隊(duì)T中前2個(gè)元素之和不能小于19，即LB[2]=19。以此類推，每個(gè)子空間都有相應(yīng)的下界值，可以利用這些下界值提前結(jié)束不必要的搜索。

算法2描述了基于動態(tài)規(guī)劃搜索算法。步驟1～4初始化解空間，令g[0][1].w=0，其余候選解分值均設(shè)為-1；步驟6～8，每加入一個(gè)元素C[i]，首先判斷當(dāng)前加入元素的位置i是否超出下界位置Lower[j]，若未超出，步驟8調(diào)用過程3對各子問題解空間更新；步驟9～12，利用定理4中的條件判斷弱關(guān)系團(tuán)隊(duì)g[K][1]是否為最優(yōu)解，若為最優(yōu)解則跳出循環(huán)，否則繼續(xù)對解空間進(jìn)行更新。

過程3中步驟1初始化堆Heap，用于存儲可行解，堆頂元素經(jīng)驗(yàn)值最大；步驟4～8，將所有可行解存入Heap中；步驟9～12，在滿足定理4情況下，首先構(gòu)造Heap，并將堆頂解Heap[0]存入g[j][i2]中，i2用于記錄Heap[0]在g[j]中的存儲位置；步驟13，從Heap中移除Heap[0]；步驟14，若不滿足定理4，則跳出循環(huán)。

算法2 ExactDP

輸出：最優(yōu)弱關(guān)系團(tuán)隊(duì)T。

過程3 SpaceUpdate(j,C[i],S,LB)

算法2假定解空間S可以保存所有的可行解，由于解的數(shù)量可能超出空間大小S，本文采用一種動態(tài)分配內(nèi)存的方式增加解空間。在過程3中用i2記錄已保存的解的個(gè)數(shù)，當(dāng)i2=S時(shí)，表示當(dāng)前解空間大小不足以存儲所有解，則將解空間進(jìn)行擴(kuò)充，每次擴(kuò)展sa個(gè)空間。

動態(tài)規(guī)劃搜索算法將可行解都保存下來，通過初始解界定可行解最小邊界，從而減少了可行解的數(shù)量。與回溯法相比，減少了結(jié)點(diǎn)的判別與替換次數(shù)，運(yùn)行效率有明顯提升。設(shè)解空間大小為S，團(tuán)隊(duì)人數(shù)為K，候選集大小為N，又因?yàn)樵撍惴ㄐ枥肎reedy算法求解進(jìn)行空間剪枝，所以基于動態(tài)規(guī)劃搜索算法時(shí)間復(fù)雜度為O(N2+S×K×N)。設(shè)在所有人數(shù)為K的團(tuán)隊(duì)中，同時(shí)滿足弱關(guān)系及關(guān)鍵字約束的團(tuán)隊(duì)所占比例為ρ，因?yàn)榻M合問題空間復(fù)雜度為O(N!)，又因?yàn)榛趧討B(tài)規(guī)劃搜索算法保存了所有滿足要求的弱關(guān)系組合，所以其空間復(fù)雜度為O(ρ×K×N!)，當(dāng)團(tuán)隊(duì)查找人數(shù)增多，解空間大小急劇增加時(shí)，算法求解效率降低，動態(tài)規(guī)劃精確求解算法不再適用。因此，本文提出一種α-近似算法。

4.3α-近似算法

本節(jié)提出一種高查詢效率的同時(shí)可以保證近似率的α-近似算法。該近似算法是在精確的動態(tài)規(guī)劃算法基礎(chǔ)上實(shí)現(xiàn)的，基本思想是利用較小的解空間只保存滿足α近似率的解。

給定參數(shù)α與解空間大小，并設(shè)定最優(yōu)解邊界值，該邊界值可以保證α倍近似率。邊界值設(shè)置方法為在不考慮成員間弱關(guān)系情況下，求得一組滿足人數(shù)要求和關(guān)鍵字約束的經(jīng)驗(yàn)值之和最大團(tuán)隊(duì)，該團(tuán)隊(duì)經(jīng)驗(yàn)值之和即為最優(yōu)解邊界值。為了充分利用解空間求得滿足近似率的解，需要為每個(gè)部分解設(shè)置邊界值使得部分解均可以保證α倍近似率。

如人數(shù)i=3時(shí)，部分解由C[1]、C[2]、C[3]構(gòu)成，邊界為30。同理，可知C[1]、C[2]、C[3]、C[4]、C[6]構(gòu)成人數(shù)為5的界限為45，由于C[5]的關(guān)鍵字為a2，而實(shí)例1中僅需要1個(gè)關(guān)鍵字為a2的元素，因此C[5]參與人數(shù)為5的邊界計(jì)算。由此可得各子問題最優(yōu)解上界值為Bound={11，21，30，38，45}。

算法3給出了近似算法描述，輸入近似率α。步驟1，初始化解空間；步驟2～5，在給定解空間K×S內(nèi)求解子問題，其中K為二維數(shù)組的行數(shù)，對應(yīng)團(tuán)隊(duì)成員數(shù)，S為二維數(shù)組的列，對應(yīng)候選解個(gè)數(shù)，利用K×S空間保存滿足近似率要求的解，即g[i][j].w≥Bound [j]/α(1≤i≤K，1≤j≤S)；步驟4，若子問題j的解空間已滿，且加入元素C[i]后有可能改變當(dāng)前解空間，則進(jìn)行子空間更新計(jì)算，反之，則不進(jìn)行計(jì)算；步驟6，若求得一組解，則跳出循環(huán)，當(dāng)前所求解即滿足α近似率。

算法3 ApproxDP

輸出：弱關(guān)系團(tuán)隊(duì)T。

定理5 ApproxDP算法所求解為α近似。

該算法僅保存了一部分滿足近似率的解進(jìn)行計(jì)算，因此可能求不到解。除了所保存的解外，還有大量滿足近似率的解在求解過程中被忽略掉了，因此在求不到解的情況下，可以對被忽略掉的解進(jìn)行重新計(jì)算。處理方法如下：首先在求解過程中記錄使得各子空間存滿時(shí)的元素，同時(shí)將各子空間存滿時(shí)的狀態(tài)存入文件中，在未求得解情況下，讀取文件至解空間g'[K][S]，并使用使得各子空間存滿時(shí)的元素，對所讀取的解空間進(jìn)行組合更新，將未出現(xiàn)在解空間g′中的組合結(jié)果存入g[K][S]中，當(dāng)g[K][S]存儲結(jié)束后，將g[K][S]作為新的解空間繼續(xù)進(jìn)行算法3計(jì)算。

α-近似算法時(shí)間復(fù)雜度為O(S×K×N)，其中S為解空間，K為團(tuán)隊(duì)人數(shù)，N為候選集大小。由于此算法所需空間遠(yuǎn)小于動態(tài)規(guī)劃精確算法，使得算法的查詢效率較高。

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

本文使用真實(shí)數(shù)據(jù)集對算法運(yùn)行效率及求解質(zhì)量進(jìn)行評估。本文算法使用C++語言實(shí)現(xiàn)，并在PC機(jī)上進(jìn)行實(shí)驗(yàn)，處理器為Intel CPU P8700 3.00 GHz，主存為4.0 GB，操作系統(tǒng)為Windows 7。本文比較了兩種精確算法（ExactBB、ExactDP）以及α-近似算法（ApproxDP）的運(yùn)行效率，還對貪心算法與ApproxDP近似算法查詢結(jié)果進(jìn)行了分析，分別為查詢結(jié)果質(zhì)量分析和團(tuán)隊(duì)影響力分析。

5.1實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用兩類真實(shí)數(shù)據(jù)集對算法進(jìn)行了評估。第一個(gè)數(shù)據(jù)集為ACM學(xué)者合作關(guān)系數(shù)據(jù)集，該數(shù)據(jù)抓取自ACM Digital Library網(wǎng)站。圖中結(jié)點(diǎn)代表學(xué)者，邊表示學(xué)者間的合作關(guān)系，每個(gè)學(xué)者都擁有研究領(lǐng)域?qū)傩?，共?0 000個(gè)結(jié)點(diǎn)。根據(jù)合作關(guān)系生成稠密圖，共有邊數(shù)100 233條。另外通過隨機(jī)刪除一部分邊生成稀疏圖，邊數(shù)為80 002。根據(jù)ACM的命名規(guī)則，第一層為研究領(lǐng)域，本文僅按第一層來提取關(guān)鍵字，并將ACM稠密圖和稀疏圖中專家結(jié)點(diǎn)上各關(guān)鍵字分值相加之和作為該結(jié)點(diǎn)的總分值，構(gòu)成兩組無關(guān)鍵字約束數(shù)據(jù)集，兩組數(shù)據(jù)集分別命名為Dataset1和Dataset2。

根據(jù)鄧巴數(shù)字[14]可知，每個(gè)人擁有穩(wěn)定社交網(wǎng)絡(luò)的人數(shù)大約維持在150個(gè)左右，其中強(qiáng)聯(lián)系有30個(gè)，弱聯(lián)系約120個(gè)。若推廣至整個(gè)社會網(wǎng)絡(luò)，可得社會網(wǎng)絡(luò)中弱關(guān)系約占整個(gè)網(wǎng)絡(luò)的80%，而強(qiáng)關(guān)系僅有20%。根據(jù)上述社會網(wǎng)絡(luò)中弱關(guān)系與強(qiáng)關(guān)系比例，計(jì)算得出ACM中稠密圖弱關(guān)系約束為3。同理，將ACM稀疏圖和DBLP圖數(shù)據(jù)中弱關(guān)系約束分別設(shè)為4和8.942。

5.2算法運(yùn)行效率比較

本節(jié)測試了團(tuán)隊(duì)人數(shù)K、解空間大小等參數(shù)對各算法運(yùn)行效率的影響。由于兩種精確算法僅適用于小規(guī)模的團(tuán)隊(duì)形成問題，實(shí)驗(yàn)中評價(jià)了查詢團(tuán)隊(duì)人數(shù)較少情況時(shí)的運(yùn)行效率。圖2為各數(shù)據(jù)集中兩種精確算法運(yùn)行效率隨著團(tuán)隊(duì)人數(shù)改變時(shí)的變化情況。圖2（a）比較了數(shù)據(jù)集Dataset1中算法運(yùn)行效率，當(dāng)團(tuán)隊(duì)人數(shù)大于30時(shí)ExactBB算法已無法運(yùn)行，而ExactDP算法可以將團(tuán)隊(duì)人數(shù)運(yùn)行到近100人。ExactDP由于采用動態(tài)規(guī)則方法保存了候選解，其效率高于回溯法ExactBB。圖2（b）（c）為Dataset2和Dataset3中ExactDP與ExactBB運(yùn)行效率對比，整體趨勢與圖2（a）相似。

實(shí)驗(yàn)表明，當(dāng)團(tuán)隊(duì)人數(shù)較小時(shí)，ExactDP算法求取精確解所需解空間較小，運(yùn)行效率較高，當(dāng)團(tuán)隊(duì)人數(shù)增多時(shí)，ExactDP算法求解所需解空間增大，運(yùn)行效率也隨之降低。而ExactBB算法隨著人數(shù)增多，其結(jié)點(diǎn)替換次數(shù)呈指數(shù)級增長，運(yùn)行時(shí)間急劇增加。以空間換時(shí)間的ExactDP算法能夠較大地提高運(yùn)行效率。

Fig.2　Efficiency comparison between ExactDP and ExactBB圖2　ExactDP與ExactBB算法運(yùn)行效率比較

圖3為近似率對ApproxDP算法所需解空間大小的影響，當(dāng)對ApproxDP算法求解質(zhì)量要求較高時(shí)，需要較大的解空間保存更多可行解。如圖3所示，當(dāng)近似率為1.2時(shí)，解空間K×S大小為K×30時(shí)才能求得滿足近似率要求的解，而當(dāng)近似率為1.5時(shí)，解空間大小為K×10時(shí)即可求得解。近似算法的近似率設(shè)置α=2，解空間大小設(shè)置為K×10。

Fig.3　Effect of approximate ratio to space sizes圖3　近似率對解空間大小的影響

圖4分析了Dataset3中解空間大小的改變對ApproxDP算法運(yùn)行效率的影響。實(shí)驗(yàn)表明當(dāng)團(tuán)隊(duì)人數(shù)較小時(shí)，ApproxDP算法求解效率對解空間大小并不敏感。而當(dāng)團(tuán)隊(duì)人數(shù)增加至600人時(shí)，解空間大小對ApproxDP算法求解效率影響較大。

5.3查詢結(jié)果分析

本節(jié)對查詢結(jié)果進(jìn)行分析，包括貪心算法與近似算法的求解質(zhì)量及查詢團(tuán)隊(duì)的影響力。

Fig.4　Effect of space sizes to efficiency ofApproxDP圖4　解空間大小對ApproxDP運(yùn)行效率的影響

實(shí)驗(yàn)比較近似算法與貪心算法求解質(zhì)量，求解質(zhì)量以團(tuán)隊(duì)成員的經(jīng)驗(yàn)值之和衡量。圖5為Dataset3 中Greedy與ApproxDP算法求解質(zhì)量比較。由圖5可得，ApproxDP算法求解質(zhì)量要優(yōu)于Greedy算法，并且團(tuán)隊(duì)成員數(shù)越多，優(yōu)勢越明顯。原因是團(tuán)隊(duì)成員數(shù)越多，Greedy算法對結(jié)點(diǎn)的排斥性越大，從而降低算法求解質(zhì)量。實(shí)驗(yàn)表明，ApproxDP算法求解質(zhì)量要優(yōu)于Greedy算法。

Fig.5　Team quality comparison among Greedy andApproxDP圖5　Greedy與ApproxDP算法求解質(zhì)量比較

本文提出的弱關(guān)系團(tuán)隊(duì)目標(biāo)是查詢滿足弱關(guān)系約束的具有最大經(jīng)驗(yàn)值和的團(tuán)隊(duì)。本文通過實(shí)驗(yàn)分析弱關(guān)系組成的團(tuán)隊(duì)的影響力。社會網(wǎng)絡(luò)中采用傳播模型來評價(jià)一組結(jié)點(diǎn)的影響力，常見的傳播模型包括獨(dú)立級聯(lián)模型和線性閾值模型[3]。本文采用獨(dú)立級聯(lián)模型將弱關(guān)系團(tuán)隊(duì)的影響力與現(xiàn)有的影響力最大化算法進(jìn)行比較。獨(dú)立級聯(lián)模型在給定初始激活結(jié)點(diǎn)下，采用激活概率與影響概率比較方式計(jì)算影響力。實(shí)驗(yàn)中采用多次模擬求平均值的方法來計(jì)算各團(tuán)隊(duì)所能影響的結(jié)點(diǎn)數(shù)目。

在獨(dú)立級聯(lián)模型下，設(shè)計(jì)了3種團(tuán)隊(duì)與Approx-DP算法所求弱關(guān)系團(tuán)隊(duì)TeamADP影響結(jié)點(diǎn)數(shù)進(jìn)行比較：一種只考慮最大化團(tuán)隊(duì)經(jīng)驗(yàn)值的團(tuán)隊(duì)，即社會網(wǎng)絡(luò)中不考慮結(jié)點(diǎn)間的關(guān)系取前K大經(jīng)驗(yàn)值的結(jié)點(diǎn)生成團(tuán)隊(duì)，這類團(tuán)隊(duì)稱為TeamMW；另一種利用最大化影響力算法生成團(tuán)隊(duì)，采用兩種影響力算法，一種為直接選取前K個(gè)度數(shù)最大的結(jié)點(diǎn)作為團(tuán)隊(duì)初始結(jié)點(diǎn)，所形成團(tuán)隊(duì)為TeamMD；另一種方法使用文獻(xiàn)[4]提出的影響力最大化算法SCG生成的團(tuán)隊(duì)，所形成團(tuán)隊(duì)命名為TeamSCG。圖6所示為上述4種團(tuán)隊(duì)影響結(jié)點(diǎn)數(shù)比較。

Fig.6　Team influence comparison圖6　團(tuán)隊(duì)影響力比較

圖6為數(shù)據(jù)集Dataset3中各團(tuán)隊(duì)影響力對比，團(tuán)隊(duì)TeamADP與TeamSCG影響結(jié)點(diǎn)數(shù)要高于團(tuán)隊(duì)TeamMD與TeamMW，且TeamADP影響結(jié)點(diǎn)數(shù)比TeamMD提升了10%。實(shí)驗(yàn)表明，當(dāng)團(tuán)隊(duì)人數(shù)相同時(shí)，ApproxDP算法所求弱關(guān)系團(tuán)隊(duì)具有較強(qiáng)的影響力。

除利用獨(dú)立級聯(lián)傳播模型對團(tuán)隊(duì)影響力進(jìn)行評價(jià)外，本文還通過比較所求非弱關(guān)系團(tuán)隊(duì)與弱關(guān)系團(tuán)隊(duì)所占社區(qū)數(shù)對該問題加以驗(yàn)證。令非弱關(guān)系團(tuán)隊(duì)為TeamMW，弱關(guān)系團(tuán)隊(duì)采用ApproxDP算法實(shí)現(xiàn)。首先，本文對數(shù)據(jù)集進(jìn)行了社區(qū)發(fā)現(xiàn)計(jì)算[1]，將DBLP數(shù)據(jù)集中結(jié)點(diǎn)劃分為25個(gè)社區(qū)，然后分析了兩個(gè)團(tuán)隊(duì)中結(jié)點(diǎn)所擁有不同社區(qū)數(shù)的分布情況。實(shí)驗(yàn)同樣采用多次模擬求平均值的方法。如圖7所示為Dataset3中兩個(gè)團(tuán)隊(duì)所占社區(qū)數(shù)比較。從圖中可以看出弱關(guān)系團(tuán)隊(duì)中結(jié)點(diǎn)所影響的不同社區(qū)數(shù)要多于非弱關(guān)系團(tuán)隊(duì)。最后，圖6、圖7表明本文所求得的弱關(guān)系團(tuán)隊(duì)具有更大的社區(qū)影響力。

Fig.7　Communities numbers comparison圖7　團(tuán)隊(duì)所占社區(qū)數(shù)比較

6　結(jié)論

本文提出了一種新的團(tuán)隊(duì)發(fā)現(xiàn)問題——弱關(guān)系團(tuán)隊(duì)發(fā)現(xiàn)，并提出了3類算法解決該問題，分別為貪心算法、精確算法、α-近似算法。貪心算法搜索效率最高，但求解質(zhì)量難以保證；精確算法分別采用回溯法與動態(tài)規(guī)劃方法實(shí)現(xiàn)，適用于問題規(guī)模較小時(shí)的應(yīng)用情況；α-近似算法在動態(tài)規(guī)劃精確算法基礎(chǔ)上，保留可以保證近似率的候選解，具有較高的查詢效率，同時(shí)可以保證一定的近似率。最后，本文利用不同的數(shù)據(jù)集對各算法運(yùn)行效率及求解質(zhì)量進(jìn)行了評價(jià)，并對弱關(guān)系團(tuán)隊(duì)的影響力進(jìn)行了分析，實(shí)驗(yàn)表明所提出的算法可以適用弱關(guān)系團(tuán)隊(duì)形成問題的不同應(yīng)用場景。

References:

[1]Blondel V,Guillaume J,Lambiotte R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,arXiv:0803.0476.

[2]Chai Bianfang,Zhao Xiaopeng,Jia Caiyan,et al.An efficient algorithm for general community detection in content networks[J].Journal of Frontiers of Computer Science and Technology,2014,8(9):1076-1084.

[3]Kempe D,Kleinberg J,Tardos E.Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,Washington,USA,Aug 24-27,2003. New York,USA:ACM,2003:137-146.

[4]Estevez PA,Vera PA,Saito K.Selecting the most influential nodes in social networks[C]//Proceedings of the 2007 International Joint Conference on Neural Networks,Orlando, USA,Aug 12-17,2007.Piscataway,USA:IEEE,2007: 2397-2402.

[5]Lappas T,Liu Kun,Terzi E.Finding a team of experts in social networks[C]//Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Paris,France,Jun 28-Jul 1,2009.New York,USA:ACM, 2009:467-476.

[6]Kargar M,An Aijun.Discovering top-k teams of experts with/without a leader in social networks[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management,Glasgow,UK,Oct 24-28,2011. New York,USA:ACM,2011:985-994.

[7]Majumde A,Datta S,Naidu K.Capacitated team formation problem on social networks[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Beijing,China,Aug 12-16,2012. New York,USA:ACM,2012:1005-1013.

[8]Anagnostopoulos A,Becchetti L,Castillo C,et al.Online team formation in social networks[C]//Proceedings of the 21st International Conference on World Wide Web,Lyon, France,Apr 16-20,2012.New York,USA:ACM,2012: 839-848.

[9]Kargar M,Zihayat M,An Aijun.Affordable and collaborative team formation in an expert network,CSE-2013-01[R]. Department of Computer Science and Engineering,York University,2013.

[10]Sun Huanliang,Lu Zhi,Liu Junling,et al.Top-k attribute difference q-clique queries in graph data[J].Chinese Journal of Computers,2012,35(11):2265-2274.

[11]Granovetter M.The strength of weak ties[J].American Journal of Sociology,1973,78(6):l-18.

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

[13]Zzkarian A,Kusiak A.Forming teams:an analytical approach[J].IIE Transactions,1999,31(1):85-97.

[14]Dunbar R.How many friends does one person need?:Dunbar?s number and other evolutionary quirks[M].London, UK:Faber and Faber,2010.

[15]Garey M R,Johnson D S.Computer and Instractability:a guide to the theory of NP-completeness[M].San Francisco, USA:W H Freeman&Company,1979.

[16]Wang Zhaocai,Tan Jian,Zhu Lanwei,et al.Solving the maximum independent set problem based on molecule parallel supercomputing[J].Applied Mathematics&Information Sciences,2014,8(5):2361-2366.

[17]Wan Pengjun,Jia Xiaohua,Dai Guojun,et al.Fast and simple approximation algorithms for maximum weighted independent set of links[C]//Proceedings of the 33rd Annual IEEE International Conference on Computer Communications,Toronto,Canada,Apr 27-May 2,2014.Piscataway, USA:IEEE,2014:1653-1661.

附中文參考文獻(xiàn):

[2]柴變芳,趙曉鵬,賈彩燕,等.內(nèi)容網(wǎng)絡(luò)廣義社區(qū)發(fā)現(xiàn)有效算法[J].計(jì)算機(jī)科學(xué)與探索,2014,8(9):1076-1084.

[10]孫煥良,盧智,劉俊嶺,等.圖數(shù)據(jù)中Top-k屬性差異qclique查詢[J].計(jì)算機(jī)學(xué)報(bào),2012,35(11):2265-2274.

SUN Huanliang was born in 1969.He is a professor at Shenyang Jianzhu University,and the senior member of CCF.His research interests include spatial database and data mining,etc.

孫煥良（1969—），男，黑龍江望奎人，沈陽建筑大學(xué)教授，CCF高級會員，主要研究領(lǐng)域?yàn)榭臻g數(shù)據(jù)庫，數(shù)據(jù)挖掘等。

FU Shanshan was born in 1989.She is an M.S.candidate at Shenyang Jianzhu University.Her research interest is data mining.

富珊珊（1989—），女，遼寧莊河人，沈陽建筑大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘。

LIU Junling was born in 1972.She is a Ph.D.candidate at Northeastern University,and the member of CCF.Her research interests include spatial database and data mining,etc.

劉俊嶺（1972—），女，遼寧沈陽人，東北大學(xué)博士研究生，CCF會員，主要研究領(lǐng)域?yàn)榭臻g數(shù)據(jù)庫，數(shù)據(jù)挖掘等。

YU Ge was born in 1962.He is a professor and Ph.D.supervisor at Northeastern University,and the senior member of CCF.His research interests include database,data mining,RFID,XML and Web data management,etc.

于戈（1962—），男，遼寧大連人，東北大學(xué)教授、博士生導(dǎo)師，CCF高級會員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫，數(shù)據(jù)挖掘，RFID，XML，Web數(shù)據(jù)管理等。

XU Hongfei was born in 1987.He is a Ph.D.candidate at Northeastern University.His research interest is spatial database.

許鴻斐（1987—），男，山西太原人，東北大學(xué)博士研究生，主要研究領(lǐng)域?yàn)榭臻g數(shù)據(jù)庫。

*The National Natural Science Foundation of China under Grant Nos.61070024,61272180(國家自然科學(xué)基金);the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20120042110028(高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金);the MOE-Intel Special Fund of Information Technology under Grent No.MOE-INTEL-2012-06(教育部-英特爾信息技術(shù)專項(xiàng)科研基金).

Received 2015-06,Accepted 2015-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-08-12,http://www.cnki.net/kcms/detail/11.5602.TP.20150812.1627.003.html

+Corresponding author:E-mail:liujl@sjzu.edu.cn

文獻(xiàn)標(biāo)志碼：A

中圖分類號：TP311

doi:10.3778/j.issn.1673-9418.1507075

Team Formation with Weak Ties in Social Networks?

SUN Huanliang1+,FU Shanshan1,LIU Junling1,2,YU Ge2,XU Hongfei2
1.School of Information and Control Engineering,Shenyang Jianzhu University,Shenyang 110168,China
2.School of Information Science and Engineering,Northeastern University,Shenyang 110006,China

Abstract:As the online social network grows rapidly,the team formation problem becomes more and more popular. Previous research on team formation aimed at finding a team of experts with the lowest communication cost.However, in expert or public jury,as untighten relationship can guarantee diversified attitudes and refrain from prejudice,there are numerous quests which to find a weak connected team.Based on this requirement,this paper proposes the problem of team formation with weak ties in social networks by introducing the concept of weak ties in sociology.This problem aims to find a team with weak ties between members and satisfy the requirement of skills and experience,it is an NP-hard problem.This paper designs three kinds of algorithms for the problem,they are greedy algorithm,exact algorithm and α-approximate algorithm.Every kind of algorithm has distinct property and scope.The experimental results onACM and DBLP real datasets show the quality and confirm the effectiveness and efficiency of proposed algorithms. Key words:social network;team formation;weak ties;greedy algorithm;exact algorithm;approximate algorithm