【正文】 續(xù)測量而不受影響，其測量結(jié)果的數(shù)據(jù)量十分可觀，有效性也能得到保障。圖 為 Ark探測源點在全球的分布。 CAIDA 是互聯(lián)網(wǎng)拓?fù)浞治鲅芯?領(lǐng)域中一個具有代表性和影響力的大型科研項目。 定義 自治域級拓?fù)洌?表示 Inter 中各個獨立的自治域之間的互聯(lián)關(guān)系，這里的一個節(jié)點表示 Inter 中的一個自治域（ Autonomous System），而圖中的邊則代表兩個自治域之間通過 BGP[32, 33]邊界網(wǎng)關(guān)協(xié)議存在著互聯(lián)關(guān)系，兩個自治域之間有一條邊。直接從 IP 級路徑生成的拓?fù)鋱D稱為 IP 級拓?fù)?[31]圖，其中一個節(jié)點代表一個 IP 地址。東北大學(xué)碩士學(xué)位論文 錯誤 !未找到引用源。 第三章介紹了 互聯(lián)網(wǎng)拓?fù)浠咎卣鞣治雠c多粒度社團發(fā)現(xiàn)算法設(shè)計 ， 在 本章中，著重分析了互聯(lián)網(wǎng)拓?fù)渲谢镜耐負(fù)涮卣鹘Y(jié)構(gòu)，并且提出了探測每種拓?fù)浣Y(jié)構(gòu)的算法，最東北大學(xué)碩士學(xué)位論文 第 1 章 緒 論 5 后對算 法做了驗證?；ヂ?lián)網(wǎng)是典型的復(fù)雜網(wǎng)絡(luò)，互聯(lián)網(wǎng)的可視化研究也有十幾年的歷史，互聯(lián)網(wǎng)的可視化可以幫助人們更加直觀的觀察網(wǎng)絡(luò)，發(fā)現(xiàn)潛在的網(wǎng)絡(luò)特征和功能，同時下一代互聯(lián)網(wǎng)的設(shè)計也需要對網(wǎng)絡(luò)的結(jié)構(gòu)和功能有深刻了解。雖然各個學(xué)科學(xué)者的研究方向都不盡相同，但研究的思路有著一定的共性，研究的方法有著相似的過程 ： 問題開始是對所研究領(lǐng)域的數(shù)據(jù)進行網(wǎng)絡(luò)建模，之后對建立的網(wǎng)絡(luò)模型應(yīng)用復(fù)雜網(wǎng)絡(luò)和傳統(tǒng)數(shù)據(jù)挖掘的各種算法進行統(tǒng)計分析，計算網(wǎng)絡(luò)靜態(tài)幾何特征量，研究網(wǎng)絡(luò)隨時間的演化過程，挖掘網(wǎng)絡(luò)所包含的信息與知識，最后對網(wǎng)絡(luò)結(jié)構(gòu)和研究結(jié)果進行可視化展示，得出結(jié)論。 目前對于復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)的研究在國際上已經(jīng)相對成熟，可是針對以互聯(lián)網(wǎng)拓?fù)涮卣鳛榛A(chǔ)的社團結(jié)構(gòu)研究還相對不足，傳統(tǒng)社團發(fā)現(xiàn)算法并不能很好的 反映 互聯(lián)網(wǎng)特有的拓?fù)涮卣?。其中彈力布局算法運用物理類比法來模擬物理系統(tǒng)， ForceAtlas2 算法是彈力布局中的經(jīng)典之作。作 為信息可視化的一個重要分支 ，復(fù)雜 網(wǎng)絡(luò)可 視化的研 究從上 世紀(jì) 90 年代中 期開始 ，在 Graph Drawing,InfoVis(IEEESymposium on Information Visualization),IV(International Conference on Information Visualization)等重要國際會議中都成為一個越來越受關(guān)注的議題，引起了各國學(xué)者的高度重視。科學(xué)計算可視化的思想是上個世紀(jì) 八十 年代美國科學(xué)基金會 （ 1CV） 提出的。 目前對于復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)的研究在國際上已經(jīng)相對成熟，可是針對以互聯(lián)網(wǎng)拓?fù)涮卣鳛榛A(chǔ)的社團結(jié)構(gòu)研究還相對不足，傳統(tǒng)社團發(fā)現(xiàn)算法并不能很好的反應(yīng)互聯(lián)網(wǎng)特有的拓?fù)涮卣鳌Ｉ鐖F結(jié)構(gòu)發(fā)現(xiàn)在很多領(lǐng)域都有廣泛應(yīng)用，比如生物學(xué)、物理學(xué)、計算機圖形學(xué)、社會學(xué)（見文獻 [13~14]）等。 圖 社團結(jié)構(gòu)劃分示意圖 the illustration of munity structure 一般而言，社團包含 模塊、類、群、組等各種含義。在利用復(fù)雜網(wǎng)絡(luò)理論對實際網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進行研究時，用來刻畫其宏觀拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)特征量主要有度分布，平均路徑長度、聚類系數(shù)、介數(shù)等等 。 從 20 世紀(jì)末開始，復(fù)雜網(wǎng)絡(luò)理論的研究已經(jīng)拓展到了從物理學(xué)到社會學(xué)等眾多學(xué)科中，其中 Watts 和 Strogatz 在 Nature 雜志上發(fā)表的文獻 [5]探討了復(fù)雜網(wǎng)絡(luò)中存在“小世界” 錯誤 !未指定書簽。nyi 建立了隨機圖理論[3](Random Graph Theory)，開創(chuàng)了復(fù)雜網(wǎng)路理論系統(tǒng)性研究。 在現(xiàn)實世界中，存在大量復(fù)雜系統(tǒng)，可把這些復(fù)雜系統(tǒng)看作各種網(wǎng)絡(luò)來研究。 V 東北大學(xué)碩士學(xué)位論文 目 錄 VI 目 錄 獨創(chuàng)性聲明 .............................................................................................................................................................................. I 摘 要 .......................................................................................................................................................................................... II Abstract ....................................................................................................................................................................................III 第 1 章 緒 論 ........................................................................................................................................................................ 1 課題研究的背景與意義 ..................................................................................................... 1 互聯(lián)網(wǎng)的社團結(jié)構(gòu)研究現(xiàn)狀 .................................................................................... 1 互聯(lián)網(wǎng)可視化研究現(xiàn)狀 ........................................................................................... 2 本文研究的意義 ....................................................................................................... 3 本文組織結(jié)構(gòu) ..................................................................................................................... 4 第 2 章 互聯(lián)網(wǎng)網(wǎng)絡(luò)數(shù)據(jù)來源及處理 ......................................................................................................................... 6 互聯(lián)網(wǎng)網(wǎng)絡(luò)數(shù)據(jù)來源 ......................................................................................................... 6 原始網(wǎng)絡(luò)數(shù)據(jù)預(yù)處理 ......................................................................................................... 8 數(shù)據(jù)格式的處理 ....................................................................................................... 8 原始網(wǎng)絡(luò)拓?fù)? ........................................................................................................... 9 最大子圖的獲取 ..................................................................................................... 10 相關(guān)特征量 ....................................................................................................................... 12 本章小結(jié) ........................................................................................................................... 13 第 3 章 互聯(lián)網(wǎng)拓?fù)浠咎卣鞣治雠c多粒度社團發(fā)現(xiàn)算法設(shè)計 ................................................................ 14 互聯(lián)網(wǎng)拓?fù)浠咎卣鞣治? ............................................................................................... 14 多粒度社團發(fā)現(xiàn)算法設(shè)計的總體思想 ........................................................................... 17 分而劃之 ......................................................................................................................... 19 層次折疊收縮算法 .................................................................................................. 19 鏈狀探測算法 .......................................................................................................... 24 高核數(shù)節(jié)點聚合探測算法 ...................................................................................... 26 中心節(jié)點組織探測算法 ......................................................................................... 32 各種網(wǎng)絡(luò)探測算法處理后的網(wǎng)絡(luò)效果 .................................................................. 35 合而聚之 ............................................................................................................................ 36 模塊度 ..................................................................................................................... 36 小社團合并算法 ...................................................................................................... 37 社團劃分比較 ................................................................................................................... 40 東北大學(xué)碩士學(xué)位論文 目 錄 VII 對于全球 IPV6 拓?fù)涞膭澐直容^ .....................................................