節點自適應社會變化的機會網絡社區檢測算法

陶 洋，倪 強

（重慶郵電大學 通信與信息工程學院，重慶400065）

0 引 言

目前，研究者通過復雜的網絡分析提出多個應用于復雜網絡的社區檢測算法［1－5］，例如利用節點的相似度和定義節點的中心度等節點屬性［6－7］來分析社區結構。這些算法可以看成是集中式的社區檢測算法，算法中考慮的節點間相似度及中心度的計算均依賴于服務器統一收集節點間聯系信息，但實際網絡環境中是很難實現的。因此，研究者在充分考慮節點的自組織特性基礎上提出由節點本身收集信息的分布式檢測算法，主要有：SIMPLE 算法、KCLIQUE算法和模塊度算法［8］。文獻 ［9］提出的Ker－nighan－Lin算法，類似于K－CLIQUE 算法定義節點能夠與所有相鄰節點相遇接觸，節點間形成一個大小為K 的完全子圖，節點視具體情況更新熟悉節點集；文獻 ［10］通過對已有社區結構檢測算法的研究，提出局部模塊化社區結構的概念，在局部社區結構內的節點不需要通過服務器來收集信息。SIMPLE 算法［8］比較其它算法表現出計算復雜度低的優勢，因此，本文在SIMPLE 算法基礎上提出兩種策略來實現局部社區動態檢測的過程。

1 問題描述

上面所述的3種分布式社區檢測算法都能夠檢測社區結構，但它們存在一個共同的限制因素：由于節點僅僅維護與其相遇節點間的信息，節點在不同社區間移動時，并不完全熟悉所在局部社區和熟悉節點集內節點的信息。例如，假設有如下場景：用戶A 的日常時間大部分聚集在兩個社會群體C1／C2中，白天處在工作范圍的社會群體中，晚上處在社交朋友的社會群體中。另假設用戶B 是用戶A的同事，如果每天在工作時間里，用戶B 與用戶A 都能夠相遇，那么可以說用戶B 存在于用戶A 的局部社區內 （反之亦然）。然而，再假設用戶A 下班后與自己身邊的朋友一起去健身，用戶A 與用戶B 之間的接觸就沒有那么頻繁甚至不能相遇，或者說用戶B 更換工作去了另一個地區。在這些情況下，以上3種算法都不能夠準確檢測到此時社區結構已發生的變化。此時，即使用戶B 與用戶A 不再見面，但用戶B（A）仍將留在用戶A（B）的局部社區內。 （如圖1所示，其中虛線代表用戶的移動）。

圖1 局部社區動態變化

從以上的示例可以得出，隨著現實場景復雜度的增加，節點間的動態交互行為變得更加不可預測，而上述分布式社區檢測算法此時不能夠準確檢測到人類社交活動中因社會場景改變而引起的局部社區的變化。

為了有效檢測局部社區的變化，本文提出的DA－CDA算法考慮節點自適應社會場景的變化，從而動態更新局部社區的結構。在后面的仿真驗證結果表明，與典型的SIMPLE算法相比，DA－CDA 算法在保持較低計算能力和高性能的同時，在檢測社區結構時能夠自適應動態的社會變化，體現了DA－CDA 算法性能的優勢。

2 節點自適應社會變化的社區檢測算法

2.1 基本描述

定義1 （熟悉節點集）某節點V0的熟悉節點集（F0）定義為：與節點V0相遇累計接觸時間tcum超過預定閾值tth的節點組成，其公式表示為

定義2 （局部社區）C0：表示節點V0的熟悉節點集內節點的集合與通過算法選取節點的集合所構成的社區。

當兩個節點V0和Vi相遇時，它們首先彼此交換局部信息：Ci，Fi，然后決定是否將遇到的節點加入熟悉節點集中 （根據閾值標準），或者加入局部社區內。

定義3 （閾值標準）當兩個節點相遇，每個節點計算累積接觸時間tcum，如果tcum≥tth時，則將遇到的節點添加到熟悉節點集中 （因此也在局部社區內）。

2.2 SIMPLE算法思想

正如算法的名稱一樣，在SIMPLE 算法生命周期中節點之間相遇時彼此交換的信息很少。該算法下每個節點維持一個信息列表，如圖2所示，其中，信息列表中計時器的值將在下一小節說明。

圖2 信息列表

當節點V0和Vi相遇，在相互接觸的時間段內，節點會發送給另一節點它的熟悉節點集和局部社區信息，在節點相互離開后，每個節點通過以下兩個準則來計算并更新自身節點維持的信息列表。

接收閾值準則：當節點V0和節點Vi相遇累計接觸時間沒有達到閾值標準，如果節點V0局部社區內的節點與相遇節點Vi的熟悉節點集的共有節點數量大于λ 倍熟悉節點集里節點的數量，則將相遇節點Vi加入到節點V0的局部社區內，其公式為

