網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化方法研究與發(fā)展

王松，張野，吳亞東

?

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化方法研究與發(fā)展

王松1,2，張野1，吳亞東1

（1. 西南科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 綿陽 621010；2. 中國工程物理研究院電子工程研究所，四川 綿陽 621010）

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化作為網(wǎng)絡(luò)檢測管理和網(wǎng)絡(luò)安全態(tài)勢感知的基礎(chǔ)，在呈現(xiàn)網(wǎng)絡(luò)的整體狀況和發(fā)現(xiàn)存在于網(wǎng)絡(luò)拓?fù)渲械臐撛谝?guī)律方面發(fā)揮著重要作用。介紹了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化的基本內(nèi)容，從網(wǎng)絡(luò)數(shù)據(jù)自身特點(diǎn)和用戶需求角度分析目前網(wǎng)絡(luò)拓?fù)淇梢暬芯恐写嬖诘闹饕魬?zhàn)。抽象領(lǐng)域?qū)＜曳治隼斫饩W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)和連接狀況，洞察網(wǎng)絡(luò)拓?fù)湫畔⒅行阅芷款i、網(wǎng)絡(luò)安全、時(shí)變特性等潛在規(guī)律的過程，提出一個(gè)自頂向下的VPI分析流程模型，包括視覺接收、過程感知和交互參與。以VPI模型為指導(dǎo)，從視覺感知增強(qiáng)、時(shí)變過程增強(qiáng)以及探索式交互增強(qiáng)3個(gè)方面綜述了網(wǎng)絡(luò)拓?fù)淇梢暬椒ǖ难芯楷F(xiàn)狀，并結(jié)合應(yīng)用需求展望未來的發(fā)展趨勢。

視覺感知增強(qiáng)；時(shí)變過程增強(qiáng)；探索式交互增強(qiáng)；VPI模型

1 引言

網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)和顯示是現(xiàn)代網(wǎng)絡(luò)管理的首要工作，借助網(wǎng)絡(luò)拓?fù)浣Y(jié)果可以了解當(dāng)前的網(wǎng)絡(luò)運(yùn)行狀態(tài)、判斷網(wǎng)絡(luò)擁塞、定位網(wǎng)絡(luò)瓶頸、發(fā)現(xiàn)網(wǎng)絡(luò)故障并分析發(fā)生的原因和位置，從而實(shí)現(xiàn)對整個(gè)網(wǎng)絡(luò)的運(yùn)行狀態(tài)進(jìn)行及時(shí)有效的監(jiān)測和控制。可視化是一種通過交互式可視化界面來輔助用戶對大規(guī)模復(fù)雜數(shù)據(jù)集進(jìn)行分析推理的科學(xué)與技術(shù)，將數(shù)據(jù)中各種抽象的信息轉(zhuǎn)化為圖形信息，并通過各種圖形交互技術(shù)，使人們加深對信息的理解和認(rèn)識。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化將網(wǎng)絡(luò)節(jié)點(diǎn)的連接關(guān)系以點(diǎn)和線等構(gòu)成的圖形圖像[1]進(jìn)行呈現(xiàn)，能夠清晰直觀地反映網(wǎng)絡(luò)運(yùn)行狀況，輔助人們對網(wǎng)絡(luò)節(jié)點(diǎn)、鏈路等各方面進(jìn)行評估、預(yù)測和分析，有效地認(rèn)識和了解網(wǎng)絡(luò)內(nèi)部信息、規(guī)律和變化[2]。

近年來，計(jì)算機(jī)網(wǎng)絡(luò)發(fā)展迅猛，網(wǎng)絡(luò)結(jié)構(gòu)的異構(gòu)性、動(dòng)態(tài)性、復(fù)雜性、發(fā)展的非集中性以及時(shí)變性等特征都給網(wǎng)絡(luò)結(jié)構(gòu)分析研究帶來了巨大的挑戰(zhàn)。要及時(shí)、快速、正確、完整地獲取網(wǎng)絡(luò)拓?fù)湫畔ⅲ汕逦€(wěn)定的拓?fù)鋱D，以圖形方式將網(wǎng)絡(luò)結(jié)構(gòu)中的節(jié)點(diǎn)和連接狀況清晰展現(xiàn)出來，為用戶理解、分析目標(biāo)網(wǎng)絡(luò)的整體狀況和發(fā)現(xiàn)存在于網(wǎng)絡(luò)拓?fù)涞臐撛谝?guī)律是網(wǎng)絡(luò)結(jié)構(gòu)可視化的研究重點(diǎn)和難點(diǎn)內(nèi)容。

網(wǎng)絡(luò)拓?fù)淇梢暬蕴岢鲆詠斫?jīng)過多年的發(fā)展，已經(jīng)取得了顯著的成果，在一定程度上解決了大量網(wǎng)絡(luò)數(shù)據(jù)和有效分析手段之間的矛盾。但隨著網(wǎng)絡(luò)數(shù)據(jù)規(guī)模劇增、拓?fù)浣Y(jié)構(gòu)復(fù)雜性增強(qiáng)，直接對其進(jìn)行可視化會(huì)導(dǎo)致顯示重疊、層次信息難以觀察等問題，無法有效降低網(wǎng)絡(luò)分析人員的負(fù)擔(dān)。針對上述問題并結(jié)合領(lǐng)域需求，總結(jié)目前網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化研究中主要存在的挑戰(zhàn)如下。1) 網(wǎng)絡(luò)節(jié)點(diǎn)和連邊數(shù)目過大時(shí)，借助多樣化的布局方式能夠有效觀察網(wǎng)絡(luò)整體拓?fù)浣Y(jié)構(gòu)。布局算法主要需要解決如何確定和分配映射在有限顯示空間內(nèi)幾何圖形的各個(gè)節(jié)點(diǎn)和邊的具體位置，良好的拓?fù)洳季炙惴軌蛴行У乇苊怙@示出來的拓?fù)浣Y(jié)構(gòu)圖中節(jié)點(diǎn)的重疊，能夠大大地減少拓?fù)浣Y(jié)構(gòu)圖中邊之間的交叉，能夠更加美觀大方地展示出要處理的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。2) 針對網(wǎng)絡(luò)時(shí)變數(shù)據(jù)在時(shí)空演化過程中可能出現(xiàn)的網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)結(jié)構(gòu)劇變等情況，提供穩(wěn)定的布局方式來避免大范圍的布局更新造成的認(rèn)知混亂和理解難度。網(wǎng)絡(luò)時(shí)變數(shù)據(jù)中包含的網(wǎng)絡(luò)節(jié)點(diǎn)種類與數(shù)目在隨時(shí)間不斷變化，網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接也在不斷出現(xiàn)與消失，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在節(jié)點(diǎn)出現(xiàn)與消失的過程中不斷發(fā)生變化。穩(wěn)定的布局方式能夠保證在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)大范圍變化的過程中用戶的關(guān)注焦點(diǎn)不會(huì)發(fā)生突變，保持用戶認(rèn)知過程的連續(xù)性，降低對時(shí)變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)理解的難度。3) 在網(wǎng)絡(luò)結(jié)構(gòu)分析和挖掘中，能夠提供有效的協(xié)同交互策略，實(shí)現(xiàn)兼顧網(wǎng)絡(luò)高層次宏觀結(jié)構(gòu)和低層次局部細(xì)節(jié)的特征分析過程。借助可視分析技術(shù)，用戶可以觀察并分析不同時(shí)間粒度下網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的時(shí)變演化過程，逐層深入分析探究感興趣區(qū)域節(jié)點(diǎn)的內(nèi)部結(jié)構(gòu)及其在整個(gè)拓?fù)浣Y(jié)構(gòu)中的作用，對比觀察網(wǎng)絡(luò)節(jié)點(diǎn)多屬性之間的差異并分析特征區(qū)域內(nèi)結(jié)構(gòu)狀態(tài)以及多屬性變量之間的關(guān)聯(lián)性。

2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化VPI分析模型

本文抽象信息安全領(lǐng)域?qū)＜曳治隼斫饩W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)和連接狀況，洞察網(wǎng)絡(luò)拓?fù)湫畔⒅行阅芷款i、網(wǎng)絡(luò)安全、時(shí)變特性等潛在規(guī)律的過程，提出一個(gè)自頂向下的VPI分析流程模型，包括視覺接收（vision）、過程感知（procedure）和交互參與（interaction）。該模型的主體思想是：提取網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征進(jìn)行幾何映射，用戶對繪制結(jié)果進(jìn)行觀察分析完成視覺接收，對于時(shí)變數(shù)據(jù)通過動(dòng)畫模擬等表達(dá)方式展現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)時(shí)變演化過程，從而幫助用戶思考?xì)w納，構(gòu)建對網(wǎng)絡(luò)數(shù)據(jù)時(shí)效性的基本理解；然后通過不斷迭代的交互反饋優(yōu)化繪制結(jié)果，并借助其他硬件輔助設(shè)備完善用戶對大規(guī)模復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)潛在信息特征和規(guī)律的認(rèn)知。VPI模型是以網(wǎng)絡(luò)數(shù)據(jù)為中心的分析流程，融合了信息安全領(lǐng)域?qū)＜曳治鰪?fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的幾種常見分析思路。1) 由整體到局部，通過可視化呈現(xiàn)掌握整體網(wǎng)絡(luò)布局結(jié)構(gòu)，基于Foucs+Context理論實(shí)現(xiàn)迭代交互全方面展示用戶感興趣區(qū)域或節(jié)點(diǎn)的連接關(guān)系與運(yùn)行態(tài)勢。2) 由表面到內(nèi)部，可視化繪制結(jié)果給用戶直觀的視覺感知，借助交互操作與先進(jìn)的硬件設(shè)備洞察網(wǎng)絡(luò)拓?fù)渖顚觾?nèi)部結(jié)構(gòu)，完成對網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的立體剖析。3) 由生疑到解惑，對于生成的網(wǎng)絡(luò)拓?fù)淇梢暬尸F(xiàn)，用戶針對不同方面產(chǎn)生的問題，通過基于視覺認(rèn)知的人機(jī)交互與硬件優(yōu)化，最終理解并解決復(fù)雜的網(wǎng)絡(luò)監(jiān)測、性能優(yōu)化、故障分析和安全評估等問題。綜合近幾年網(wǎng)絡(luò)拓?fù)淇梢暬I(lǐng)域相關(guān)的學(xué)術(shù)成果，大多研究主題集中在網(wǎng)絡(luò)拓?fù)淇梢暬尸F(xiàn)的感知優(yōu)化方面。以VPI模型為指導(dǎo)，將目前網(wǎng)絡(luò)拓?fù)淇梢暬较虻闹饕芯窟M(jìn)展劃分為視覺感知增強(qiáng)、時(shí)變過程增強(qiáng)以及探索式交互增強(qiáng)3個(gè)方面。圖1是基于VPI模型的網(wǎng)絡(luò)拓?fù)淇梢暬诸惤Y(jié)構(gòu)的示意，本文按照該分類策略系統(tǒng)地整理了近幾年大部分代表性網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化工作。

