群智感知網(wǎng)絡(luò)中基于社會(huì)關(guān)系的社區(qū)發(fā)現(xiàn)算法

龍 浩 ，張書奎 ，張 力

1.蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006

2.徐州工業(yè)職業(yè)技術(shù)學(xué)院 信息與電氣工程學(xué)院，江蘇 徐州 221002

3.江蘇省現(xiàn)代企業(yè)信息化應(yīng)用支撐軟件工程技術(shù)研發(fā)中心，江蘇 蘇州 215104

1 引言

隨著嵌入了大量傳感器的移動(dòng)智能設(shè)備迅速普及，移動(dòng)群智感知應(yīng)用得到了廣泛的應(yīng)用，移動(dòng)用戶攜帶移動(dòng)終端設(shè)備能夠在不同的位置監(jiān)測到復(fù)雜的數(shù)據(jù)信息（比如：噪音、天氣、大氣、交通）。目前開發(fā)了大量的移動(dòng)群智感知應(yīng)用，包括醫(yī)療健康、環(huán)境監(jiān)測、交通狀況等方面[1-2]。移動(dòng)群智感知應(yīng)用的任務(wù)一般需要根據(jù)用戶的位置信息和行為特征進(jìn)行分配，因此統(tǒng)計(jì)并分析用戶的歷史記錄，挖掘用戶的行為模式是感知任務(wù)分配的重要前提。從社交網(wǎng)絡(luò)可以看出，現(xiàn)實(shí)中用戶內(nèi)部社會(huì)屬性通過凝聚和細(xì)化形成社區(qū)結(jié)構(gòu)，即同一社區(qū)中的用戶彼此緊密聯(lián)系，彼此之間建立了一定的信任關(guān)系，因此社會(huì)關(guān)系比較固定。相反，不同社區(qū)的用戶社會(huì)屬性包括興趣愛好、活動(dòng)范圍、交往聯(lián)系等都相差很大。社區(qū)發(fā)現(xiàn)的目標(biāo)是根據(jù)用戶特定的行為模式和社會(huì)屬性劃分網(wǎng)絡(luò)，并探索網(wǎng)絡(luò)潛在關(guān)系模型，提煉社區(qū)成員具有的共同特性。群智感知應(yīng)用利用用戶的移動(dòng)和交互完成感知任務(wù)，現(xiàn)實(shí)中執(zhí)行感知任務(wù)的人具有一定的社會(huì)關(guān)系，它是用戶生活工作所具備的基本社會(huì)屬性，根據(jù)行為規(guī)則和交互頻率，可以將不同的用戶劃分為不同的社區(qū)。群智感知應(yīng)用依靠歷史記錄信息進(jìn)行聚類發(fā)掘，識(shí)別網(wǎng)絡(luò)固有的社區(qū)結(jié)構(gòu)，感知平臺(tái)可以根據(jù)不同社區(qū)的特征值將對(duì)應(yīng)的感知任務(wù)分發(fā)給該社區(qū)的用戶執(zhí)行，提高任務(wù)分發(fā)效率和任務(wù)執(zhí)行的正確性[3]。因此，通過社區(qū)分配感知任務(wù)是群智感知應(yīng)用研究的重要步驟，目前社區(qū)劃分方法有基于用戶社會(huì)角色的屬性社區(qū)劃分[4]，基于用戶地理位置的位置社區(qū)劃分[5]等。社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)對(duì)于提升感知任務(wù)用戶群的匹配度，節(jié)約感知任務(wù)執(zhí)行時(shí)間，提高感知數(shù)據(jù)質(zhì)量都具有十分重要作用。

2 相關(guān)工作

