發(fā)布時(shí)間：2020-08-03 08:48

【摘要】：近年來(lái),隨著在線社交網(wǎng)絡(luò)的流行及智能移動(dòng)終端設(shè)備的普及,越來(lái)越多的人將在線社交作為一種重要的生活方式,在線社交網(wǎng)絡(luò)的數(shù)據(jù)量也愈發(fā)龐大。社區(qū)探測(cè)作為社交網(wǎng)絡(luò)研究的一個(gè)重要方向,在研究網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)、分析用戶關(guān)系、探索消息傳播方式及掌握輿論動(dòng)向方面有重要意義。由于單機(jī)的硬件配置升級(jí)存在邊際效應(yīng),以及一些傳統(tǒng)的社區(qū)探測(cè)算法在處理超大數(shù)據(jù)時(shí)的限制,使得分布式計(jì)算模型成為處理大型社交網(wǎng)絡(luò)數(shù)據(jù)的一個(gè)優(yōu)秀解決方案�，F(xiàn)有的分布式網(wǎng)絡(luò)社區(qū)探測(cè)算法,在實(shí)現(xiàn)大型網(wǎng)絡(luò)數(shù)據(jù)的社區(qū)探測(cè)的同時(shí),會(huì)產(chǎn)生社區(qū)質(zhì)量下降的問題,還有一部分算法穩(wěn)定性不強(qiáng),對(duì)數(shù)據(jù)節(jié)點(diǎn)重新排序編號(hào)會(huì)大幅影響計(jì)算結(jié)果的質(zhì)量。本文在研究現(xiàn)有的分布式社區(qū)探測(cè)算法的基礎(chǔ)上,提出了一種基于標(biāo)簽傳播分區(qū)的優(yōu)化分布式Louvain算法-LPPDLA算法,并將算法應(yīng)用于社區(qū)探測(cè)系統(tǒng)。本文的主要工作為以下幾點(diǎn):(1)分析分布式社區(qū)探測(cè)的需求和現(xiàn)有分布式社區(qū)探測(cè)算法,提出三點(diǎn)改進(jìn):1、使用VF算法簡(jiǎn)化圖數(shù)據(jù)的節(jié)點(diǎn)分布,縮短運(yùn)行時(shí)間以優(yōu)化社區(qū)探測(cè)計(jì)算效率;2、將大小約束的標(biāo)簽傳播算法應(yīng)用于圖分區(qū),提高算法穩(wěn)定性;3、以虛節(jié)點(diǎn)增強(qiáng)分區(qū)之間的關(guān)聯(lián)關(guān)系,并制定節(jié)點(diǎn)跨分區(qū)移動(dòng)規(guī)則。(2)將Louvain算法結(jié)合以上三個(gè)改進(jìn),在MapReduce分布式計(jì)算模型上提出LPPDLA算法。并使用LPPDLA算法對(duì)公共數(shù)據(jù)進(jìn)行社區(qū)探測(cè)計(jì)算,以驗(yàn)證算法的有效性及評(píng)估計(jì)算獲得的社區(qū)質(zhì)量。(3)設(shè)計(jì)并實(shí)現(xiàn)一個(gè)社區(qū)探測(cè)系統(tǒng),以可視化界面提供網(wǎng)絡(luò)數(shù)據(jù)采集功能,圖文件讀取功能,可以使用LPPDLA算法對(duì)網(wǎng)絡(luò)圖數(shù)據(jù)進(jìn)行分布式社區(qū)探測(cè),并以展示探測(cè)結(jié)果。通過實(shí)驗(yàn)對(duì)比分析,本論文提出的LPPDLA算法可以在較短時(shí)間內(nèi)準(zhǔn)確地對(duì)大型圖數(shù)據(jù)進(jìn)行社區(qū)探測(cè),并且可以有效降低分布式社區(qū)探測(cè)的質(zhì)量衰減問題,使社區(qū)質(zhì)量達(dá)到原始Louvain算法同等水平。
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：TP393.09
【圖文】：

該節(jié)點(diǎn)的標(biāo)簽更新為這個(gè)最大的標(biāo)簽，同時(shí)隨機(jī)地?cái)嚅_連接，完成一次標(biāo)簽的傳逡逑播。隨著標(biāo)簽的傳播，密集連接的節(jié)點(diǎn)會(huì)迅速的形成一個(gè)相同標(biāo)簽的組合體（如逡逑圖２－１所示）。在標(biāo)簽傳播的初期，網(wǎng)絡(luò)圖中可能會(huì)形成多個(gè)這種集合體（稱為逡逑共識(shí)小組），他們的標(biāo)簽將作為影響力較大標(biāo)簽向外輻射，以獲得更多的節(jié)點(diǎn)加逡逑１０逡逑