3 視覺感知增強(qiáng)類網(wǎng)絡(luò)拓?fù)淇梢暬?/h2>

視覺感知增強(qiáng)類網(wǎng)絡(luò)拓?fù)淇梢暬椒ㄖ饕獋?cè)重于對直觀可視化呈現(xiàn)的優(yōu)化，增強(qiáng)形狀、顏色、深度等信息，以提高視覺空間表現(xiàn)力，有效傳達(dá)網(wǎng)絡(luò)數(shù)據(jù)拓?fù)湫畔ⅲ瑥亩鵀橛脩籼峁└鼫?zhǔn)確的視覺認(rèn)知。嘗試解決的核心問題包括對幾何映射布局方式的優(yōu)化，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)與連邊數(shù)目過大時(shí)仍能夠有效呈現(xiàn)拓?fù)浣Y(jié)構(gòu)；對研究者關(guān)心的結(jié)構(gòu)特征進(jìn)行提取與呈現(xiàn)，以及如何實(shí)現(xiàn)對特定區(qū)域與特定節(jié)點(diǎn)的局部細(xì)節(jié)呈現(xiàn)，減少由于對象間遮擋導(dǎo)致的感知偏差。

3.1 布局方式優(yōu)化

本文網(wǎng)絡(luò)拓?fù)洳季炙惴ㄖ饕鉀Q的問題是如何確定和分配映射在顯示界面上的幾何圖形的各個(gè)節(jié)點(diǎn)和邊的空間位置。一個(gè)良好的拓?fù)洳季炙惴軌蛴行У乇苊馔負(fù)浣Y(jié)構(gòu)圖中節(jié)點(diǎn)的重疊現(xiàn)象，大大減少結(jié)構(gòu)圖中邊之間的交叉問題，清晰美觀的拓?fù)涑尸F(xiàn)便于管理人員獲取網(wǎng)絡(luò)信息，進(jìn)行網(wǎng)絡(luò)管理。拓?fù)洳季炙惴梢苑譃槲锢聿季址绞胶瓦壿嫴季址绞絻纱箢怺3]。物理布局的主要思想是將節(jié)點(diǎn)的地理位置信息簡單地解析為與其對應(yīng)的布局坐標(biāo)，使在拓?fù)鋱D中能夠清晰地發(fā)現(xiàn)節(jié)點(diǎn)的位置信息以及節(jié)點(diǎn)之間的相對位置和相對距離。邏輯布局主要根據(jù)網(wǎng)絡(luò)拓?fù)涞玫降木唧w節(jié)點(diǎn)的情況設(shè)計(jì)分配節(jié)點(diǎn)的布局空間和布局策略，不依賴網(wǎng)絡(luò)節(jié)點(diǎn)的物理位置，更側(cè)重于網(wǎng)絡(luò)節(jié)點(diǎn)的相互關(guān)系和網(wǎng)絡(luò)拓?fù)鋱D的內(nèi)在特性。

常用的拓?fù)洳季炙惴ㄈ缦隆?) 樹形布局算法。樹形結(jié)構(gòu)具有任意的深度和任意的寬度，所以樹形布局算法具有很強(qiáng)的適用性、通用性，同時(shí)樹形布局的結(jié)構(gòu)簡單直觀，層次分明，連接顯示清晰易判斷。2)射線型布局算法[4]。樹形布局算法的極坐標(biāo)顯示形式。射線型布局的最大優(yōu)點(diǎn)在于空間利用率較高，分布相對比較均勻，在很大程度上避免了網(wǎng)絡(luò)節(jié)點(diǎn)扎堆布局在一起的問題。3) 層次型布局算法[5]。針對圖的內(nèi)部層次結(jié)構(gòu)關(guān)系特性對圖進(jìn)行分層處理，在呈現(xiàn)大型網(wǎng)絡(luò)整體的同時(shí)，能夠詳細(xì)展示局部區(qū)域的連接關(guān)系。4) 網(wǎng)格型布局算法。將界面分割成方形的網(wǎng)格狀，直線交叉的位置安排網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行繪制，這種布局充分地平均了節(jié)點(diǎn)的顯示空間，從理論上杜絕了節(jié)點(diǎn)的重疊和網(wǎng)絡(luò)節(jié)點(diǎn)過于集中的問題。5) 力導(dǎo)向布局算法[6]。為拓?fù)鋱D中的頂點(diǎn)和邊賦予一定的物理性質(zhì)，通過對具有物理性質(zhì)的頂點(diǎn)和邊組成的系統(tǒng)的調(diào)整，使該物理系統(tǒng)達(dá)到一個(gè)力學(xué)平衡狀態(tài)，從而實(shí)現(xiàn)對拓?fù)鋱D的布局繪制。對于網(wǎng)絡(luò)結(jié)構(gòu)簡單、節(jié)點(diǎn)數(shù)少、連接關(guān)系不復(fù)雜的網(wǎng)絡(luò)能夠有效解決連線密集、節(jié)點(diǎn)覆蓋、圖像聚集等問題。6) 啟發(fā)式布局算法[7]。采用分而治之的算法思想，將要處理的大型網(wǎng)絡(luò)通過一定的規(guī)則或者條件分割成若干個(gè)較小的區(qū)域和集群，根據(jù)局部區(qū)域的特點(diǎn)采用合適的布局算法對小區(qū)域進(jìn)行排序和布局。該布局策略在整體和局部都能夠更好地體現(xiàn)出待處理網(wǎng)絡(luò)本身具有的網(wǎng)絡(luò)拓?fù)涮匦裕诳傮w上大大降低了問題的規(guī)模和難度，布局效率明顯提升。但常見的這幾類拓?fù)洳季炙惴ㄈ匀粵]有解決當(dāng)圖的規(guī)模變大時(shí)劇增的節(jié)點(diǎn)和邊導(dǎo)致的布局規(guī)模和布局約束問題。

一個(gè)好的拓?fù)洳季炙惴ㄐ枰獫M足3個(gè)條件：1) 有效避免拓?fù)鋱D中節(jié)點(diǎn)的重疊；2) 拓?fù)浣Y(jié)構(gòu)圖中邊的交叉盡可能減少；3) 網(wǎng)絡(luò)拓?fù)錆M足基本美學(xué)標(biāo)準(zhǔn)，如區(qū)域最小原則、邊交叉最小原則、節(jié)點(diǎn)密度均勻原則[8]。Chaturvedi等[9]提出了一種名為GIB（group-in-a-box）的布局方式。如圖2(a)所示（見彩插頁1），該布局方式為每個(gè)組繪制一個(gè)單獨(dú)的矩形框，根據(jù)組包含的節(jié)點(diǎn)數(shù)確定大小。這些矩形框在屏幕空間中不連貫地排列。然后，使用力導(dǎo)向、圓形、網(wǎng)格或其他可用的布局在相關(guān)的框中放置單個(gè)組。組布局是獨(dú)立于網(wǎng)絡(luò)的其余部分完成的。GIB布局可揭示組成員身份，本地組內(nèi)網(wǎng)絡(luò)結(jié)構(gòu)和成員屬性，這種有組織的安排對于其中由于節(jié)點(diǎn)和邊緣數(shù)量過多而隱藏組內(nèi)關(guān)系的網(wǎng)絡(luò)特別有用；對于研究更廣泛的群際關(guān)系也是有價(jià)值的。Yoghourdjian等[10]提出了一種分組網(wǎng)絡(luò)的高質(zhì)量超緊湊網(wǎng)格布局方法，利用LNS啟發(fā)式算法找到一個(gè)初始的解決方案，然后通過選擇一組節(jié)點(diǎn)進(jìn)行迭代改進(jìn)，并提出一種超緊湊的網(wǎng)格式網(wǎng)絡(luò)布局美學(xué)標(biāo)準(zhǔn)進(jìn)行性能評估，高效地解決布局上的質(zhì)量問題。Wu等[11]提出一種新穎的基于Voronoi樹圖的聚類布局方式。該方法先計(jì)算群體的屬性、群體間的關(guān)聯(lián)度等信息，根據(jù)群體的內(nèi)部連接性、外部連接性及其組合以各種方式計(jì)算該群體的質(zhì)量，最后借助格式塔定律對群體進(jìn)行聚類。這種布局方式能更好地顯示節(jié)點(diǎn)群體間的關(guān)聯(lián)和分析其層次結(jié)構(gòu)，如圖2(b)所示（見彩插頁1）。

圖2 針對布局方式優(yōu)化的網(wǎng)絡(luò)拓?fù)淇梢暬?/p>

3.2 減少視覺混亂與遮擋

