人類社會(huì)早已被網(wǎng)絡(luò)化,萬(wàn)維網(wǎng)、社交網(wǎng)絡(luò)和交通網(wǎng)絡(luò)等復(fù)雜網(wǎng)絡(luò)普遍存在于人們的生活當(dāng)中。復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是理解和解釋網(wǎng)絡(luò)動(dòng)態(tài)行為或過(guò)程的有效手段。對(duì)于計(jì)算機(jī)病毒在計(jì)算機(jī)網(wǎng)絡(luò)上的傳播、信息或者謠言在社會(huì)網(wǎng)絡(luò)中的擴(kuò)散等一些應(yīng)用性很強(qiáng)的網(wǎng)絡(luò)行為,都需要依靠網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行分析研究。通過(guò)社區(qū)發(fā)現(xiàn)算法發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu),同時(shí)利用可視化布局方法展示復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu),能夠幫助研究者發(fā)掘網(wǎng)絡(luò)中有用信息。針對(duì)現(xiàn)有的社區(qū)發(fā)現(xiàn)算法存在社區(qū)質(zhì)量低,算法執(zhí)行效率不高的問(wèn)題,以及FR算法社區(qū)結(jié)構(gòu)不明顯,算法不適用于復(fù)雜網(wǎng)絡(luò)的問(wèn)題。本文提出了一種基于Louvain算法的改進(jìn)社區(qū)發(fā)現(xiàn)算法和一種基于FR算法的改進(jìn)社區(qū)布局算法。首先,在Louvain算法的基礎(chǔ)上研究一種面向復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法。復(fù)雜網(wǎng)絡(luò)的特征包括小世界及無(wú)尺度,節(jié)點(diǎn)度數(shù)表現(xiàn)為冪率分布規(guī)律,以及大部分節(jié)點(diǎn)度數(shù)較低而少部分節(jié)點(diǎn)度數(shù)偏高。其中復(fù)雜網(wǎng)絡(luò)中度數(shù)高的節(jié)點(diǎn)和相鄰度數(shù)低的節(jié)點(diǎn)容易構(gòu)成一個(gè)社區(qū)。為了解決Louvain算法效率不高、社區(qū)劃分不合理的問(wèn)題,通過(guò)在重要節(jié)點(diǎn)中選取重要程度高的節(jié)點(diǎn),控制大社區(qū)過(guò)度歸并的趨勢(shì),減少算法的迭代周期,在迭代過(guò)程中迅速地歸并小社區(qū),提高算法運(yùn)行效率,同時(shí)提高社區(qū)劃分質(zhì)量。實(shí)驗(yàn)結(jié)果表明,通過(guò)優(yōu)化改進(jìn)后的Louvain算法在社區(qū)劃分質(zhì)量和算法效率上都有所提高。其次,在FR算法的基礎(chǔ)上研究一種社區(qū)布局算法,該算法能展示網(wǎng)絡(luò)社區(qū)結(jié)構(gòu),對(duì)社區(qū)引力和斥力模型進(jìn)行了優(yōu)化,引力的計(jì)算考慮了節(jié)點(diǎn)的親密度信息,斥力的計(jì)算考慮了節(jié)點(diǎn)的重要程度信息,使得引力和斥力的計(jì)算步驟更加高效。結(jié)合社區(qū)發(fā)現(xiàn)算法執(zhí)行結(jié)果,對(duì)社區(qū)結(jié)構(gòu)進(jìn)行布局。實(shí)驗(yàn)結(jié)果表明,改進(jìn)的算法有效地提高了算法執(zhí)行效率,使得社區(qū)結(jié)構(gòu)布局更加清晰。
【學(xué)位單位】：重慶郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類】：TP301.6;O157.5
【部分圖文】：

意義物聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，各種終端、傳感器、類型的數(shù)據(jù)，這些數(shù)據(jù)源源不斷地進(jìn)入信息系復(fù)雜的數(shù)據(jù)中獲得有價(jià)值的信息是一項(xiàng)雖然繁，把實(shí)體當(dāng)作節(jié)點(diǎn)，把實(shí)體之間的關(guān)系作為邊連接的網(wǎng)絡(luò)，這種網(wǎng)絡(luò)被稱為復(fù)雜網(wǎng)絡(luò)[1]，如絡(luò)，小聚居”的特征。該網(wǎng)絡(luò)具有自組織，自，復(fù)雜網(wǎng)絡(luò)具有部分或全部網(wǎng)絡(luò)特征。其中，無(wú)標(biāo)度。小世界特征意味著網(wǎng)絡(luò)有一個(gè)小的平標(biāo)度特征意味著網(wǎng)絡(luò)連通性的分布具有冪律形

