美章網 資料文庫 復雜網絡拓撲論文范文

復雜網絡拓撲論文范文

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

復雜網絡拓撲論文

復雜網絡可視化方案設計的關鍵在于可視化工具和算法的選擇,本文設計的方案中,可視化工具選擇基于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’。

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

主站蜘蛛池模板: 精品无码AV一区二区三区不卡| jjzz亚洲亚洲女人| 欧美日韩第一页| 午夜精品一区二区三区在线观看| www.羞羞视频| 天堂а√在线中文在线| 中文字幕视频网| 果冻传媒国产电影免费看| 亚洲色成人网一二三区| 色偷偷的xxxx8888| 国产男女猛烈无遮挡免费视频网站| 99这里只有精品| 成人妇女免费播放久久久| 久久综合九色综合欧洲| 欧美精品久久一区二区三区 | 波多野结衣在线观看免费区| 咪咪色在线视频| 香蕉视频一区二区三区| 国产精品单位女同事在线| www.91久久| 操动漫美女视频| 北条麻妃在线一区二区| 里番acg全彩| 国产成人福利精品视频| 香蕉视频污在线观看| 国内精品久久久久久久影视麻豆| tube人妖多泄精妖精| 成人免费无码大片A毛片抽搐| 久久久久亚洲av无码专区| 日韩人妻一区二区三区蜜桃视频 | 亚洲乱码无码永久不卡在线| 欧美精品黑人粗大| 亚洲韩国在线一卡二卡| 真实国产乱子伦久久| 午夜成人无码福利免费视频| 色依依视频视频在线观看| 国产乡下三级全黄三级| 风间由美性色一区二区三区| 国产成人在线观看网站| 国产在线a免费观看| 国产激情视频一区二区三区|