基于Web 的復雜網絡可視化仿真平臺VPCN 的設計與實現?

王月明 張 琨 張佳慧 蔡 穎 麻孟越

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

復雜網絡［1］是指具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質的網絡［2］。復雜網絡科學研究的是各不相同的復雜網絡之間的共性和處理它們的普適方法，利用分析實際網絡過程中產生的共性的概念、方法和理論，可以反過來為各種實際網絡的分析與設計提供宏觀指導和具體手段。復雜網絡可視化仿真平臺將成為研究復雜網絡的基礎和必不可少的重要工具，仿真平臺的設計與實現已成為復雜網絡研究的熱點?，F如今，國外知名的復雜網絡可視化仿真平臺包括Cytoscape、Netdraw、Matlab、Pajek 等［3］，為我國研究學者研究復雜網絡帶來了新的思維和良好的支持［4］。但是這些平臺具有一定的應用背景，源代碼不開放，二次開發(fā)難度較大，且大部分是基于單機版本，運行效率低，不能較好地處理大規(guī)模復雜網絡的參數計算和特性分析。因此，本文基于Web 技術，自主設計和實現了一個復雜網絡可視化仿真平臺，并通過實際應用，驗證了平臺的有效性和可靠性。

2 傳統(tǒng)復雜網絡可視化與基于Web的復雜網絡可視化研究概述

2.1 傳統(tǒng)的復雜網絡可視化技術

傳統(tǒng)的復雜網絡可視化平臺［5］使用如VC++、Java等編程語言中的圖形繪制庫，在程序窗體之中調用圖形繪制函數分別繪制網絡點和線來實現網絡可視化。關于圖形繪制庫，在VC++中常常使用CGraph，在 Java 中則是 Graphics2D，兩者的思路都是在窗體類創(chuàng)建的窗體內部繪制網絡圖形，并在窗體的文本顯示區(qū)域輸出運行結果。

經過長時間的VC++、Java 復雜網絡平臺的使用和對平臺代碼的調試，發(fā)現傳統(tǒng)復雜網絡可視化的效果受圖形繪制庫的性能影響很大，在網站規(guī)格較大的時候顯示會有一定延遲。而且由于編程語言的特點，調用圖形繪制函數的代碼往往和正常的網絡參數計算代碼交叉在一起影響識別，增加了圖形顯示的工作量，影響了基于復雜網絡的可視化顯示。

2.2 基于Web的復雜網絡可視化技術

基于Web 的復雜網絡可視化仿真平臺的核心在于利用具有開放式接口的Web圖形顯示服務，來為復雜網絡可視化提供有效支持。

在數據運算方面，基于Web的復雜網絡可視化仿真平臺使用了J2EE技術為Web界面提供數據支持。利用Java 的多種技術實現數據處理算法的區(qū)分和插件式管理，對應于Web界面的每類功能能夠有對應的功能模塊處理相關數據。

為加速數據處理算法的運算，本平臺將計算規(guī)模擴大，使用Spark集群，采用了一種適用于網絡參數計算的高效并行作業(yè)執(zhí)行框架。網絡參數計算作業(yè)提交后，根據各個節(jié)點的狀態(tài)，作業(yè)調度器將網絡參數計算任務分割并提交到空閑節(jié)點上并行執(zhí)行。

3 基于Web 的復雜網絡可視化仿真平臺（VPCN）的設計

3.1 總體設計框架

本平臺支持真實拓撲、典型網絡拓撲的自動導入和網絡拓撲的生成［6］，支持對網絡拓撲的動態(tài)調整和關鍵節(jié)點的識別與顯示，支持網絡度分布、聚集系數、中介中心性、節(jié)點中心度、網絡直徑、網絡最短路徑參數等拓撲屬性參數［7］的計算，網絡拓撲規(guī)模最大可支持6500 個節(jié)點，并能夠根據屬性參數自動挖掘關鍵節(jié)點。本平臺總體設計框架如圖1所示。

圖1 VPCN總體設計框架