在群智感知研究中，任務(wù)分配是群智感知應(yīng)用研究的重要環(huán)節(jié)，而任務(wù)分配主要通過挖掘用戶特征提升任務(wù)分配用戶群的匹配度，從而提升感知數(shù)據(jù)質(zhì)量?；谏鐓^(qū)發(fā)現(xiàn)的感知任務(wù)分配算法是目前研究的熱點(diǎn)方向。在群智感知應(yīng)用中，移動(dòng)用戶的交互構(gòu)成了一種典型的動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)，用戶之間的社會(huì)關(guān)系為感知任務(wù)的分配和執(zhí)行提供了強(qiáng)有力的支持，相互之間內(nèi)在的社會(huì)關(guān)系形成了緊密相聯(lián)的社區(qū)[6-7]。趙衛(wèi)績等人[8]提出一種基于加權(quán)共同鄰居相似度的局部社區(qū)發(fā)現(xiàn)算法，通過計(jì)算節(jié)點(diǎn)間的相似度指標(biāo)發(fā)現(xiàn)局部社區(qū)。然而該方法社區(qū)發(fā)現(xiàn)的特征因子過于單一，其準(zhǔn)確性有待進(jìn)一步提高。趙健等人[9]在群智感知服務(wù)中提出了一種面向有向加權(quán)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法，通過計(jì)算節(jié)點(diǎn)間的最優(yōu)路徑，相似度等合理劃分社區(qū)。然而該方法中并沒有考慮節(jié)點(diǎn)的動(dòng)態(tài)性，也沒有考慮特征因子的權(quán)重分配。Chen等人[10]提出了一種基于用戶交互行為的加權(quán)動(dòng)態(tài)在線社交網(wǎng)絡(luò)社區(qū)檢測方法，研究了在線社交網(wǎng)絡(luò)中用戶的交互行為，通過描述個(gè)體之間的親密度以及用戶模塊密度進(jìn)行社區(qū)探測。Ibrahim等人[11]提出了一種基于網(wǎng)絡(luò)概念格結(jié)構(gòu)的概念興趣度社區(qū)檢測算法，首先探測所有的小團(tuán)體和團(tuán)體之間的關(guān)聯(lián)，然后使用穩(wěn)定性指數(shù)去除社區(qū)之間的關(guān)聯(lián)，合并相關(guān)的鄰近小團(tuán)體。然而該方法中基于興趣度的小團(tuán)體探測，未考慮到節(jié)點(diǎn)的位置因素，社區(qū)合并方法時(shí)間復(fù)雜度較高，不適合實(shí)時(shí)性要求高的群智感知應(yīng)用。針對(duì)群智感知社區(qū)發(fā)現(xiàn)算法的問題，提出了一種基于社會(huì)關(guān)系的社區(qū)發(fā)現(xiàn)算法，首先給出了用戶之間邊權(quán)重定義方式，并基于此定義選擇權(quán)重最大的邊生成最優(yōu)生成樹作為初始社區(qū)；進(jìn)而計(jì)算未劃入社區(qū)的其他用戶與初始社區(qū)的合并因子，形成明顯的社區(qū)結(jié)構(gòu)；最后，將重疊率比較高的用戶劃分到對(duì)應(yīng)社區(qū)，從而得到最終的社區(qū)發(fā)現(xiàn)結(jié)果。

3 社區(qū)發(fā)現(xiàn)算法

通過量化節(jié)點(diǎn)之間的社會(huì)關(guān)系，將節(jié)點(diǎn)聚類成具有真實(shí)社會(huì)關(guān)系的社區(qū)網(wǎng)絡(luò)。針對(duì)網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)，首先構(gòu)造出節(jié)點(diǎn)的最優(yōu)生成樹，形成初始社區(qū)，然后計(jì)算相鄰節(jié)點(diǎn)的合并因子，通過合并因子來判斷節(jié)點(diǎn)是否處于同一社區(qū)，完成最優(yōu)生成樹的合并，形成明顯的社區(qū)結(jié)構(gòu)，最后用社區(qū)調(diào)整因子來檢驗(yàn)社區(qū)劃分的緊密度，衡量社區(qū)結(jié)構(gòu)劃分效果，并進(jìn)行適當(dāng)調(diào)整，從而完成網(wǎng)絡(luò)中社區(qū)的最佳劃分。具體社區(qū)劃分過程如圖1所示。

