侯思權，張振宇，文少杰

（新疆大學 信息科學與工程學院，新疆 烏魯木齊830046）

0 引 言

社區(qū)檢測作為復雜網絡的一個重要研究課題，已涌現(xiàn)出許多相關算法［1，2］，這些算法可以檢測出不相交的社區(qū)結構。最近研究發(fā)現(xiàn)復雜網絡的社區(qū)結構是相交的、分層的，許多算法［3－6］設計用來檢測這些重疊的、分層的社區(qū)結構，重疊社區(qū)檢測成為了當前復雜網絡結構挖掘的前沿熱點。

機會網絡［7］是一個具有結構動態(tài)性、間歇性鏈接的特殊復雜網絡。社區(qū)檢測具有一些其它網絡不具備的難點：節(jié)點移動性較強、無法預知社區(qū)規(guī)模、社區(qū)個數(shù)不確定、具有重疊社區(qū)現(xiàn)象等。目前針對機會網絡社區(qū)結構的研究多基于復雜網絡社區(qū)檢測原理，包括MCPD［8］、DCDA［9］、NBDE［10］等。文獻 ［8］利用節(jié)點間最大連通概率 （MCP）作為分裂圖的依據，并使用GN 算法得到社區(qū)結構，然而在機會網絡中，節(jié)點有電量和計算能力的限制，并不能得到網絡全局拓撲結構。文獻 ［9］利用傳統(tǒng)復雜網絡社區(qū)檢測理論，簡單的根據節(jié)點接觸信息，把小于某個閾值的邊移除，并把網絡拓撲結構圖簡單地轉化為無權圖，忽略了節(jié)點間關系強度信息。文獻 ［10］提出節(jié)點歸屬性動態(tài)社區(qū)檢測算法 （NBDE），利用機會網絡中鄰居節(jié)點信息計算節(jié)點對社區(qū)的歸屬性，并根據歸屬性，利用標簽傳遞原理來檢測社區(qū)。文獻 ［11］利用機會網絡中隨時間演化的邊上權重，提出一種可檢測時變社區(qū)結構的方法。該方法的計算復雜度稍高，考慮到網絡節(jié)點能量和計算能力限制，在現(xiàn)實應用中實現(xiàn)相對不易。以上方法對機會網絡中節(jié)點間關系強度信息利用較少，且重疊社區(qū)的研究相對較少，同時在機會網絡中檢測重疊節(jié)點，具有很重要的意義，其利用重疊節(jié)點作為社區(qū)間通信的橋渡節(jié)點，這些重疊節(jié)點對機會網絡中消息轉發(fā)和路由的可靠性具有較大改善。因此需要提出一種適合機會網絡特征的重疊社區(qū)檢測方法。

為了解決機會網絡中重疊社區(qū)的檢測問題，本文結合節(jié)點間關系強度，給出了一個針對機會網絡特點的基于邊權重局部擴展的社區(qū)檢測方法 （LWLE），找到局部關系強度值最大且密集的節(jié)點集合作為社區(qū)，這樣得到的社區(qū)更符合機會網絡的社會屬性。

1 基于邊權重的局部擴展社區(qū)檢測方法

1.1 關系強度計算及網絡結構建立

關系強度表示節(jié)點間鏈接強弱，節(jié)點間相遇間隔時間越短，相遇時間越長，則關系強度值越大，并把其值作為機會網絡中節(jié)點間邊的權重。定義關系強度為

式中：α——控制參數(shù)，范圍為 ［0－1］，ict——相遇間隔時間，cd——相遇時間。

本文使用文獻［12］中提出的滑動窗口方法來建立具有邊權重的機會網絡結構，每個節(jié)點都有一個滑動窗口，它是一個大小為t的時間幀。隨著時間步的移動，滑動窗口內容更新，使用式 （1）計算出現(xiàn)在滑動窗口內與鄰居節(jié)點間的關系強度值，當節(jié)點間關系強度大于某閾值時，則節(jié)點與鄰居節(jié)點之間建立邊，并把該關系強度值作為邊權重。節(jié)點保存篩選過的鄰居節(jié)點集合及權重值。這樣可以得到一個具有邊權重的動態(tài)機會網絡結構。該方法建立的網絡結構較真實地表現(xiàn)了節(jié)點間的社會關系，在該網絡結構下使用社區(qū)檢測算法得出的社區(qū)結構更符合實際情況。

