龍 浩 ，張書奎 ，張 力

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

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

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

1 引言

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

2 相關(guān)工作

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

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

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

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

3.1 最優(yōu)生成樹

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

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

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

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

最優(yōu)生成樹的建立過程類似最小生成樹算法Prim的原理，是以網(wǎng)絡(luò)中的任意節(jié)點vi∈V作為根節(jié)點，并每條邊的權(quán)重按降序排序，每次挑選一個權(quán)重最大的邊，使用Union-Find算法檢查將其加入到最優(yōu)生成樹時，是否會形成環(huán)，重復該步驟直到最優(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個相互獨立的部分，把它稱為初始社區(qū)，記為U={u1,u2,…,uh},h=V-1。

3.2 節(jié)點合并

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

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

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

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

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

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

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

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

3.4 社區(qū)劃分算法

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

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

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

4 算法性能分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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