圖1 社區(qū)劃分過程示意圖

3.1 最優(yōu)生成樹

假設(shè)G(V,E)是無向加權(quán)網(wǎng)絡(luò)，節(jié)點(diǎn)集合V包含了n個(gè)節(jié)點(diǎn)，邊集合E包含了e條邊，每一條邊有兩個(gè)頂點(diǎn)(vi,vj)在V中。社區(qū)劃分的目標(biāo)就是要將G劃分成k個(gè)社區(qū)：U={u1,u2,…,uk}，其中ui≠ui∩uj=

定義1從網(wǎng)絡(luò)G中的節(jié)點(diǎn)vi開始，直到包含所有的節(jié)點(diǎn)集合V截止，以任意節(jié)點(diǎn)vi為開始的最優(yōu)生成樹路徑值的計(jì)算通過以下公式得出：

其中，j,x,y為中間相鄰節(jié)點(diǎn)，最優(yōu)生成樹的構(gòu)造是通過所有相鄰節(jié)點(diǎn)的權(quán)值φ最大值求和[12]，φ(i,j)為計(jì)算兩相鄰節(jié)點(diǎn)的權(quán)重值，稱作兩節(jié)點(diǎn)的社會(huì)關(guān)系值，具體計(jì)算辦法如下：

式（2）中Γ(vi)表示節(jié)點(diǎn)i的鄰居集。

最優(yōu)生成樹的建立過程類似最小生成樹算法Prim的原理，是以網(wǎng)絡(luò)中的任意節(jié)點(diǎn)vi∈V作為根節(jié)點(diǎn)，并每條邊的權(quán)重按降序排序，每次挑選一個(gè)權(quán)重最大的邊，使用Union-Find算法檢查將其加入到最優(yōu)生成樹時(shí)，是否會(huì)形成環(huán)，重復(fù)該步驟直到最優(yōu)生成樹中有V-1條邊。網(wǎng)絡(luò)G(V,E)的一棵最優(yōu)生成樹設(shè)為OST(V′,E′),V′=V,|V′|=|V|,E′?E,E′=V-1 。在最優(yōu)生成樹OST中選擇邊權(quán)值最大的V-1條邊，設(shè)為集合E′，然后將OST中在集合E′中的邊移除，得到了V-1個(gè)相互獨(dú)立的部分，把它稱為初始社區(qū)，記為U={u1,u2,…,uh},h=V-1。

3.2 節(jié)點(diǎn)合并

目前大多數(shù)社區(qū)劃分算法通過計(jì)算節(jié)點(diǎn)間的相似度來實(shí)現(xiàn)，然而由于聚類方法的不同，節(jié)點(diǎn)間相似度的定義在不同的算法中各不相同?？紤]到群智感知的應(yīng)用場景，劃分的最終目標(biāo)是根據(jù)節(jié)點(diǎn)區(qū)域來分發(fā)不同的任務(wù)，因此社區(qū)的劃分主要根據(jù)節(jié)點(diǎn)間的社會(huì)關(guān)系和位置聚類形成的，本文社區(qū)劃分方法提出節(jié)點(diǎn)合并因子的定義，將節(jié)點(diǎn)的節(jié)點(diǎn)合并因子定義為節(jié)點(diǎn)間社會(huì)關(guān)聯(lián)度和位置特征，通過節(jié)點(diǎn)合并因子來實(shí)現(xiàn)初始社區(qū)的合并，形成明顯的社區(qū)結(jié)構(gòu)。本文將節(jié)點(diǎn)合并因子量化為兩個(gè)值：第一個(gè)值是根據(jù)節(jié)點(diǎn)歷史相遇記錄引入一個(gè)社會(huì)壓力度量值（Social Pressure Metric，SPM）來探測節(jié)點(diǎn)間連接質(zhì)量πi,j[13]，衡量節(jié)點(diǎn)間的社會(huì)關(guān)聯(lián)度；第二個(gè)值是通過GPS獲取移動(dòng)用戶的位置特征（經(jīng)度和緯度）并采用歐氏距離公式計(jì)算兩節(jié)點(diǎn)的距離作為節(jié)點(diǎn)位置特征。社區(qū)的合并需要根據(jù)節(jié)點(diǎn)間的聯(lián)系緊密度來計(jì)算，一般來說兩個(gè)節(jié)點(diǎn)之間屬于朋友和鄰居關(guān)系，可以認(rèn)為這兩個(gè)節(jié)點(diǎn)聯(lián)系緊密，具有較高的連接質(zhì)量。然而，存在朋友關(guān)系的節(jié)點(diǎn)對(duì)可能會(huì)處在距離比較遠(yuǎn)的兩個(gè)區(qū)域，根據(jù)感知任務(wù)區(qū)域劃分的特點(diǎn)，這兩個(gè)節(jié)點(diǎn)不能劃分到同一社區(qū)，因此，需要考慮采用節(jié)點(diǎn)的位置特征值來進(jìn)行校驗(yàn)。下面具體對(duì)節(jié)點(diǎn)合并因子進(jìn)行定義。

