【摘要】：近年來,復(fù)雜網(wǎng)絡(luò)分析研究表明大量現(xiàn)實(shí)網(wǎng)絡(luò)如社交網(wǎng)絡(luò)、交通運(yùn)輸網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、蛋白質(zhì)網(wǎng)絡(luò)、規(guī)則關(guān)聯(lián)網(wǎng)絡(luò)等具有非平凡的拓?fù)涮卣�。�?fù)雜網(wǎng)絡(luò)分析的主要目標(biāo)是檢測(cè)并發(fā)現(xiàn)這些結(jié)構(gòu)以有利于人們理解其中蘊(yùn)含的規(guī)律。網(wǎng)絡(luò)可視化是實(shí)現(xiàn)上述目標(biāo)的重要支撐技術(shù),也是信息可視化的分支研究領(lǐng)域。快速、高效地、多尺度地可視化這些網(wǎng)絡(luò)拓?fù)?降低研究復(fù)雜性,以供網(wǎng)絡(luò)分析專家高效瀏覽并直觀發(fā)現(xiàn)網(wǎng)絡(luò)中隱含的規(guī)律或趨勢(shì),已成為當(dāng)前重要的研究課題。隨著網(wǎng)絡(luò)規(guī)模的快速膨脹,網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜多樣,傳統(tǒng)網(wǎng)絡(luò)可視化方法已經(jīng)難以滿足實(shí)際需求。為此,本課題致力于大規(guī)模網(wǎng)絡(luò)的可視化技術(shù)研究,將其分解為“網(wǎng)絡(luò)結(jié)構(gòu)特征檢測(cè)——網(wǎng)絡(luò)結(jié)構(gòu)展示”兩個(gè)階段,解決如下四個(gè)方面的具體問題:(1)大規(guī)模網(wǎng)絡(luò)中重疊社團(tuán)結(jié)構(gòu)的快速檢測(cè);(2)網(wǎng)絡(luò)拓?fù)渲懈唠A依賴關(guān)系的檢測(cè)和刻畫;(3)大規(guī)模網(wǎng)絡(luò)全局拓?fù)浣Y(jié)構(gòu)的多尺度展示;(4)局部高密度網(wǎng)絡(luò)的精確展示。具體研究工作如下:1.針對(duì)現(xiàn)有重疊社團(tuán)挖掘算法易將重疊區(qū)域錯(cuò)誤地劃分為獨(dú)立的社團(tuán)且計(jì)算復(fù)雜的問題,提出了一種基于局部信息度量的快速重疊社團(tuán)挖掘算法。首先,為節(jié)點(diǎn)定義局部信息度量指標(biāo)——社團(tuán)連接度和鄰居連接度,建模節(jié)點(diǎn)與社團(tuán)的關(guān)系,縮小計(jì)算范圍;然后,每次并行地迭代執(zhí)行縮減、擴(kuò)展、去重等操作,并更新局部度量指標(biāo),通過松弛每次迭代的終止條件,發(fā)現(xiàn)近似最優(yōu)社團(tuán)集合而不是最優(yōu)社團(tuán),最終算法復(fù)雜度為O(7)m(10)n(8)�；谡鎸�(shí)的大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)的試驗(yàn)分析表明:與當(dāng)前流行的重疊社團(tuán)挖掘算法相比,本文算法在不損失檢測(cè)質(zhì)量的前提下,大幅提升了計(jì)算效率。2.針對(duì)網(wǎng)絡(luò)數(shù)據(jù)中高階關(guān)聯(lián)特性,設(shè)計(jì)了一種基于進(jìn)化博弈理論的網(wǎng)絡(luò)可視化聚類方法。首先采用超圖描述網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)間的高階關(guān)聯(lián)特性,其次,將超圖聚類的動(dòng)態(tài)過程建模為進(jìn)化博弈理論,證明了均衡點(diǎn)與優(yōu)化問題解的一一對(duì)應(yīng)關(guān)系,并推導(dǎo)出用于求解聚類的動(dòng)力學(xué)方程,算法無需設(shè)定聚類的數(shù)目。人工和真實(shí)數(shù)據(jù)集相結(jié)合的試驗(yàn)表明:本文算法能夠自動(dòng)確定分簇?cái)?shù)目,具有良好的聚類效果以及較強(qiáng)的魯棒性。3.針對(duì)大規(guī)模網(wǎng)絡(luò)全局結(jié)構(gòu)多尺度展示的問題,提出了一種基于非重要節(jié)點(diǎn)拆分融合的網(wǎng)絡(luò)層次壓縮算法。該算法首先在定義節(jié)點(diǎn)塊及其關(guān)系的基礎(chǔ)上,給出了針對(duì)節(jié)點(diǎn)塊的拓?fù)浣Y(jié)構(gòu)重要性度量方法;然后,利用資源分配和分流原理,提出了基于節(jié)點(diǎn)拆分的拓?fù)鋵哟尉酆蠙C(jī)制;最后,通過將網(wǎng)絡(luò)中每一層的非重要節(jié)點(diǎn)塊拆分融合到與其相鄰的節(jié)點(diǎn)塊中,實(shí)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的快速壓縮。與現(xiàn)有算法相比,本文算法效率較高,而且可以得到更加連貫的層次結(jié)構(gòu),從而更好實(shí)現(xiàn)多尺度展示。4.針對(duì)高密度網(wǎng)絡(luò)中邊的精確展示問題,提出面向強(qiáng)連接網(wǎng)絡(luò)圖的無損壓縮算法,借助冪圖分析技術(shù),將所有具有相同鄰居的節(jié)點(diǎn)集合匯聚成單個(gè)模塊(modules)以大幅壓縮網(wǎng)絡(luò)圖,連接到某個(gè)模塊的一條邊表明該邊與模塊內(nèi)的所有元素都相連。從而,整個(gè)圖均可以無損地可視化展示。首先,本文證明了含有單個(gè)模塊的最優(yōu)冪圖問題為NP難問題,進(jìn)而擴(kuò)展一般地最優(yōu)冪圖分解計(jì)算為NP難問題;其次,在梳理現(xiàn)有整數(shù)線性規(guī)劃模型和約束規(guī)劃模型等問題的基礎(chǔ)上,本文提出了基于回溯策略的波束搜索算法,以使有限的回溯策略提供啟發(fā)信息,相較于已知啟發(fā)式方法更快速地得到更優(yōu)的結(jié)果;最后,通過生成的隨機(jī)無標(biāo)度圖,驗(yàn)證了本文算法的有效性。
【學(xué)位授予單位】：戰(zhàn)略支援部隊(duì)信息工程大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2018
【分類號(hào)】：O157.5
【圖文】：

