節(jié)點(diǎn)自適應(yīng)社會(huì)變化的機(jī)會(huì)網(wǎng)絡(luò)社區(qū)檢測(cè)算法

陶 洋，倪 強(qiáng)

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

0 引 言

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

1 問(wèn)題描述

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

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

從以上的示例可以得出，隨著現(xiàn)實(shí)場(chǎng)景復(fù)雜度的增加，節(jié)點(diǎn)間的動(dòng)態(tài)交互行為變得更加不可預(yù)測(cè)，而上述分布式社區(qū)檢測(cè)算法此時(shí)不能夠準(zhǔn)確檢測(cè)到人類(lèi)社交活動(dòng)中因社會(huì)場(chǎng)景改變而引起的局部社區(qū)的變化。

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

2 節(jié)點(diǎn)自適應(yīng)社會(huì)變化的社區(qū)檢測(cè)算法

2.1 基本描述

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

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

當(dāng)兩個(gè)節(jié)點(diǎn)V0和Vi相遇時(shí)，它們首先彼此交換局部信息：Ci，F(xiàn)i，然后決定是否將遇到的節(jié)點(diǎn)加入熟悉節(jié)點(diǎn)集中 （根據(jù)閾值標(biāo)準(zhǔn)），或者加入局部社區(qū)內(nèi)。

定義3 （閾值標(biāo)準(zhǔn)）當(dāng)兩個(gè)節(jié)點(diǎn)相遇，每個(gè)節(jié)點(diǎn)計(jì)算累積接觸時(shí)間tcum，如果tcum≥tth時(shí)，則將遇到的節(jié)點(diǎn)添加到熟悉節(jié)點(diǎn)集中 （因此也在局部社區(qū)內(nèi)）。

2.2 SIMPLE算法思想

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

圖2 信息列表

當(dāng)節(jié)點(diǎn)V0和Vi相遇，在相互接觸的時(shí)間段內(nèi)，節(jié)點(diǎn)會(huì)發(fā)送給另一節(jié)點(diǎn)它的熟悉節(jié)點(diǎn)集和局部社區(qū)信息，在節(jié)點(diǎn)相互離開(kāi)后，每個(gè)節(jié)點(diǎn)通過(guò)以下兩個(gè)準(zhǔn)則來(lái)計(jì)算并更新自身節(jié)點(diǎn)維持的信息列表。

接收閾值準(zhǔn)則：當(dāng)節(jié)點(diǎn)V0和節(jié)點(diǎn)Vi相遇累計(jì)接觸時(shí)間沒(méi)有達(dá)到閾值標(biāo)準(zhǔn)，如果節(jié)點(diǎn)V0局部社區(qū)內(nèi)的節(jié)點(diǎn)與相遇節(jié)點(diǎn)Vi的熟悉節(jié)點(diǎn)集的共有節(jié)點(diǎn)數(shù)量大于λ 倍熟悉節(jié)點(diǎn)集里節(jié)點(diǎn)的數(shù)量，則將相遇節(jié)點(diǎn)Vi加入到節(jié)點(diǎn)V0的局部社區(qū)內(nèi)，其公式為

式中：λ——接收閾值。

合并閾值準(zhǔn)則：當(dāng)節(jié)點(diǎn)V0與節(jié)點(diǎn)Vi相遇并滿(mǎn)足閾值標(biāo)準(zhǔn)或接收閾值準(zhǔn)則而加入到節(jié)點(diǎn)V0的局部社區(qū)內(nèi)，如果局部社區(qū)C0和局部社區(qū)Ci內(nèi)共有的節(jié)點(diǎn)數(shù)量大于γ 倍C0和Ci內(nèi)節(jié)點(diǎn)取并集后的數(shù)量，那么將該兩個(gè)局部社區(qū)合并

式中：γ——合并閾值。

2.3 DA－CDA算法設(shè)計(jì)

考慮在網(wǎng)絡(luò)整體數(shù)據(jù)無(wú)法獲取的情況下如何準(zhǔn)確進(jìn)行社區(qū)檢測(cè)劃分，DA－CDA 算法在基于SIMPLE 算法的思想上，從網(wǎng)絡(luò)的局部拓?fù)浣Y(jié)構(gòu)出發(fā)，利用節(jié)點(diǎn)的自組織特性檢測(cè)到其所在局部社區(qū)，充分考慮網(wǎng)絡(luò)中節(jié)點(diǎn)間相互作用的關(guān)系對(duì)局部社區(qū)實(shí)施動(dòng)態(tài)更新，使得節(jié)點(diǎn)能夠動(dòng)態(tài)自適應(yīng)社會(huì)變化。

基于以上的分析，提出節(jié)點(diǎn)動(dòng)態(tài)自適應(yīng)社會(huì)變化的社區(qū)檢測(cè)算法是屬于SIMPLE 算法在復(fù)雜性和性能之間的折中考慮。DA－CDA 算法的更新策略是通過(guò)考慮解決以下問(wèn)題來(lái)實(shí)現(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真與分析

本文的仿真工作是為了驗(yàn)證DA－CDA 算法的有效性，并通過(guò)與SIMPLE算法進(jìn)行仿真對(duì)比分析，驗(yàn)證其在動(dòng)態(tài)社區(qū)結(jié)構(gòu)檢測(cè)情況下的性能。

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

本 文 采 用ONE （opportunistic network environment）仿真平臺(tái)對(duì)該算法進(jìn)行驗(yàn)證，節(jié)點(diǎn)移動(dòng)按照HCMM 移動(dòng)模型。盡管這是一個(gè)特定和簡(jiǎn)單的場(chǎng)景，也足以驗(yàn)證DACDA 算法在實(shí)現(xiàn)社區(qū)檢測(cè)時(shí)能夠正確識(shí)別并適應(yīng)社會(huì)變化的突出性能。

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

3.2 仿真結(jié)果及分析

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

仿真參數(shù)設(shè)置見(jiàn)表1。

表1 仿真參數(shù)設(shè)置

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

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

圖3 第一種模擬運(yùn)行下自適應(yīng)節(jié)點(diǎn)檢測(cè)的社區(qū)結(jié)構(gòu)

圖4 第二種模擬運(yùn)行下自適應(yīng)節(jié)點(diǎn)檢測(cè)的社區(qū)結(jié)構(gòu)

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

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

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

圖5 第一種模擬運(yùn)行6h到12h時(shí)間內(nèi)局部社區(qū)結(jié)構(gòu)變化

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

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

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

4 結(jié)束語(yǔ)

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

［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ī)會(huì)網(wǎng)絡(luò) ［J］.軟件學(xué)報(bào)，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聚類(lèi)算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法［J］.計(jì)算機(jī)應(yīng)用研究，2009，26 （6）：2041－2049.］

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