定義2節(jié)點(diǎn)合并因子包括節(jié)點(diǎn)間社會(huì)關(guān)聯(lián)度和位置特征，節(jié)點(diǎn)之間的社會(huì)關(guān)聯(lián)度定義為SPM的倒數(shù)。節(jié)點(diǎn)間的位置特征值由歐氏距離公式[14]計(jì)算獲得。

其中，T為任務(wù)執(zhí)行周期，tinter為節(jié)點(diǎn)相遇間隔時(shí)間，r為間隔次數(shù)，(xi,yi)為節(jié)點(diǎn)i的坐標(biāo)位置。下面介紹具體合并過程。首先計(jì)算初始社區(qū)中任意兩個(gè)社區(qū)節(jié)點(diǎn)對(duì)的社會(huì)關(guān)聯(lián)度是否大于閾值ψ，如果大于閾值則計(jì)算節(jié)點(diǎn)間距離是否小于閾值ε，兩個(gè)條件都滿足則建立兩個(gè)節(jié)點(diǎn)的連接，并將兩個(gè)節(jié)點(diǎn)保存到同一社區(qū)ui中，直到所有的社區(qū)不能再合并為止，形成的{u1,u2,…,uk}即為合并的社區(qū)劃分。為了降低節(jié)點(diǎn)間節(jié)點(diǎn)合并因子的計(jì)算和判別，考慮如果兩個(gè)初始社區(qū)中任意節(jié)點(diǎn)對(duì)之間的社會(huì)關(guān)聯(lián)度和距離滿足閾值，則將兩個(gè)社區(qū)進(jìn)行合并。

在社區(qū)合并過程中，可能會(huì)有一些顧慮。首先，假設(shè)節(jié)點(diǎn)在一定時(shí)間內(nèi)處于有限的遷移場景中。事實(shí)上，節(jié)點(diǎn)的活動(dòng)具有一定的特點(diǎn)，在某個(gè)時(shí)間段，節(jié)點(diǎn)的活動(dòng)范圍一般情況下并不會(huì)超出所屬社區(qū)的范圍，尤其在接收感知任務(wù)期間。第二個(gè)問題是有部分節(jié)點(diǎn)移動(dòng)到別的區(qū)域或者有新的節(jié)點(diǎn)加入。首先可以根據(jù)移動(dòng)節(jié)點(diǎn)的歷史信息計(jì)算是否可以加入對(duì)應(yīng)社區(qū)，如果不滿足條件，計(jì)算移動(dòng)節(jié)點(diǎn)或新節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的距離，如果小于閾值ε則加入鄰居節(jié)點(diǎn)社區(qū)。第三個(gè)問題是在某個(gè)時(shí)間階段后，大部分節(jié)點(diǎn)進(jìn)行了移動(dòng)，社區(qū)需要進(jìn)行重新劃分。社區(qū)的動(dòng)態(tài)變化特征超出了本文的范圍，將其作為未來的工作。