由此得出的跨分區(qū)移動(dòng)規(guī)則為：當(dāng)本分區(qū)內(nèi)的節(jié)點(diǎn)因?yàn)槟K度增加而需要向逡逑虛節(jié)點(diǎn)所在的社區(qū)移動(dòng)時(shí)，需要額外對(duì)比該節(jié)點(diǎn)與虛節(jié)點(diǎn)的度。若該節(jié)點(diǎn)的度小逡逑于虛節(jié)點(diǎn)的度，則將節(jié)點(diǎn)移動(dòng)至虛節(jié)點(diǎn)所在的社區(qū)；否則不移動(dòng)。如圖３－４的（ｂ）逡逑所示，節(jié)點(diǎn)ｉ與節(jié)點(diǎn)ｊ分別處于兩個(gè)分區(qū)中，互為對(duì)方分區(qū)的虛節(jié)點(diǎn)。假設(shè)節(jié)點(diǎn)逡逑ｉ的度小于節(jié)點(diǎn)ｊ的度，貝``計(jì)算中，節(jié)點(diǎn)ｉ會(huì)移動(dòng)至節(jié)點(diǎn)ｊ所在的社區(qū)，而節(jié)點(diǎn)逡逑ｊ保持不動(dòng)，這樣就避免了社區(qū)互換問題。逡逑另一個(gè)跨區(qū)間移動(dòng)產(chǎn)生的問題是描述滯后現(xiàn)象。如圖３－５所示，節(jié)點(diǎn)ｉ屬于逡逑分Ｋ邋Ｃ，節(jié)點(diǎn)ｊ與節(jié)點(diǎn)ｋ屬于另一個(gè)分區(qū)Ｄ。分區(qū)Ｄ在執(zhí)行本地移動(dòng)的過程中節(jié)逡逑點(diǎn)ｊ邋Ｗ模塊度增加而移動(dòng)到丫節(jié)點(diǎn)ｋ所在的社區(qū)中，而節(jié)點(diǎn)Ｃ因?yàn)橄偟臏笮�，逡逑不知道�?jié)點(diǎn)ｊ已經(jīng)發(fā)生移動(dòng)

社區(qū)互換問題的解決方案即為節(jié)點(diǎn)在分區(qū)間的移動(dòng)增加一個(gè)限制條件，使得逡逑只有一方的節(jié)點(diǎn)產(chǎn)生移動(dòng)，這樣就能保證兩個(gè)節(jié)點(diǎn)聚集到同一個(gè)社區(qū)中。本文以逡逑節(jié)點(diǎn)的度作為評(píng)判標(biāo)準(zhǔn)，節(jié)點(diǎn)的度為節(jié)點(diǎn)直連的所有邊的權(quán)重之和，度大的節(jié)點(diǎn)逡逑相對(duì)其周邊節(jié)點(diǎn)更具有中心性，因此向度更大的節(jié)點(diǎn)移動(dòng)更為合理。逡逑由此得出的跨分區(qū)移動(dòng)規(guī)則為：當(dāng)本分區(qū)內(nèi)的節(jié)點(diǎn)因?yàn)槟K度增加而需要向逡逑虛節(jié)點(diǎn)所在的社區(qū)移動(dòng)時(shí)，需要額外對(duì)比該節(jié)點(diǎn)與虛節(jié)點(diǎn)的度。若該節(jié)點(diǎn)的度小逡逑于虛節(jié)點(diǎn)的度，則將節(jié)點(diǎn)移動(dòng)至虛節(jié)點(diǎn)所在的社區(qū)；否則不移動(dòng)。如圖３－４的（ｂ）逡逑所示，節(jié)點(diǎn)ｉ與節(jié)點(diǎn)ｊ分別處于兩個(gè)分區(qū)中，互為對(duì)方分區(qū)的虛節(jié)點(diǎn)。假設(shè)節(jié)點(diǎn)逡逑ｉ的度小于節(jié)點(diǎn)ｊ的度，貝``計(jì)算中，節(jié)點(diǎn)ｉ會(huì)移動(dòng)至節(jié)點(diǎn)ｊ所在的社區(qū)，而節(jié)點(diǎn)逡逑ｊ保持不動(dòng)，這樣就避免了社區(qū)互換問題。逡逑另一個(gè)跨區(qū)間移動(dòng)產(chǎn)生的問題是描述滯后現(xiàn)象。如圖３－５所示，節(jié)點(diǎn)ｉ屬于逡逑分Ｋ邋Ｃ，節(jié)點(diǎn)ｊ與節(jié)點(diǎn)ｋ屬于另一個(gè)分區(qū)Ｄ。分區(qū)Ｄ在執(zhí)行本地移動(dòng)的過程中節(jié)逡逑點(diǎn)ｊ邋Ｗ模塊度增加而移動(dòng)到丫節(jié)點(diǎn)ｋ所在的社區(qū)中，而節(jié)點(diǎn)Ｃ因?yàn)橄偟臏笮�，逡逑不知道�?jié)點(diǎn)ｊ已經(jīng)發(fā)生移動(dòng)，所以扔按照原先的情況進(jìn)行計(jì)兌。到收縮階段時(shí)，逡逑節(jié)點(diǎn)ｉ進(jìn)入分丨ＸＤ中，因?yàn)楣?jié)點(diǎn)ｊ放棄了原先的社區(qū)，導(dǎo)致廣節(jié)點(diǎn)ｉ仍舊是－個(gè)逡逑獨(dú)立社區(qū)的取獨(dú)節(jié)點(diǎn)，而沒有和節(jié)點(diǎn)ｊ及節(jié)點(diǎn)ｋ聚合在一起。逡逑

【參考文獻(xiàn)】

相關(guān)期刊論文 前4條

1 陳東明;劉健;王冬琦;徐曉偉;;基于MapReduce的分布式網(wǎng)絡(luò)數(shù)據(jù)聚類算法[J];計(jì)算機(jī)工程;2013年07期

2 唐艷琴;潘志松;吳君青;;基于MapReduce的快速Newman并行算法[J];華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年S1期

3 金弟;劉大有;楊博;劉杰;何東曉;田野;;基于局部探測(cè)的快速?gòu)?fù)雜網(wǎng)絡(luò)聚類算法[J];電子學(xué)報(bào);2011年11期

4 金弟;劉杰;賈正雪;劉大有;;基于k最近鄰網(wǎng)絡(luò)的數(shù)據(jù)聚類算法[J];模式識(shí)別與人工智能;2010年04期

本文編號(hào)：2779390