式中：λ——接收閾值。

合并閾值準則：當節點V0與節點Vi相遇并滿足閾值標準或接收閾值準則而加入到節點V0的局部社區內，如果局部社區C0和局部社區Ci內共有的節點數量大于γ 倍C0和Ci內節點取并集后的數量，那么將該兩個局部社區合并

式中：γ——合并閾值。

2.3 DA－CDA算法設計

考慮在網絡整體數據無法獲取的情況下如何準確進行社區檢測劃分，DA－CDA 算法在基于SIMPLE 算法的思想上，從網絡的局部拓撲結構出發，利用節點的自組織特性檢測到其所在局部社區，充分考慮網絡中節點間相互作用的關系對局部社區實施動態更新，使得節點能夠動態自適應社會變化。

基于以上的分析，提出節點動態自適應社會變化的社區檢測算法是屬于SIMPLE 算法在復雜性和性能之間的折中考慮。DA－CDA 算法的更新策略是通過考慮解決以下問題來實現：

（1）隨著節點與熟悉節點相遇間隔時間的老化，熟悉節點集如何更新；

（2）如何刪除一些長時間聯系不上的節點。

DA－CDA 算法的主要思想是在保持原來SIMPLE 算法中描述節點的基本特征和閾值準則外，同時增加兩種新的策略，它能夠識別并刪除局部社區內一些長期無法聯系上的節點并更新熟悉節點集和局部社區。因此，在節點間相遇接觸時，將沿用SIMPLE 算法相同的閾值準則，節點之間交換熟悉節點集和局部社區并更新自身節點信息列表，該算法中增加使用以下策略。

2.3.1 熟悉節點集更新策略該策略是定義熟悉節點集中任意節點間相遇接觸持續時間的比例保持在一個穩定估計值。如果該估計值低于給定的閾值，那么將決定刪除熟悉節點集中的節點。因此，可以將時間分成若干時隙T，節點計算每個時隙內與其熟悉節點集中所有節點相遇接觸持續時間的比例定義為：SampleΔT。在下一個時隙到達前，節點根據之前的估計值EstimatedΔT 和新的樣本估計值SampleΔT 得出加權平均值從而計算并估計一個新的EstimatedΔT′，由下式（4）定義

式中：α——計算EstimatedΔT 的加權參數。α 值越小則表明在一個時隙內節點間相遇接觸的持續時間的比例變化越大；相反，α值越大該比例值將保持在一個穩定范圍，表明此時節點不能快速適應局部社區的變化。

最后，某時隙內節點Vi與熟悉節點相遇接觸持續時間的比例為EstimatedΔTi，如果下式成立的話，那么節點Vi將被從熟悉節點集中刪除

式中：FSoutth——節點Vi保持在局部社區內要求最小的閾值。

2.3.2 局部社區更新策略

該策略是要求所有社區內任意節點都維持一個計時器（LCouttimer），當某個節點進入局部社區內 （如節點Vi進入局部社區C0），它的計時器將被設置為起始狀態；當下面情況之一發生時，計時器的值將被更新。

（1）節點V0與節點Vi相遇；

（2）節點V0與另一節點相遇 （如節點Vt），而節點Vi存在節點Vt的局部社區內。

另外，當相應節點的計時器超時，該節點將被從局部社區內刪除。如果被刪除節點存在局部社區內某節點的熟悉節點集中，那么節點將從熟悉節點集中被其刪除，這保證了兩種更新策略的一致性。

需要注意的是局部社區更新策略能夠保證節點被刪除僅僅當局部社區內所有節點都與它長時間沒有接觸聯系，而當局部社區內至少存在一個節點與它存在接觸聯系，那么該節點必須保留在局部社區內。

3 仿真與分析

本文的仿真工作是為了驗證DA－CDA 算法的有效性，并通過與SIMPLE算法進行仿真對比分析，驗證其在動態社區結構檢測情況下的性能。

3.1 仿真環境設置

本 文 采 用ONE （opportunistic network environment）仿真平臺對該算法進行驗證，節點移動按照HCMM 移動模型。盡管這是一個特定和簡單的場景，也足以驗證DACDA 算法在實現社區檢測時能夠正確識別并適應社會變化的突出性能。