3.3 社區(qū)調(diào)整

考慮到在實(shí)際網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)是自然形成的，社區(qū)內(nèi)部各個(gè)節(jié)點(diǎn)的連接比社區(qū)間節(jié)點(diǎn)的連接要緊密得多，然而這只是一個(gè)定性的指標(biāo)。本文提出了社區(qū)調(diào)整因子的概念，從定量角度來衡量社區(qū)劃分的質(zhì)量，對(duì)一些社區(qū)間的重疊節(jié)點(diǎn)做進(jìn)一步優(yōu)化，重疊節(jié)點(diǎn)即節(jié)點(diǎn)i∈uk，同時(shí)i∈uj，優(yōu)化的目的是要將重疊節(jié)點(diǎn)i劃分到對(duì)應(yīng)社區(qū)中。

定義3社區(qū)調(diào)整因子通過任意節(jié)點(diǎn)i的度來衡量社區(qū)劃分質(zhì)量。如果?i∈uk，社區(qū)uk應(yīng)滿足(uk)≥(uk)。

其中(uk)表示節(jié)點(diǎn)i與社區(qū)uk內(nèi)中其他節(jié)點(diǎn)連接邊的條數(shù)，(uk)表示節(jié)點(diǎn)i與社區(qū)uk外其他節(jié)點(diǎn)連接的邊數(shù)。如果社區(qū)內(nèi)任意節(jié)點(diǎn)與社區(qū)外部節(jié)點(diǎn)的連接，比它與社區(qū)內(nèi)部節(jié)點(diǎn)的連接更緊密，那么就將該節(jié)點(diǎn)調(diào)節(jié)到對(duì)應(yīng)社區(qū)。

3.4 社區(qū)劃分算法

社區(qū)劃分算法實(shí)現(xiàn)過程主要包括三個(gè)步驟：（1）根據(jù)公式（2）計(jì)算各節(jié)點(diǎn)的權(quán)值，構(gòu)造一棵最優(yōu)生成樹，然后刪除最優(yōu)生成樹中集合E*中的邊，將最優(yōu)生成樹分裂成h個(gè)初始社區(qū)；（2）根據(jù)公式（3）計(jì)算相鄰節(jié)點(diǎn)對(duì)的節(jié)點(diǎn)合并因子，判斷節(jié)點(diǎn)合并因子是否滿足閾值，將初始社區(qū)進(jìn)行合并，重復(fù)該步驟，直到所有的初始社區(qū)全部合并為止；（3）判斷社區(qū)調(diào)整因子指標(biāo)，衡量社區(qū)劃分質(zhì)量，調(diào)節(jié)不滿足定義3的相關(guān)節(jié)點(diǎn)到對(duì)應(yīng)社區(qū)。

算法1社區(qū)劃分算法具體描述如下：

輸入：網(wǎng)絡(luò)G(V,E)，相鄰節(jié)點(diǎn)合并因子閾值ψandε。

輸出：劃分完整的社區(qū)結(jié)構(gòu)集合U={u1,u2,…,uk}。

1.for each node pair(vi,vj)inV

2. Calculatedφ(i,j)by（2）

3.end for

4.Build OSTT

5.RemovingV-1the edges of highest weight fromE′

6. ProducedV-1communitiesU={u1,u2,…,uh}

7.for each community pair(ui,uj)inU

8. if ?πi,j>ψandd(vi,vj)<εthen

9. mergeuiandujtoui

10. deleteui

11. end if

12.if all communities cannot merge then

13. break

14. end if

15.end for

16.Get merged communitiesU={u1,u2,…,uk}

17.whileifrom 1 tokdo

18. if

19. continue

20. else

21.adjustiinto the corresponding community

22. end if

23.end

24.returnU={u1,u2,…,uk}