社團(tuán)挖掘是網(wǎng)絡(luò)結(jié)構(gòu)分析的重要手段，也是網(wǎng)絡(luò)可視化的重要研究?jī)?nèi)容。社團(tuán)挖掘算法通過將網(wǎng)絡(luò)中連接緊密的節(jié)點(diǎn)劃分到一起，形成若干個(gè)連接緊密的社團(tuán)，從而可以得到網(wǎng)絡(luò)的結(jié)構(gòu)組成，效果如圖1.1所示[20]。文獻(xiàn)[21]便基于模塊度提出了一個(gè)快速社團(tuán)挖掘方法，即Louvain算法，極大的提升了社團(tuán)挖掘的速度；Rosvall等[22]把社團(tuán)劃分問題轉(zhuǎn)化為壓縮編碼問題，提出了基于隨機(jī)游走的社團(tuán)劃分方法（Infomap），Infomap算法實(shí)用性強(qiáng)、劃分效果好，但算法復(fù)雜度相對(duì)較高。通常網(wǎng)絡(luò)社團(tuán)呈現(xiàn)動(dòng)態(tài)性、重疊性等特性導(dǎo)致檢測(cè)不準(zhǔn)確而影響應(yīng)用性能。文獻(xiàn)[25]則以社團(tuán)的局部統(tǒng)計(jì)重要性為優(yōu)化目標(biāo)提出了OSLOM社團(tuán)聚類方法，該方法能滿足多目標(biāo)優(yōu)化，且克服了Infomap不能應(yīng)用于重疊社團(tuán)劃分的問題；文獻(xiàn)[26]給出了一種動(dòng)態(tài)迭代算法檢測(cè)社團(tuán)結(jié)構(gòu)，通過構(gòu)建一種離散收斂的動(dòng)態(tài)系統(tǒng)，通過動(dòng)態(tài)迭代獲取最優(yōu)解。文獻(xiàn)[27]從多尺度的角度分析了社團(tuán)結(jié)構(gòu)的動(dòng)態(tài)穩(wěn)定性。文獻(xiàn)[28-30]聚焦于重疊社區(qū)的檢測(cè)