HCMM 移動模型是根據真實人類運動模式而得出統計數據的一個移動模型，每個節點最初與一個特定的社區（即家庭社區）相關聯，并且與家庭社區的所有其它成員具有一定的社會關系。其中某些節點還具有保持與家庭社區外的外部社區有聯系。對于每個社會關系，特殊的外部社區和該外部社區內的特定節點都是按照均勻分布來選定的。節點的移動模型是由其社會關系確定的，即一個家庭社區的節點向某個特定的社區 （家庭社區或者外部社區）移動的概率與該社區內與其存在社會關系的節點數量成正比。另外，當節點進入一個外部社區后，給定它仍存在于該外部社區內移動的概率為pe，而返回家庭社區的概率為1－pe。因此，HCMM 移動模型是與現實逼真的模擬場景，用戶一般包括同一個家庭社區內的成員，同時也包括一些尚未返回家庭社區的外部社區成員。

3.2 仿真結果及分析

仿真的目的是要驗證DA－CDA 算法是否能夠正確檢測社區，同時也能自適應動態的社區變化。仿真持續48h，并且每6h對參數進行重新配置。這意味著在每次重新配置之后，自適應節點都要隨機選擇加入一個或兩個社區。因此，我們主要觀察每次在進行重新配置時間間隔內各社區內節點數目的變化。

仿真參數設置見表1。

表1 仿真參數設置

依據SIMPLE算法驗證采取設置的較有效的λ、γ 的參數值來驗證DA－CDA 算法，在引入兩種更新策略的參數后，我們觀察在一個固定值的時隙T 內，FSoutth的設置也應該需要考慮社區交往的動態性。在仿真驗證中，節點之間都保持著較短時間的接觸 （即累積接觸時間較短），因此FSoutth值設置不應該超過5%，否則熟悉節點集大部分時間都將保持為空的狀態。對于局部社區更新策略中使用的計時器（LCouttimer），必須根據時隙T 相應的順序來設置相應的值，否則將會導致局部社區錯誤刪除節點。

圖3和圖4描述的是在兩種不同選擇下模擬仿真運行的運行結果，其中兩幅圖中的圖 （a）和圖 （b）均分別表示SIMPLE算法和DA－CDA 算法下自適應節點檢測到的局部社區結構，自適應節點不采用家庭社區內的節點。仿真期間兩種模擬運行因自適應節點進入不同社區和社區順序不同而形成不同結果。柱狀圖表示在每次進行重新配置的時間間隔結束前局部社區結構的變化，括號內的數字表示在這段時間自適應節點進入社區的序號。

圖3 第一種模擬運行下自適應節點檢測的社區結構

圖4 第二種模擬運行下自適應節點檢測的社區結構

從圖3 （a）和圖4 （a）中可以很清楚的看出SIMPLE算法的局限性。在兩種不同模擬運行的情況下，隨著模擬時間的增加局部社區變大。在每次完成重新配置間隔時間后，自適應節點都會不斷增加新的節點加入局部社區內，同時維護過去所有相遇節點的信息。因此，當局部社區在某個時候達到最大規模54時 （兩種不同選擇都在24h處），接下來的模擬時間將保持這個最大規模運行。需要特別說明的是，在模擬運行6h到12h之間的一種特殊的情況。比如在圖3 （a）中，即使自適應節點只選擇加入社區一，但是局部社區內包含社區二的節點數量依然增加。這可以看作是一個過渡階段，由于每次重新配置的開始階段仿真嚴格要求與自適應節點位置相連的原因而造成的影響，是由節點移動模型決定的，如果節點進入其它外部社區，它回到家庭社區的概率為1－pe，而它選擇留在該外部社區內的概率為pe。因此，如果后者事件發生的話，它將繼續與該外部社區內的其它節點進行接觸。這就是在12h時局部社區內包含社區二的節點數量增加的原因。

從圖3 （b）和圖4 （b）可以看出，DA－CDA 算法能夠實現自適應節點不斷動態更新局部社區內包含每個社區的節點數量。由于加入更新策略，自適應節點通過保留家庭社區內的節點和更新進入的外部社區內的節點對局部社區進行更新，同時刪除那些和局部社區不相關的節點。這些節點要么屬于之前加入的社區 （例如，當自適應節點從社區一移動到社區二，那么它將刪除所有與社區一相關聯的節點，反之亦然）；要么屬于剛加入的社區尚未有足夠時間接觸的節點 （例如，這種情況出現在圖3 （b）的30h處，即使在重新配置后進入的外部社區相同且節點數量沒有改變，局部社區還是減小了）。需要特別說明的是，在12h到18h階段，局部社區很明顯的變大，是由于在這期間，自適應節點屬于進入一個歷史上曾進入過的社區內。因此，由于自適應節點與該社區內其它節點相遇接觸的累計持續時間已經很接近閾值TTH，從而有很大可能增加更多的節點加入局部社區內。

圖5表示在第一種模擬仿真運行情況下，在重新配置間隔時間為6h到12h階段，自適應節點通過局部社區中包含的社區一和社區二的節點數量的變化來進行對比來檢測算法的演變。（需要注意的是：家庭社區內的節點變化不包括在該圖中）