算法描述中節(jié)點(diǎn)對(duì)的社會(huì)關(guān)聯(lián)度判斷閾值ψ需要根據(jù)任務(wù)的時(shí)間周期來決定。連接距離判定閾值ε根據(jù)感知任務(wù)區(qū)域的半徑（單位：m）一般ε∈（50，250）[15]。算法復(fù)雜度分析，首先最優(yōu)生成樹的建立類似如Prim算法，其運(yùn)行時(shí)間是O(|E|+|V|lb|V|)=O(m+nlbn)，然后將初始社區(qū)合并時(shí)間復(fù)雜度為O(n2)，社區(qū)調(diào)整因子檢驗(yàn)時(shí)間復(fù)雜度為k。因此整個(gè)社區(qū)劃分算法的時(shí)間復(fù)雜度為O(n2+nlbn+n)。

4 算法性能分析

為了驗(yàn)證社區(qū)發(fā)現(xiàn)算法的劃分效果，通過計(jì)算機(jī)合成網(wǎng)絡(luò)和真實(shí)世界網(wǎng)絡(luò)分別進(jìn)行社區(qū)發(fā)現(xiàn)實(shí)驗(yàn)。實(shí)驗(yàn)在一臺(tái)配置了Inter Core i7-5557U CPU 3.10 GHz和8 GB內(nèi)存的筆記本上進(jìn)行，操作系統(tǒng)為 Windows 8.1，使用JAVA語言在myclipse編程實(shí)現(xiàn)。本文算法與常見典型社區(qū)發(fā)現(xiàn)算法進(jìn)行了對(duì)比實(shí)驗(yàn)，采用的對(duì)比算法主要包括：基準(zhǔn)社區(qū)發(fā)現(xiàn)算法（CNM）[16]，基于增量密度的社區(qū)檢測算法（IncOrder）[16]，基于最優(yōu)生成樹和模塊的社區(qū)劃分算法（CDOSTM）[12]。采用下面三種評(píng)價(jià)方法評(píng)價(jià)社區(qū)發(fā)現(xiàn)算法的效果，驗(yàn)證社區(qū)結(jié)構(gòu)的有效性、合理性和正確性。所有實(shí)驗(yàn)結(jié)果至少1 000輪后取平均值。

采用歸一化互信息[17］（Normalized Mutual Information，NMI）來度量通過算法劃分社區(qū)和真實(shí)社區(qū)之間的差異程度。設(shè)真實(shí)社區(qū)結(jié)構(gòu)劃分為G={g1,g2,…,gn}，算法劃分的社區(qū)結(jié)構(gòu)為C={u1,u2,…,uk}。社區(qū)劃分的歸一化互信息表示為：

其中，Nij=gn?uk表示原始社區(qū)和算法劃分社區(qū)共同擁有的節(jié)點(diǎn)數(shù)，Ni.表示社區(qū)gn的節(jié)點(diǎn)數(shù)，N.j表示社區(qū)uk的節(jié)點(diǎn)數(shù)，算法劃分的社區(qū)與原始社區(qū)完全一致，則NMI=1，當(dāng)完全不一致時(shí)，NMI=0。

采用社區(qū)模塊度評(píng)價(jià)函數(shù)Q[18-19]來評(píng)價(jià)社區(qū)劃分的質(zhì)量，函數(shù)定義為社區(qū)內(nèi)實(shí)際連接數(shù)目與隨機(jī)條件下期望連接數(shù)之差，具體函數(shù)公式如下：

公式中，n表示劃分社區(qū)的數(shù)量，E表示節(jié)點(diǎn)連接的總邊數(shù)，Ec表示社區(qū)中節(jié)點(diǎn)間連接的總邊數(shù)，DC表示劃分社區(qū)后節(jié)點(diǎn)間的權(quán)重之和。由公式（5）可以知道，當(dāng)網(wǎng)絡(luò)具有明顯的社區(qū)結(jié)構(gòu)時(shí)，Q接近為1，當(dāng)網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)不明顯時(shí)，Q接近于0。在實(shí)際社區(qū)劃分算法中Q通常在[0.3，0.7]之間，通常認(rèn)為Q>0.3時(shí)算法劃分具有較好的社區(qū)結(jié)構(gòu)。

