陶 洋，倪 強

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

0 引 言

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

1 問題描述

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

圖1 局部社區(qū)動態(tài)變化

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

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

2 節(jié)點自適應社會變化的社區(qū)檢測算法

2.1 基本描述

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

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

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

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

2.2 SIMPLE算法思想

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

圖2 信息列表

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

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

式中：λ——接收閾值。

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

式中：γ——合并閾值。

2.3 DA－CDA算法設計

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

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

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

（2）如何刪除一些長時間聯(lián)系不上的節(jié)點。

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

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

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

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

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

2.3.2 局部社區(qū)更新策略

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

（1）節(jié)點V0與節(jié)點Vi相遇；

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

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

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

3 仿真與分析

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

3.1 仿真環(huán)境設置

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

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

3.2 仿真結果及分析

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

仿真參數設置見表1。

表1 仿真參數設置

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

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

圖3 第一種模擬運行下自適應節(jié)點檢測的社區(qū)結構

圖4 第二種模擬運行下自適應節(jié)點檢測的社區(qū)結構

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

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

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

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

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

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

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

4 結束語

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

［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聚類算法的復雜網絡社團發(fā)現新方法［J］.計算機應用研究，2009，26 （6）：2041－2049.］

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