3.2 功能模塊

VPCN 的功能模塊如圖2 所示，具體包括四大功能模塊:復雜網絡生成導入模塊、復雜網絡調整模塊、復雜網絡參數計算模塊和仿真結果表現模塊。

圖2 VPCN功能模塊

1）復雜網絡生成導入模塊:復雜網絡生成導入模塊在VPCN 仿真平臺啟動后，用于為整個復雜網絡仿真進行網絡數據生成和導入，包括經典隨機網絡生成和真實交通網絡導入。

2）復雜網絡調整模塊:復雜網絡調整模塊是在復雜網絡生成或導入后對復雜網絡點和邊進行調整的模塊，用于為復雜網絡仿真的細節(jié)更改提供可視化支持。

3）復雜網絡參數計算模塊:復雜網絡參數計算模塊負責計算復雜網絡的各種參數，在實現時具體分為兩類參數。一類是復雜網絡基本參數，包括度分布、網絡直徑、網絡最短路徑、中介中心性等；另一類是一些用于復雜網絡及節(jié)點重要性、演化等內容研究所設計的擴展參數，包括節(jié)點中心度、聚集系數、最大鄰居連通度、最大鄰居連通密度、聚集系數等。

4）仿真結果展示模塊:仿真結果展示模塊是對整個仿真平臺輸出結果表現方式的確定，目前采用了兩種輸出方式表現整個仿真結果。

（1）將結果輸出至指定的文件:這種表現方式是將一些計算的參數結果和仿真過程中的信息保存至指定的文件，便于用戶的研究分析和事后處理；

（2）在可視化圖形界面表現結果:在仿真結束后，可在復雜網絡拓撲窗口中直接顯示一些結構，例如，標出重要節(jié)點、顯示網絡結構信息等，給用戶一種直觀的效果。

4 基于Web 的復雜網絡可視化仿真平臺（VPCN）的實現

4.1 復雜網絡的基本定義以及關鍵類設計

定義1:復雜網絡基本模型。復雜網絡用簡單連通圖G=(V ,E )表示。其中，圖中的節(jié)點集V={v1,v2,…,vn} 代表節(jié)點集合；n= |V |表示節(jié)點的總數。 復雜網絡的邊（ 連接）集為E={e1,e2,…,em} ，m= |E |表示整個復雜網絡的邊的總數［8］。對每條邊 es?E(1 ≤ s ≤ m )，在 V 中有一對節(jié)點(vi,vj)(1 ≤i ≤n,1 ≤j ≤n )與之對應。

定義2:關鍵節(jié)點。復雜網絡中相對于其它點具有較高價值的點稱為關鍵節(jié)點，點的價值的評價標準不同，對應的關鍵節(jié)點也會不同。對于無向網絡，常見的點的價值評價標準有度分布、中介中心性、聚集系數等。在公共交通中，站點抽象成的點的價值，表示該站點相對于其它站點在結構上有著特殊的重要性［9］。其度數越大，表明經過的公交路線越多，往往重要性也就越高。

根據上述定義，設計如下。

4.1.1 關鍵類設計

在復雜網絡中，點、邊以及圖的類的設計往往對復雜網絡仿真平臺的設計有著重要的作用，因此設計點、邊以及圖的類如下。

class Node//網絡點的類

｛

String name；//節(jié)點名稱

double lng；//節(jié)點經度

double lat；//節(jié)點緯度

｝

class Line//網絡邊的類

｛

Node［］nodelist；//線路節(jié)點序列

int nodeinline；//節(jié)點數量

String linename；//線路名稱

｝

class Map//網絡圖的類

｛

int nodenum；//網絡節(jié)點總數

int linenum；//網絡線路總數

Line［］linelist；//網絡線路序列

int［］［］map；//網絡鄰接矩陣

int［］［］neighbor；//網絡鄰接表

｝

4.1.2 復雜網絡拓撲展示區(qū)域設計