結(jié)合人類在認(rèn)知外部事物的過程中，充分利用了能夠感知到的所有視覺信息來理解周圍的世界。從視覺呈現(xiàn)的角度，對象間的遮擋會(huì)導(dǎo)致用戶在感知上發(fā)生偏差引起認(rèn)知錯(cuò)誤，而大規(guī)模網(wǎng)絡(luò)節(jié)點(diǎn)和邊的繪制所導(dǎo)致的視覺混亂與遮擋問題隨處可見。如何有效地呈現(xiàn)大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)內(nèi)在的復(fù)雜性，實(shí)現(xiàn)視覺空間表現(xiàn)力極大化，盡量避免視覺遮擋與混亂現(xiàn)象，是視覺感知增強(qiáng)類網(wǎng)絡(luò)拓?fù)淇梢暬椒ǖ囊粋€(gè)核心研究方向。目前的研究思路分為2種：一是在盡量不減少原圖信息量（包括邊和節(jié)點(diǎn)的數(shù)目）的前提下對圖進(jìn)行邊綁定；二是根據(jù)信息可視化的信息分級原則，對大規(guī)模圖進(jìn)行層次化簡化。

邊綁定算法的核心思想是在保持信息量（即不減少邊和節(jié)點(diǎn)總數(shù)）的情況下，將圖上互相靠近的邊捆綁成束，從而達(dá)到去繁就簡的效果。Cui等[12]提出的基于幾何的邊綁定方法第一次成功地解決了對任意圖的邊綁定問題。基本思想是在圖上生成均勻的輔助網(wǎng)格，計(jì)算網(wǎng)格內(nèi)邊的平均走向，通過對相似網(wǎng)格進(jìn)行合并實(shí)現(xiàn)對邊走向的調(diào)整。Peng等[13]提出SideKnot綁定算法，與傳統(tǒng)方法在中段進(jìn)行合并不同，采取了在邊靠近節(jié)點(diǎn)一側(cè)按照走向進(jìn)行綁定的策略，對連接到節(jié)點(diǎn)的所有邊按其走向進(jìn)行聚類，再對每個(gè)類根據(jù)邊的平均方向和長度產(chǎn)生一系列控制點(diǎn)，最后以B樣條的方式生成可視化效果，如圖3(a)所示（見彩插頁2）。Hurter等[14]提出基于核心密度估計(jì)的邊綁定技術(shù)，先使用內(nèi)核密度估算方法將給定的大圖轉(zhuǎn)化為密度圖，對該密度圖的梯度進(jìn)行邊緣平流并反復(fù)迭代該過程，從而提供一個(gè)獨(dú)立光滑的邊綁定結(jié)構(gòu)圖，最后采用一種新的陰影技術(shù)來提高邊綁定的視覺效果。在此基礎(chǔ)上，Peysakhovich等[15]提出了一種屬性驅(qū)動(dòng)邊綁定技術(shù)，如圖3(b)所示（見彩插頁2），該算法先對多個(gè)屬性進(jìn)行兼容從而構(gòu)成綁定圖，分別計(jì)算邊緣的方向和時(shí)間戳這2個(gè)流向圖，然后計(jì)算這2個(gè)屬性的子空間，再在這2個(gè)子空間的交集上計(jì)算出梯度，最終計(jì)算出多變準(zhǔn)集合布局完成邊綁定。屬性驅(qū)動(dòng)邊綁定技術(shù)是一種基于邊緣性兼容方案的新型框架，能夠根據(jù)一或多個(gè)數(shù)值的邊緣屬性定義綁定圖的兼容性，并支持GPU加速算法處理大規(guī)模數(shù)據(jù)集。Bach等[16]提出一種CD（confluent drawing）邊綁定技術(shù)，對每個(gè)集合節(jié)點(diǎn)新建節(jié)點(diǎn)，將集合節(jié)點(diǎn)之間的連接關(guān)系轉(zhuǎn)換成新建節(jié)點(diǎn)之間的連接。與傳統(tǒng)的空間邊綁定技術(shù)相比，該方法的優(yōu)點(diǎn)在于能夠按照圖的拓?fù)浣Y(jié)構(gòu)進(jìn)行邊綁定，綁定結(jié)果更加注重圖的連接關(guān)系。在提供給用戶復(fù)雜連接圖全局概覽的同時(shí)，通過邊的粗細(xì)與顏色深度呈現(xiàn)圖中主要連接關(guān)系的信息，有效減少在圖繪制中邊的混亂程度。Bouts等[17]提出一種新的鏈接聚類和路由算法來實(shí)現(xiàn)邊綁定。該算法通過完全成對分離方法對鏈路集群進(jìn)行分類，采用貪心稀疏方法實(shí)現(xiàn)路由繪制和鏈接排序，從而通過支持用戶自定義鏈路集群和路由算法計(jì)算鏈路路由，減少節(jié)點(diǎn)連接圖繪制方式中出現(xiàn)的視覺混亂，如圖3(c)所示（見彩插頁2）。

圖的拓?fù)浣Y(jié)構(gòu)包括節(jié)點(diǎn)和邊2個(gè)部分，圖的簡化算法一方面對邊進(jìn)行提取，另一方面將強(qiáng)連通的節(jié)點(diǎn)進(jìn)行聚類，從而將聚類后的節(jié)點(diǎn)集作為一個(gè)新的超級節(jié)點(diǎn)繪制到可視化結(jié)果中。Rosvall等[18]采用社區(qū)發(fā)現(xiàn)算法對節(jié)點(diǎn)進(jìn)行聚類，如圖4(a)所示（見彩插頁3），原有的6 000多個(gè)節(jié)點(diǎn)被迅速縮小為88個(gè)超級節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)代表一個(gè)聚類，而節(jié)點(diǎn)的大小則被編碼為聚類中原來節(jié)點(diǎn)的數(shù)目。Liao等[19]針對大規(guī)模復(fù)雜網(wǎng)絡(luò)采用力導(dǎo)引布局呈現(xiàn)網(wǎng)絡(luò)訪問圖，對于大型網(wǎng)絡(luò)的節(jié)點(diǎn)連接圖可能出現(xiàn)連線混雜等問題，通過基于網(wǎng)絡(luò)拓?fù)湫畔⒌膱D壓縮方法對圖進(jìn)行簡化，利用中心點(diǎn)將網(wǎng)絡(luò)的主機(jī)分成幾個(gè)區(qū)域，從而大大簡化了連接復(fù)雜度，并且凸顯了關(guān)鍵主機(jī)。Shi等[20]提出一種用于大型異構(gòu)網(wǎng)絡(luò)的探索式可視分析集成框架OnionGraph，通過可擴(kuò)展的算法創(chuàng)建基于屬性的聚合，并對各種結(jié)構(gòu)的等價(jià)網(wǎng)絡(luò)進(jìn)行分區(qū)，從而結(jié)合語義和拓?fù)湫畔⑦M(jìn)行分層抽象，實(shí)現(xiàn)對異構(gòu)網(wǎng)絡(luò)不同級別的查看。通過交互式探索，用戶可以在網(wǎng)絡(luò)上創(chuàng)建多個(gè)分層的焦點(diǎn)。每個(gè)聚焦的子網(wǎng)絡(luò)都與一個(gè)獨(dú)立的抽象概況相關(guān)聯(lián)，如圖4(b)所示（見彩插頁3）。Zinsmaier等[21]提出一種層次渲染的顯示方法，采用基于密度的節(jié)點(diǎn)和邊聚類表現(xiàn)方式解決視覺混亂問題。如圖4(c)所示（見彩插頁3），首先采用核密度估計(jì)算法創(chuàng)建密度場實(shí)現(xiàn)節(jié)點(diǎn)聚合，借助攀爬算法實(shí)現(xiàn)與聚合節(jié)點(diǎn)在視覺上耦合的邊聚合，從而允許用戶交互式分析不同細(xì)節(jié)層面的直線大圖繪制結(jié)果。

圖3 基于邊綁定技術(shù)的視覺呈現(xiàn)優(yōu)化

圖4 基于圖簡化技術(shù)的視覺呈現(xiàn)優(yōu)化

4 時(shí)變過程增強(qiáng)類網(wǎng)絡(luò)拓?fù)淇梢暬?/h2>

時(shí)變過程增強(qiáng)類網(wǎng)絡(luò)拓?fù)淇梢暬椒ㄖ饕獋?cè)重于呈現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)的動(dòng)態(tài)特性，追蹤拓?fù)浣Y(jié)構(gòu)的時(shí)間演變過程，有效表達(dá)節(jié)點(diǎn)和連線的數(shù)量和屬性等信息隨時(shí)間的變化過程，幫助用戶更有效地理解復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，提高對動(dòng)態(tài)網(wǎng)絡(luò)數(shù)據(jù)的過程感知。綜合目前動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)淇梢暬芯砍晒篌w劃分為兩類主要的增強(qiáng)方法。1) 時(shí)變過程動(dòng)畫法。通過動(dòng)畫等刻畫時(shí)變信息的方式描述時(shí)變過程，幫助用戶基于時(shí)間流的方式直觀了解圖演化過程，增強(qiáng)對復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)的時(shí)變認(rèn)知。2) 特征跟蹤法。動(dòng)態(tài)圖突然性的結(jié)構(gòu)變化可能破壞用戶的思維地圖，繼而破壞結(jié)構(gòu)的穩(wěn)定性。通過數(shù)據(jù)挖掘技術(shù)結(jié)合時(shí)間線等呈現(xiàn)方式有效跟蹤結(jié)構(gòu)特征變化，提高時(shí)變認(rèn)知效率。

4.1 時(shí)變過程動(dòng)畫

