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

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

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

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

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

【參考文獻】

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

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

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

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

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

本文編號：2779390