為有效實現復雜網絡仿真平臺的可視化，本平臺利用百度地圖技術，將復雜網絡拓撲中的節(jié)點分布于百度地圖的背景所規(guī)定的大小的笛卡爾坐標系上，生成隨機圖時將分別產生隨機浮點數作為各個節(jié)點的坐標，實現復雜網絡拓撲的可視化。本平臺使用的百度地圖版本為2.0 版，調用Map（）函數構造百度地圖顯示區(qū)域，使用PointCollection（）函數支持海量點的顯示，利用Polyline（）函數實現邊的繪制，通過Label（）函數展示網絡的相關文本信息。設計成矩形區(qū)域可以適應人類的瀏覽習慣，且生成隨機點的方法便于計算以及后續(xù)將隨機點與數據結合進行處理，還可以在保證顯示效果的同時提高圖形的顯示速度。

4.2 復雜網絡的關鍵算法設計

4.2.1 無標度隨機網絡生成算法

無標度隨機網絡的無標度性質用于描述大型復雜網絡整體上嚴重不均勻分布的一種內在性質，是隨機網絡的一種經典類型。

目前常用的無標度隨機網絡生成算法為B-A無標度網絡生成算法，該算法中節(jié)點連接選擇的擇優(yōu)概率公式為

其中n 代表網絡中的節(jié)點總數，ki代表第i 個點在網絡中的連接數，α 為常數，代表初始連接數。本平臺采用以上的擇優(yōu)概率公式提供了生成無標度隨機網絡的一種算法，算法步驟如下:

2）生成一個1到n 之間的隨機整數 a，作為第一個點的序號；

4）判斷 (va,vb)節(jié)點對所對應的邊是否存在，即rab和rba為是否為1，如果存在回到步驟2）；

5）將 (va,vb)節(jié)點對所對應的邊添加進連通數組R，即設置rab和rba為1，同時更新連接概率數組 P ，即 pa和 pb自增1；

6）判斷添加的邊的數量是否到達設定的最大值，是則網絡生成技術，否則回到步驟2）繼續(xù)。

4.2.2 復雜網絡參數計算算法-中介中心性

復雜網絡參數計算算法常見的有度分布、聚集系數、中介中心性、節(jié)點中心度、網絡直徑、網絡最短路徑等［10］，下面以中介中心性為例介紹本平臺的復雜網絡參數計算流程。

復雜網絡中點的中介中心性反映途經這一節(jié)點的最短路徑數目在全部路徑中所占的比例，體現了節(jié)點對于整個網絡的最優(yōu)交通路徑的影響力，對于復雜網絡的優(yōu)化研究具有重要意義。本平臺提供了生成計算復雜網絡中介中心性的一種算法，復雜網絡其中最短路徑數計算步驟如下:

點i 和節(jié)點 j 之間存在的最短路徑數量，初始值為rij，最短路徑長度矩陣，其中l(wèi)ij(1 ≤i ≤ n,1 ≤ j ≤ n )表示節(jié)點 i 和節(jié)點 j 之間存在的最短路徑數量，初始值為0 ，鄰居矩陣，其中hij(1 ≤ i ≤ n,1 ≤ j ≤ n )表示節(jié)點i 的第 j 個鄰居的序號，空值為0，初始化節(jié)點標志位 p，表示當前訪問的節(jié)點序號，初始值為1；

2）新建一個空的隊列結構Q，滿足先進先出原則，初始化訪問標志位數組T={t1,t2,…,tn} ，其中ti(1 ≤i ≤n )表示第 i 個節(jié)點已經被訪問，初始值為0，第 p 個點進入隊列結構Q；

3）隊列結構Q為空則轉至步驟7），非空則隊首元素x出隊，按照鄰居矩陣H 遍歷該節(jié)點的鄰居節(jié)點值hxq(1 ≤ q ≤ n )，tx置 1；

4）鄰居節(jié)點 hxq如果為0，則跳轉到步驟3），否則到步驟5）；

5）鄰居節(jié)點hxq與節(jié)點 p 是否已經存在最短路徑，是則轉至步驟7）；