點(diǎn)提取局部網(wǎng)絡(luò)，并將標(biāo)識(shí)傳播算法應(yīng)用其中，最終可以發(fā)現(xiàn)已有社團(tuán)之間的聯(lián)盟檢測(cè)到重疊社團(tuán)結(jié)構(gòu)。但是該算法仍不能避免LPA算法的限制�？梢暬垲愌芯恐饕枷胧菍⒕垲惤Y(jié)果進(jìn)行可視化展示，與社團(tuán)挖掘算法類似網(wǎng)絡(luò)可視化研究的內(nèi)容之一。Kwon等[41]針對(duì)大量聚類算法及其參數(shù)的選擇問題，一種幫助用戶決策最佳聚類算法的可視化分析工具——Clustervision。文獻(xiàn)[42]設(shè)計(jì)了Clusterix系統(tǒng)，允許用戶動(dòng)態(tài)地添加或刪除聚類特征。Hongsen Liao等[43]針對(duì)基于的數(shù)據(jù)可視化分析面臨的多維擴(kuò)展問題，提出了基于聚類的可視化抽象方法增強(qiáng)多點(diǎn)圖的可視化。Zhiguang Zhou等[44]將可視化聚類方法應(yīng)用于空氣質(zhì)量分析中，提高析效率�；诰W(wǎng)格和密度的聚類方法作為一類重要的聚類技術(shù)，與本文算法類似，法不需要將分簇?cái)?shù)目作為輸入?yún)?shù)，適用于處理大規(guī)模數(shù)據(jù)集且類別可伸縮場(chǎng)景。度的聚類算法通過對(duì)象密度計(jì)算任意形狀的分簇結(jié)構(gòu)，典型的代表為OPTICS算法[劃分簇，而是產(chǎn)生一個(gè)聚類結(jié)構(gòu)，算法輸入?yún)?shù)為領(lǐng)域半徑和分簇的最小對(duì)象數(shù)，度閾值動(dòng)態(tài)劃分不同分簇�；诰W(wǎng)絡(luò)的聚類算法，將數(shù)據(jù)對(duì)象組織為矩陣，并使用構(gòu)劃分為矩形塊的值空間，通過塊信息分布實(shí)現(xiàn)聚類，代表性算法為STING算法[46]中，網(wǎng)格聚類通常與基于密度聚類的方法相結(jié)合，如GDILC算法[47]。

第二章 面向大規(guī)模網(wǎng)絡(luò)的快速重疊社團(tuán)挖掘算法確保在任何社團(tuán)中的任意節(jié)點(diǎn)在社團(tuán)中至少存在K 個(gè)鄰居，公 1 , 0ii j i i jjN v K S K N v K 若，其它常大的值，小而稠密的社團(tuán)將被忽略。另一方面，若K 為非常疏的大型社團(tuán)和微小的社團(tuán)，且算法不會(huì)受K 取較小值的影響值為 0.6 時(shí)（關(guān)于社團(tuán)相似度將在 2.3.3 節(jié)（4）步驟中定義）出了本文算法應(yīng)用于 Amazon 網(wǎng)絡(luò)[104]時(shí)檢測(cè)的社團(tuán)的統(tǒng)計(jì)變化，稀疏的拓?fù)鋵⒉淮嬖谏鐖F(tuán)結(jié)構(gòu)。除高密度網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之外，。

【參考文獻(xiàn)】

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

1 常振超;陳鴻昶;劉陽;于洪濤;黃瑞陽;;基于聯(lián)合矩陣分解的節(jié)點(diǎn)多屬性網(wǎng)絡(luò)社團(tuán)檢測(cè)[J];物理學(xué)報(bào);2015年21期

2 郭曉波;趙書良;王長(zhǎng)賓;陳敏;;一種新的面向普通用戶的多值屬性關(guān)聯(lián)規(guī)則可視化挖掘方法[J];電子學(xué)報(bào);2015年02期

3 陳紅倩;張德政;陳誼;;一種超圖的區(qū)域型可視化方法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2015年02期

4 李慧嘉;李慧穎;李愛華;;多尺度的社團(tuán)結(jié)構(gòu)穩(wěn)定性分析[J];計(jì)算機(jī)學(xué)報(bào);2015年02期

5 任磊;杜一;馬帥;張小龍;戴國忠;;大數(shù)據(jù)可視分析綜述[J];軟件學(xué)報(bào);2014年09期

6 程學(xué)旗;靳小龍;王元卓;郭嘉豐;張鐵贏;李國杰;;大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J];軟件學(xué)報(bào);2014年09期

7 劉樹新;季新生;劉彩霞;郭虹;;一種信息傳播促進(jìn)網(wǎng)絡(luò)增長(zhǎng)的網(wǎng)絡(luò)演化模型[J];物理學(xué)報(bào);2014年15期

8 吳燁;鐘志農(nóng);熊偉;陳犖;景寧;;一種高效的屬性圖聚類方法[J];計(jì)算機(jī)學(xué)報(bào);2013年08期

9 陳玉明;苗奪謙;;基于冪圖的屬性約簡(jiǎn)搜索式算法[J];計(jì)算機(jī)學(xué)報(bào);2009年08期

本文編號(hào)：2794875