社區(qū)劃分結(jié)果的正確性通過調(diào)整蘭德系數(shù)ARI（Adjusted Rand Index）[20]指標(biāo)進(jìn)行評(píng)價(jià)，ARI的定義如下：

數(shù)據(jù)集的兩個(gè)社區(qū)劃分設(shè)為A和B，其中A有KA個(gè)簇，B有KB個(gè)簇，Ni表示劃分A中第i個(gè)簇中節(jié)點(diǎn)的數(shù)量，Nj表示劃分B中的第j個(gè)簇中節(jié)點(diǎn)的數(shù)量，Nij表示在劃分A的第i個(gè)簇中的節(jié)點(diǎn)同時(shí)也在劃分B的第j個(gè)簇中節(jié)點(diǎn)的數(shù)量。ARI可以用來評(píng)價(jià)社區(qū)發(fā)現(xiàn)算法的效率和劃分社區(qū)與真實(shí)社區(qū)的吻合程度。從ARI的定義可以看到，ARI(A,B)越接近于1，表示社區(qū)之間的關(guān)系越獨(dú)立，如果ARI(A,B)越接近于0，則表示社區(qū)之間的關(guān)系越緊密。

首先進(jìn)行合成網(wǎng)絡(luò)實(shí)驗(yàn)，采用LFR作為測試網(wǎng)絡(luò)，LFR是目前社區(qū)發(fā)現(xiàn)算法實(shí)驗(yàn)的基準(zhǔn)測試網(wǎng)絡(luò)，是最為常用的模擬數(shù)據(jù)集，它模擬了真實(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)度和社區(qū)大小的無標(biāo)度性質(zhì)，能夠用來評(píng)價(jià)算法發(fā)現(xiàn)社區(qū)的質(zhì)量。通過設(shè)置不同的混合參數(shù)，能夠生成不同類型的模擬網(wǎng)絡(luò)，節(jié)點(diǎn)間的權(quán)重隨機(jī)生成。實(shí)驗(yàn)中LFR基準(zhǔn)網(wǎng)絡(luò)設(shè)置參數(shù)如表1所示。

表1 LFR基準(zhǔn)測試網(wǎng)絡(luò)參數(shù)設(shè)置

在表1中列出a和b兩種綜合網(wǎng)絡(luò)的參數(shù)，其中a代表網(wǎng)絡(luò)劃分的社區(qū)數(shù)相對(duì)較少，b代表網(wǎng)絡(luò)劃分的社區(qū)數(shù)相對(duì)較多。n表示節(jié)點(diǎn)的總數(shù)；m表示節(jié)點(diǎn)之間邊的總數(shù)；k表示網(wǎng)絡(luò)中節(jié)點(diǎn)間平均權(quán)重；minc表示最小社區(qū)包含的節(jié)點(diǎn)的數(shù)量；maxc表示最大社區(qū)包含的節(jié)點(diǎn)的數(shù)量；mu表示節(jié)點(diǎn)與社區(qū)外部連接的概率，定義為重疊參數(shù)。LFR基準(zhǔn)網(wǎng)絡(luò)中，mu的值越大，社區(qū)發(fā)現(xiàn)的難度就越大。因此對(duì)每個(gè)重疊參數(shù)mu值，在實(shí)驗(yàn)過程中隨機(jī)生成20個(gè)模擬網(wǎng)絡(luò)，對(duì)應(yīng)四個(gè)算法的NMI，ARI值分別為在這20個(gè)模擬網(wǎng)絡(luò)上運(yùn)行得到它們的平均值。算法對(duì)比如圖2、圖3所示。

圖2 LFR基準(zhǔn)網(wǎng)絡(luò)中NMI值的算法對(duì)比圖

