【文章內(nèi)容簡介】 成熟，可是針對以互聯(lián)網(wǎng)拓撲特征為基礎(chǔ)的社團結(jié)構(gòu)研究還相對不足，傳統(tǒng)社團發(fā)現(xiàn)算法并不能很好的反映互聯(lián)網(wǎng)特有的拓撲特征。本文提取CAIDA上的互聯(lián)網(wǎng)拓撲數(shù)據(jù)，建立互聯(lián)網(wǎng)拓撲，并利用經(jīng)典可視化算法forceAtlas2[27]對互聯(lián)網(wǎng)拓撲結(jié)構(gòu)可視化，發(fā)現(xiàn)了互聯(lián)網(wǎng)特有的一些拓撲特征，如邊緣局部特征（類樹狀結(jié)構(gòu)）、鏈狀結(jié)構(gòu)特征、局部區(qū)域高核數(shù)節(jié)點相互聚類特征、中心節(jié)點特征等，這些特殊的結(jié)構(gòu)特征并不是偶然形成的，而是有著很強的規(guī)律性的，比如類樹狀結(jié)構(gòu)就是一個真實的局域網(wǎng)絡(luò)的結(jié)構(gòu)，鏈狀結(jié)構(gòu)特征則說明這是一條網(wǎng)絡(luò)專線或者是BGP的外部路由線路等，局部區(qū)域高核數(shù)節(jié)點相互聚類特征則是由互聯(lián)網(wǎng)的非均質(zhì)性和混沌性所引起（后面會詳細解釋），而中心節(jié)點特征則說明網(wǎng)絡(luò)中存在一些重要的節(jié)點。如果能設(shè)計一種針對這些特有的互聯(lián)網(wǎng)的拓撲特征探測算法，那么將對互聯(lián)網(wǎng)的社團研究提供幫助。如今，許多科學(xué)研究者都開始應(yīng)用復(fù)雜網(wǎng)絡(luò)理論和數(shù)據(jù)挖掘方法去分析各種現(xiàn)象，解決實際的問題。雖然各個學(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é)論。在整個研究過程中，僅系統(tǒng)建模的步驟只需要數(shù)學(xué)理論和相關(guān)的領(lǐng)域知識，而其它步驟如:對網(wǎng)絡(luò)進行算法分析和對網(wǎng)絡(luò)結(jié)構(gòu)進行可視化展示等，都需要計算機軟件的輔助來完成。然而，在不同學(xué)科的研究過程中，很多學(xué)科專家對計算機工具的開發(fā)并不熟悉，從而無法集中精力來解決其領(lǐng)域問題，影響了他們的研究進程和效果。因此復(fù)雜網(wǎng)絡(luò)的可視化對于處理大規(guī)模關(guān)系數(shù)據(jù)的科研學(xué)者們來說至關(guān)重要?；ヂ?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)和功能有深刻了解。對互聯(lián)網(wǎng)拓撲結(jié)構(gòu)中的社團特征的可視化研究在很多方面都有著重要意義，比如，簡化整個網(wǎng)絡(luò)拓撲，幫助人們理解網(wǎng)絡(luò)的整個拓撲架構(gòu)，社團還以映射具體的地理位置，使各地的互聯(lián)網(wǎng)的發(fā)展普及情況一目了然。 本文組織結(jié)構(gòu)本文共分為五章，各章的主要內(nèi)容如下：第一章為緒論，介紹了互聯(lián)網(wǎng)的社團結(jié)構(gòu)研究以及可視化研究的現(xiàn)狀，論述了互聯(lián)網(wǎng)的社團結(jié)構(gòu)研究以及可視化研究的重要意義。第二章介紹了互聯(lián)網(wǎng)拓撲數(shù)據(jù)的來源，以及數(shù)據(jù)的預(yù)處理過程，并且還簡單介紹了后續(xù)論文用到了一些特征量的含義。第三章介紹了互聯(lián)網(wǎng)拓撲基本特征分析與多粒度社團發(fā)現(xiàn)算法設(shè)計，在本章中，著重分析了互聯(lián)網(wǎng)拓撲中基本的拓撲特征結(jié)構(gòu)，并且提出了探測每種拓撲結(jié)構(gòu)的算法，最后對算法做了驗證。第四章介紹了傳統(tǒng)的一些可視化布局算法，并提出了新的面向社團的網(wǎng)絡(luò)拓撲可視化算法visualCommunity。visualCommunity在可視化網(wǎng)絡(luò)拓撲時分為三步：第一步，模擬物理系統(tǒng)環(huán)境，全自動布局社團節(jié)點；第二步，采用動態(tài)交互模式，手動調(diào)整社團節(jié)點位置；第三步，采用射線布局模式，可視化社團節(jié)點內(nèi)部的拓撲結(jié)構(gòu)。第五章是本文的總結(jié)與展望。68東北大學(xué)碩士學(xué)位論文 Error! Reference source not found. 第2章 互聯(lián)網(wǎng)網(wǎng)絡(luò)數(shù)據(jù)來源及處理互聯(lián)網(wǎng)是一個分層設(shè)計的網(wǎng)絡(luò)，Internet中的計算機在物理層面上基于物理連接關(guān)系可以構(gòu)成一種拓撲，而在應(yīng)用層面上還可以構(gòu)成應(yīng)用層拓撲，比如在P2P應(yīng)用中，peer[28,29]之間構(gòu)成的拓撲。目前所討論較多的Internet拓撲有三種：IP級拓撲[30,31]、路由級拓撲和自治域級拓撲。定義 IP級拓撲：traceroute機制測量得到的選路路徑是IP地址級的路徑，除最后一跳之外，其它地址各對應(yīng)一個路由器接口地址。直接從IP級路徑生成的拓撲圖稱為IP級拓撲[31]圖，其中一個節(jié)點代表一個IP地址。 路由級拓撲：指互聯(lián)網(wǎng)中的路由器基于互聯(lián)關(guān)系而構(gòu)成的一種拓撲。圖中的節(jié)點指代的是一個路由器，而邊則表示兩個路由器之間存在著直接的連接關(guān)系。而由于實際物理線路比較難于測量，當(dāng)前的Internet路由器級拓撲數(shù)據(jù)的獲得通?；趖raceroute類的工具。 自治域級拓撲：表示Internet中各個獨立的自治域之間的互聯(lián)關(guān)系，這里的一個節(jié)點表示Internet中的一個自治域（Autonomous System），而圖中的邊則代表兩個自治域之間通過BGP[32, 33]邊界網(wǎng)關(guān)協(xié)議存在著互聯(lián)關(guān)系，兩個自治域之間有一條邊。自治域級拓撲又稱AS級拓撲。本文研究社團發(fā)現(xiàn)選用的是IP級拓撲。 互聯(lián)網(wǎng)網(wǎng)絡(luò)數(shù)據(jù)來源目前針對互聯(lián)網(wǎng)探測數(shù)據(jù)有多種來源，本文使用的是CAIDA（The Cooperative Association for Internet Data Analysis，一個對全球范圍Internet結(jié)構(gòu)及數(shù)據(jù)進行研究的國際合作機構(gòu)）提供的探測數(shù)據(jù)。CAIDA是互聯(lián)網(wǎng)拓撲分析研究領(lǐng)域中一個具有代表性和影響力的大型科研項目。CAIDA的探測架構(gòu)是Ark（Archipelago）架構(gòu)，這是一種分布式測量方式，通過元組空間實現(xiàn)各個探測節(jié)點之間的通信，可實現(xiàn)探測源點之間的協(xié)作測量。目前探測節(jié)點主要分布在北美洲、歐洲眾多國家的研究院所、高校、軍事機構(gòu)中，而亞洲、大洋洲、南美洲、非洲分布較少。東北大學(xué)經(jīng)過該組織授權(quán)建立CAIDA中國第一節(jié)點(Neu Node, she)，成為該組織在中國地區(qū)的首個合作者。 Ark探測源點在全球的分布 The distribution of Ark monitors in the worldArk項目迄今的活動節(jié)點共54個，其中亞洲5個。 Ark位于亞洲的監(jiān)測點 Ark monitors in AsiaNameCityCountryContinentOrganizationOrganization classificationcjjkrDaejeonKRAsiaKREONet1research networkmnlphQuezon CityPHAsiaASTIresearchnrtjpTokyoJPAsiaAPANresearch networksheShenyangCNAsiaNortheastern UniversityuniversitytpetwHsinchuTWAsiaTWARENresearch networkCAIDA的測量源點分布在世界幾大洲內(nèi)，從不同的視角對互聯(lián)網(wǎng)拓撲結(jié)構(gòu)進行全面的測量與分析。其測量范圍的廣泛程度，就目前而言在主動測量項目中較有優(yōu)勢，此外CAIDA 測量源點擁有完全自主的控制權(quán)與所屬權(quán)，可以不間斷地持續(xù)測量而不受影響，其測量結(jié)果的數(shù)據(jù)量十分可觀，有效性也能得到保障。作為Ark項目的成員，Neu節(jié)點不僅自身采集互聯(lián)網(wǎng)拓撲數(shù)據(jù)，還可以以合作者的身份，獲得CAIDA遍布全球眾多測量源點所提供的海量的、更新及時的數(shù)據(jù)。為了清晰簡單的分析互聯(lián)網(wǎng)拓撲結(jié)構(gòu)，本文選取的是2011年9月29號CAIDA全球所有站點探測到的合并的數(shù)據(jù)。 原始網(wǎng)絡(luò)數(shù)據(jù)預(yù)處理 數(shù)據(jù)格式的處理1. CAIDA原始數(shù)據(jù)格式CAIDA探測的傳統(tǒng)的數(shù)據(jù)格式不能直接在可視化工具上加以分析，需要轉(zhuǎn)換格式。CAIDA利用traceroute原始的數(shù)據(jù)格式如下：traceroute from to 1 ms 2 ms 3 ms 4 mstraceroute from to 1 ms 2 ms3 *4 *5 ms6 ms2. traceroute的工作原理如果要正確的解析CAIDA原始數(shù)據(jù)格式，必須要深刻理解traceroute的工作原理。traceroute程序的設(shè)計是利用ICMP及IP header的TTL（Time To Live）欄位（field）。首先，traceroute送出一個TTL是1的IP datagram（其實，每次送出的為3個40字節(jié)的包，包括源地址，目的地址和包發(fā)出的時間標(biāo)簽）到目的地，當(dāng)路徑上的第一個路由器（router）收到這個datagram時，它將TTL減1。此時，TTL變?yōu)?了，所以該路由器會將此datagram丟掉，并送回一個ICMP time exceeded消息（包括發(fā)IP包的源地址，IP包的所有內(nèi)容及路由器的IP地址），traceroute 收到這個消息后，便知道這個路由器存在于這個路徑上，接著traceroute 再送出另一個TTL是2 的datagram，發(fā)現(xiàn)第2 個路由器...... traceroute 每次將送出的datagram的TTL 加1來發(fā)現(xiàn)另一個路由器，這個重復(fù)的動作一直持續(xù)到某個datagram 抵達目的地。當(dāng)datagram到達目的地后，該主機并不會送回ICMP time exceeded消息，因為它已是目的地了，那么traceroute如何得知目的地到達了呢？ traceroute在送出UDP datagrams到目的地時，它所選擇送達的port number 是一個一般應(yīng)用程序都不會用的號碼（30000 以上），所以當(dāng)此UDP datagram 到達目的地后該主機會送回一個ICMP port unreachable的消息，而當(dāng)traceroute 收到這個消息時，便知道目的地已經(jīng)到達了。 traceroute 有一個固定的時間等待響應(yīng)(ICMP TTL到期消息)。如果這個時間過了，它將打印出一系列的*號表明：在這個路徑上，這個設(shè)備不能在給定的時間內(nèi)發(fā)出ICMP TTL到期消息的響應(yīng)。然后，Traceroute給TTL記數(shù)器加1，繼續(xù)進行。3. 格式轉(zhuǎn)化在理解traceroute的工作原理后，CAIDA原始數(shù)據(jù)格式的意義也將迎刃而解。“traceroute from sourceIP to targetIP”中的sourceIP、targetIP分別表示源IP和目的IP，而“*”表示這條探測鏈路上的設(shè)備不能及時地向源設(shè)備返回ICMP TTL到期消息的響應(yīng)。本文在研究社團發(fā)現(xiàn)用的可視化工具gephi支持的是一種XML文件格式，具體文件內(nèi)容由節(jié)點和邊組成。從CAIDA原始數(shù)據(jù)提出節(jié)點和邊的過程相對比較簡單，在此不再累述。 原始網(wǎng)絡(luò)拓撲在獲取CAIDA上的互聯(lián)網(wǎng)數(shù)據(jù)之后，建立網(wǎng)絡(luò)拓撲結(jié)構(gòu)，然后對其拓撲結(jié)構(gòu)利用可視化工具Gephi[34]中的 ForceAtlas2[27]算法可視化，網(wǎng)絡(luò)中存在著很多孤立的節(jié)點和邊。事實上，互聯(lián)網(wǎng)網(wǎng)絡(luò)拓撲中的任何一節(jié)點都不會是處在孤立狀態(tài)，但是由于互聯(lián)網(wǎng)拓撲結(jié)構(gòu)的復(fù)雜性、互聯(lián)網(wǎng)網(wǎng)絡(luò)協(xié)議的復(fù)雜性、以及不同區(qū)域網(wǎng)絡(luò)的不同級別的安全限制等，導(dǎo)致有些節(jié)點不會被探測到，有些節(jié)點、邊、局部區(qū)域處于孤立狀態(tài)。這種情況將嚴(yán)重影響本文互聯(lián)網(wǎng)社團發(fā)現(xiàn)的研究。為了后續(xù)社團發(fā)現(xiàn)研究的方便，需要把網(wǎng)絡(luò)中孤立節(jié)點和孤立邊以及孤立區(qū)域過濾掉。下一小節(jié)將討論處理這種情況的方式。 圖 原始網(wǎng)絡(luò)拓撲 Fig Original network topology 最大子圖的獲取圖 、孤立邊、孤立區(qū)域，即有太多的分離的子圖，這不利于研究互聯(lián)網(wǎng)的社團結(jié)構(gòu)。造成網(wǎng)絡(luò)拓撲失真的原因則是網(wǎng)絡(luò)結(jié)構(gòu)以及協(xié)議過于復(fù)雜，有些節(jié)點對探測包根本就不做任何回應(yīng)。即使是“失真“的網(wǎng)絡(luò)拓撲，依然具有復(fù)雜網(wǎng)絡(luò)以及英特網(wǎng)的本質(zhì)特征，不影響對于社團結(jié)構(gòu)的研究。最大子圖的提取采用了廣度優(yōu)先搜索策略。舉個例子，(a)來說，(b)。 （a） （b） 圖 獲取最大子圖Fig obtaining biggest subgraph 下面探討具體的算法實施過程。1. 算法設(shè)計在網(wǎng)絡(luò)拓撲N中有3個分離子圖(圖a)：A（2個節(jié)點），B（4個節(jié)點），C(10個節(jié)點)。算法目標(biāo)是提取出最大子圖C。算法如下：a) 初始化整個網(wǎng)絡(luò)節(jié)點，節(jié)點的屬性visited設(shè)置為false，節(jié)點的屬性 subgraph 值為1,子圖個數(shù)subgraphNum = 0 。 存儲容器nodeVector = null，nextNodeVector = null。b) 遍歷網(wǎng)絡(luò)中的第一個節(jié)點currentNode,如果visited==false,設(shè)置visited屬性值為true，subgraphNum++，然后把節(jié)點currentNode的所有鄰居節(jié)點存入nodeVector。否則遍歷下一個節(jié)點直到遍歷當(dāng)前的節(jié)點的visited==false才可以進行下一步。c) 依次遍歷nodeVector中的每一個節(jié)點，對于遍歷的當(dāng)前節(jié)點currentNode，設(shè)置visited屬性值為false， subgraph = subgraphNum ；if當(dāng)前節(jié)點currentNode的鄰居節(jié)點的visited ==true,把此鄰居節(jié)點加入到nextNodeVector。d) ()==0，遍歷結(jié)束。否則nodeVector = nextNodeVector ，nextNodeVector = null，返回到上一步。 e) 子圖，這一步算法相對簡單，就是根據(jù)節(jié)點屬性subgraph的值來確定每一個子圖節(jié)點的數(shù)目，然后再找出節(jié)點數(shù)最多的子圖即可（當(dāng)節(jié)點的subgraph值相同時，它們就屬于同一個子圖）。2. 算法流程圖 The flow chart of algorithm obtaining biggest subgraph3. 算法驗證下面是處理后獲得的最大的子網(wǎng)。在圖 ，可以看出，那些之前分布在邊緣的分離