本文關(guān)鍵詞：社交網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)機(jī)制的研究

  更多相關(guān)文章： 社區(qū)發(fā)現(xiàn) 非重疊社區(qū) 重疊社區(qū) BSP Propinquity

【摘要】：復(fù)雜網(wǎng)絡(luò)一般是指節(jié)點(diǎn)數(shù)量多且節(jié)點(diǎn)間交互關(guān)系復(fù)雜的網(wǎng)絡(luò)。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的拓?fù)涮攸c(diǎn)之一,整個(gè)網(wǎng)絡(luò)由若干社區(qū)構(gòu)成,社區(qū)內(nèi)部節(jié)點(diǎn)的交互頻繁,社區(qū)間節(jié)點(diǎn)的交互較弱。如何從復(fù)雜網(wǎng)絡(luò)中解構(gòu)出社區(qū)結(jié)構(gòu),已成為復(fù)雜系統(tǒng)研究領(lǐng)域中一大熱點(diǎn)。隨著網(wǎng)絡(luò)規(guī)模的逐漸增大,特別是Facebook、Twitter、微博等社交網(wǎng)絡(luò)的崛起,復(fù)雜網(wǎng)絡(luò)的規(guī)模指數(shù)上漲,不僅對社區(qū)發(fā)現(xiàn)算法的計(jì)算復(fù)雜度提出了苛刻的要求,同時(shí)也引入了對算法并行化的要求。在不考慮重疊社區(qū)的情況下,雖然目前已經(jīng)提出了一些線性時(shí)間復(fù)雜度的算法,但由于這些算法通常采用較為激進(jìn)的貪婪策略,因此在網(wǎng)絡(luò)規(guī)模較大且稠密的圖拓?fù)渲薪Y(jié)果并不可靠。在重疊社區(qū)發(fā)現(xiàn)算法中,現(xiàn)有方案通常需要經(jīng)過多次計(jì)算來獲得最佳的社團(tuán)數(shù),計(jì)算開銷過大。同時(shí),由于文獻(xiàn)中多數(shù)社區(qū)發(fā)現(xiàn)算法均不具備并行能力,無法基于分割后的局部點(diǎn)集實(shí)現(xiàn)算法邏輯,這將很難滿足復(fù)雜網(wǎng)絡(luò)下海量數(shù)據(jù)的計(jì)算需求�；诖�,本文分別針對非重疊社區(qū)和重疊社區(qū),提出兩個(gè)社區(qū)發(fā)現(xiàn)算法,以滿足在大規(guī)模網(wǎng)絡(luò)分析中實(shí)現(xiàn)高效并行計(jì)算的需求。本文針對相關(guān)程度矩陣的計(jì)算,提出了一種基于節(jié)點(diǎn)動(dòng)態(tài)閾值調(diào)節(jié)的優(yōu)化方式,不僅解決了現(xiàn)有算法收斂速度較慢的問題,同時(shí)引入了節(jié)點(diǎn)自身特性輔助閾值設(shè)置,提升了算法準(zhǔn)確性。在權(quán)重設(shè)計(jì)方面,考慮原算法中相關(guān)程度矩陣各個(gè)組成部分的重要程度不同,進(jìn)行了有區(qū)分度的權(quán)重設(shè)置,并增加了算法對加權(quán)圖的支持。針對非重疊社區(qū),提出了兩個(gè)社區(qū)發(fā)現(xiàn)算法:基于關(guān)鍵節(jié)點(diǎn)的社區(qū)發(fā)現(xiàn)算法CKE(Community Detection based on Key Nodes Extracting)和基于譜聚類的社區(qū)發(fā)現(xiàn)算法SKC(SpectralKMeans Cluster based Detection)。CKE算法為了解決原算法中將連通組成部分作為社區(qū)結(jié)構(gòu)導(dǎo)致社區(qū)間錯(cuò)誤合并的問題,引入了點(diǎn)介數(shù)算法輔助篩選出關(guān)鍵節(jié)點(diǎn),利用關(guān)鍵節(jié)點(diǎn)在多個(gè)社區(qū)間起橋梁作用這一特性,將其作為劃分社區(qū)的分界節(jié)點(diǎn),結(jié)合BFS算法實(shí)現(xiàn)非重疊社區(qū)。通過仿真可以證明,CKE算法能夠準(zhǔn)確找到關(guān)鍵節(jié)點(diǎn),得到有效的社區(qū)劃分。SKC算法則是利用了聚類思想,通過譜聚類將相關(guān)程度矩陣轉(zhuǎn)換為效用矩陣,以完成社區(qū)劃分。針對現(xiàn)有算法中K值和初心難以預(yù)估的問題,引入Canopy聚類輔助設(shè)置。針對重疊社區(qū),提出了兩個(gè)社區(qū)發(fā)現(xiàn)算法:基于點(diǎn)聚集的社區(qū)發(fā)現(xiàn)算法CCO(Core-clique Combination Optimization detection algorithm)和基于擴(kuò)散標(biāo)記的社區(qū)發(fā)現(xiàn)算法IMB(Iterative diffusion Markbased on high-Betweennes)。CCO算法以發(fā)掘高內(nèi)聚度的點(diǎn)聚集為核心,通過在其上提取重疊節(jié)點(diǎn)完成社區(qū)發(fā)現(xiàn)。常規(guī)的重疊點(diǎn)發(fā)現(xiàn)策略通常以聚類密度進(jìn)行判定,其計(jì)算復(fù)雜度較高,針對這一問題在CCO算法中提出了簡化的解決策略。IMB算法則是通過擴(kuò)散標(biāo)記思想實(shí)現(xiàn)重疊社區(qū)的發(fā)現(xiàn)。為了保證不同規(guī)模的社區(qū)結(jié)構(gòu)均能被提取,IMB算法引入了基準(zhǔn)閾值?作為標(biāo)準(zhǔn),利用其能夠度量節(jié)點(diǎn)與鄰接節(jié)點(diǎn)間緊密程度這一特性,實(shí)現(xiàn)擴(kuò)散標(biāo)記。通過仿真可以看出,在少量的幾輪迭代標(biāo)記后,即可獲得較好的重疊社區(qū)劃分結(jié)果。針對大規(guī)模網(wǎng)絡(luò)分析中實(shí)現(xiàn)高效并行計(jì)算這一需求,需要為算法建立以節(jié)點(diǎn)為中心的并發(fā)模型,結(jié)合圖的分割思想,引入分布式計(jì)算框架,才能取得較好的社區(qū)劃分結(jié)果。因此,本文還探討了如何在Hadoop上分布式執(zhí)行上述幾種算法,實(shí)現(xiàn)社區(qū)劃分。
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
，

本文編號：1273466