基于互聯網拓撲特征的多粒度社團發現算法及其可視化_碩士學位畢業論文-資料下載頁

【導讀】本人聲明，所呈交的學位論文是在導師的指導下完成的。或撰寫過的研究成果，也不包括本人為獲得其他學位而使用過的材料。的說明并表示謝意。復印件和磁盤，允許論文被查閱和借閱。本人同意東北大學可以將學。位論文的全部或部分內容編入有關數據庫進行檢索、交流。東北大學碩士學位論文錯誤!系統的社團結構與其功能息息相關，對于Inter社團結構特征的深刻理解，可以。防治互聯網病毒傳播新策略、網絡控制等。域高核數節點相互聚類特征組織，中心節點算法可以探測到Inter中心節點特征組織。內聚低耦合特征的社團，這就是合而聚之。可是要使合并后的網絡的社團模塊度達到最。部最優的模塊度，最終一個具有典型社團結構劃分特征的網絡拓撲浮出水面。的社團發現算法由一組多粒度社團發現算法混合而成，稱之為105算法。據物理類比法，模擬物理系統環境，全自動布局社團節點；其二，在第一步完成之后，由于大規模數據的復雜性以及考慮了突出社團特征等問題，這必將犧牲畫布資源。

　　

【正文】 誤 !未找到引用源。 9 一 般應用程序都不會用的號碼（ 30000 以上），所以當此 UDP datagram 到達目的地后該主機會送回一個 ICMP port unreachable 的消息，而當 traceroute 收到這個消息時，便知道目的地已經到達了。 traceroute 有一個固定的時間等待響應 (ICMP TTL 到期消息 )。如果這個時間過了，它將打印出一系列的 *號表明：在這個路徑上，這個設備不能在給定的時間內發出 ICMP TTL 到期消息的響應。然后， Traceroute 給 TTL 記數器加 1，繼續進行 。 3. 格式轉化 在理解 traceroute 的工作原理后， CAIDA 原始數據格式的意義也將迎刃而解。“ traceroute from sourceIP to targetIP”中的 sourceIP、 targetIP 分別表示源 IP 和目的 IP，而“ *”表示這條探測鏈路上的設備不能及時 地 向源設備返回 ICMP TTL 到期消息的響應。 本文在研究社團發現用的可視化工具 gephi 支持的是一種 XML 文件格式，具體文件內容由節點和邊組成。從 CAIDA 原始數據提出節點和邊的過程相對比較簡單，在此不再累述。 原始網絡拓撲 在獲取 CAIDA 上的互聯網 數據之后，建立網絡拓撲結構，然后對其拓撲結構利用可視化工具 Gephi[34]中的 ForceAtlas2[27]算法可視 化，由圖 可觀察出，網絡中存在著很多孤立的節點和邊。事實上，互聯網網絡拓撲中的任何一節點都不會是處在孤立狀態，但是由于互聯網拓撲結構的復雜性、互聯網網絡協議的復雜性、以及不同區域網絡的不同級別的安全限制等，導致有些節點不會被探測到，有些節點、邊、局部區域處于孤立狀態。這種情況將嚴重影響本文互聯網社團發現的研究。為了后續社團發現研究的方便，需要把網絡中孤立節點和孤立邊以及孤立區域過濾掉。 下一小節將討論處理這種情況的方式。 東北大學碩士學位論文 錯誤 !未找到引用源。 10 圖 原始網絡拓撲 Fig Original work topology 最大子圖的獲取 圖 有太多的孤立節點、孤立邊、孤立區域，即有太多的分離的子圖，這不利于研究互聯網的社團結構。造成網絡拓撲失真的原因則是網絡結構以及協議過于復雜，有些節點對探測包根本就不做任何回應。即使是“失真“的網絡拓撲，依然具有復雜網絡以及英特網的本質特征，不影響對于社團結構的研究。最大子圖的提取采用了廣度優先搜索策略。舉個例子，對于下圖 (a)來說，最大子圖的獲取的結果將是圖 (b)。 （ a） （ b） 圖 獲取最大子圖 Fig obtaining biggest subgraph 下面探討具體的算法實施過程。 1. 算法設計 在網絡拓撲 N 中有 3 個分離子圖 (圖 a)： A（ 2 個節點）， B（ 4 個節點）， C(10 個節點 )。算法目標是提取出最大子圖 C。算法如下： a) 初始化整個網絡節點，節點的屬性 visited 設置為 false，節點的屬性 subgraph 值為 1, 子圖 個數 subgraphNum = 0 。 存儲容 器 nodeVector = null ，nextNodeVector = null。 b) 遍歷網絡中的第一個節點 currentNode,如果 visited==false,設置 visited 屬性值為true， subgraphNum++，然后把節點 currentNode的所有鄰居節點存入 nodeVector。否則遍歷下一個節點直到遍歷當前的節點的 visited==false 才可以進 行下一步。 c) 依次遍歷 nodeVector 中的每一個節點，對于遍歷的當前節點 currentNode，設置 visited 屬性值為 false， subgraph = subgraphNum ； if 當前節點 currentNode東北大學碩士學位論文 錯誤 !未找到引用源。 11 的鄰居節點的 visited ==true,把此鄰居節點加入到 nextNodeVector。 d) 如果 ()==0，遍歷結束。否則 nodeVector = nextNodeVector ，nextNodeVector = null，返回到上一步。 e) 子圖，這一步 算法相對簡單，就是根據節點屬性 subgraph 的值來確定每一個子圖節點的數目，然后再找出節點數最多的子圖即可（當節點的 subgraph 值相同時，它們就屬于同一個子圖）。 2. 算法流程圖 算 法 開 始加 載 原 始 網 絡 拓 撲 數 據 ， 初 始 化 網 絡 節 點 屬 性 ， v i s i t e d = f a l s e , s u b g r a p h = 1 , s u b g r a p h N u m = 0遍 歷 網 絡 中 第 一 個 節 點 N ， i f v i s i t e d = f a l s e , v i s i t e d = t r u e , s u b g r a p h N u m + + , 把 節 點 N 的 所 有鄰 居 節 點 存 入 n o d e V e c t o r 。 e l s e 遍 歷 下 一 次 節 點 。 直 到 v i s i t e d = = f a l s ec u r r e n t N o d e 的 鄰 居節 點 是 否 遍 歷 完依 次 遍 歷 n o d e V e c t o r 中 的 每 一 個 節 點 c u r r e n t N o d e ， v i s i t e d = f a l s e , s u b g r a p h = s u b g r a p h N u mI f c u r r e n t N o d e的 鄰 居 節 點 屬 性 v i s i t e d為 t r u e把 此 鄰 居 節 點 加 入 到 n e x t N o d e V e c t o r遍 歷 c u r r e n t N o d e 的 下 一 個 鄰 居 節 點n e x t N o d e , c u r r e n t N o d e = n e x t N o d e是否否是n o d e V e c t o r 中 的 節 點 是 否 遍 歷 完n o d e V e c t o r = n e x t N o d e V e c t o r n e x t N o d e V e c t o r = n u l lI f n e x t N o d e V e c t o r . s i z e ( ) = = 0否是網 絡 中 所 有 節 點 的v i s i t e d 是 否 全 部 為 t r u e否是尋 找 最 大 的 子 圖 ， 這 一 步 算 法 相 對 簡 單 ， 就 是 根 據 節 點屬 性 s u b g r a p h 的 值 來 確 定 每 一 個 子 圖 節 點 的 數 目 ， 然 后再 找 出 節 點 數 最 多 的 子 圖 即 可 （ 當 節 點 的 s u b g r a p h 值 相同 時 ， 它 們 就 屬 于 同 一 個 子 圖 ）算 法 結 束否東北大學碩士學位論文 錯誤 !未找到引用源。 12 圖 提取最大子圖算法流程圖 The flow chart of algorithm obtaining biggest subgraph 3. 算法驗證 下面是處理后獲得的最大的子網。在圖 中，可以看出，那些之前分布在邊緣的分離節點和邊以及被過濾 掉，這也證明了最大連通子圖的獲取算法是正確有效的。后面關于互聯網社團發現的研究將圍繞這個最大子網展開，為方便起見，這個子網命名為studyedNet。 圖 最大子圖 Fig biggest subgraph 相關特征量 定義 k核： 拓撲圖的 k核是指“在圖中反復去掉度小于等于 k 的節點及其連接所余下的子圖”。如果一個節點存在于 k核，但在 (k+1)核中被移除，則此節點的核數為 k,即對于 v?V(G)，如果 v?corek– corek+1， vCoreness k? 。 核數表示的是節點在核中的深度， k 值越大意味著該核在拓撲圖中位置更為核心。可以通過 k核解析由外層至內層一層一層地解析網絡，直到最內層為止，從而揭示網絡的層次結構性質。 定義 度分布： 度分布 (Degree Distribution)是指圖 G(V， E)中所有節點的度的分布情況，可用分布函數 p(k)來描述。 p (k)表示的是一個隨機節點的度恰好是 k 的概率， ? ?? ?? ?Pkpk VG?， 其中 ??Pk為度為 k 的節點數目， ? ?VG為節點總數。 東北大學碩士學位論文 錯誤 !未找到引用源。 13 本章小結 本章主要介紹了后續研究用到的互聯網拓撲數據來源以及原始數據的預處理過程，最后還介紹了下文涉及到的一些基本特征量的概念。在本章的基礎上，接下來一章將進行基于互聯網拓撲特征的多粒度社團發現研究。 東北大學碩士學位論文 錯誤 !未找到引用源。 14 第 3 章 互聯網拓撲基本特征分析與多粒度社團發現算法設計 本章主要針對互聯網特有的基本拓撲特征展開分析，并設計了一組探測算法（ 總稱105 算法）可以分 別探測這些基本的拓撲結構，之后評價了本文提出的社團發現算法；為了考驗算法的普適性，在其它網絡上做了驗證；最后探討了社團劃分的新思路。 互聯網拓撲基本 特征分析 互聯網作為一種典型的復雜網絡，它的拓撲特征必定有復雜網絡的特征。本文將用復雜網絡的理論分析互聯網的拓撲特征結構。對于互聯網拓撲特征進行分析，有效的手段就是對其可視化，在可視化的基礎上通過觀察統計比較等方式來發現互聯網的基本特征結構。在用可視化的手段分析前，先根據互聯網的網絡協議做一個實際互聯網結構的猜想。 首先，互聯網的結構應該是非均質的，有許 許多多的局域網組成；其次，在這些局域網之間，應該有外部路由器連接；再次，每個分離的大陸之間應該有至少一條鏈狀線路；再次，在局域網內部，應該還可以包含更小的局域網；再次，互聯網作為一種典型的復雜網絡，整個網絡拓撲的節點的重要性程度應該滿足二八定律，互聯網中應該會有一些比較重要的中心節點，一般來說度值越大，節點的重要性也越大，最后，應該有許多互聯網的服務節點，這些節點不是內網節點，并且相關服務的節點連接可能會很密切。整體上，根據復雜網絡理論，互聯網的結構應該具有分形特征。 為了驗證上述的猜想，本文借助 Gephi[34]具對互聯網拓撲可視化。為了節省篇幅，只截取相關的局部圖形加以說明驗證。 1. 互聯網中的局域邊緣結構 東北大學碩士學位論文 錯誤 !未找到引用源。 15 圖 真實互聯網局部結構 Fig . local structure of real Inter 縱觀整個網絡拓撲，其中包含了大大小小的許多類似上圖的局部聚集結構，最小的結構只包含幾個節點，最大的則包含數百個節點，在這些高度聚集的局部結構之間稀稀疏疏的連接一些中間節點，節點度分布很不均勻，有很多度值較小的節點，但也有度值較大的 Hub 節點，這些 Hub 節點實際上可能是連接外網的路由 節點，從圖 可看出，這些 Hub 節點都有一條或幾條鏈路與其它局部區域相連接，節點度分布直觀上出現了具有無尺度特征的長尾現象，這樣的特征是典型的互聯網局域網結構特征。 2. 互聯網中的鏈路特征 在圖 中，可以發現有很多鏈狀的節點，這些節點連接不同的局域網，它們的度值基本上是 2，這些度值為 2 的節點完全是中轉節點，這些節點具有路由來自其它網絡的數據包功能。這些鏈狀節點大都是 BGP 外部路由器，當然也有可能是一個大的局域網內部的路由鏈路。 3. 互聯網高核節點聚類特征 為了便于分析，去掉了互聯網中核數為 0 的節點，即去掉了互 聯網中的局部區域結構，圖 便是 1 核網絡集合視圖。從圖中看出，網絡中的一些高核節點出現聚類現象，這種聚類節點應該是