由于時(shí)變網(wǎng)絡(luò)的動(dòng)畫表達(dá)是將其時(shí)間序列直接映射到可視化的時(shí)間軸，構(gòu)建一個(gè)隨時(shí)間演化的動(dòng)畫布局序列，適合用戶觀察動(dòng)態(tài)圖在整體上的變化趨勢。而單純的動(dòng)畫呈現(xiàn)只是簡單的布局直接轉(zhuǎn)換，瞬間改變的信息容易給用戶造成認(rèn)知困難。目前廣泛采用的方法包括動(dòng)畫過渡和增量式布局2種方法。動(dòng)畫過渡技術(shù)通過在布局之間的轉(zhuǎn)換過程中增加一個(gè)階段過渡，Benjamin等[22]設(shè)計(jì)的GraphDiaries系統(tǒng)在增減元素、轉(zhuǎn)換布局等過程中都增加了過渡階段來有效降低用戶識別、跟蹤和理解動(dòng)態(tài)網(wǎng)絡(luò)的變化過程。如圖5(a)所示（見彩插頁4），在刪除元素階段設(shè)計(jì)圍繞頂點(diǎn)和邊的紅暈漸入動(dòng)畫，在增加元素階段設(shè)計(jì)圍繞頂點(diǎn)和邊的藍(lán)暈先漸入再消失，在轉(zhuǎn)換布局過程中將保留的頂點(diǎn)和邊光滑的移動(dòng)到新位置等動(dòng)畫。Griffen等[23]通過動(dòng)畫過渡技術(shù)和“小倍數(shù)多重顯示方法”的實(shí)驗(yàn)對比，發(fā)現(xiàn)動(dòng)畫過渡技術(shù)能夠更準(zhǔn)確和快速地發(fā)現(xiàn)動(dòng)態(tài)圖中空間和時(shí)間的聚類。Lin等[24]采用模擬退火算法保持動(dòng)態(tài)圖中的思維地圖。思維地圖是用戶觀察動(dòng)態(tài)圖可視化時(shí)在大腦中形成的抽象結(jié)構(gòu)信息，通過動(dòng)畫過渡技術(shù)維護(hù)用戶的思維地圖，保持網(wǎng)絡(luò)布局的穩(wěn)定性。

增量式布局方式是在時(shí)空演化過程中通過相對穩(wěn)定的布局方式有效應(yīng)對可能出現(xiàn)的網(wǎng)絡(luò)規(guī)模劇變等情況，減少大范圍的布局更新造成的認(rèn)知混亂和理解難度。Fisherman等[25]針對包含潛在分組的頂點(diǎn)集提出一種增量布局算法，在動(dòng)態(tài)演化過程中維持網(wǎng)絡(luò)的聚類結(jié)構(gòu)，避免大量節(jié)點(diǎn)的位置改變。在此基礎(chǔ)上，文獻(xiàn)[26]為了維持網(wǎng)絡(luò)的全局結(jié)構(gòu)，提出一種在線動(dòng)態(tài)圖繪制算法。如圖5(b)所示（見彩插頁4），該算法通過減少節(jié)點(diǎn)位移來保持用戶的意象圖，同時(shí)允許對連續(xù)的布局進(jìn)行任意的增量修改。算法支持GPU加速并采用各種剔除方法減少布局時(shí)間，從而能夠處理較大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)。Che等[27]提出一種基于拉普拉斯的動(dòng)態(tài)布局方法來保持時(shí)變圖的整體結(jié)構(gòu)。依據(jù)統(tǒng)一的節(jié)點(diǎn)分布和最小的交叉數(shù)量等審美標(biāo)準(zhǔn)，通過拉普拉斯嵌套距離約束算法對初始布局進(jìn)行優(yōu)化，支持自由地調(diào)整節(jié)點(diǎn)位置來保持圖形組件的形狀，同時(shí)支持用戶自定義參數(shù)來保留意象圖的程度，如圖5(c)所示（見彩插頁4）。

4.2 特征跟蹤

特征跟蹤法主要針對時(shí)變網(wǎng)絡(luò)復(fù)雜結(jié)構(gòu)進(jìn)行劃分，強(qiáng)調(diào)網(wǎng)絡(luò)的層次化構(gòu)成；突出重點(diǎn)環(huán)節(jié)的時(shí)變演化特性，并通過對比分析增強(qiáng)對時(shí)變演化過程關(guān)鍵步驟的理解認(rèn)知。依據(jù)聚焦特征的不同，以及不同層次特征的呈現(xiàn)方式不同，特征跟蹤法表現(xiàn)出不同類型的可視化繪制效果。Kumar等[28]通過基于邊的分布構(gòu)建層次模型，將復(fù)雜時(shí)變網(wǎng)絡(luò)圖以一種層次化的方式呈現(xiàn)。該布局重點(diǎn)關(guān)注中心節(jié)點(diǎn)和有代表性的節(jié)點(diǎn)，能夠創(chuàng)建清晰的時(shí)變動(dòng)畫，保持幀間一致性，同時(shí)支持對節(jié)點(diǎn)和邊的過濾交互，使用戶能夠深入查看細(xì)節(jié)，如圖6(a)所示（見彩插頁5）。James等[29]解決了數(shù)據(jù)規(guī)模達(dá)幾十萬個(gè)節(jié)點(diǎn)和數(shù)百萬條邊的動(dòng)態(tài)網(wǎng)絡(luò)可視化問題，為了發(fā)現(xiàn)和跟蹤重要的網(wǎng)絡(luò)元素，該文提出興趣度的概念，它量化每個(gè)時(shí)間步上每個(gè)圖形元素的興趣程度，充分考慮動(dòng)態(tài)圖中相鄰結(jié)構(gòu)信息、節(jié)點(diǎn)或者邊的屬性數(shù)值以及它們隨時(shí)間的變化。如圖6(b)所示（見彩插頁5），為了有效地分析全局概覽和局部細(xì)節(jié)2個(gè)層次，該文在分析局部改變的同時(shí)保持全局動(dòng)態(tài)網(wǎng)絡(luò)的抽象視圖。這樣具有高興趣度的元素在細(xì)節(jié)層次上被跟蹤，低興趣度的元素只在全局概覽層次上整體顯示時(shí)被跟蹤。Cui等[30]提出一種GraphFlow的表現(xiàn)方式分析時(shí)變網(wǎng)絡(luò)數(shù)據(jù)，采用一種靜態(tài)流的編碼方式呈現(xiàn)網(wǎng)絡(luò)圖中節(jié)點(diǎn)、邊等度量屬性的演化過程，并引入能量的概念定量分析特征屬性的變化量，方便用戶輕松識別演化圖中的關(guān)鍵部分。此外，通過關(guān)聯(lián)一組排列良好的節(jié)點(diǎn)鏈接圖，GraphFlow支持用戶比較不同時(shí)間點(diǎn)的詳細(xì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖6(c)所示（見彩插頁5）。

圖5 基于過程動(dòng)畫的時(shí)變網(wǎng)絡(luò)拓?fù)淇梢暬?/p>

5 探索式交互增強(qiáng)類網(wǎng)絡(luò)拓?fù)淇梢暬?/h2>

網(wǎng)絡(luò)拓?fù)淇梢暬惴ǔ艘曈X呈現(xiàn)部分，另外一個(gè)核心要素是用戶交互。交互是用戶通過與系統(tǒng)之間的對話和互動(dòng)操作和理解數(shù)據(jù)的過程。交互操作有效地緩解了有限的可視化空間和數(shù)據(jù)過載之間的矛盾，幫助拓展可視化中信息表達(dá)的空間，從而解決有限空間與數(shù)據(jù)量和復(fù)雜度之間的差距。同時(shí)交互能讓用戶更好地參與對數(shù)據(jù)的理解和分析，幫助用戶探索數(shù)據(jù)、提高視覺認(rèn)知。Shneiderman[31]早期提出可視化信息搜索的基本原則，歸納了幾種最基本交互操作，包括概覽、縮放、過濾、按需提供細(xì)節(jié)、關(guān)聯(lián)、記錄和提取。Kein[32]提出了5類交互模式：投影、過濾、縮放、失真變形、鏈接與刷動(dòng)。Ward等[33]在按照交互操作分類的基礎(chǔ)上，進(jìn)一步提出了更完善的框架，定義交互為操作符和操作空間的組合。其中，操作符包括3類：導(dǎo)航、選擇和變形；操作空間包括6種：屏幕空間、數(shù)據(jù)值空間、數(shù)據(jù)結(jié)構(gòu)空間、屬性空間、對象空間和可視化結(jié)構(gòu)空間。大多可視化中交互技術(shù)都可以按照上面描述的操作符和操作空間表示。綜合近幾年網(wǎng)絡(luò)拓?fù)淇梢暬矫娴慕换パ芯浚饕难芯繜狳c(diǎn)如下。1) 焦點(diǎn)+上下文交互。致力于顯示用戶興趣焦點(diǎn)部分的細(xì)節(jié)信息，同時(shí)體現(xiàn)焦點(diǎn)和周邊的關(guān)系關(guān)聯(lián)，整合當(dāng)前聚焦點(diǎn)的細(xì)節(jié)信息與概覽部分的上下文信息。2) 直接交互。通過直觀的交互方式直接操作于可視化繪制結(jié)果，提高交互效率與交互結(jié)果的可預(yù)測性，降低用戶認(rèn)知困難、精力分散等交互障礙。3) 關(guān)聯(lián)性交互。借助可視分析技術(shù)，深入探究網(wǎng)絡(luò)數(shù)據(jù)的深層隱含信息與特征之間的關(guān)聯(lián)性，采用多視圖等表達(dá)方式幫助用戶同時(shí)觀察網(wǎng)絡(luò)的不同屬性，支持從不同角度和不同顯示方式觀察數(shù)據(jù)，提高對復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的認(rèn)知深度。4) 沉浸式模擬。它是虛擬現(xiàn)實(shí)技術(shù)與網(wǎng)絡(luò)拓?fù)淇梢暬夹g(shù)的有效結(jié)合，借助直觀的立體成像、三維交互、立體聽覺和三維觸覺反饋等保證用戶在虛擬環(huán)境中的沉浸感，提高分析和理解網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的效率和質(zhì)量。

圖6 基于特征跟蹤的時(shí)變網(wǎng)絡(luò)拓?fù)淇梢暬?/p>

5.1 焦點(diǎn)+上下文交互