6）初始化最短路徑長度矩陣L 中l(wèi)pq值為lpx+1，最短路徑計數矩陣C 中的cpq值為cpx；

7）當前搜索路徑長度lpx+1與最短路徑長度矩陣L 中l(wèi)pq比較是否相等，是則更新最短路徑計數矩陣 C ，即設置 cpq自增 cpx，q 自增 1，轉至步驟4）；

8）p 是否為n，是則運算結束，否則 p 自增1，回到步驟2）。

根據以上流程計算出的最短路徑數，根據中介中心性的計算方法，節(jié)點 p 的中介中心性計算公式為

公式中用到的cij、lij等數值取自最短路徑計數矩陣C 和最短路徑長度矩陣L，經過該公式計算可以求得復雜網絡中介中心性的值。

5 復雜網絡節(jié)點重要性評價方法仿真實例

本節(jié)通過多種復雜網絡節(jié)點重要性評價方法的仿真實例對本仿真平臺的有效性進行說明。仿真平臺中內置了北京公交網絡數據，該數據來源為百度地圖 api（http://map.baidu.com/）和圖吧公交（http://bus.mapbar.com），對北京公交站點和路線組成的復雜網絡進行節(jié)點重要性評價。

該平臺立足于公共交通的應用背景，故選用真實的北京公交網絡進行網絡的顯示和網絡參數的計算，平臺可視化的效果如圖3、圖4所示。

圖3 交通網絡圖

圖3 所用的交通網絡數據來源于北京市公交網絡，選取了含有7504個節(jié)點和17667條邊的數據進行顯示?？梢钥吹浇煌ňW絡在地圖背景下顯得更為真實，實際加載時間和地圖縮放延遲都體現了該可視化平臺的實時性特點。同時網絡的調整功能可以對網絡進行一定的操作，如圖中演示的網絡節(jié)點刪除功能。

圖4 顯示的是網絡關鍵節(jié)點的可視化效果。參數運算部分運行完成后可以即時傳至網頁端表格顯示，關鍵節(jié)點可以在信息計算完成的同時立即顯示。

圖4 關鍵節(jié)點顯示圖

本平臺實驗中選取網絡度分布、聚集系數、中介中心性、節(jié)點中心度參數對北京市公交網絡進行參數分析，得到參數計算結果如圖5 所示，可以看出本平臺能夠有效發(fā)掘復雜網絡關鍵節(jié)點的信息，通過序號和節(jié)點名稱的形式準確查找到關鍵節(jié)點的位置，是一種高效且可視化效果優(yōu)秀的復雜網絡可視化仿真平臺。

圖5 復雜網絡參數計算結果圖

6 結語

從網絡可視化效果可以看出，基于Web的復雜網絡可視化仿真平臺相對于傳統(tǒng)的復雜網絡可視化平臺有著更好的顯示效果，能夠通過在網絡圖上添加網絡相關信息的方式有效提升復雜網絡的可視化效果，從而為公共交通的分析提供有效支持。

在網絡性能方面，規(guī)模較大的網絡可以實現較為流暢的顯示，網絡縮放功能也能夠在保持操作流暢的情況下提升網絡所能容納的信息量，充分展現網絡的利用價值，為公共交通的設計提供有效參考。

從拓展性角度上看，該基于Web的復雜網絡可視化仿真平臺和地理信息的結合度較高，比較適合網絡按照地理位置分布并與地理信息有高度相關性的網絡，除公共交通網絡之外還有在電力網絡、生物遷徙網絡、病毒傳播網絡等等場景下的應用可能性。研究方向上，未來還將添加對于復雜網絡抗毀性［11］的連通度［12］、復雜網絡聚類算法［13］的改進［14］和數據場［15］的應用方面的研究。性能提升方面，為了應對超大規(guī)模網絡上高復雜度算法的運算，未來將在Java平臺的基礎上改進連接Spark［16］大數據運算平臺運算的部分以加快運算速度。