【正文】 ......................... 37 社團劃分比較 ................................................................................................................... 40 東北大學碩士學位論文 目 錄 VII 對于全球 IPV6 拓撲的劃分比較 .................................................................................. 41 105 算法在其它網(wǎng)絡上的測試 ......................................................................................... 43 Karate 俱樂部 ....................................................................................................... 43 東北大學嵌入式實驗室 聊天網(wǎng)絡 — 網(wǎng)絡的共產(chǎn)主義 .................................. 45 東大嵌入式實驗室日常人際交流網(wǎng)絡 — 地理位置隔離的社團結(jié)構(gòu) ............... 46 新的衡量社團劃分質(zhì)量方法的探討 ............................................................................... 48 新的社團發(fā)現(xiàn)思路 ............................................................................................... 48 新的求解最短路徑的算法 ...................................................................................... 49 本章小結(jié) .................................................................................................................... 49 第 4 章 一種新的面向社團的網(wǎng)絡拓撲可視化算法 ......................................................................................... 51 可視化算法綜述 ............................................................................................................... 51 面向社團結(jié)構(gòu)特征的可視化 ........................................................................................... 53 所用開發(fā)工具 .......................................................................................................... 53 算法思想 ................................................................................................................. 54 算法設(shè)計與實現(xiàn) ...................................................................................................... 54 本章小結(jié) ........................................................................................................................... 59 第 5 章 總結(jié)與展望 .......................................................................................................................................................... 60 本文所做的工作 ............................................................................................................... 60 不足及展望 ....................................................................................................................... 61 參考文獻 ................................................................................................................................................................................ 62 致 謝 ..................................................................................................................................................................................... 66 攻讀碩士期間發(fā)表的論文 ............................................................................................................................................. 68 東北大學碩士學位論文 第 1 章 緒 論 1 第 1 章 緒 論 課題研究的背景與意義 互聯(lián)網(wǎng)的社 團結(jié)構(gòu)研究現(xiàn)狀 近年來 ,隨著信息系統(tǒng)（如 WWW、 電信網(wǎng)、 廣播電視網(wǎng) 、移動網(wǎng)絡等 ）的迅猛發(fā)展，網(wǎng)絡拓撲數(shù)據(jù)的規(guī)?？焖僭龃? ，以致人們不能通過傳統(tǒng)技術(shù)和方式來管理和運作這些復雜網(wǎng)絡。在利用復雜網(wǎng)絡理論對實際網(wǎng)絡拓撲結(jié)構(gòu)進行研究時，用來刻畫其宏觀拓撲結(jié)構(gòu)的網(wǎng)絡特征量主要有度分布，平均路徑長度、聚類系數(shù)、介數(shù)等等 ?？茖W計算可視化的思想是上個世紀 八十 年代美國科學基金會 （ 1CV） 提出的。雖然各個學科學者的研究方向都不盡相同，但研究的思路有著一定的共性，研究的方法有著相似的過程 ： 問題開始是對所研究領(lǐng)域的數(shù)據(jù)進行網(wǎng)絡建模，之后對建立的網(wǎng)絡模型應用復雜網(wǎng)絡和傳統(tǒng)數(shù)據(jù)挖掘的各種算法進行統(tǒng)計分析，計算網(wǎng)絡靜態(tài)幾何特征量，研究網(wǎng)絡隨時間的演化過程，挖掘網(wǎng)絡所包含的信息與知識，最后對網(wǎng)絡結(jié)構(gòu)和研究結(jié)果進行可視化展示，得出結(jié)論。直接從 IP 級路徑生成的拓撲圖稱為 IP 級拓撲 [31]圖，其中一個節(jié)點代表一個 IP 地址。其測量范圍的廣泛程度， 就目前而言在主動測量項目中較有優(yōu)勢，此外 CAIDA 測量源點擁有完全自主的控制權(quán)與所屬權(quán)，可以不間斷地持續(xù)測量而不受影響，其測量結(jié)果的數(shù)據(jù)量十分可觀，有效性也能得到保障。 本文在研究社團發(fā)現(xiàn)用的可視化工具 gephi 支持的是一種 XML 文件格式，具體文件內(nèi)容由節(jié)點和邊組成。算法如下： a) 初始化整個網(wǎng)絡節(jié)點，節(jié)點的屬性 visited 設(shè)置為 false，節(jié)點的屬性 subgraph 值為 1, 子圖 個數(shù) subgraphNum = 0 。如果一個節(jié)點存在于 k核，但在 (k+1)核中被移除，則此節(jié)點的核數(shù)為 k,即對于 v?V(G)，如果 v?corek– corek+1， vCoreness k? 。 為了驗證上述的猜想，本文借助 Gephi[34]具對互聯(lián)網(wǎng)拓撲可視化。 首先，互聯(lián)網(wǎng)的結(jié)構(gòu)應該是非均質(zhì)的，有許 許多多的局域網(wǎng)組成；其次，在這些局域網(wǎng)之間，應該有外部路由器連接；再次，每個分離的大陸之間應該有至少一條鏈狀線路；再次，在局域網(wǎng)內(nèi)部，應該還可以包含更小的局域網(wǎng)；再次，互聯(lián)網(wǎng)作為一種典型的復雜網(wǎng)絡，整個網(wǎng)絡拓撲的節(jié)點的重要性程度應該滿足二八定律，互聯(lián)網(wǎng)中應該會有一些比較重要的中心節(jié)點，一般來說度值越大，節(jié)點的重要性也越大，最后，應該有許多互聯(lián)網(wǎng)的服務節(jié)點，這些節(jié)點不是內(nèi)網(wǎng)節(jié)點，并且相關(guān)服務的節(jié)點連接可能會很密切。后面關(guān)于互聯(lián)網(wǎng)社團發(fā)現(xiàn)的研究將圍繞這個最大子網(wǎng)展開，為方便起見，這個子網(wǎng)命名為studyedNet。 1. 算法設(shè)計 在網(wǎng)絡拓撲 N 中有 3 個分離子圖 (圖 a)： A（ 2 個節(jié)點）， B（ 4 個節(jié)點）， C(10 個節(jié)點 )。 3. 格式轉(zhuǎn)化 在理解 traceroute 的工作原理后， CAIDA 原始數(shù)據(jù)格式的意義也將迎刃而解。 7 圖 Ark 探測源點在全球的分布 The distribution of Ark monitors in the world Ark 項目迄今的活動節(jié)點共 54 個，其中亞洲 5 個，亞洲的 5 個測量點如表 所示。目前所討論較多的 Inter 拓撲有三種： IP 級拓撲 [30,31]、路由級拓撲和自治域級拓撲。如果能設(shè)計一種針對這些特有的互聯(lián)網(wǎng)的拓撲特征探測算法，那么將對互聯(lián)網(wǎng)的社團研究提供幫助。 互聯(lián)網(wǎng)可視化研究現(xiàn)狀 互聯(lián)網(wǎng)的結(jié)構(gòu)非常復雜，如果僅用數(shù)據(jù)表格或文字的形式來表示網(wǎng)絡，理解起來非東北大學碩士學位論文 第 1 章 緒 論 3 常 困難 ， 導致網(wǎng)絡所包含的信息無從體現(xiàn)。si 和 Albert 在 Science 雜志上發(fā)表的文獻 [6]探討了隨機網(wǎng)絡中“無標度”現(xiàn)象，這兩篇文獻被認為是復雜網(wǎng)絡研究新紀元的標志。visual Community。 III 評價標準上的優(yōu)秀性；就多粒度特征而言， 105 算法發(fā)現(xiàn)的社團內(nèi)部包含多種不同粒度的互聯(lián)網(wǎng)基本拓撲結(jié)構(gòu)，比如鏈狀、高核聚類狀、局部樹狀、中心節(jié)點狀等，而 FUOCILN算法發(fā)現(xiàn)的社團內(nèi)部只有節(jié)點信息， 105 算法的社團內(nèi)部信息容量要遠大于 FUOCILN。論文中取得的研究成果除加以標注和致謝的地方外，不包含其他人己經(jīng)發(fā)表或撰寫過的研究成果，也不包括本人為獲得其他學位而使用過的材料。由于大規(guī)模數(shù)據(jù)的復雜性以及考慮了突出社團特征等問題，這必將犧牲畫布資源。人們通過對生物網(wǎng)絡、 社會關(guān)系網(wǎng)、 Web 網(wǎng)等的研究 ,發(fā)現(xiàn)這些網(wǎng)絡都具有某些共同特點，包括：整體相對稀疏 ，局部比較密集；頂點度值服從冪率分布，也被稱為無標度特性 [1]；整體分布具有高聚集度、 低平均最短路徑 (平均最短路徑為 O (loglog N) ) 的小世界特性 [2]。隨著對網(wǎng)絡性質(zhì)的物理意義及數(shù)學特性的研究分析，人們發(fā)現(xiàn)包括 Inter 在內(nèi)的許多網(wǎng)絡有一個共同的性質(zhì)，即社團特性或者稱為群聚現(xiàn)象。當時在科學計算中產(chǎn)生了大量數(shù)據(jù)，人們很難清楚知道這些數(shù)據(jù)所表示的含義以及數(shù)據(jù)之間的關(guān)系，于是提出了將它們以圖形化的方式顯示出來的可視化思想。在整個研究過程中，僅系統(tǒng)建模的步驟只需要數(shù)學理論和相關(guān)的領(lǐng)域知識，而其它步驟如 :對網(wǎng)絡進行算法分析和對網(wǎng)絡結(jié)構(gòu)進行可視化展示等，都需要計算機軟件的輔助來 完成。 定 義 路由級拓撲 ： 指互聯(lián)網(wǎng)中的路由器基于互聯(lián)關(guān)系而構(gòu)成的一種拓撲。作為 Ark 項目的成員， Neu節(jié)點不僅自身采集互聯(lián)網(wǎng)拓撲數(shù)據(jù)，還可以以合作者的身份，獲得 CAIDA 遍布全球眾多測量源點所提供的海量的、更新及時的數(shù)據(jù)。從 CAIDA 原始數(shù)據(jù)提出節(jié)點和邊的過程相對比較簡單，在此不再累述。 存儲容 器 nodeVector = null ，nextNodeVector = null。 核數(shù)表示的是節(jié)點在核中的深度， k 值越大意味著該核在拓撲圖中位置更為核心。為了節(jié)省篇幅，只截取相關(guān)的局部圖形加以說明驗證。在用可視化的手段分析前，先根據(jù)互聯(lián)網(wǎng)的網(wǎng)絡協(xié)議做一個實際互聯(lián)網(wǎng)結(jié)構(gòu)的猜想。在圖 中，可以看出，那些之前分布在邊緣的分離節(jié)點和邊以及被過濾 掉，這也證明了最大連通子圖的獲取算法是正確有效