焦點(diǎn)+上下文作為信息可視化領(lǐng)域的常用交互方式，其基本思想是將用戶關(guān)心的區(qū)域定義為焦點(diǎn)區(qū)域，采用高亮等方式顯示細(xì)粒度信息；其他區(qū)域作為上下文區(qū)域，通過聚合等操作顯示粗粒度信息。該概念被引入網(wǎng)絡(luò)拓?fù)淇梢暬泻螅谔岣呃L制效率的同時(shí)，能夠有效地處理龐大數(shù)據(jù)集中提取用戶感興趣部分的問題，有利于解決三維映射阻塞現(xiàn)象，受到大量網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化研究人員的青睞。Robert等[34]開發(fā)了網(wǎng)絡(luò)可視化系統(tǒng)VISUAL用于感知內(nèi)外網(wǎng)主機(jī)通信模式，采用主機(jī)位置固定策略，內(nèi)網(wǎng)主機(jī)的網(wǎng)絡(luò)矩陣在中心區(qū)域，外網(wǎng)主機(jī)分布在四周，從連線的多少和外網(wǎng)主機(jī)方塊大小可以很直觀地發(fā)現(xiàn)一些異常活躍的內(nèi)外網(wǎng)主機(jī)，主機(jī)位置固定策略能夠保持良好的主機(jī)邏輯拓?fù)潢P(guān)系。支持“先概覽，然后縮放和過濾，最后根據(jù)需求詳細(xì)分析”的交互過程幫助用戶建立對網(wǎng)絡(luò)活動(dòng)模式的精準(zhǔn)理解。文獻(xiàn)[20]提出的可視化集成框架OnionGraph中，網(wǎng)絡(luò)節(jié)點(diǎn)的子集可以在分層的焦點(diǎn)+上下文交互模型下進(jìn)行靈活的分割和合并。通過交互式探索，用戶可以在網(wǎng)絡(luò)上創(chuàng)建多個(gè)分層的焦點(diǎn)，每個(gè)聚焦的子網(wǎng)絡(luò)都與獨(dú)立的抽象概況相關(guān)聯(lián)，從而實(shí)現(xiàn)對復(fù)雜網(wǎng)絡(luò)的多層次分析。Feng等[35]提供一種新的時(shí)變網(wǎng)絡(luò)繪制方法，采用超圖的概念保持網(wǎng)絡(luò)數(shù)據(jù)的時(shí)空一致性，同時(shí)支持多焦點(diǎn)+上下文的交互方式維持交互過程的動(dòng)態(tài)穩(wěn)定性，通過阻止節(jié)點(diǎn)尺寸和位置發(fā)現(xiàn)突變來保護(hù)用戶的思維地圖，從而提供可讀性更強(qiáng)的視覺效果，如圖7(a)所示（見彩插頁6）。魚眼變換[36]也是一種基于焦點(diǎn)+上下文技術(shù)的常用交互手段，它使用一種焦距極短并且視角接近于180°的鏡頭，在突出正前方物體的基礎(chǔ)上，覆蓋角度所及的范圍最廣。通過魚眼技術(shù)在網(wǎng)絡(luò)拓?fù)鋱D分析過程中可以根據(jù)用戶關(guān)注的焦點(diǎn)進(jìn)行有針對性的縮放，從而揭示局部區(qū)域內(nèi)節(jié)點(diǎn)的連接關(guān)系。Tominski等[37]采用魚眼樹形視圖和組合透鏡來支持對網(wǎng)絡(luò)拓?fù)湟晥D的可視化探索。如圖7(b)所示（見彩插頁6），通過魚眼扭曲算法實(shí)現(xiàn)對聚類圖層次結(jié)構(gòu)的分析，組合透鏡技術(shù)促進(jìn)對大規(guī)模稠密拓?fù)洳季值男畔⒊尸F(xiàn)，其中，局部邊透鏡用于解決圖的邊遮擋問題，鄰居透鏡用于呈現(xiàn)當(dāng)前聚焦節(jié)點(diǎn)的鄰接節(jié)點(diǎn)。Van等[38]將網(wǎng)絡(luò)拓?fù)渚垲惓橄蟪纱箢w粒的節(jié)點(diǎn)，同時(shí)邊也根據(jù)聚類特征聚合為不同粗細(xì)的集束，當(dāng)用戶希望瀏覽具體的細(xì)節(jié)時(shí)，可通過透鏡將抽象結(jié)構(gòu)逐級細(xì)化，最終分解成準(zhǔn)確的結(jié)構(gòu)。如圖7(c)所示（見彩插頁6），當(dāng)透鏡接近顆粒時(shí)，顆粒開始分解，完全被透鏡覆蓋的區(qū)域顯示具體而準(zhǔn)確的圖結(jié)構(gòu)。針對規(guī)模特別龐大的圖結(jié)構(gòu)，Gansner等[39]提出拓?fù)漪~眼技術(shù)，先計(jì)算出復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在不同尺度下簡化后的結(jié)構(gòu)表達(dá)，當(dāng)用戶指定了關(guān)注區(qū)域后，不同層級的簡化結(jié)構(gòu)表達(dá)被混合顯示，以達(dá)到從關(guān)注區(qū)域到外沿細(xì)節(jié)不斷減少的效果，最后在關(guān)注區(qū)域?qū)嵤~眼式的徑向放大，從而既保持足夠的細(xì)節(jié)信息，又不丟失原圖結(jié)構(gòu)粗略的輪廓。

5.2 直接交互

直接交互方式通過直接操作可視化繪制結(jié)果進(jìn)行更深層次的挖掘與分析，有效地提高交互效率與交互結(jié)果的可預(yù)測性，降低用戶認(rèn)知困難、精力分散等交互障礙。Frisch等[40]在交互式顯示屏上采用多點(diǎn)觸控和筆手勢實(shí)現(xiàn)對網(wǎng)絡(luò)拓?fù)鋱D的交互式結(jié)構(gòu)編輯和草圖繪制。如圖8(a)所示（見彩插頁7），以網(wǎng)絡(luò)圖分析需求為核心設(shè)計(jì)了筆手勢集合，包括創(chuàng)建圖元素（節(jié)點(diǎn)、邊）、選擇和移動(dòng)節(jié)點(diǎn)、刪除圖元素、修改邊類型、成比例縮放和移動(dòng)等。Schmidt等[41]對圖可視化中的多點(diǎn)觸屏交互技術(shù)進(jìn)行了深入的研究。針對節(jié)點(diǎn)?鏈路的布局方式，設(shè)計(jì)了一系列的交互集合實(shí)現(xiàn)對網(wǎng)絡(luò)圖中邊的探索分析，有效解決節(jié)點(diǎn)?鏈路布局中邊數(shù)目過多造成的視覺遮擋。交互操作包括接觸拉動(dòng)、接觸定位、接觸波動(dòng)、接觸綁定和透鏡扭曲。Prouzeau等[42]在大屏顯示墻上借助多用戶觸控交互來探索網(wǎng)絡(luò)圖的拓?fù)浣Y(jié)構(gòu)，重點(diǎn)關(guān)注用戶間協(xié)同交互來提高對復(fù)雜拓?fù)鋱D的理解效率和準(zhǔn)確性，包括局部區(qū)域選擇和從原始節(jié)點(diǎn)擴(kuò)散的過程選擇交互，如圖8(b)所示（見彩插頁7）。Kister等[43]將可被檢測位置的移動(dòng)設(shè)備和大屏結(jié)合起來，利用移動(dòng)設(shè)備交互自然和大屏幕顯示信息豐富的優(yōu)點(diǎn)，設(shè)計(jì)一套全面的交互模型支持對網(wǎng)絡(luò)圖的交互、分析任務(wù)，包括選擇、展示細(xì)節(jié)、焦點(diǎn)轉(zhuǎn)換、交互式透鏡、數(shù)據(jù)編輯等。如圖8(c)所示（見彩插頁7），用戶通過觸摸、單擊、移動(dòng)等肢體動(dòng)作直接操控移動(dòng)設(shè)備，從而實(shí)現(xiàn)對大屏幕顯示場景的探索式交互。

圖7 基于焦點(diǎn)+上下文交互的網(wǎng)絡(luò)拓?fù)淇梢暦治?/p>

圖8 基于直接交互的網(wǎng)絡(luò)拓?fù)淇梢暦治?/p>

5.3 關(guān)聯(lián)性交互

