大規(guī)模網(wǎng)絡(luò)可視化關(guān)鍵技術(shù)研究

1、大規(guī)模網(wǎng)絡(luò)可視化關(guān)鍵技術(shù)研究近年來, 復(fù)雜網(wǎng)絡(luò)分析研究說明大量現(xiàn)實網(wǎng)絡(luò)如社交網(wǎng)絡(luò)、交通運輸網(wǎng)絡(luò)、 引文網(wǎng)絡(luò)、蛋白質(zhì)網(wǎng)絡(luò)、 規(guī)那么關(guān)聯(lián)網(wǎng)絡(luò)等具有非平凡的拓撲特征。 復(fù)雜網(wǎng)絡(luò)分析 的主要目標是檢測并發(fā)現(xiàn)這些結(jié)構(gòu)以有利于人們理解其中蘊含的規(guī)律。網(wǎng)絡(luò)可視化是實現(xiàn)上述目標的重要支撐技術(shù) , 也是信息可視化的分支研究領(lǐng) 域?？焖佟⒏咝У?、多尺度地可視化這些網(wǎng)絡(luò)拓撲 ,降低研究復(fù)雜性 , 以供網(wǎng)絡(luò)分 析專家高效瀏覽并直觀發(fā)現(xiàn)網(wǎng)絡(luò)中隱含的規(guī)律或趨勢 , 已成為當(dāng)前重要的研究課 題。隨著網(wǎng)絡(luò)規(guī)模的快速膨脹 , 網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜多樣 ,傳統(tǒng)網(wǎng)絡(luò)可視化方法已經(jīng)難 以滿足實際需求。為此, 本課題致力于大規(guī)模網(wǎng)絡(luò)的可視化技

2、術(shù)研究 ,將其分解為 “網(wǎng)絡(luò)結(jié)構(gòu)特征檢測網(wǎng)絡(luò)結(jié)構(gòu)展示兩個階段 , 解決如下四個方面的具體問 題 :(1) 大規(guī)模網(wǎng)絡(luò)中重疊社團結(jié)構(gòu)的快速檢測 ;(2) 網(wǎng)絡(luò)拓撲中高階依賴關(guān)系的 檢測和刻畫 ;(3) 大規(guī)模網(wǎng)絡(luò)全局拓撲結(jié)構(gòu)的多尺度展示 ;(4) 局部高密度網(wǎng)絡(luò)的 精確展示。具體研究工作如下 :1. 針對現(xiàn)有重疊社團挖掘算法易將重疊區(qū)域錯誤地劃分 為獨立的社團且計算復(fù)雜的問題 , 提出了一種基于局部信息度量的快速重疊社團 挖掘算法。首先 , 為節(jié)點定義局部信息度量指標社團連接度和鄰居連接度 , 建模節(jié)點與社團的關(guān)系 ,縮小計算范圍 ;然后,每次并行地迭代執(zhí)行縮減、擴展、 去重等操作 , 并更新局

3、部度量指標 ,通過松弛每次迭代的終止條件 , 發(fā)現(xiàn)近似最優(yōu) 社團集合而不是最優(yōu)社團 , 最終算法復(fù)雜度為 O(7)m(10)n(8) 。基于真實的大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)的試驗分析說明 : 與當(dāng)前流行的重疊社團挖 掘算法相比 ,本文算法在不損失檢測質(zhì)量的前提下 ,大幅提升了計算效率。 2.針對 網(wǎng)絡(luò)數(shù)據(jù)中高階關(guān)聯(lián)特性 , 設(shè)計了一種基于進化博弈理論的網(wǎng)絡(luò)可視化聚類方法。首先采用超圖描述網(wǎng)絡(luò)內(nèi)節(jié)點間的高階關(guān)聯(lián)特性 , 其次, 將超圖聚類的動態(tài) 過程建模為進化博弈理論 ,證明了均衡點與優(yōu)化問題解的一一對應(yīng)關(guān)系 , 并推導(dǎo) 出用于求解聚類的動力學(xué)方程 , 算法無需設(shè)定聚類的數(shù)目。人工和真實數(shù)據(jù)集相 結(jié)合的

4、試驗說明 :本文算法能夠自動確定分簇數(shù)目 , 具有良好的聚類效果以及較 強的魯棒性。3.針對大規(guī)模網(wǎng)絡(luò)全局結(jié)構(gòu)多尺度展示的問題 , 提出了一種基于非重要節(jié)點 拆分融合的網(wǎng)絡(luò)層次壓縮算法。該算法首先在定義節(jié)點塊及其關(guān)系的根底上 , 給 出了針對節(jié)點塊的拓撲結(jié)構(gòu)重要性度量方法 ; 然后,利用資源分配和分流原理 ,提 出了基于節(jié)點拆分的拓撲層次聚合機制 ;最后, 通過將網(wǎng)絡(luò)中每一層的非重要節(jié) 點塊拆分融合到與其相鄰的節(jié)點塊中 , 實現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的快速壓縮。與現(xiàn)有算法相比 , 本文算法效率較高 , 而且可以得到更加連貫的層次結(jié)構(gòu) , 從 而更好實現(xiàn)多尺度展示。 4.針對高密度網(wǎng)絡(luò)中邊的精確展示問題 , 提出面向強連 接網(wǎng)絡(luò)圖的無損壓縮算法 ,借助冪圖分析技術(shù) , 將所有具有相同鄰居的節(jié)點集合 會聚成單個模塊 (modules) 以大幅壓縮網(wǎng)絡(luò)圖 , 連接到某個模塊的一條邊說明該 邊與模塊內(nèi)的所有元素都相連。從而,整個圖均可以無損地可視化展示。 首先, 本文證明了含有單個模塊的最 優(yōu)幕圖問題為NP難問題,進而擴展一般地最優(yōu)幕圖分解計算為 NP難問題;其次, 在梳理現(xiàn)有整數(shù)線性規(guī)劃模型和約束規(guī)劃模型等問題的根底上 ,本文提出了基于 回溯策略的波束搜索算法