【正文】 他人己經(jīng)發(fā)表或撰寫過的研究成果，也不包括本人為獲得其他學位而使用過的材料。與我一同 工作的同志對本研究所做的任何貢獻均己在論文中作了明確的說明并表示謝意。 II 基于互聯(lián)網(wǎng)拓撲特征的多粒度社團發(fā)現(xiàn)算法及其可視化 摘 要 近年來，復雜網(wǎng)絡的社團研究相對比較成熟，可針對以 Inter 拓撲結構為基礎的社團特征研究至目前為止還是相對不足，并且沒有很好的從 Inter 特有的結構特征入手。經(jīng)過前面幾步的處理，一個完整網(wǎng)絡拓撲的大大小小的組織結構就呈現(xiàn)出來，下一步就需要把這些大大小的網(wǎng)絡組織結構合并成為一個個具有高內聚低耦合特征的社團，這就是合而聚之。 III 評價標準上的優(yōu)秀性；就多粒度特征而言， 105 算法發(fā)現(xiàn)的社團內部包含多種不同粒度的互聯(lián)網(wǎng)基本拓撲結構，比如鏈狀、高核聚類狀、局部樹狀、中心節(jié)點狀等，而 FUOCILN算法發(fā)現(xiàn)的社團內部只有節(jié)點信息， 105 算法的社團內部信息容量要遠大于 FUOCILN。為此，本可視化算法開辟一個新的畫布資源，采用射線布局算法顯示某個特定社團內部節(jié)點的拓撲結構。 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。具有以上性質（無標度性、小世界性）的網(wǎng)絡被稱為復雜網(wǎng)絡 。網(wǎng)絡的研究最早可追溯到 18 世紀，數(shù)學家歐拉在對“ Konigsberg 七橋問題”的研究時提出的一個數(shù)學分支 —— 圖論，圖論在較長的時間內一直未能有突破性進展。隨機圖理論有明顯的缺點，它不能很好的描述 很多實際網(wǎng)絡，因為大部分實際網(wǎng)絡并不是完全隨機的。si 和 Albert 在 Science 雜志上發(fā)表的文獻 [6]探討了隨機網(wǎng)絡中“無標度”現(xiàn)象，這兩篇文獻被認為是復雜網(wǎng)絡研究新紀元的標志。也就是說網(wǎng)絡是由若干東北大學碩士學位論文 第 1 章 緒 論 2 個“群 (group)” 或“模塊 (module)“， 在群內部節(jié)點的連接非常緊密，而相對的在各個群組之間的連接則較為稀疏。在電信網(wǎng)絡或生物網(wǎng)絡中，也可以根據(jù)不同的性質將各節(jié)點化為不同的社團（見文獻 [10~12]）。目前對于復雜網(wǎng)絡中的社團特性的研究主要集中在社團劃分算法、社團結構研究及基于社團結構的建模：例如文獻 [17]提出了一種基于信息編碼為標準的社團劃分算法，擴展了之前通常是基于模塊度 [18,19]或是特征向量 [20]的社團劃分算法；文獻 [21]則將社團劃分算法又擴展到了加權網(wǎng)絡中。 互聯(lián)網(wǎng)可視化研究現(xiàn)狀 互聯(lián)網(wǎng)的結構非常復雜，如果僅用數(shù)據(jù)表格或文字的形式來表示網(wǎng)絡，理解起來非東北大學碩士學位論文 第 1 章 緒 論 3 常 困難 ， 導致網(wǎng)絡所包含的信息無從體現(xiàn)。復雜網(wǎng)絡研究的興起進一步促進了網(wǎng)絡可視化技術的發(fā)展，同時對可視化技術提出了更高的要求。這些可視化工具中包含著各式各樣的圖布局算法。本文將根據(jù)這些不足展開對突出社團結構特征的可視化研究。如果能設計一種針對這些特有的互聯(lián)網(wǎng)的拓撲特征探測算法，那么將對互聯(lián)網(wǎng)的社團研究提供幫助。然而，在不同學科的研究過程中，很多學科專家對計算機工具的開發(fā)并不熟悉，從而無法集中精力來解決其領域問題，影響了他們的研究進程和效果。 本文組織結構 本文共分為五章，各章的主要內容如下： 第一章為緒論，介紹了互聯(lián)網(wǎng)的社團結構研究以及可視化研究的現(xiàn)狀，論述了互聯(lián)網(wǎng)的社團結構研究以及可視化研究的重要意義。 visualCommunity 在可視化網(wǎng)絡拓撲時分為三步：第一步，模擬物理系統(tǒng)環(huán)境，全自動布局社團節(jié)點；第二步，采用動態(tài)交互模式，手動調整社團節(jié)點 位置 ；第三步，采用射線布局模式，可視化社團節(jié)點內部的拓撲結構。目前所討論較多的 Inter 拓撲有三種： IP 級拓撲 [30,31]、路由級拓撲和自治域級拓撲。圖中的節(jié)點指代的是一個路由器，而邊則表示兩個路由器之間存在著直接的連接關系。 本文研究社團發(fā)現(xiàn)選用的是 IP 級拓撲。目前探測節(jié)點主要分布在北美洲、歐洲眾多國家的研究院所、高校、軍事機構中，而亞洲、大洋洲、南美洲、非洲分布較少。 7 圖 Ark 探測源點在全球的分布 The distribution of Ark monitors in the world Ark 項目迄今的活動節(jié)點共 54 個，其中亞洲 5 個，亞洲的 5 個測量點如表 所示。 為了清晰簡單的分析互聯(lián)網(wǎng)拓撲結構，本文選取的是 20xx 年 9 月 29 號 CAIDA 全球所有站點探測到的合并的數(shù)據(jù)。traceroute 程序的設計是利用 ICMP 及 IP header 的 TTL（ Time To Live）欄位（ field）。 9 一 般應用程序都不會用的號碼（ 30000 以上），所以當此 UDP datagram 到達目的地后該主機會送回一個 ICMP port unreachable 的消息，而當 traceroute 收到這個消息時，便知道目的地已經(jīng)到達了。 3. 格式轉化 在理解 traceroute 的工作原理后， CAIDA 原始數(shù)據(jù)格式的意義也將迎刃而解。 原始網(wǎng)絡拓撲 在獲取 CAIDA 上的互聯(lián)網(wǎng) 數(shù)據(jù)之后，建立網(wǎng)絡拓撲結構，然后對其拓撲結構利用可視化工具 Gephi[34]中的 ForceAtlas2[27]算法可視 化，由圖 可觀察出，網(wǎng)絡中存在著很多孤立的節(jié)點和邊。 下一小節(jié)將討論處理這種情況的方式。即使是“失真“的網(wǎng)絡拓撲，依然具有復雜網(wǎng)絡以及英特網(wǎng)的本質特征，不影響對于社團結構的研究。 1. 算法設計 在網(wǎng)絡拓撲 N 中有 3 個分離子圖 (圖 a)： A（ 2 個節(jié)點）， B（ 4 個節(jié)點）， C(10 個節(jié)點 )。 b) 遍歷網(wǎng)絡中的第一個節(jié)點 currentNode,如果 visited==false,設置 visited 屬性值為true， subgraphNum++，然后把節(jié)點 currentNode的所有鄰居節(jié)點存入 nodeVector。 d) 如果 ()==0，遍歷結束。 e l s e 遍 歷 下 一 次 節(jié) 點 。后面關于互聯(lián)網(wǎng)社團發(fā)現(xiàn)的研究將圍繞這個最大子網(wǎng)展開，為方便起見，這個子網(wǎng)命名為studyedNet?？梢酝ㄟ^ k核解析由外層至內層一層一層地解析網(wǎng)絡，直到最內層為止，從而揭示網(wǎng)絡的層次結構性質。 13 本章小結 本章主要介紹了后續(xù)研究用到的互聯(lián)網(wǎng)拓撲數(shù)據(jù)來源以及原始數(shù)據(jù)的預處理過程，最后還介紹了下文涉及到的一些基本特征量的概念。 互聯(lián)網(wǎng)拓撲基本 特征分析 互聯(lián)網(wǎng)作為一種典型的復雜網(wǎng)絡，它的拓撲特征必定有復雜網(wǎng)絡的特征。 首先，互聯(lián)網(wǎng)的結構應該是非均質的，有許 許多多的局域網(wǎng)組成；其次，在這些局域網(wǎng)之間，應該有外部路由器連接；再次，每個分離的大陸之間應該有至少一條鏈狀線路；再次，在局域網(wǎng)內部，應該還可以包含更小的局域網(wǎng)；再次，互聯(lián)網(wǎng)作為一種典型的復雜網(wǎng)絡，整個網(wǎng)絡拓撲的節(jié)點的重要性程度應該滿足二八定律，互聯(lián)網(wǎng)中應該會有一些比較重要的中心節(jié)點，一般來說度值越大，節(jié)點的重要性也越大，最后，應該有許多互聯(lián)網(wǎng)的服務節(jié)點，這些節(jié)點不是內網(wǎng)節(jié)點，并且相關服務的節(jié)點連接可能會很密切。 1. 互聯(lián)網(wǎng)中的局域邊緣結構 東北大學碩士學位論文 錯誤 !未找到引用源。 3. 互聯(lián)網(wǎng)高核節(jié)點聚類特征 為了便于分析，去掉了互聯(lián)網(wǎng)中核數(shù)為 0 的節(jié)點，即去掉了互 聯(lián)網(wǎng)中的局部區(qū)域結構，圖 便是 1 核網(wǎng)絡集合視圖。 2. 互聯(lián)網(wǎng)中的鏈路特征 在圖 中，可以發(fā)現(xiàn)有很多鏈狀的節(jié)點，這些節(jié)點連接不同的局域網(wǎng)，它們的度值基本上是 2，這些度值為 2 的節(jié)點完全是中轉節(jié)點，這些節(jié)點具有路由來自其它網(wǎng)絡的數(shù)據(jù)包功能。 為了驗證上述的猜想，本文借助 Gephi[34]具對互聯(lián)網(wǎng)拓撲可視化。對于互聯(lián)網(wǎng)拓撲特征進行分析，有效的手段就是對其可視化，在可視化的基礎上通過觀察統(tǒng)計比較等方式來發(fā)現(xiàn)互聯(lián)網(wǎng)的基本特征結構。 東北大學碩士學位論文 錯誤 !未找到引用源。 p (k)表示的是一個隨機節(jié)點的度恰好是 k 的概率， ? ?? ?? ?Pkpk VG?， 其中 ??Pk為度為 k 的節(jié)點數(shù)目， ? ?VG為節(jié)點總數(shù)。如果一個節(jié)點存在于 k核，但在 (k+1)核中被移除，則此節(jié)點的核數(shù)為 k,即對于 v?V(G)，如果 v?corek– corek+1， vCoreness k? 。 12 圖 提取最大子圖算法流程圖 The flow chart of algorithm obtaining biggest subgraph 3. 算法驗證 下面是處理后獲得的最大的子網(wǎng)。 e) 子圖，這一步 算法相對簡單，就是根據(jù)節(jié)點屬性 subgraph 的值來確定每一個子圖節(jié)點的數(shù)目，然后再找出節(jié)點數(shù)最多的子圖即可（當節(jié)點的 subgraph 值相同時，它們就屬于同一個子圖）。 c) 依次遍歷 nodeVector 中的每一個節(jié)點，對于遍歷的當前節(jié)點 currentNode，設置 visited 屬性值為 false， subgraph = subgraphNum ； if 當前節(jié)點 currentNode東北大學碩士學位論文 錯誤 !未找到引用源。算法如下： a) 初始化整個網(wǎng)絡節(jié)點，節(jié)點的屬性 visited 設置為 false，節(jié)點的屬性 subgraph 值為 1, 子圖 個數(shù) subgraphNum = 0 。舉個例子，對于下圖 (a)來說，最大子圖的獲取的結果將是圖 (b)。 10 圖 原始網(wǎng)絡拓撲 Fig Original work topology 最大子圖的獲取 圖 有太多的孤立節(jié)點、孤立邊、孤立區(qū)域，即有太多的分離的子圖，這不利于研究互聯(lián)網(wǎng)的社團結構。這種情況將嚴重影響本文互聯(lián)網(wǎng)社團發(fā)現(xiàn)的研究。 本文在研究社團發(fā)現(xiàn)用的可視化工具 gephi 支持的是一種 XML 文件格式，具體文件內容由節(jié)點和邊組成。如果這個時間過了，它將打印出一系列的 *號表明：在這個路徑上，這個設備不能在給定的時間內發(fā)出 ICMP TTL 到期消息的響應。此時， TTL 變?yōu)?0 了，所以該路由器會將此 datagram 丟掉，并送回一個 ICMP time exceeded 消息（包括發(fā) IP 包的源地址，IP 包的所有內容及路由器的 IP 地址）， traceroute 收到這個消息后，便知道這個路由器存在于這個路徑上，接著 traceroute 再送出另一個 TTL 是 2 的 datagram，發(fā)現(xiàn)第 2 個路由器 ...... traceroute 每次將送出的 datagram 的 TTL 加 1 來發(fā)現(xiàn)另一個路由器，這個重復的動作一直持續(xù)到某個 datagram 抵達目的地。 8 原始網(wǎng)絡數(shù)據(jù)預處理 數(shù)據(jù)格式的處理 1. CAIDA 原始數(shù)據(jù)格式 CAIDA 探測的傳統(tǒng)的數(shù)據(jù)格式不能直接在可視化工具上加以分析，需要轉換格式。其測量范圍的廣泛程度， 就目前而言在主動測量項目中較有優(yōu)勢，此外 CAIDA 測量源點擁有完全自主的控制權與所屬權，可以不間斷地持