多變量可視化領(lǐng)域的交互基本上已經(jīng)形成，其以多關(guān)聯(lián)視圖為基礎(chǔ)，分析視圖用于顯示和分析屬性關(guān)系，主呈現(xiàn)視圖用于顯示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征，使用高維傳輸函數(shù)和畫刷及其衍生技術(shù)為特征選取技術(shù)，以焦點(diǎn)+上下文或其他變種為數(shù)據(jù)和特征顯示方法的基本框架。關(guān)聯(lián)性交互是多變量可視化交互的基礎(chǔ)和重要手段，在分析變量之間的相互關(guān)系以及建立數(shù)據(jù)空間和各種抽象空間的聯(lián)系方面，有著無可替代的作用。近年來，多變量大規(guī)模時(shí)變網(wǎng)絡(luò)數(shù)據(jù)越來越復(fù)雜，網(wǎng)絡(luò)數(shù)據(jù)分析越來越抽象，大多研究工作的研究重心逐漸偏向于對網(wǎng)絡(luò)屬性之間的關(guān)系和變化趨勢的分析。Rufiange等[44]提出的DiffAni系統(tǒng)針對時(shí)變網(wǎng)絡(luò)數(shù)據(jù)采用混合差分圖和動(dòng)畫技術(shù)，通過按時(shí)間排序的連續(xù)塊可視化動(dòng)態(tài)圖，其中每個(gè)塊包含一個(gè)或多個(gè)時(shí)間步布局。DiffAni支持3種類型塊：差分塊顯示某時(shí)間段內(nèi)各時(shí)間步布局之間的差異；動(dòng)畫塊顯示某時(shí)間段內(nèi)布局的變化過程；小組圖塊顯示某時(shí)間步的動(dòng)態(tài)圖狀態(tài)。通過各個(gè)模塊之間的協(xié)同交互可以快速識別網(wǎng)絡(luò)拓?fù)涓淖儯ㄎ桓櫢信d趣的頂點(diǎn)。Ko等[45]利用多視圖綜合各種可視化技術(shù)探索高維多變量的時(shí)空網(wǎng)絡(luò)數(shù)據(jù)，并提出Petal和Thread可視表達(dá)共同有效地呈現(xiàn)具有多變量屬性的動(dòng)態(tài)有向網(wǎng)絡(luò)，其中，Petal表示網(wǎng)絡(luò)數(shù)據(jù)的概覽視圖，Thread編碼節(jié)點(diǎn)多變量屬性的關(guān)聯(lián)細(xì)節(jié)。該方法還有效地利用信息理論模型實(shí)現(xiàn)跨維度的異常檢測、異常的高亮顯示和探索過程的管理，如圖9(a)所示（見彩插頁7）。Hadlak等[46]采用相關(guān)時(shí)間屬性聚類算法支持對動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的可視分析。如圖9(b)所示（見彩插頁7），通過在時(shí)間維度上對節(jié)點(diǎn)或邊的屬性進(jìn)行聚類，將原始的圖數(shù)據(jù)劃分成多個(gè)聚類，把每個(gè)聚類當(dāng)作節(jié)點(diǎn)構(gòu)造超圖，通過相似度視圖、多尺度時(shí)間屬性圖、全局網(wǎng)絡(luò)視圖相互關(guān)聯(lián)來交互探索和改善聚類結(jié)果，進(jìn)一步指導(dǎo)用戶分析動(dòng)態(tài)網(wǎng)絡(luò)。Dang等[47]提出一種新穎的可視化展示形式TimeArcs來可視展示、分析動(dòng)態(tài)圖中的波動(dòng)模式。在TimeArcs構(gòu)建過程中，根據(jù)節(jié)點(diǎn)的權(quán)重和節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)聯(lián)強(qiáng)度，過濾出重要的關(guān)聯(lián)關(guān)系；并在力導(dǎo)向布局算法中添加限制，對剩余的節(jié)點(diǎn)及其關(guān)聯(lián)關(guān)系進(jìn)行布局。在可視化階段，采用直線表示節(jié)點(diǎn)，曲線連接2個(gè)具有關(guān)聯(lián)關(guān)系的節(jié)點(diǎn)。Elzen等[48]提出一種新穎的方法來分析動(dòng)態(tài)圖的變化模式。如圖9(c)所示（見彩插頁7），將每個(gè)時(shí)間步的網(wǎng)絡(luò)轉(zhuǎn)換成高維向量，將這些高維向量投影到二維平面，用點(diǎn)表示。投影后得到的布局中，每個(gè)點(diǎn)表示一個(gè)時(shí)間步的snapshot，每條邊連接了2個(gè)相鄰時(shí)刻的頂點(diǎn)。通過不同視圖間的關(guān)聯(lián)互動(dòng)可以有效地幫助用戶探索分析動(dòng)態(tài)圖的穩(wěn)定狀態(tài)、重現(xiàn)狀態(tài)、異常狀態(tài)以及狀態(tài)與狀態(tài)之間的轉(zhuǎn)移過程。

圖9 基于關(guān)聯(lián)性交互的網(wǎng)絡(luò)拓?fù)淇梢暦治?/p>

5.4 沉浸式模擬

沉浸式模擬通過在深度信息增強(qiáng)的虛擬環(huán)境中支持直接交互數(shù)據(jù)，為用戶提供一種更具體的主動(dòng)學(xué)習(xí)方式。Dede[49]的研究表明，沉浸式模擬借助多維視角、情境學(xué)習(xí)和場景變換，能夠幫助用戶個(gè)體更好地理解并保留空間信息，有效分析復(fù)雜現(xiàn)象。虛擬現(xiàn)實(shí)技術(shù)與網(wǎng)絡(luò)拓?fù)淇梢暬夹g(shù)的結(jié)合，從本質(zhì)上拓展了人機(jī)交互手段，有效地提高了分析和理解網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的效率和質(zhì)量。Tong等[50]將沉浸式引入三維圖可視化中，以O(shè)culus Rift + Leap Motion為開發(fā)平臺(tái)，借助空間變形模型和鏡頭形狀模型，在有效解決視覺遮擋等現(xiàn)象的同時(shí)，可保持三維空間結(jié)構(gòu)特征；并在沉浸式環(huán)境下凸顯深度信息，為解決三維圖可視化中視覺遮擋與覆蓋問題提供了新的思路，如圖10(a)所示（見彩插頁8）。在此基礎(chǔ)上，Huang等[51]針對沉浸式環(huán)境中的手勢交互問題，從直覺感受、操作可行性和符合人體工程學(xué)3個(gè)角度出發(fā)，設(shè)計(jì)了8種手勢交互動(dòng)作，并通過引入虛擬彈簧模型緩解原始手勢異常抖動(dòng)等問題；最后從精確度、操作難度、完成時(shí)間和用戶體驗(yàn)等方面驗(yàn)證沉浸式模擬下手勢交互在探索網(wǎng)絡(luò)結(jié)構(gòu)可視化方面的有效性。Kwon等[52]為了在沉浸式環(huán)境下取得更良好的立體視覺效果，將網(wǎng)絡(luò)節(jié)點(diǎn)通過球心投影算法映射到球面上，并采用球面線性插值改進(jìn)的de Boor算法將所有邊以邊綁定的方式呈現(xiàn)在球面的表面上，再采用深度路由方法將邊拉出球面，減少邊與點(diǎn)的交叉和遮擋，從而提高沉浸式環(huán)境下對網(wǎng)絡(luò)數(shù)據(jù)的分析理解精度和效率，如圖10(b)所示（見彩插頁8）。Cordeil等[53]則通過實(shí)驗(yàn)對比在傳統(tǒng)CAVE沉浸式虛擬現(xiàn)實(shí)環(huán)境和頭戴式設(shè)備HMD這2種沉浸式環(huán)境下完成網(wǎng)絡(luò)圖連通性探索任務(wù)時(shí)的性能表現(xiàn)、合作效果和用戶體驗(yàn)，證明HMD在完成分析任務(wù)的效率和沉浸式肢體交互性能上的優(yōu)越性，如圖10(c)所示（見彩插頁8）。

6 網(wǎng)絡(luò)拓?fù)淇梢暬ぞ?/h2>

網(wǎng)絡(luò)可視化工具種類、數(shù)量繁多，目前市場上主流的通用網(wǎng)絡(luò)可視化工具包括NodeXL、Gephi、Cytoscape、yEd、GraphViz等，這些工具功能豐富、適用性強(qiáng)，并不局限于特定的使用目的。其中，NodeXL是一個(gè)免費(fèi)的Execl插件，專門設(shè)計(jì)用于自動(dòng)收集社交網(wǎng)絡(luò)數(shù)據(jù)，為圖組織數(shù)據(jù)以及可視化圖，主要用于分析社交網(wǎng)絡(luò)。Gephi是一款開源、免費(fèi)跨平臺(tái)、基于JVM的復(fù)雜網(wǎng)絡(luò)分析軟件，主要用于各種網(wǎng)絡(luò)和復(fù)雜系統(tǒng)，動(dòng)態(tài)和分層圖的交互可視化與探測開源工具。Gephi提供了各類代表性圖布局方法并允許用戶進(jìn)行布局設(shè)置，支持時(shí)變網(wǎng)絡(luò)數(shù)據(jù)可視化并支持用戶實(shí)時(shí)過濾網(wǎng)絡(luò)，從過濾結(jié)果建立新網(wǎng)絡(luò)。Gephi使用聚類和分層圖的方法處理較大規(guī)模的圖，通過加速探索編輯大型分層結(jié)構(gòu)圖來探究多層圖，如社交區(qū)和網(wǎng)絡(luò)交通圖；利用數(shù)據(jù)屬性和內(nèi)置的聚類算法聚合圖網(wǎng)絡(luò)。Gephi適用于處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)，處理的圖規(guī)模上限約50 000個(gè)節(jié)點(diǎn)和10 000 000條邊。Cytoscape是一個(gè)提供開源的網(wǎng)絡(luò)可視化和分析軟件系統(tǒng)。Cytoscape提供了直觀的界面，可用來創(chuàng)建可視化及可視化交互，與其他軟件包相比，具有更加廣泛的視覺特性，靈活的映射、注釋和交互式輸出。幾乎任何視覺特性都可以被映射到數(shù)據(jù)，包括大小、顏色、節(jié)點(diǎn)邊框顏色、節(jié)點(diǎn)邊框?qū)挾取⒐?jié)點(diǎn)透明度、邊的線條類型、邊的透明度等。其最初是專注于生物網(wǎng)絡(luò)的可視化和相關(guān)數(shù)據(jù)的融合，隨著功能不斷地?cái)U(kuò)展，已經(jīng)成為面向各種復(fù)雜網(wǎng)絡(luò)的可視化工具。不過強(qiáng)項(xiàng)依然是生物網(wǎng)絡(luò)，最吸引人的是眾多的插件和強(qiáng)悍的數(shù)據(jù)融合能力以及其強(qiáng)悍的互動(dòng)能力。yEd提供了很強(qiáng)的通過鼠標(biāo)單擊創(chuàng)建和編輯圖的能力，能夠生成特殊類型的圖，同時(shí)提供許多健壯的布局和良好的標(biāo)簽處理能力，并能夠根據(jù)布局規(guī)則布置多次拐彎的連接。GraphViz是由貝爾實(shí)驗(yàn)室設(shè)計(jì)的一個(gè)開源的圖形繪制工具，支持Windows、linux和Mac等各種操作系統(tǒng)，使用一個(gè)特定的DSL（領(lǐng)域特定語言）——dot作為腳本語言，并使用布局引擎解析此腳本，提供自動(dòng)布局算法。GraphViz的dot腳本語言非常簡單方便，而且提供了大量的自動(dòng)布局算法和豐富的導(dǎo)出格式供用戶選擇。支持將結(jié)構(gòu)輸出整合到文本、網(wǎng)頁和應(yīng)用程序。它的強(qiáng)大還主要體現(xiàn)在“所思即所得”，即用GraphViz來繪圖時(shí)，GraphViz會(huì)安排好各種事情，不用自己思考太多。雖然這些工具或軟件包都有各自的功能特點(diǎn)，但在可擴(kuò)展性、大規(guī)模數(shù)據(jù)處理、表現(xiàn)方式優(yōu)化、自主可控等方面仍然存在諸多缺陷。

