復(fù)雜網(wǎng)絡(luò)拓?fù)湔撐姆段?/h1>
本站小編為你精心準(zhǔn)備了復(fù)雜網(wǎng)絡(luò)拓?fù)湔撐膮⒖挤段模高@些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。
復(fù)雜網(wǎng)絡(luò)可視化方案設(shè)計(jì)的關(guān)鍵在于可視化工具和算法的選擇，本文設(shè)計(jì)的方案中，可視化工具選擇基于Python的軟件包NetworkX[7]，壓縮算法采用提出的一種基于節(jié)點(diǎn)和邊的關(guān)鍵性壓縮網(wǎng)絡(luò)拓?fù)?/a>的算法（NECB，NodeandEdgeCentralityBasedNetworkCompressingAlgorithm），布點(diǎn)算法則選擇基于FDA改進(jìn)的經(jīng)典FR算法[8]，整體方案如圖2-1所示。原始的網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)經(jīng)過(guò)NetworkX作圖生成網(wǎng)絡(luò)拓?fù)鋱D，而NECB算法和FR算法則利用NetworkX通過(guò)Python編程實(shí)現(xiàn)。
1NetworkX介紹
NetworkX是一基于Python語(yǔ)言開(kāi)發(fā)的網(wǎng)絡(luò)可視化工具，集成了眾多專門針對(duì)復(fù)雜網(wǎng)絡(luò)的分析算法，非常適合復(fù)雜網(wǎng)絡(luò)拓?fù)涞目梢暬⒛芙Y(jié)合其它的Python軟件包，比如Numpy、Scipy、Matplotlib、Pygraphviz、Mayavi2等數(shù)據(jù)分析和可視化工具進(jìn)行使用。NetworX支持鄰接矩陣、邊列表、GML、Pajek等多種類型的網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)的讀寫，也可逐個(gè)添加或刪除單個(gè)節(jié)點(diǎn)和邊，同時(shí)還提供了大量直接生成某一類型復(fù)雜網(wǎng)絡(luò)的函數(shù)，針對(duì)網(wǎng)絡(luò)拓?fù)涞男阅芊治觯琋etworkX也提供了許多算法，對(duì)于同類型的網(wǎng)絡(luò)，還支持并集、交集、差、子圖等集合操作。
2NECB壓縮算法
基于節(jié)點(diǎn)和邊的拓?fù)鋲嚎s關(guān)鍵在于壓縮標(biāo)準(zhǔn)的制定，如何評(píng)判壓縮算法的有效性也是重要的方面。
2.1壓縮節(jié)點(diǎn)的選擇NECB壓縮算法中的壓縮是針對(duì)節(jié)點(diǎn)進(jìn)行的，這里僅針對(duì)簡(jiǎn)單無(wú)向圖進(jìn)行討論，對(duì)于網(wǎng)絡(luò)拓?fù)銰=(V，E)中任意節(jié)點(diǎn)v，是否刪除它的參考標(biāo)準(zhǔn)主要有兩點(diǎn)：節(jié)點(diǎn)v的度deg(v)和網(wǎng)絡(luò)拓?fù)渲薪?jīng)過(guò)該點(diǎn)最短路徑數(shù)。節(jié)點(diǎn)的度是網(wǎng)絡(luò)拓?fù)渥钪匾膶傩灾唬绻粋€(gè)節(jié)點(diǎn)的度數(shù)越大，說(shuō)明它與很多節(jié)點(diǎn)都有關(guān)聯(lián)，那么它在網(wǎng)絡(luò)拓?fù)渲幸簿惋@得很關(guān)鍵[9]。NECB算法采用的計(jì)算公式如下。是為了將其值歸一化在[0，1]范圍內(nèi)。網(wǎng)絡(luò)拓?fù)涞钠骄疃搪窂介L(zhǎng)度也是其重要的屬性之一，如果網(wǎng)絡(luò)拓?fù)渲卸鄺l最短路徑經(jīng)過(guò)某一節(jié)點(diǎn)，顯然該節(jié)點(diǎn)扮演著重要角色[9]，NECB算法采用的計(jì)算公式如下。用Wpath(v)的值衡量節(jié)點(diǎn)v關(guān)于最短路徑的關(guān)鍵性，Π(s，t)表示網(wǎng)絡(luò)拓?fù)渲兴凶疃搪窂降募希斜硎窘?jīng)過(guò)節(jié)點(diǎn)v的最短路徑，(|V|-1)(|V|-2)/2是經(jīng)過(guò)節(jié)點(diǎn)v的最短路徑數(shù)最大可能值，乘以2/((|V|-1)(|V|-2))可以將其值歸一化在[0，1]范圍內(nèi)。
2.2壓縮算法流程N(yùn)ECB算法中的壓縮本質(zhì)上就是刪除節(jié)點(diǎn)，這里對(duì)刪除進(jìn)行一下說(shuō)明：對(duì)于網(wǎng)絡(luò)拓?fù)銰=(V，E)，刪除節(jié)點(diǎn)v是指從E中刪除所有包含v的邊，然后從V中刪除v生成新的網(wǎng)絡(luò)G’，NECB算法流程如圖2-2所示。
首先計(jì)算網(wǎng)絡(luò)拓?fù)渲懈鱾€(gè)節(jié)點(diǎn)的度和所有節(jié)點(diǎn)之間的最短路徑，然后根據(jù)公式和分別計(jì)算Wdeg(v)和Wpath(v)，刪除值相對(duì)較小的次要節(jié)點(diǎn)，保留值相對(duì)較大的重要節(jié)點(diǎn)，再將得到的兩個(gè)節(jié)點(diǎn)集合并。假設(shè)合并后的節(jié)點(diǎn)集合為V1，對(duì)于復(fù)雜網(wǎng)絡(luò)，通常情況下，節(jié)點(diǎn)集合V1構(gòu)成的壓縮圖是連通的，若不連通，則需要對(duì)壓縮拓?fù)溥M(jìn)行補(bǔ)充，選擇一個(gè)最小的節(jié)點(diǎn)集合V2補(bǔ)充到壓縮拓?fù)渲校辽偈沟糜蒝1∪V2中節(jié)點(diǎn)構(gòu)成的壓縮圖是連通的，這是一個(gè)NP完全問(wèn)題，NECB采用的是一種叫做KeepOne的策,。V1中節(jié)點(diǎn)在G中的任意一條最短路徑上的所有節(jié)點(diǎn)組成V2，V1∪V2的完全圖與原始網(wǎng)絡(luò)拓?fù)銰的交集即為最終的壓縮網(wǎng)絡(luò)拓?fù)銰’。
作者：張暢謝鈞胡谷雨段偉偉單位：解放軍理工大學(xué)，指揮信息系統(tǒng)學(xué)院
