社會網(wǎng)絡中弱關系團隊形成問題研究*

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

?

社會網(wǎng)絡中弱關系團隊形成問題研究*

孫煥良1+，富珊珊1，劉俊嶺1,2，于戈2，許鴻斐2
1.沈陽建筑大學 信息與控制工程學院，沈陽 110168
2.東北大學 信息科學與工程學院，沈陽 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)絡的迅速發(fā)展，社會網(wǎng)絡的團隊形成問題逐漸成為研究熱點?，F(xiàn)有的社會網(wǎng)絡中團隊形成問題目標是尋找一個成員間溝通代價最小的團隊。然而，實際應用中團隊成員間的不緊密關系使得團隊的觀點多樣化、多角度、無偏見，可以廣泛應用于形成專家評審團隊、大眾評審團等?；诖诵枨?，將社會學的弱關系概念引入團隊形成問題中，提出了一種社會網(wǎng)絡中弱關系團隊形成問題。該問題旨在尋找成員間為弱關系，同時滿足技能、經(jīng)驗值要求的一個團隊，為NP-hard問題。提出了3類算法解決該問題，分別為貪心算法、精確算法、α-近似算法，每類算法有各自的特點與適用范圍。利用ACM和DBLP兩類真實的數(shù)據(jù)集進行實驗，綜合評估了各類算法的效率與求解質(zhì)量，證明了提出算法的有效性。

關鍵詞：社會網(wǎng)絡；團隊形成；弱關系；貪心算法；精確算法；近似算法

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

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

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

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

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

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

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

綜上所述，本文的主要貢獻如下:

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

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

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

2　相關工作

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

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

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

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

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

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

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

3　問題定義

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

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

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

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

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

定理1社會網(wǎng)絡中的弱關系團隊發(fā)現(xiàn)問題是一個NP-hard問題。

4　查詢處理算法

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

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

6.return 1;

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

4.1貪心算法

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

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

4.2精確算法

4.2.1回溯搜索算法

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

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

證明略。

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

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

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

算法1 ExactBB

輸出：最優(yōu)弱關系團隊Tbest。

過程2 Replace(T,s,i)

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

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

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

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

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

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

（2）當C[s]與g[i-1][j]滿足弱關系和關鍵字約束時，在g[i-1][j]基礎上加入C[s]，所得解為g[i-1][j]+ C[s]；

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

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

定理3設已求得一組弱關系團隊g[K][1]，當前要加入元素分值為w，若對任意i(0≤i

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

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

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

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

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

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

算法2 ExactDP

輸出：最優(yōu)弱關系團隊T。

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

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

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

4.3α-近似算法

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

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

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

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

算法3 ApproxDP

輸出：弱關系團隊T。

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

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

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

5　實驗結(jié)果與分析

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

5.1實驗數(shù)據(jù)

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

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

5.2算法運行效率比較

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

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

Fig.2　Efficiency comparison between ExactDP and ExactBB圖2　ExactDP與ExactBB算法運行效率比較

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

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

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

5.3查詢結(jié)果分析

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

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

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

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

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

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

Fig.6　Team influence comparison圖6　團隊影響力比較

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

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

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

6　結(jié)論

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

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.

附中文參考文獻:

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

[10]孫煥良,盧智,劉俊嶺,等.圖數(shù)據(jù)中Top-k屬性差異qclique查詢[J].計算機學報,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—），男，黑龍江望奎人，沈陽建筑大學教授，CCF高級會員，主要研究領域為空間數(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—），女，遼寧莊河人，沈陽建筑大學碩士研究生，主要研究領域為數(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—），女，遼寧沈陽人，東北大學博士研究生，CCF會員，主要研究領域為空間數(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—），男，遼寧大連人，東北大學教授、博士生導師，CCF高級會員，主要研究領域為數(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—），男，山西太原人，東北大學博士研究生，主要研究領域為空間數(shù)據(jù)庫。

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

Received 2015-06,Accepted 2015-08.

CNKI網(wǎng)絡優(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

文獻標志碼：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