【正文】 3. 互聯(lián)網(wǎng)高核節(jié)點(diǎn)聚類特征 為了便于分析，去掉了互聯(lián)網(wǎng)中核數(shù)為 0 的節(jié)點(diǎn)，即去掉了互 聯(lián)網(wǎng)中的局部區(qū)域結(jié)構(gòu)，圖 便是 1 核網(wǎng)絡(luò)集合視圖。 2. 互聯(lián)網(wǎng)中的鏈路特征 在圖 中，可以發(fā)現(xiàn)有很多鏈狀的節(jié)點(diǎn)，這些節(jié)點(diǎn)連接不同的局域網(wǎng)，它們的度值基本上是 2，這些度值為 2 的節(jié)點(diǎn)完全是中轉(zhuǎn)節(jié)點(diǎn)，這些節(jié)點(diǎn)具有路由來自其它網(wǎng)絡(luò)的數(shù)據(jù)包功能。 1. 互聯(lián)網(wǎng)中的局域邊緣結(jié)構(gòu) 東北大學(xué)碩士學(xué)位論文 錯(cuò)誤 !未找到引用源。 為了驗(yàn)證上述的猜想，本文借助 Gephi[34]具對(duì)互聯(lián)網(wǎng)拓?fù)淇梢暬? 首先，互聯(lián)網(wǎng)的結(jié)構(gòu)應(yīng)該是非均質(zhì)的，有許 許多多的局域網(wǎng)組成；其次，在這些局域網(wǎng)之間，應(yīng)該有外部路由器連接；再次，每個(gè)分離的大陸之間應(yīng)該有至少一條鏈狀線路；再次，在局域網(wǎng)內(nèi)部，應(yīng)該還可以包含更小的局域網(wǎng)；再次，互聯(lián)網(wǎng)作為一種典型的復(fù)雜網(wǎng)絡(luò)，整個(gè)網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)的重要性程度應(yīng)該滿足二八定律，互聯(lián)網(wǎng)中應(yīng)該會(huì)有一些比較重要的中心節(jié)點(diǎn)，一般來說度值越大，節(jié)點(diǎn)的重要性也越大，最后，應(yīng)該有許多互聯(lián)網(wǎng)的服務(wù)節(jié)點(diǎn)，這些節(jié)點(diǎn)不是內(nèi)網(wǎng)節(jié)點(diǎn)，并且相關(guān)服務(wù)的節(jié)點(diǎn)連接可能會(huì)很密切。對(duì)于互聯(lián)網(wǎng)拓?fù)涮卣鬟M(jìn)行分析，有效的手段就是對(duì)其可視化，在可視化的基礎(chǔ)上通過觀察統(tǒng)計(jì)比較等方式來發(fā)現(xiàn)互聯(lián)網(wǎng)的基本特征結(jié)構(gòu)。 互聯(lián)網(wǎng)拓?fù)浠?特征分析 互聯(lián)網(wǎng)作為一種典型的復(fù)雜網(wǎng)絡(luò)，它的拓?fù)涮卣鞅囟ㄓ袕?fù)雜網(wǎng)絡(luò)的特征。 東北大學(xué)碩士學(xué)位論文 錯(cuò)誤 !未找到引用源。 13 本章小結(jié) 本章主要介紹了后續(xù)研究用到的互聯(lián)網(wǎng)拓?fù)鋽?shù)據(jù)來源以及原始數(shù)據(jù)的預(yù)處理過程，最后還介紹了下文涉及到的一些基本特征量的概念。 p (k)表示的是一個(gè)隨機(jī)節(jié)點(diǎn)的度恰好是 k 的概率， ? ?? ?? ?Pkpk VG?， 其中 ??Pk為度為 k 的節(jié)點(diǎn)數(shù)目， ? ?VG為節(jié)點(diǎn)總數(shù)?？梢酝ㄟ^ k核解析由外層至內(nèi)層一層一層地解析網(wǎng)絡(luò)，直到最內(nèi)層為止，從而揭示網(wǎng)絡(luò)的層次結(jié)構(gòu)性質(zhì)。如果一個(gè)節(jié)點(diǎn)存在于 k核，但在 (k+1)核中被移除，則此節(jié)點(diǎn)的核數(shù)為 k,即對(duì)于 v?V(G)，如果 v?corek– corek+1， vCoreness k? 。后面關(guān)于互聯(lián)網(wǎng)社團(tuán)發(fā)現(xiàn)的研究將圍繞這個(gè)最大子網(wǎng)展開，為方便起見，這個(gè)子網(wǎng)命名為studyedNet。 12 圖 提取最大子圖算法流程圖 The flow chart of algorithm obtaining biggest subgraph 3. 算法驗(yàn)證 下面是處理后獲得的最大的子網(wǎng)。 e l s e 遍 歷 下 一 次 節(jié) 點(diǎn) 。 e) 子圖，這一步 算法相對(duì)簡(jiǎn)單，就是根據(jù)節(jié)點(diǎn)屬性 subgraph 的值來確定每一個(gè)子圖節(jié)點(diǎn)的數(shù)目，然后再找出節(jié)點(diǎn)數(shù)最多的子圖即可（當(dāng)節(jié)點(diǎn)的 subgraph 值相同時(shí)，它們就屬于同一個(gè)子圖）。 d) 如果 ()==0，遍歷結(jié)束。 c) 依次遍歷 nodeVector 中的每一個(gè)節(jié)點(diǎn)，對(duì)于遍歷的當(dāng)前節(jié)點(diǎn) currentNode，設(shè)置 visited 屬性值為 false， subgraph = subgraphNum ； if 當(dāng)前節(jié)點(diǎn) currentNode東北大學(xué)碩士學(xué)位論文 錯(cuò)誤 !未找到引用源。 b) 遍歷網(wǎng)絡(luò)中的第一個(gè)節(jié)點(diǎn) currentNode,如果 visited==false,設(shè)置 visited 屬性值為true， subgraphNum++，然后把節(jié)點(diǎn) currentNode的所有鄰居節(jié)點(diǎn)存入 nodeVector。算法如下： a) 初始化整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，節(jié)點(diǎn)的屬性 visited 設(shè)置為 false，節(jié)點(diǎn)的屬性 subgraph 值為 1, 子圖 個(gè)數(shù) subgraphNum = 0 。 1. 算法設(shè)計(jì) 在網(wǎng)絡(luò)拓?fù)?N 中有 3 個(gè)分離子圖 (圖 a)： A（ 2 個(gè)節(jié)點(diǎn)）， B（ 4 個(gè)節(jié)點(diǎn)）， C(10 個(gè)節(jié)點(diǎn) )。舉個(gè)例子，對(duì)于下圖 (a)來說，最大子圖的獲取的結(jié)果將是圖 (b)。即使是“失真“的網(wǎng)絡(luò)拓?fù)?，依然具有?fù)雜網(wǎng)絡(luò)以及英特網(wǎng)的本質(zhì)特征，不影響對(duì)于社團(tuán)結(jié)構(gòu)的研究。 10 圖 原始網(wǎng)絡(luò)拓?fù)? Fig Original work topology 最大子圖的獲取 圖 有太多的孤立節(jié)點(diǎn)、孤立邊、孤立區(qū)域，即有太多的分離的子圖，這不利于研究互聯(lián)網(wǎng)的社團(tuán)結(jié)構(gòu)。 下一小節(jié)將討論處理這種情況的方式。這種情況將嚴(yán)重影響本文互聯(lián)網(wǎng)社團(tuán)發(fā)現(xiàn)的研究。 原始網(wǎng)絡(luò)拓?fù)? 在獲取 CAIDA 上的互聯(lián)網(wǎng) 數(shù)據(jù)之后，建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，然后對(duì)其拓?fù)浣Y(jié)構(gòu)利用可視化工具 Gephi[34]中的 ForceAtlas2[27]算法可視 化，由圖 可觀察出，網(wǎng)絡(luò)中存在著很多孤立的節(jié)點(diǎn)和邊。 本文在研究社團(tuán)發(fā)現(xiàn)用的可視化工具 gephi 支持的是一種 XML 文件格式，具體文件內(nèi)容由節(jié)點(diǎn)和邊組成。 3. 格式轉(zhuǎn)化 在理解 traceroute 的工作原理后， CAIDA 原始數(shù)據(jù)格式的意義也將迎刃而解。如果這個(gè)時(shí)間過了，它將打印出一系列的 *號(hào)表明：在這個(gè)路徑上，這個(gè)設(shè)備不能在給定的時(shí)間內(nèi)發(fā)出 ICMP TTL 到期消息的響應(yīng)。 9 一 般應(yīng)用程序都不會(huì)用的號(hào)碼（ 30000 以上），所以當(dāng)此 UDP datagram 到達(dá)目的地后該主機(jī)會(huì)送回一個(gè) ICMP port unreachable 的消息，而當(dāng) traceroute 收到這個(gè)消息時(shí)，便知道目的地已經(jīng)到達(dá)了。此時(shí)， TTL 變?yōu)?0 了，所以該路由器會(huì)將此 datagram 丟掉，并送回一個(gè) ICMP time exceeded 消息（包括發(fā) IP 包的源地址，IP 包的所有內(nèi)容及路由器的 IP 地址）， traceroute 收到這個(gè)消息后，便知道這個(gè)路由器存在于這個(gè)路徑上，接著 traceroute 再送出另一個(gè) TTL 是 2 的 datagram，發(fā)現(xiàn)第 2 個(gè)路由器 ...... traceroute 每次將送出的 datagram 的 TTL 加 1 來發(fā)現(xiàn)另一個(gè)路由器，這個(gè)重復(fù)的動(dòng)作一直持續(xù)到某個(gè) datagram 抵達(dá)目的地。traceroute 程序的設(shè)計(jì)是利用 ICMP 及 IP header 的 TTL（ Time To Live）欄位（ field）。 8 原始網(wǎng)絡(luò)數(shù)據(jù)預(yù)處理 數(shù)據(jù)格式的處理 1. CAIDA 原始數(shù)據(jù)格式 CAIDA 探測(cè)的傳統(tǒng)的數(shù)據(jù)格式不能直接在可視化工具上加以分析，需要轉(zhuǎn)換格式。 為了清晰簡(jiǎn)單的分析互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)，本文選取的是 20xx 年 9 月 29 號(hào) CAIDA 全球所有站點(diǎn)探測(cè)到的合并的數(shù)據(jù)。其測(cè)量范圍的廣泛程度， 就目前而言在主動(dòng)測(cè)量項(xiàng)目中較有優(yōu)勢(shì)，此外 CAIDA 測(cè)量源點(diǎn)擁有完全自主的控制權(quán)與所屬權(quán)，可以不間斷地持續(xù)測(cè)量而不受影響，其測(cè)量結(jié)果的數(shù)據(jù)量十分可觀，有效性也能得到保障。 7 圖 Ark 探測(cè)源點(diǎn)在全球的分布 The distribution of Ark monitors in the world Ark 項(xiàng)目迄今的活動(dòng)節(jié)點(diǎn)共 54 個(gè)，其中亞洲 5 個(gè)，亞洲的 5 個(gè)測(cè)量點(diǎn)如表 所示。圖 為 Ark探測(cè)源點(diǎn)在全球的分布。目前探測(cè)節(jié)點(diǎn)主要分布在北美洲、歐洲眾多國(guó)家的研究院所、高校、軍事機(jī)構(gòu)中，而亞洲、大洋洲、南美洲、非洲分布較少。 CAIDA 是互聯(lián)網(wǎng)拓?fù)浞治鲅芯?領(lǐng)域中一個(gè)具有代表性和影響力的大型科研項(xiàng)目。 本文研究社團(tuán)發(fā)現(xiàn)選用的是 IP 級(jí)拓?fù)洹? 定義 自治域級(jí)拓?fù)洌?表示 Inter 中各個(gè)獨(dú)立的自治域之間的互聯(lián)關(guān)系，這里的一個(gè)節(jié)點(diǎn)表示 Inter 中的一個(gè)自治域（ Autonomous System），而圖中的邊則代表兩個(gè)自治域之間通過 BGP[32, 33]邊界網(wǎng)關(guān)協(xié)議存在著互聯(lián)關(guān)系，兩個(gè)自治域之間有一條邊。圖中的節(jié)點(diǎn)指代的是一個(gè)路由器，而邊則表示兩個(gè)路由器之間存在著直接的連接關(guān)系。直接從 IP 級(jí)路徑生成的拓?fù)鋱D稱為 IP 級(jí)拓?fù)?[31]圖，其中一個(gè)節(jié)點(diǎn)代表一個(gè) IP 地址。目前所討論較多的 Inter 拓?fù)溆腥N： IP 級(jí)拓?fù)?[30,31]、路由級(jí)拓?fù)浜妥灾斡蚣?jí)拓?fù)?。東北大學(xué)碩士學(xué)位論文 錯(cuò)誤 !未找到引用源。 visualCommunity 在可視化網(wǎng)絡(luò)拓?fù)鋾r(shí)分為三步：第一步，模擬物理系統(tǒng)環(huán)境，全自動(dòng)布局社團(tuán)節(jié)點(diǎn)；第二步，采用動(dòng)態(tài)交互模式，手動(dòng)調(diào)整社團(tuán)節(jié)點(diǎn) 位置 ；第三步，采用射線布局模式，可視化社團(tuán)節(jié)點(diǎn)內(nèi)部的拓?fù)浣Y(jié)構(gòu)。 第三章介紹了 互聯(lián)網(wǎng)拓?fù)浠咎卣鞣治雠c多粒度社團(tuán)發(fā)現(xiàn)算法設(shè)計(jì) ， 在 本章中，著重分析了互聯(lián)網(wǎng)拓?fù)渲谢镜耐負(fù)涮卣鹘Y(jié)構(gòu)，并且提出了探測(cè)每種拓?fù)浣Y(jié)構(gòu)的算法，最東北大學(xué)碩士學(xué)位論文 第 1 章 緒 論 5 后對(duì)算 法做了驗(yàn)證。 本文組織結(jié)構(gòu) 本文共分為五章，各章的主要內(nèi)容如下： 第一章為緒論，介紹了互聯(lián)網(wǎng)的社團(tuán)結(jié)構(gòu)研究以及可視化研究的現(xiàn)狀，論述了互聯(lián)網(wǎng)的社團(tuán)結(jié)構(gòu)研究以及可視化研究的重要意義?；ヂ?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ò)特征和功能，同時(shí)下一代互聯(lián)網(wǎng)的設(shè)計(jì)也需要對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)和功能有深刻了解。然而，在不同學(xué)科的研究過程中，很多學(xué)科專家對(duì)計(jì)算機(jī)工具的開發(fā)并不熟悉，從而無法集中精力來解決其領(lǐng)域問題，影響了他們的研究進(jìn)程和效果。雖然各個(gè)學(xué)科學(xué)者的研究方向都不盡相同，但研究的思路有著一定的共性，研究的方法有著相似的過程 ： 問題開始是對(duì)所研究領(lǐng)域的數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)建模，之后對(duì)建立的網(wǎng)絡(luò)模型應(yīng)用復(fù)雜網(wǎng)絡(luò)和傳統(tǒng)數(shù)據(jù)挖掘的各種算法進(jìn)行統(tǒng)計(jì)分析，計(jì)算網(wǎng)絡(luò)靜態(tài)幾何特征量，研究網(wǎng)絡(luò)隨時(shí)間的演化過程，挖掘網(wǎng)絡(luò)所包含的信息與知識(shí)，最后對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和研究結(jié)果進(jìn)行可視化展示，得出結(jié)論。如果能設(shè)計(jì)一種針對(duì)這些特有的互聯(lián)網(wǎng)的拓?fù)涮卣魈綔y(cè)算法，那么將對(duì)互聯(lián)網(wǎng)的社團(tuán)研究提供幫助。 目前對(duì)于復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的研究在國(guó)際上已經(jīng)相對(duì)成熟，可是針對(duì)以互聯(lián)網(wǎng)拓?fù)涮卣鳛榛A(chǔ)的社團(tuán)結(jié)構(gòu)研究還相對(duì)不足，傳統(tǒng)社團(tuán)發(fā)現(xiàn)算法并不能很好的 反映 互聯(lián)網(wǎng)特有的拓?fù)涮卣鳌１疚膶⒏鶕?jù)這些不足展開對(duì)突出社團(tuán)結(jié)構(gòu)特征的可視化研究。其中彈力布局算法運(yùn)用物理類比法來模擬物理系統(tǒng)， ForceAtlas2 算法是彈力布局中的經(jīng)典之作。這些可視化工具中包含著各式各樣的圖布局算法。作 為信息可視化的一個(gè)重要分支 ，復(fù)雜 網(wǎng)絡(luò)可 視化的研 究從上 世紀(jì) 90 年代中 期開始 ，在 Graph Drawing,InfoVis(IEEESymposium on Information Visualization),IV(International Conference on Information Visualization)等重要國(guó)際會(huì)議中都成為一個(gè)越來越受關(guān)注的議題，引起了各國(guó)學(xué)者的高度重視。復(fù)雜網(wǎng)絡(luò)研究的興起進(jìn)一步促進(jìn)了網(wǎng)絡(luò)可視化技術(shù)的發(fā)展，同時(shí)對(duì)可視化技術(shù)提出了更高的要求?？茖W(xué)計(jì)算可視化的思想是上個(gè)世紀(jì) 八十 年代美國(guó)科學(xué)基金會(huì) （ 1CV） 提出的。 互聯(lián)網(wǎng)可視化研究現(xiàn)狀 互聯(lián)網(wǎng)的結(jié)構(gòu)非常復(fù)雜，如果僅用數(shù)據(jù)表格或文字的形式來表示網(wǎng)絡(luò)，理解起來非東北大學(xué)碩士學(xué)位論文 第 1 章 緒 論 3 常 困難 ， 導(dǎo)致網(wǎng)絡(luò)所包含的信息無從體現(xiàn)。 目前對(duì)于復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的研究在國(guó)際上已經(jīng)相對(duì)成熟，可是針對(duì)以互聯(lián)網(wǎng)拓?fù)涮卣鳛榛A(chǔ)的社團(tuán)結(jié)構(gòu)研究還相對(duì)不足，傳統(tǒng)社團(tuán)發(fā)現(xiàn)算法并不能很好的反應(yīng)互聯(lián)網(wǎng)特有的拓?fù)涮卣?。目前?duì)于復(fù)雜網(wǎng)絡(luò)中的社團(tuán)特性的研究主要集中在社團(tuán)劃分算法、社團(tuán)結(jié)構(gòu)研究及基于社團(tuán)結(jié)構(gòu)的建模：例如文獻(xiàn) [17]提出了一種基于信息編碼為標(biāo)準(zhǔn)的社團(tuán)劃分算法，擴(kuò)展了之前通常是基于模塊度 [18,19]或是特征向量 [20]的社團(tuán)劃分算法；文獻(xiàn) [21]則將社團(tuán)劃分算法又?jǐn)U展到了加權(quán)網(wǎng)絡(luò)中。社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)在很多領(lǐng)域都有廣泛應(yīng)用，比如生物學(xué)、物理學(xué)、計(jì)算機(jī)圖形學(xué)、社會(huì)學(xué)（見文獻(xiàn) [13~14]）等。在電信網(wǎng)絡(luò)或生物網(wǎng)絡(luò)中，也可以根據(jù)不同的性質(zhì)將各節(jié)點(diǎn)化為不同的社團(tuán)（見文獻(xiàn) [10~12]）。 圖 社團(tuán)結(jié)構(gòu)劃分示意圖 the illustration of munity structure 一般而言，社團(tuán)包含 模塊、類、群、組等各種含義。也就是說網(wǎng)絡(luò)是由若干東北大學(xué)碩士學(xué)位論文 第 1 章 緒 論 2 個(gè)“群 (group)