1.2 局部擴展方法

研究表明社區(qū)是一組關聯(lián)緊密的節(jié)點集合，在機會網絡中，表現(xiàn)為局部結構中關聯(lián)強度最大的一組節(jié)點。由于機會網絡中節(jié)點受到通信范圍及能量的限制，節(jié)點一般不具備整個網絡拓撲結構知識，僅保存了其與鄰居節(jié)點間的關聯(lián)信息。因此，本文結合機會網絡特點，使用局部擴展社區(qū)檢測方法來得到重疊社區(qū)結構。如圖1所示，已知機會網絡中節(jié)點僅知道鄰居節(jié)點信息，區(qū)域N 為已探知區(qū)域，而U 為未知區(qū)域，由紅色節(jié)點區(qū)域C向區(qū)域U 逐步擴展。在已知的區(qū)域 （C＋N），C 占的關系強度比重越大，C就越有可能成為一個社區(qū)。如果確定C 為C＋N 區(qū)域中具有最大的關系強度比值，那么就認定C 為一個最優(yōu)局部社區(qū)。

因此，使用式 （2）的最大值來確定最大關系強度區(qū)域

圖1 局部擴展

式中：rs（e）——節(jié)點關系強度 （邊權重），C——社區(qū)，N為鄰居節(jié)點區(qū)域。ΔCS（i）——節(jié)點i對C 社區(qū)關系強度的貢獻。從任一節(jié)點出發(fā)，根據式 （2），選擇具有較大ΔCS（i）值的鄰居節(jié)點逐一擴展區(qū)域C，直到CS 的值達到局部最大，則確定C 為一個社區(qū)，繼續(xù)隨機選擇下一個未分配社區(qū)的節(jié)點擴展，當所有節(jié)點都分配了社區(qū)時，算法終止。

1.3 優(yōu)化策略及重疊社區(qū)檢測

由于局部擴展方法對初始節(jié)點的選擇比較敏感，以上方法存在初始節(jié)點選擇隨機、重復計算等不足，為了更好的得到社區(qū)結構，本文使用節(jié)點聚集系數(shù)［13］對初始節(jié)點選擇進行優(yōu)化。節(jié)點i的聚集系數(shù)計算見式 （4）

式 中：E（i）——節(jié)點i的鄰居節(jié)點間的實際連邊數(shù)。k（i）——節(jié)點i的度。該公式表示i的鄰居節(jié)點間的連邊數(shù)與有可能達到的最大連邊數(shù)的一個比值，c（i）值越大，表明節(jié)點i的鄰居節(jié)點間的聯(lián)系越緊密。即節(jié)點i與其鄰居節(jié)點更可能成為一個社區(qū)的中心。

使用聚集系數(shù)較大的節(jié)點作為初始種子節(jié)點，進行局部擴展，得出的社區(qū)劃分結果比較合理。

因此其社區(qū)檢測步驟為：

（1）計算節(jié)點聚集系數(shù)，根據節(jié)點聚集系數(shù)對節(jié)點進行中心性排名，得到節(jié)點集合S。

（2）從S中選擇具有最大節(jié)點聚集系數(shù)且未分配社區(qū)的節(jié)點作為種子節(jié)點，標記為社區(qū)C，并從S中移除該節(jié)點。遍歷獲得種子節(jié)點的鄰居節(jié)點集合，并根據式 （3）得到鄰居節(jié)點的貢獻值集合B，選擇具有最大貢獻值且為正值的鄰居節(jié)點加入社區(qū)C。

（3）擴展社區(qū)C 的鄰居節(jié)點集合 （包含已分配社區(qū)的節(jié)點），并重新計算每個鄰居節(jié)點對社區(qū)C的貢獻值，更新集合B，選擇具有最大貢獻值的節(jié)點加入社區(qū)C。

（4）重復步驟 （3），直到社區(qū)C 的所有鄰居節(jié)點對社區(qū)C貢獻值ΔCS（i）＜＝0，算法停止，得到社區(qū)C。

（5）重復步驟 （2），直到所有節(jié)點都分配了社區(qū)，最終可以得到重疊社區(qū)。

