【正文】 他人己經(jīng)發(fā)表或撰寫過的研究成果，也不包括本人為獲得其他學(xué)位而使用過的材料。與我一同 工作的同志對(duì)本研究所做的任何貢獻(xiàn)均己在論文中作了明確的說明并表示謝意。 II 基于互聯(lián)網(wǎng)拓?fù)涮卣鞯亩嗔６壬鐖F(tuán)發(fā)現(xiàn)算法及其可視化 摘 要 近年來，復(fù)雜網(wǎng)絡(luò)的社團(tuán)研究相對(duì)比較成熟，可針對(duì)以 Inter 拓?fù)浣Y(jié)構(gòu)為基礎(chǔ)的社團(tuán)特征研究至目前為止還是相對(duì)不足，并且沒有很好的從 Inter 特有的結(jié)構(gòu)特征入手。經(jīng)過前面幾步的處理，一個(gè)完整網(wǎng)絡(luò)拓?fù)涞拇蟠笮⌒〉慕M織結(jié)構(gòu)就呈現(xiàn)出來，下一步就需要把這些大大小的網(wǎng)絡(luò)組織結(jié)構(gòu)合并成為一個(gè)個(gè)具有高內(nèi)聚低耦合特征的社團(tuán)，這就是合而聚之。 III 評(píng)價(jià)標(biāo)準(zhǔn)上的優(yōu)秀性；就多粒度特征而言， 105 算法發(fā)現(xiàn)的社團(tuán)內(nèi)部包含多種不同粒度的互聯(lián)網(wǎng)基本拓?fù)浣Y(jié)構(gòu)，比如鏈狀、高核聚類狀、局部樹狀、中心節(jié)點(diǎn)狀等，而 FUOCILN算法發(fā)現(xiàn)的社團(tuán)內(nèi)部只有節(jié)點(diǎn)信息， 105 算法的社團(tuán)內(nèi)部信息容量要遠(yuǎn)大于 FUOCILN。為此，本可視化算法開辟一個(gè)新的畫布資源，采用射線布局算法顯示某個(gè)特定社團(tuán)內(nèi)部節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)。 III Community Structure Detecting of Multiple Granularity and Visualization Based on Inter Network Topology Abstract The munity studies of plex work have relatively matured, but the study for munity based on characteristics of the Inter topology so far is relatively lacked, and not starts from the Inter39。 this layout is divided into two big steps: the layout of the entire work munity, the layout of the internal nodes in each munity. The first step consists of two levels: firstly, according to the physical analogy, it simulates the physical system environment, and automatically layouts munity node。visual Community。具有以上性質(zhì)（無標(biāo)度性、小世界性）的網(wǎng)絡(luò)被稱為復(fù)雜網(wǎng)絡(luò) 。網(wǎng)絡(luò)的研究最早可追溯到 18 世紀(jì)，數(shù)學(xué)家歐拉在對(duì)“ Konigsberg 七橋問題”的研究時(shí)提出的一個(gè)數(shù)學(xué)分支 —— 圖論，圖論在較長(zhǎng)的時(shí)間內(nèi)一直未能有突破性進(jìn)展。隨機(jī)圖理論有明顯的缺點(diǎn)，它不能很好的描述 很多實(shí)際網(wǎng)絡(luò)，因?yàn)榇蟛糠謱?shí)際網(wǎng)絡(luò)并不是完全隨機(jī)的。si 和 Albert 在 Science 雜志上發(fā)表的文獻(xiàn) [6]探討了隨機(jī)網(wǎng)絡(luò)中“無標(biāo)度”現(xiàn)象，這兩篇文獻(xiàn)被認(rèn)為是復(fù)雜網(wǎng)絡(luò)研究新紀(jì)元的標(biāo)志。也就是說網(wǎng)絡(luò)是由若干東北大學(xué)碩士學(xué)位論文 第 1 章 緒 論 2 個(gè)“群 (group)” 或“模塊 (module)“， 在群內(nèi)部節(jié)點(diǎn)的連接非常緊密，而相對(duì)的在各個(gè)群組之間的連接則較為稀疏。在電信網(wǎng)絡(luò)或生物網(wǎng)絡(luò)中，也可以根據(jù)不同的性質(zhì)將各節(jié)點(diǎn)化為不同的社團(tuán)（見文獻(xiàn) [10~12]）。目前對(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ò)中。 互聯(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)。復(fù)雜網(wǎng)絡(luò)研究的興起進(jìn)一步促進(jìn)了網(wǎng)絡(luò)可視化技術(shù)的發(fā)展，同時(shí)對(duì)可視化技術(shù)提出了更高的要求。這些可視化工具中包含著各式各樣的圖布局算法。本文將根據(jù)這些不足展開對(duì)突出社團(tuán)結(jié)構(gòu)特征的可視化研究。如果能設(shè)計(jì)一種針對(duì)這些特有的互聯(lián)網(wǎng)的拓?fù)涮卣魈綔y(cè)算法，那么將對(duì)互聯(lián)網(wǎng)的社團(tuán)研究提供幫助。然而，在不同學(xué)科的研究過程中，很多學(xué)科專家對(duì)計(jì)算機(jī)工具的開發(fā)并不熟悉，從而無法集中精力來解決其領(lǐng)域問題，影響了他們的研究進(jì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)研究以及可視化研究的重要意義。 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)。目前所討論較多的 Inter 拓?fù)溆腥N： IP 級(jí)拓?fù)?[30,31]、路由級(jí)拓?fù)浜妥灾斡蚣?jí)拓?fù)洹D中的節(jié)點(diǎn)指代的是一個(gè)路由器，而邊則表示兩個(gè)路由器之間存在著直接的連接關(guān)系。 本文研究社團(tuán)發(fā)現(xiàn)選用的是 IP 級(jí)拓?fù)?。目前探測(cè)節(jié)點(diǎn)主要分布在北美洲、歐洲眾多國家的研究院所、高校、軍事機(jī)構(gòu)中，而亞洲、大洋洲、南美洲、非洲分布較少。 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)如表 所示。 為了清晰簡(jiǎn)單的分析互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)，本文選取的是 20xx 年 9 月 29 號(hào) CAIDA 全球所有站點(diǎn)探測(cè)到的合并的數(shù)據(jù)。traceroute 程序的設(shè)計(jì)是利用 ICMP 及 IP header 的 TTL（ Time To Live）欄位（ field）。 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á)了。 3. 格式轉(zhuǎn)化 在理解 traceroute 的工作原理后， CAIDA 原始數(shù)據(jù)格式的意義也將迎刃而解。 原始網(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)和邊。 下一小節(jié)將討論處理這種情況的方式。即使是“失真“的網(wǎng)絡(luò)拓?fù)?，依然具有?fù)雜網(wǎng)絡(luò)以及英特網(wǎng)的本質(zhì)特征，不影響對(duì)于社團(tuán)結(jié)構(gòu)的研究。 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) )。 b) 遍歷網(wǎng)絡(luò)中的第一個(gè)節(jié)點(diǎn) currentNode,如果 visited==false,設(shè)置 visited 屬性值為true， subgraphNum++，然后把節(jié)點(diǎn) currentNode的所有鄰居節(jié)點(diǎn)存入 nodeVector。 d) 如果 ()==0，遍歷結(jié)束。 e l s e 遍 歷 下 一 次 節(jié) 點(diǎn) 。后面關(guān)于互聯(lián)網(wǎng)社團(tuán)發(fā)現(xiàn)的研究將圍繞這個(gè)最大子網(wǎng)展開，為方便起見，這個(gè)子網(wǎng)命名為studyedNet。可以通過 k核解析由外層至內(nèi)層一層一層地解析網(wǎng)絡(luò)，直到最內(nèi)層為止，從而揭示網(wǎng)絡(luò)的層次結(jié)構(gòu)性質(zhì)。 13 本章小結(jié) 本章主要介紹了后續(xù)研究用到的互聯(lián)網(wǎng)拓?fù)鋽?shù)據(jù)來源以及原始數(shù)據(jù)的預(yù)處理過程，最后還介紹了下文涉及到的一些基本特征量的概念。 互聯(lián)網(wǎng)拓?fù)浠?特征分析 互聯(lián)網(wǎng)作為一種典型的復(fù)雜網(wǎng)絡(luò)，它的拓?fù)涮卣鞅囟ㄓ袕?fù)雜網(wǎng)絡(luò)的特征。 首先，互聯(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ì)很密切。 1. 互聯(lián)網(wǎng)中的局域邊緣結(jié)構(gòu) 東北大學(xué)碩士學(xué)位論文 錯(cuò)誤 !未找到引用源。 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ù)包功能。 為了驗(yàn)證上述的猜想，本文借助 Gephi[34]具對(duì)互聯(lián)網(wǎng)拓?fù)淇梢暬?duì)于互聯(lián)網(wǎng)拓?fù)涮卣鬟M(jìn)行分析，有效的手段就是對(duì)其可視化，在可視化的基礎(chǔ)上通過觀察統(tǒng)計(jì)比較等方式來發(fā)現(xiàn)互聯(lián)網(wǎng)的基本特征結(jié)構(gòu)。 東北大學(xué)碩士學(xué)位論文 錯(cuò)誤 !未找到引用源。 p (k)表示的是一個(gè)隨機(jī)節(jié)點(diǎn)的度恰好是 k 的概率， ? ?? ?? ?Pkpk VG?， 其中 ??Pk為度為 k 的節(jié)點(diǎn)數(shù)目， ? ?VG為節(jié)點(diǎn)總數(shù)。如果一個(gè)節(jié)點(diǎn)存在于 k核，但在 (k+1)核中被移除，則此節(jié)點(diǎn)的核數(shù)為 k,即對(duì)于 v?V(G)，如果 v?corek– corek+1， vCoreness k? 。 12 圖 提取最大子圖算法流程圖 The flow chart of algorithm obtaining biggest subgraph 3. 算法驗(yàn)證 下面是處理后獲得的最大的子網(wǎng)。 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è)子圖）。 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ò)誤 !未找到引用源。算法如下： a) 初始化整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，節(jié)點(diǎn)的屬性 visited 設(shè)置為 false，節(jié)點(diǎn)的屬性 subgraph 值為 1, 子圖 個(gè)數(shù) subgraphNum = 0 。舉個(gè)例子，對(duì)于下圖 (a)來說，最大子圖的獲取的結(jié)果將是圖 (b)。 10 圖 原始網(wǎng)絡(luò)拓?fù)? Fig Original work topology 最大子圖的獲取 圖 有太多的孤立節(jié)點(diǎn)、孤立邊、孤立區(qū)域，即有太多的分離的子圖，這不利于研究互聯(lián)網(wǎng)的社團(tuán)結(jié)構(gòu)。這種情況將嚴(yán)重影響本文互聯(lián)網(wǎng)社團(tuán)發(fā)現(xiàn)的研究。 本文在研究社團(tuán)發(fā)現(xiàn)用的可視化工具 gephi 支持的是一種 XML 文件格式，具體文件內(nèi)容由節(jié)點(diǎn)和邊組成。如果這個(gè)時(shí)間過了，它將打印出一系列的 *號(hào)表明：在這個(gè)路徑上，這個(gè)設(shè)備不能在給定的時(shí)間內(nèi)發(fā)出 ICMP TTL 到期消息的響應(yīng)。此時(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á)目的地。 8 原始網(wǎng)絡(luò)數(shù)據(jù)預(yù)處理 數(shù)據(jù)格式的處理 1. CAIDA 原始數(shù)據(jù)格式 CAIDA 探測(cè)的傳統(tǒng)的數(shù)據(jù)格式不能直接在可視化工具上加以分析，需要轉(zhuǎn)換格式。其測(cè)量范圍的廣泛程度， 就目前而言在主動(dòng)測(cè)量項(xiàng)目中較有優(yōu)勢(shì)，此外 CAIDA 測(cè)量源點(diǎn)擁有完全自主的控制權(quán)與所屬權(quán)，可以不間斷地持