圖10 基于沉浸式模擬的網(wǎng)絡(luò)拓?fù)淇梢暦治?/p>

7 結(jié)束語

本文首先介紹了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化基本理論，從網(wǎng)絡(luò)數(shù)據(jù)自身特點(diǎn)和用戶需求角度分析網(wǎng)絡(luò)拓?fù)淇梢暬幕咎攸c(diǎn)與要求。結(jié)合近年的研究工作，總結(jié)了目前網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化研究中存在的主要挑戰(zhàn)。文中介紹了感知增強(qiáng)類網(wǎng)絡(luò)拓?fù)淇梢暬椒ǖ幕纠碚摚橄箢I(lǐng)域?qū)＜曳治隼斫饩W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)和連接狀況，洞察網(wǎng)絡(luò)拓?fù)湫畔⒅行阅芷款i、網(wǎng)絡(luò)安全、時(shí)變特性等潛在規(guī)律的過程，提出一個(gè)自頂向下的VPI分析流程模型，包括視覺接收、過程感知和交互參與，并以VPI模型為指導(dǎo)，從視覺感知增強(qiáng)、時(shí)變過程增強(qiáng)以及探索式交互增強(qiáng)3個(gè)方面分析目前網(wǎng)絡(luò)拓?fù)淇梢暬较蛑饕难芯窟M(jìn)展。其中，視覺感知增強(qiáng)類網(wǎng)絡(luò)拓?fù)淇梢暬椒òú季址绞絻?yōu)化和減少視覺混亂與遮擋這2個(gè)方面，從不同角度提高視覺空間表現(xiàn)力，從而提供更準(zhǔn)確的視覺認(rèn)知。時(shí)變過程增強(qiáng)類網(wǎng)絡(luò)拓?fù)淇梢暬〞r(shí)變過程動(dòng)畫和特征跟蹤，重點(diǎn)突出時(shí)變網(wǎng)絡(luò)數(shù)據(jù)的演化過程與復(fù)雜結(jié)構(gòu)，提高對動(dòng)態(tài)網(wǎng)絡(luò)的結(jié)構(gòu)感知、過程理解和時(shí)變認(rèn)知。探索式交互增強(qiáng)類網(wǎng)絡(luò)拓?fù)淇梢暬ń裹c(diǎn)+上下文、直接交互、關(guān)聯(lián)性交互和沉浸式模擬，通過不同類型的交互操作有效緩解了有限的可視化空間和數(shù)據(jù)過載之間的矛盾，幫助拓展可視化中信息表達(dá)的空間，實(shí)現(xiàn)從不同角度和不同顯示方式觀察數(shù)據(jù)，提高對復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的認(rèn)知深度。不同類型的感知增強(qiáng)類網(wǎng)絡(luò)拓?fù)淇梢暬椒ɑ驹怼⒑诵牟襟E與依賴條件各不相同，但都圍繞有效展現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征、各屬性間的相互作用及其復(fù)雜的時(shí)變網(wǎng)絡(luò)演化過程，為用戶提供良好的網(wǎng)絡(luò)拓?fù)淇梢暬治霏h(huán)境，提高網(wǎng)絡(luò)數(shù)據(jù)處理效率和可視分析能力這一研究目標(biāo)在進(jìn)行不斷的算法改進(jìn)和理論創(chuàng)新。

隨著數(shù)據(jù)規(guī)模的繼續(xù)擴(kuò)大，屬性信息的不斷增加，以及在用戶應(yīng)用需求方面精細(xì)化、實(shí)用化和普適性要求越來越高，給網(wǎng)絡(luò)拓?fù)淇梢暬牟煌芯糠椒◣硇碌陌l(fā)展機(jī)遇和挑戰(zhàn)。

1) 視覺感知增強(qiáng)方面。布局方式上的基本模型樣式趨于飽和，構(gòu)造更新穎的網(wǎng)絡(luò)拓?fù)洳季炙惴ú辉偈侵髁餮芯糠较颍于呄蛴谝远喾N可視化表現(xiàn)方式綜合繪制的方法提高視覺表現(xiàn)力。針對大規(guī)模網(wǎng)絡(luò)節(jié)點(diǎn)和邊的繪制所造成的視覺混亂和遮擋問題仍然會(huì)是主要難點(diǎn)問題。同時(shí)強(qiáng)調(diào)布局算法方法的普遍適用性和實(shí)用化，要求算法設(shè)計(jì)與用戶關(guān)心的對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的理解認(rèn)知緊密結(jié)合，促進(jìn)新技術(shù)方法的推廣應(yīng)用。

2) 時(shí)變過程增強(qiáng)方面。隨著數(shù)據(jù)的特殊性和結(jié)構(gòu)復(fù)雜性不斷提高、數(shù)據(jù)流的規(guī)模擴(kuò)大，如何在動(dòng)畫呈現(xiàn)中保持用戶的思維地圖，通過相對穩(wěn)定的布局方式有效應(yīng)對可能出現(xiàn)的網(wǎng)絡(luò)規(guī)模劇變等情況，減少大范圍的布局更新造成的認(rèn)知混亂和理解難度，有效呈現(xiàn)易于理解的層次結(jié)構(gòu)和特征時(shí)變演化過程，高效地挖掘和分析隨時(shí)間演變的流動(dòng)規(guī)律。

3) 探索式交互增強(qiáng)方面。直接交互方式將在大屏超分辨率繪制中發(fā)揮越來越重要的作用。同時(shí)隨著多變量網(wǎng)絡(luò)數(shù)據(jù)越來越復(fù)雜，網(wǎng)絡(luò)數(shù)據(jù)分析越來越抽象，研究重心將圍繞對數(shù)據(jù)屬性之間的關(guān)系和變化趨勢的分析。關(guān)聯(lián)性交互借助可視分析技術(shù)，深入探究網(wǎng)絡(luò)數(shù)據(jù)的深層隱含信息與特征之間的關(guān)聯(lián)性，在分析變量之間的相互關(guān)系以及建立數(shù)據(jù)空間和各種抽象空間的聯(lián)系方面有著無可替代的作用。同時(shí)隨著虛擬現(xiàn)實(shí)技術(shù)的火熱發(fā)展，沉浸式模擬將成為未來可視化展示的主流方式，先進(jìn)的增強(qiáng)現(xiàn)實(shí)技術(shù)如何借助輸入設(shè)備和顯示屏與可視化繪制過程完美結(jié)合，開展在通過沉浸式模擬和交互提高網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化質(zhì)量以及分析和理解網(wǎng)絡(luò)數(shù)據(jù)的效率等方面深入的研究勢在必行。

[1] ROHRER R, SWING E. Web-based information visualization[C]//IEEE Computer Graphics and Applications. 1997: 52-59.

[2] 王宇曉.大規(guī)模網(wǎng)絡(luò)拓?fù)淇梢暬芯縖D]. 北京：北京理工大學(xué), 2016.

WANG X Y. Research on large-scale network topology visualization[D]. Beijing: Beijing Institute of Technology, 2016.

[3] 張偉明, 羅軍勇, 王清賢. 網(wǎng)絡(luò)拓?fù)淇梢暬芯烤C述[J].計(jì)算機(jī)應(yīng)用研究, 2008, 25(6): 1606-1610. ZHANG W M, LUO J Y, WANG Q X. Survey on network topology visualization[J]. Application Research of Computers, 2008, 25(6): 1606-1610.

[4] GRAHAM J W. Nicheworks-interactive visualization of very large graphs[J]. Journal of Computational and Graphical Statistics, 1999, 8(2): 190-212.

[5] SUGIYAMA K, TAGAWA S, TODA M. Methods for visual understanding of hierarchical systems[J]. IEEE Transactions on Sys-tems Man & Cybermetics, 1981, 11(2):109-125.

[6] AU S C, LECKIE C, PARHAR A, et al. Efficient visualization of large routing topologies[J]. International Journal of Network Management, 2004, 14(2):105-118.

[7] 何鵬, 陸建新, 施佺, 等. 一種園區(qū)級網(wǎng)絡(luò)拓?fù)鋱D布局算法[J].微計(jì)算機(jī)信息, 2007, 23(3): 143-145.

HE P, LU J, SHI Q, et al. A campus scale network map layout algorithm[J]. Microcomputer Information, 2007, 23(3): 143-145.

[8] WARE C, PURCHASE H, COLPOYS L, et al. Cognitive measurements of graph aesthetics[J]. Information Visualization, 2002, 1(2): 103-110.

[9] CHATURVEDI S, DUNNE C, ASHKTORAB Z, et al. Group- in-a-box meta-layouts for topological clusters and attribute-based groups: space-efficient visualizations of network communities and their ties[J]. Computer Graphics Forum, 2014, 33(8): 52-68.

[10] YOGHOURDJIAN V, DWYER T, GANGE G, et al. High-quality ultra-compact grid layout of grouped networks[J]. IEEE Transactions on Visualization and Computer Graphics, 2016, 22(1): 339-348.

[11] WU Y, WU W, YANG S, et al. Interactive visual summary of major communities in a large network[C]// IEEE Pacific Visualization Symposium, 2015: 47-54.