iiG聚類系數(shù)iC 的平均值就是整個(gè)網(wǎng)絡(luò)的聚類系數(shù) 之間。網(wǎng)絡(luò)中，局部聚類系數(shù)iC 隨著節(jié)點(diǎn) i 的減小而，如果網(wǎng)絡(luò)規(guī)模比較大，聚類系數(shù)接近于零。遠(yuǎn)大于零，即具有明顯的聚類特征。節(jié)點(diǎn)可劃分為幾個(gè)組，是許多現(xiàn)實(shí)網(wǎng)絡(luò)的共同組之間的節(jié)點(diǎn)連接稀疏，圖 2.1 顯示了一個(gè)擁

于解釋網(wǎng)絡(luò)的均度，聚類系數(shù)和最短路徑等特性具有重要作用。由于發(fā)現(xiàn)網(wǎng)絡(luò)中連接的發(fā)現(xiàn)需要耗費(fèi)高昂的費(fèi)用，導(dǎo)致許多真實(shí)網(wǎng)絡(luò)不完預(yù)測(cè)網(wǎng)絡(luò)中丟失的連接意義重大。Clauset 在已有建立模型基礎(chǔ)上，提出了連接的預(yù)測(cè)器，與傳統(tǒng)的算法相比，優(yōu)點(diǎn)是能夠適用于更廣泛類型的網(wǎng)絡(luò)結(jié)2 社區(qū)發(fā)現(xiàn)算法復(fù)雜網(wǎng)絡(luò)可以表示為圖 G (V ,E)，其中V 是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，E是的邊集，而復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)實(shí)質(zhì)上是對(duì)圖的劃分。綜合當(dāng)前社區(qū)發(fā)現(xiàn)究現(xiàn)狀，王永程[61]將社區(qū)劃分方法分為傳統(tǒng)的社區(qū)劃分算法與新型社區(qū)劃從劃分思想的角度，傳統(tǒng)方法主要基于圖分割理論、標(biāo)簽、層次聚類、隨新型方法主要基于統(tǒng)計(jì)推斷、重疊社區(qū)、密度、動(dòng)態(tài)距離，整體框架如圖。

【參考文獻(xiàn)】

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

1 王軍;劉金輝;;大數(shù)據(jù)的國(guó)內(nèi)外研究現(xiàn)狀及發(fā)展動(dòng)態(tài)分析[J];電子技術(shù)與軟件工程;2015年23期

2 劉瑤;康曉慧;高紅;劉嶠;吳祖峰;秦志光;;基于節(jié)點(diǎn)親密度和度的社會(huì)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)方法[J];計(jì)算機(jī)研究與發(fā)展;2015年10期

3 吳渝;李藻旭;李紅波;溫磊;;展示復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的社團(tuán)引力導(dǎo)引的布局算法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2015年08期

4 馬曉亭;;圖書館大數(shù)據(jù)可視化分析系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J];圖書館學(xué)研究;2015年10期

5 水超;陳濤;李慧;陳國(guó)升;;基于力導(dǎo)向模型的網(wǎng)絡(luò)圖自動(dòng)布局算法綜述[J];計(jì)算機(jī)工程與科學(xué);2015年03期

6 曾新紅;蔡慶河;黃華軍;林偉明;;基于力導(dǎo)向模型的非一致節(jié)點(diǎn)群組布局可視化算法研究[J];現(xiàn)代圖書情報(bào)技術(shù);2014年09期

7 熊金石;李建華;沈迪;王剛;;基于邊介數(shù)的信息系統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估方法[J];科技導(dǎo)報(bào);2013年14期

8 吳祖峰;王鵬飛;秦志光;蔣紹權(quán);;改進(jìn)的Louvain社團(tuán)劃分算法[J];電子科技大學(xué)學(xué)報(bào);2013年01期

9 朱志良;林森;崔坤;于海;;基于復(fù)雜網(wǎng)絡(luò)社區(qū)劃分的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化布局算法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2011年11期

10 孫揚(yáng);蔣遠(yuǎn)翔;趙翔;肖衛(wèi)東;;網(wǎng)絡(luò)可視化研究綜述[J];計(jì)算機(jī)科學(xué);2010年02期

相關(guān)碩士學(xué)位論文 前2條

1 趙潤(rùn)乾;多維海量社交網(wǎng)絡(luò)數(shù)據(jù)可視化技術(shù)研究[D];重慶郵電大學(xué);2016年

2 朱楓彤;面向復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法研究[D];吉林大學(xué);2015年

本文編號(hào)：2829009