群智感知網絡中基于社會關系的社區發現算法

龍 浩 ，張書奎 ，張 力

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

2.徐州工業職業技術學院 信息與電氣工程學院，江蘇 徐州 221002

3.江蘇省現代企業信息化應用支撐軟件工程技術研發中心，江蘇 蘇州 215104

1 引言

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

2 相關工作

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

3 社區發現算法

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

圖1 社區劃分過程示意圖

3.1 最優生成樹

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

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

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

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

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

3.2 節點合并

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

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

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

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

3.3 社區調整

考慮到在實際網絡中社區結構是自然形成的，社區內部各個節點的連接比社區間節點的連接要緊密得多，然而這只是一個定性的指標。本文提出了社區調整因子的概念，從定量角度來衡量社區劃分的質量，對一些社區間的重疊節點做進一步優化，重疊節點即節點i∈uk，同時i∈uj，優化的目的是要將重疊節點i劃分到對應社區中。

定義3社區調整因子通過任意節點i的度來衡量社區劃分質量。如果?i∈uk，社區uk應滿足(uk)≥(uk)。

其中(uk)表示節點i與社區uk內中其他節點連接邊的條數，(uk)表示節點i與社區uk外其他節點連接的邊數。如果社區內任意節點與社區外部節點的連接，比它與社區內部節點的連接更緊密，那么就將該節點調節到對應社區。

3.4 社區劃分算法

社區劃分算法實現過程主要包括三個步驟：（1）根據公式（2）計算各節點的權值，構造一棵最優生成樹，然后刪除最優生成樹中集合E*中的邊，將最優生成樹分裂成h個初始社區；（2）根據公式（3）計算相鄰節點對的節點合并因子，判斷節點合并因子是否滿足閾值，將初始社區進行合并，重復該步驟，直到所有的初始社區全部合并為止；（3）判斷社區調整因子指標，衡量社區劃分質量，調節不滿足定義3的相關節點到對應社區。

算法1社區劃分算法具體描述如下：

輸入：網絡G(V,E)，相鄰節點合并因子閾值ψandε。

輸出：劃分完整的社區結構集合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}

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

4 算法性能分析

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

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

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

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

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

社區劃分結果的正確性通過調整蘭德系數ARI（Adjusted Rand Index）[20]指標進行評價，ARI的定義如下：

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

首先進行合成網絡實驗，采用LFR作為測試網絡，LFR是目前社區發現算法實驗的基準測試網絡，是最為常用的模擬數據集，它模擬了真實網絡中節點度和社區大小的無標度性質，能夠用來評價算法發現社區的質量。通過設置不同的混合參數，能夠生成不同類型的模擬網絡，節點間的權重隨機生成。實驗中LFR基準網絡設置參數如表1所示。

表1 LFR基準測試網絡參數設置

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

圖2 LFR基準網絡中NMI值的算法對比圖

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

圖3 LFR基準網絡中ARI值的算法對比圖

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

表2 不同數據集的具體算法比較

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

5 結束語

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