復雜網絡拓撲論文范文

本站小編為你精心準備了復雜網絡拓撲論文參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

復雜網絡可視化方案設計的關鍵在于可視化工具和算法的選擇，本文設計的方案中，可視化工具選擇基于Python的軟件包NetworkX[7]，壓縮算法采用提出的一種基于節點和邊的關鍵性壓縮網絡拓撲的算法（NECB，NodeandEdgeCentralityBasedNetworkCompressingAlgorithm），布點算法則選擇基于FDA改進的經典FR算法[8]，整體方案如圖2-1所示。原始的網絡拓撲數據經過NetworkX作圖生成網絡拓撲圖，而NECB算法和FR算法則利用NetworkX通過Python編程實現。

1NetworkX介紹

NetworkX是一基于Python語言開發的網絡可視化工具，集成了眾多專門針對復雜網絡的分析算法，非常適合復雜網絡拓撲的可視化，并能結合其它的Python軟件包，比如Numpy、Scipy、Matplotlib、Pygraphviz、Mayavi2等數據分析和可視化工具進行使用。NetworX支持鄰接矩陣、邊列表、GML、Pajek等多種類型的網絡拓撲數據的讀寫，也可逐個添加或刪除單個節點和邊，同時還提供了大量直接生成某一類型復雜網絡的函數，針對網絡拓撲的性能分析，NetworkX也提供了許多算法，對于同類型的網絡，還支持并集、交集、差、子圖等集合操作。

2NECB壓縮算法

基于節點和邊的拓撲壓縮關鍵在于壓縮標準的制定，如何評判壓縮算法的有效性也是重要的方面。

2.1壓縮節點的選擇NECB壓縮算法中的壓縮是針對節點進行的，這里僅針對簡單無向圖進行討論，對于網絡拓撲G=(V，E)中任意節點v，是否刪除它的參考標準主要有兩點：節點v的度deg(v)和網絡拓撲中經過該點最短路徑數。節點的度是網絡拓撲最重要的屬性之一，如果一個節點的度數越大，說明它與很多節點都有關聯，那么它在網絡拓撲中也就顯得很關鍵[9]。NECB算法采用的計算公式如下。是為了將其值歸一化在[0，1]范圍內。網絡拓撲的平均最短路徑長度也是其重要的屬性之一，如果網絡拓撲中多條最短路徑經過某一節點，顯然該節點扮演著重要角色[9]，NECB算法采用的計算公式如下。用Wpath(v)的值衡量節點v關于最短路徑的關鍵性，Π(s，t)表示網絡拓撲中所有最短路徑的集合，π表示經過節點v的最短路徑，(|V|-1)(|V|-2)/2是經過節點v的最短路徑數最大可能值，乘以2/((|V|-1)(|V|-2))可以將其值歸一化在[0，1]范圍內。

2.2壓縮算法流程NECB算法中的壓縮本質上就是刪除節點，這里對刪除進行一下說明：對于網絡拓撲G=(V，E)，刪除節點v是指從E中刪除所有包含v的邊，然后從V中刪除v生成新的網絡G’，NECB算法流程如圖2-2所示。

首先計算網絡拓撲中各個節點的度和所有節點之間的最短路徑，然后根據公式和分別計算Wdeg(v)和Wpath(v)，刪除值相對較小的次要節點，保留值相對較大的重要節點，再將得到的兩個節點集合并。假設合并后的節點集合為V1，對于復雜網絡，通常情況下，節點集合V1構成的壓縮圖是連通的，若不連通，則需要對壓縮拓撲進行補充，選擇一個最小的節點集合V2補充到壓縮拓撲中，至少使得由V1∪V2中節點構成的壓縮圖是連通的，這是一個NP完全問題，NECB采用的是一種叫做KeepOne的策,。V1中節點在G中的任意一條最短路徑上的所有節點組成V2，V1∪V2的完全圖與原始網絡拓撲G的交集即為最終的壓縮網絡拓撲G’。

作者：張暢謝鈞胡谷雨段偉偉單位：解放軍理工大學，指揮信息系統學院