從圖2（a）和圖3（a）中可以觀察到本文算法相比其他三種算法具有較優(yōu)的社區(qū)檢測結(jié)果。尤其當(dāng)mu<0.4時(shí)，本文算法的NMI和ARI值接近于1，此時(shí)的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)比較清晰，能夠很準(zhǔn)確地檢測到網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，得到的劃分結(jié)果幾乎完全接近正確的劃分結(jié)果，而檢測結(jié)果最差的是基準(zhǔn)算法CNM。當(dāng)0.4

圖3 LFR基準(zhǔn)網(wǎng)絡(luò)中ARI值的算法對(duì)比圖

真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)中，選擇三個(gè)數(shù)據(jù)集來驗(yàn)證算法的有效性，包括Football、Amazon、Gowalla。其中Football有115個(gè)節(jié)點(diǎn)，613條邊，劃分成12個(gè)社區(qū)，節(jié)點(diǎn)關(guān)系比較清晰，網(wǎng)絡(luò)相對(duì)較簡單。Amazon是一個(gè)大型網(wǎng)絡(luò)，每個(gè)商品都有自己的屬性，根據(jù)商品的不同屬性進(jìn)行分類，能更好地測試算法性能的伸縮性。Gowalla數(shù)據(jù)集是一個(gè)基于地點(diǎn)的社交網(wǎng)絡(luò)，用戶用簽到的方式通過公共API分享他的位置，通過不定時(shí)的簽到能夠獲得用戶的位置信息，為分析人的行為特征提供了重要的依據(jù)，Gowalla數(shù)據(jù)集非常適合對(duì)本文算法進(jìn)行性能檢驗(yàn)。三種真實(shí)網(wǎng)絡(luò)由簡單到復(fù)雜，網(wǎng)絡(luò)節(jié)點(diǎn)有各自的特點(diǎn)，因此更能檢驗(yàn)算法的性能和效果。采用三種評(píng)價(jià)標(biāo)準(zhǔn)來進(jìn)行算法的比較，具體結(jié)果如表2所示。

表2 不同數(shù)據(jù)集的具體算法比較

從表2中可以看出本文算法相比其他三種算法，無論是簡單網(wǎng)絡(luò)還是復(fù)雜網(wǎng)絡(luò)的社區(qū)劃分都能取得很好的效果，尤其對(duì)Gowalla數(shù)據(jù)集的社區(qū)劃分，其他三個(gè)算法的效果與本文的算法相差較大，由于Gowalla數(shù)據(jù)集中用戶是動(dòng)態(tài)移動(dòng)的，用戶移動(dòng)到什么地方，怎樣移動(dòng)，用戶的移動(dòng)和社會(huì)關(guān)系是如何關(guān)聯(lián)的，都是隨時(shí)變化的，而本文算法恰好是基于移動(dòng)節(jié)點(diǎn)的行為特征來進(jìn)行社區(qū)的劃分，因此能取得很好的效果。

5 結(jié)束語

社會(huì)關(guān)系是目前群智感知應(yīng)用中任務(wù)分發(fā)的研究難點(diǎn)，涉及記錄的時(shí)間、空間和行為等多種特征因子。本文首先借助社會(huì)網(wǎng)絡(luò)理論，綜合考慮影響社會(huì)關(guān)系的多維因素，提取移動(dòng)節(jié)點(diǎn)間的最優(yōu)生成樹、節(jié)點(diǎn)合并因子、社區(qū)調(diào)整因子作為社會(huì)關(guān)系量化的特征因子，抽象和識(shí)別出節(jié)點(diǎn)的行為模式，將用戶合理劃分成不同的社區(qū)。最后，通過實(shí)驗(yàn)驗(yàn)證本文所提社區(qū)發(fā)現(xiàn)算法具有較好的動(dòng)態(tài)適應(yīng)性、有效性和準(zhǔn)確性。后續(xù)工作將主要針對(duì)社區(qū)劃分的動(dòng)態(tài)性，以及基于社區(qū)劃分的移動(dòng)群智感知任務(wù)分配算法進(jìn)行研究。