圖5 第一種模擬運行6h到12h時間內局部社區結構變化

圖5 （a）描述的是檢測SIMPLE 算法的演變，在開始階段 （21600s），局部社區僅由社區二中的4個節點組成；在過渡階段 （21600s－24000s），由于自適應節點與社區二中的節點逐漸相遇接觸導致局部社區包含社區二節點的數量曲線上升，當節點間相互接觸的社會活動減少并逐漸消失時，曲線將保持不變。與此同時，自適應節點與社區一中的節點之間相互接觸機會變大，局部社區包含社區一節點的數量曲線也將上升。

圖5 （b）描述的是相同情況下檢測DA－CDA 算法的演變。從圖中可以看出，社區二的節點數量曲線大概在26500 s之前與圖5 （a）類似。但是，由于自適應節點與社區二中相關聯的熟悉節點間接觸時間間隔已超期，節點將刪除接觸時間間隔已超期的熟悉節點并更新自身的信息列表。大約在30000s左右時局部社區包含社區二節點的數量曲線下降到零。相反，從32000s時間點開始，由于自適應節點與社區一中的節點相互接觸的機會比較頻繁使得局部社區包含社區一節點的數量曲線上升。最后，在配置間隔的時間結束時，自適應節點所在的局部社區僅由社區一中的節點組成 （當然也包括自適應節點家庭社區內的節點）。

從以上仿真驗證分析結果可以看出，由于不能很好的自適應社會變化，SIMPLE 算法的性能較低；而DA－CDA算法則能夠達到更高的性能。第二種模擬仿真運行情況與第一種類似，考慮到本文的空間故將其省略。

4 結束語

目前已有研究中包括很多的社區檢測算法，但是很少有算法能有效處理局部社區的動態變化。因此，本文提出一種節點動態自適應社會變化的機會網絡社區檢測算法。通過仿真驗證，DA－CDA 算法在保持較低計算能力要求的同時，較之SIMPLE算法由于能夠保證每個用戶都能夠了解整個局部社區內用戶的動態變化而體現出更高的性能，將是一種更好執行檢測社區的解決方案。然而，本文提出DA－CDA 算法的準確度也與很多因素有關，如節點的密集程度和局部社區結構的隨機性等，而這些因素都會影響算法的整體性能，本文所提算法有待進一步優化。DA－CDA算法能夠動態檢測社區結構，這將有利于提高機會網絡中消息傳遞的成功率，尤其是對時間敏感型的消息，在后續的工作中將作為重點的研究。

［1］Pelusi L，Passarella A，Conti M.Opportunistic networking：data forwarding in disconnected mobile ad hoc networks［C］／／IEEE Communication Magazine，2006：134－141.

［2］XIONG Yongping，SUN Limin，NIU Jianwei，et al.Opportunistic networks［J］.Journal of Software，2009，20 （1）：124－137 （in Chinese）.［熊永平，孫利民，牛建偉，等.機會網絡 ［J］.軟件學報，2009，20 （1）：124－137.］

［3］PAN Hui，Jon Crowcroft，Eiko Yoneki.BUBBLE Rap：Social－based forwarding in delay tolerant networks ［C］／／IEEE Transactions on Mobile Computing，2011：1576－1589.

［4］Bum Soon Jang，Timoth Mann，Yoonsuck Choe.Effects of varying the delay distribution in random，scale－free，and smallworld networks ［C］／／Future Information Technology and Management Engineering，Texas A＆M University.USA：IEEE，2008：316－321.

［5］WANG Dan，JING Yuanwei，YAN Minxiu.Effect of network structure on packet delivery in small－world network ［C］／／International Conference on Communication Software and Networks.China：IEEE，2009：399－403.

［6］LUO Qi.A new community structure detection method based on structural similarity ［C］／／International Conference on Computational Intelligence and Security，IEEE， 2011：1260－1262.

［7］CHEN Qiong，WU Tingting.A method for local community detection by finding maximal－degree nodes［C］／／International Conference on Machine Learning and Cybernetics，IEEE，2010：8－13.

［8］Hui P，Yoneki E，Chan SY，et al.Distributed community detection in delay tolerant networks ［C］／／Proceedings of MobiArch，2007.

［9］ZHAO Fengxia，XIE Fuding.Detecting community in complex networks using K－means cluster algorithm ［J］.Application Research of Computers，2009，26 （6）：2041－2049 （in Chinese）.［趙鳳霞，謝福鼎.基于K－means聚類算法的復雜網絡社團發現新方法［J］.計算機應用研究，2009，26 （6）：2041－2049.］

［10］Clauset A.Finding local community structures in networks［C］／／Physical Review E Stat，2005.