[12] CUI W, ZHOU H, QU H, et al. Geometry-based edge clustering for graph visualization[J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 14(6):1277-1284.

[13] PENG D, LU N, CHEN W, et al. SideKnot: revealing relation pat-terns for graph visualization[C]//IEEE Pacific Visualization Symposium. 2012: 65-72.

[14] HURTER C, ERSOY O, TELEA A. Graph bundling by kernel density estimation[J]. Computer Graphics Forum, 2012, 31(3): 435-443.

[15] PEYSAKHOVICH V, HURTER C, TELEA A. Attribute-driven edge bundling for general graphs with applications in trail analysis[C]// IEEE Pacific Visualization Symposium. 2015: 39-46.

[16] BACH B, RICHE N H, HURTER C, et al. Towards unambiguous edge bundling: investigating confluent drawings for network visualization[J]. IEEE Transactions on Visualization and Computer Graphics, 2016, 23(1):541-550.

[17] BOUTS Q W, SPECKMANN B. Clustered edge routing[C]// IEEE Pacific Visualization Symposium. 2015: 55-62.

[18] ROSVALL M, BERGSTROM C T. Maps of random walks on complex networks reveal community structure[C]//The National Academy of Sciences of the United States of America, 2008, 105(4): 1118-1123.

[19] LIAO Q, SHI L, WANG C. Visual analysis of large-scale network anomalies[J]. IBM Journal of Research and Development, 2013, 57(3/4): 13: 1-13.

[20] SHI L, LIAO Q, TONG H, et al. Hierarchical Focus+Context Het-erogeneous network visualization[C]//IEEE Pacific Visualization Symposium. 2014:89-96.

[21] ZINSMAIER M, BRANDES U, DEUSSEN O, et al. Interactive level-of-detail rendering of large graphs[J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(12): 2486-2495.

[22] BENJAMIN B, EMMANUEL P, JEAN-DANIEL F. GraphDiaries: animated transitions and temporal navigation for dynamic networks[J]. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(5): 740-754.

[23] GRIFFEN A L, MACEACHREN A M, HARDISTY F, et al. A comparison of animated maps with static small-multiple maps for visually identifying space-time clusters[J]. Annals of the Association of American Geographers, 2006, 96(4): 740-753.

[24] LIN C C, LEE Y Y, YEN H C. Mental map preserving graph drawing using simulated annealing[J]. Information Science, 2011, 181(19): 4253-4272.

[25] FRISHMAN Y, TAL A. Dynamic drawing of clustered graphs[C]// IEEE Symposium on Information Visualization. 2004: 191-198.

[26] FISHERMAN Y, TAL A. Online dynamic graph drawing[J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 14(4): 727-740.

[27] CHE L, LIANG J, YUAN X, et al. Laplacian-based dynamic graph visualization[C]//IEEE Pacific Visualization Symposium. 2015: 69-73.

[28] KUMAR G, GARLAND M. Visual exploration of complex time-varying graphs[J]. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(5): 805-812.

[29] JAMES A, STEFFEN H, HEIDRUN S, et al. A modular degree-of-interest specification for the visual analysis of large dynamic networks[J]. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(3): 337-350.

[30] CUI W, WANG X, LIU S, et al. Let it flow: a static method for exploring dynamic graphs[C]//IEEE Pacific Visualization Symposium. 2014: 121-128.

[31] SHNEIDERMAN B. The eye have it: a task by data type taxonomy for information visualization[C]//IEEE Symposium on Visual Languages. 1996: 336-343

[32] KEIN D A. Information visualization and visual data mining[J]. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(3): 377-390

[33] WARD M O, YANG J. Interaction spaces in data and information visualization[C]//The 6th Joint Euro graphics/IEEE TCVG Symposium on Visualization. 2004: 137-146

[34] ROBERT B, GLENN A F, CHRIS N. Home-centric visualization of network traffic for security administration[C]//The ACM Workshop on Visualization and Data Mining for Computer Security. 2004, 55-64.

[35] FENG K C, WANG C, SHEN H W, et al. Coherent time-varing graph drawing with multifocus+context interaction[J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(8): 1330-1342.

[36] BENJAMN B B, AARON C, MARY P C, et al. DateLens: a fisheye calendar interface for PDAs[J]. ACM Transactions on Computer-Human Interaction, 2004, 11(1): 90-119.

[37] TOMINSKI C, ABELLO J, VAN HAM F, et al. Fisheye tree views and lenses for graph visualization[C]//The Conference on Information Visualization. 2006: 17-24.

[38] VAN-HAM F, VAN-WIJK J J. Interactive visualization of small world graphs[C]//The IEEE Symposium on Information Visualization. 2004: 199-206.

[39] GANSNER E R, KOREN Y, NORTH S C. Topological fisheye views for visualizing large graphs[J]. IEEE Transactions on Visualization and Computer Graphics, 2005, 20(5): 740-754.

[40] FRISCH M, HEYDEKORN J, DACHSELT R. Diagram editing on interac-tive displays using multi-touch and pen gestures[C]//The 6th international conference on Diagrammatic representation and inference. 2010: 182-196.

[41] SCHMIDT S, NACENTA M A, DACHSELT R, et al. A set of multi-touch graph interaction techniques[C]//ACM International Conference on Interactive Tabletops and Surfaces. 2010:113-116.

[42] PROUZEAU A, BEZERIANOS A, CHAPUIS O. Evaluating multi-user selection for exploring graph topology on wall-displays[J]. IEEE Transactions on Visualization and Computer Graphics, 2017, 23(8):1936-1951.

[43] KISTER U, KLAMKA K, TOMINSKI C,et al. GRASP: combining spatially-aware mobile devices and a display wall for graph visualization and interaction[J]. Computer Graphics Forum, 2017, 36(3): 503-514.

[44] RUFIANGE S, MCGUFFIN M J. DiffAni: visualizing dynamic graphs with a hybrid of difference maps and animation[J]. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(12):2556-2565.

[45] KO S, AFZAL S, WALTON S, et al. Analyzing high-dimensional mul-tivariate network links with integrated anomaly detection, highlighting and exploration[C]//The IEEE Vis-ual Science and Technology.Los Alamitos: IEEE Computer So-ciety Press, 2014: 823-825.

[46] HADLAK S, SCHUMANN H, CAP C H, et al. Supporting the visual analysis of dynamic networks by clustering associated temporal Attributes[J]. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(12): 2267-2276.

[47] DANG T N, PENDAR N, FORBES A G. TimeArcs: visualizing fluctuations in dynamic networks[J]. Computer Graphics Forum, 2016, 35(3):61-69.

[48] ELZEN S V D, HOLTEN D, BLAAS J, et al. Reducing snapshots to points: a visual analytics approach to dynamic network exploration[J]. IEEE Transactions on Visualization and Computer Graphics, 2016, 22(1): 1-10.

[49] DEDE C. Immersive interface for engagement and learning[J]. Science, 2009, 323(5910): 66-69.

[50] TONG X, LI C, SHEN H W. GlyphLens: view-dependent occlusion management in the interactive glyph visualization[J]. IEEE Transactions on Visualization and Computer Graphics, 2017, 23(1): 891-900.

[51] HUANG Y J, FUJIWARA T, LIN Y X, et al. A gesture system for graph visualization in virtual reality environments[C]//IEEE VGTC Pacific Visualization Symposium. 2017: 41-45.

[52] KWON O H, MUELDER C, LEE K, et al. A study of layout, rendering, and interaction methods for immersive graph visualization[J]. IEEE Transactions on Visualization and Computer Graphics, 2016, 22(7): 1802-1815.

[53] CORDEIL M, DWYER T, KLEIN K, et al. Immersive collaborative analysis of network connectivity: CAVE-style or head-mounted display?[J]. IEEE Transactions on Visualization and Computer Graphics, 2016, 23(1): 441-450.

Survey on network topology visualization

WANG Song1,2, ZHANG Ye1, WU Yadong1

1. School of Computer and Technology, Southwest University of Science and Technology, Mianyang 621010, China 2. Institute of Electronic Engineering, China Academy of Engineering Physics, Mianyang 621010, China

As the basis of network monitoring, network management, and network security situation awareness, network topology visualization plays an underlying role in reflecting the whole state of the network and discovering the potential rules in the network topology. The basic content of network topology visualization was introduced and the main challenges in the research of network topology visualization were summarized from two aspects: the internal characteristics of network data and the point of the applied demand angle of the users. A top-down VPI model for network topology visualization and analysis drawing from the experience of domain experts by analyzing and understanding the nodes and connection status of network topology, having an insight into the potential laws of topological information like performance bottleneck, network security, time-varying characteristics and so on. This model includes vision, procedure, and interaction. According to the VPI model, visualization methods based on perception enhance were summarized from three aspects: enhancement of visual perception, enhancement of time-varied procedure and enhancement of exploratory interaction. Finally, future development trend of those topics were discussed combined with application demand.

enhancement of visual perception, enhancement of time-varied procedure, enhancement of exploratory interaction, VPI model

TP393

A

10.11959/j.issn.2096-109x.2018014

王松（1989-），男，安徽安慶人，中國工程物理研究院博士生，主要研究方向?yàn)榭茖W(xué)可視化、可視分析。

張野（1994-），男，四川樂山人，西南科技大學(xué)碩士生，主要研究方向?yàn)榫W(wǎng)絡(luò)安全可視化。

吳亞東（1979-），男，河南周口人，博士，西南科技大學(xué)教授，主要研究方向?yàn)閳D像圖形處理、可視化與可視分析。

2018-01-03；

2018-02-04

吳亞東，wyd028@163.com

科技部“前沿科技創(chuàng)新”專項(xiàng)基金資助項(xiàng)目（No.2016QY04W0801）；四川省科技廳基金資助項(xiàng)目（No.2017TJPT0200, No.2017KZ0023, No.2017GZ0186）

: The National Key Research and Development Program of China (No.2016QY04W0801), Project of Science and Technology Department of Sichuan Province (No.2017TJPT0200, No.2017KZ0023, No.2017GZ0186)