LWLE中計算節(jié)點聚集系數(shù)時間復雜度為O（kn），k為節(jié)點度，n為網絡節(jié)點數(shù)。局部擴展社區(qū)檢測方法中時間復雜度為O（ncs2c），nc為社區(qū)規(guī)模，sc為社區(qū)大小，最壞情況為整個網絡為一個社區(qū)情況，時間復雜度為O（n2）。

2 仿真結果及分析

為驗證LWLE算法在機會網絡中社區(qū)檢測的準確性，本文使用DTN 網絡環(huán)境模擬器ONE，對算法進行仿真。ONE平臺充分擬合了機會網絡特點，它將節(jié)點移動模型、DTN 路由和可視化的圖形界面整合為一體。這樣ONE 就非常容易進行擴展，并可以提供大量的結果報告和分析模型［14］。使用ONE作為該算法的模擬平臺能夠更真實的驗證本算法的性能。在仿真中，本文使用基于社區(qū)的移動模型，其根據節(jié)點間社會關系計算每個社區(qū)對節(jié)點吸引力，移動節(jié)點，模擬0～12h節(jié)點運動狀況，收集運動接觸產生的數(shù)據，然后使用LWLE 算法與節(jié)點動態(tài)歸屬性算法（NBDE）對收集的數(shù)據進行對比分析，得出社區(qū)劃分結果，計算節(jié)點被正確劃分的比率。ONE 仿真使用環(huán)境參數(shù)見表1。

表1 仿真環(huán)境參數(shù)

基于社區(qū)的模型是一種考慮了節(jié)點社會性的移動模型，該模型在本質上還是基于移動周期的，但是引入了節(jié)點社區(qū)的概念，目的是為了更好的模擬現(xiàn)實中節(jié)點的社會性，它使用CAVEMAN 模型生成節(jié)點間社會關系圖作為社區(qū)模型的社會關系矩陣輸入，如圖2所示，該圖具有10個節(jié)點3個社區(qū)，節(jié)點間的數(shù)字表示節(jié)點間的社會關系緊密程度，值越大表明兩者的關系越緊密。

從圖2 可以看出該拓撲結構具有3 個社區(qū) ｛A，B，C｝、｛D，E，F(xiàn)，G｝、｛H，I，L｝。仿真運行0～12h，在每個時間點分別生成5次數(shù)據，分別使用LWLE 與NBDE算法對數(shù)據進行社區(qū)分析，比較社區(qū)劃分的平均準確率，比較結果如圖3所示。

圖2 社會關系

圖3 社區(qū)檢測正確率對比

在本次仿真中可以，隨著仿真時間增加，LWLE 正確檢測社區(qū)的概率也在增加，運行到第4個小時檢測正確率已經超過NBDE 算法，當運行到第6 個小時的時候，LWLE算法已經能夠正確的檢測出社區(qū)結果。主要原因是仿真時間越長，所有節(jié)點之間接觸越多，同一個社區(qū)內節(jié)點間關系強度值比社區(qū)間的關系強度逐步增強，因此LWLE檢測出的社區(qū)結果正確率越高，而NBDE 算法是基于標簽傳遞的原理，隨著運行時間的增加，節(jié)點間的接觸也越來越多，鄰居節(jié)點增加，由于該算法并沒有區(qū)分節(jié)點間關系強度大小，并不能夠完全正確的得到節(jié)點所屬社區(qū)，只能正確檢測部分節(jié)點的所屬社區(qū)。

在該仿真環(huán)境下，網絡較為稠密時，節(jié)點為30 個、4個社區(qū)時的LWLE與NBDE社區(qū)檢測正確率對比情況，如圖4所示，隨著仿真時間增加，LWLE 檢測正確率逐漸增加，到第5個小時時接近100%，而NBDE 算法檢測正確率相對上圖還有所下降，僅為60%。

為驗證本文提出算法對機會網絡中重疊社區(qū)檢測正確率，首先調整社區(qū)模型，然后輸入一個具有23 個節(jié)點，｛Ca，Cb，Cc，Cd｝4 個社區(qū)的一個社會關系矩陣，其中Ca，Cb社區(qū)有1 個重疊節(jié)點，Cb，Cc社區(qū)有3 個重疊節(jié)點。在ONE平臺下模擬節(jié)點運動，收集0～12h產生的數(shù)據，使用LWLE算法分析結果，如圖5所示，重疊社區(qū)檢測正確率接近90%，僅個別重疊節(jié)點未被正確檢測。

圖4 網絡節(jié)點稠密時，社區(qū)檢測正確率對比

圖5 重疊社區(qū)劃分正確率

仿真結果表明，該方法與機會網絡耦合度很高，充分利用了機會網絡中節(jié)點間的關系強度信息，LWLE 能夠以較高正確率檢測出了重疊的并且關系強度較高的一組節(jié)點集合。

3 結束語

本文針對機會網絡中社區(qū)重疊問題，利用節(jié)點間的關系強度值，建立具有邊權重的網絡拓撲，提出一種基于邊權重局部擴展的社區(qū)檢測算法 （LWLE）。為解決局部擴展方法中的隨機選擇初始節(jié)點、重復計算的問題，給出一種利用節(jié)點聚集系數(shù)對初始節(jié)點選擇的局部擴展優(yōu)化策略。LWLE能夠較準確的發(fā)現(xiàn)機會網絡中的重疊社區(qū)結構。然而機會網絡中的節(jié)點具有較強的移動性，網絡結構不穩(wěn)定，動態(tài)重疊社區(qū)檢測的研究是今后工作中研究方向。

［1］Newman MEJ.Communities，modules and large－scale structure in networks［J］.Nature Physics，2011，8 （1）：25－31.

［2］Raghavan UN，Albert R，Kumara S.Near linear time algorithm to detect community structures in large－scale networks［J］.Physical Review E，2007，76 （3）：036106.

［3］Lancichinetti A，F(xiàn)ortunato S，Kertész J.Detecting the over－lapping and hie－rarchical community structure in complex networks［J］.New Journal of Physics，2009，11 （3）：033015.

［4］Ahn YY，Bagrow JP，Lehmann S.Link communities reveal multi－scale complexity in networks ［J］.Nature，2010，466（7307）：761－764.

［5］Shen H，Cheng X，Cai K，et al.Detect overlapping and hierarchical community structure in networks ［J］.Physica A：Statistical Mechanics and its Applications，2009，388 （8）：1706－1712.

［6］Zhubing L，Jian W，Yuzhou L.An overview on overlapping community detection ［C］／／7th International Conference on Computer Science ＆Education.IEEE，2012：486－490.

［7］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.］

［8］Zhang Y，Han Y，Li J，et al.Community detection using maximum connection probability in opportunistic network［C］／／4th International Conference on Intelligent Systems Modelling ＆Simulation.IEEE，2013 475－480.

［9］Hui P，Yoneki E，Chan SY，et al.Distributed community detection in delay tolerant networks ［C］／／Proceedings of 2nd ACM／IEEE International Workshop on Mobility in the Evolving Internet Architecture.ACM，2007.

［10］WU Dapeng，XIANG Xiaohua，WANG Ruyan，et al.Nodebelongingness dynamic estimate community detect strategy in opportunistic networks ［J］.Computer Engineering And Design，2012，33 （10）：3673－3677 （in Chinese）. ［吳大鵬，向小華，王汝言，等.節(jié)點歸屬性動態(tài)估計的機會網絡社區(qū)檢測策略 ［J］.計算機工程與設計，2012，33 （10）：3673－3677.］

［11］Xu K，Yang GH，Li VOK，et al.Detecting dynamic communities in opportunistic networks ［C］／／First International Conference on Ubiquitous and Future Networks.IEEE，2009：159－164.

［12］Lenando H，Zen K，Jambli MN，et al.Forming a social structure in mobile opportunistic networks ［C］／／17th Asia－Pacific Conference on Communications.IEEE，2011：450－455.

［13］LI Kongwen，GU Qing，ZHANG Yao，et al.Local community detecting method based on the clustering coefficient［J］.Computer Science，2010，37 （7）：46－49 （in Chinese）. ［李孔文，顧慶，張堯，等.一種基于聚集系數(shù)的局部社團劃分算法 ［J］.計算機科學，2010，37 （7）：46－49.］

［14］WANG Zhen，WANG Xinhua，SUI Jinglin.Extending research for ONE simulator of opportunistic network ［J］.Application Research of Computers，2012，29 （1）：272－277 （in Chinese）.［王朕，王新華，隋敬麒.機會網絡模擬器ONE及其擴展研究 ［J］.計算機應用研究，2012，29 （1）：272－277.］