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

王松，張野，吳亞?wèn)|

?

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

王松1,2，張野1，吳亞?wèn)|1

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

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化作為網(wǎng)絡(luò)檢測(cè)管理和網(wǎng)絡(luò)安全態(tài)勢(shì)感知的基礎(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)和用戶(hù)需求角度分析目前網(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ī)律的過(guò)程，提出一個(gè)自頂向下的VPI分析流程模型，包括視覺(jué)接收、過(guò)程感知和交互參與。以VPI模型為指導(dǎo)，從視覺(jué)感知增強(qiáng)、時(shí)變過(guò)程增強(qiáng)以及探索式交互增強(qiáng)3個(gè)方面綜述了網(wǎng)絡(luò)拓?fù)淇梢暬椒ǖ难芯楷F(xiàn)狀，并結(jié)合應(yīng)用需求展望未來(lái)的發(fā)展趨勢(shì)。

視覺(jué)感知增強(qiáng)；時(shí)變過(guò)程增強(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)對(duì)整個(gè)網(wǎng)絡(luò)的運(yùn)行狀態(tài)進(jìn)行及時(shí)有效的監(jiān)測(cè)和控制?？梢暬且环N通過(guò)交互式可視化界面來(lái)輔助用戶(hù)對(duì)大規(guī)模復(fù)雜數(shù)據(jù)集進(jìn)行分析推理的科學(xué)與技術(shù)，將數(shù)據(jù)中各種抽象的信息轉(zhuǎn)化為圖形信息，并通過(guò)各種圖形交互技術(shù)，使人們加深對(duì)信息的理解和認(rèn)識(shí)。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化將網(wǎng)絡(luò)節(jié)點(diǎn)的連接關(guān)系以點(diǎn)和線(xiàn)等構(gòu)成的圖形圖像[1]進(jìn)行呈現(xiàn)，能夠清晰直觀地反映網(wǎng)絡(luò)運(yùn)行狀況，輔助人們對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)、鏈路等各方面進(jìn)行評(píng)估、預(yù)測(cè)和分析，有效地認(rèn)識(shí)和了解網(wǎng)絡(luò)內(nèi)部信息、規(guī)律和變化[2]。

近年來(lái)，計(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)分析研究帶來(lái)了巨大的挑戰(zhàn)。要及時(shí)、快速、正確、完整地獲取網(wǎng)絡(luò)拓?fù)湫畔?，生成清晰穩(wěn)定的拓?fù)鋱D，以圖形方式將網(wǎng)絡(luò)結(jié)構(gòu)中的節(jié)點(diǎn)和連接狀況清晰展現(xiàn)出來(lái)，為用戶(hù)理解、分析目標(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ù)淇梢暬蕴岢鲆詠?lái)經(jīng)過(guò)多年的發(fā)展，已經(jīng)取得了顯著的成果，在一定程度上解決了大量網(wǎng)絡(luò)數(shù)據(jù)和有效分析手段之間的矛盾。但隨著網(wǎng)絡(luò)數(shù)據(jù)規(guī)模劇增、拓?fù)浣Y(jié)構(gòu)復(fù)雜性增強(qiáng)，直接對(duì)其進(jìn)行可視化會(huì)導(dǎo)致顯示重疊、層次信息難以觀察等問(wèn)題，無(wú)法有效降低網(wǎng)絡(luò)分析人員的負(fù)擔(dān)。針對(duì)上述問(wèn)題并結(jié)合領(lǐng)域需求，總結(jié)目前網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化研究中主要存在的挑戰(zhàn)如下。1) 網(wǎng)絡(luò)節(jié)點(diǎn)和連邊數(shù)目過(guò)大時(shí)，借助多樣化的布局方式能夠有效觀察網(wǎng)絡(luò)整體拓?fù)浣Y(jié)構(gòu)。布局算法主要需要解決如何確定和分配映射在有限顯示空間內(nèi)幾何圖形的各個(gè)節(jié)點(diǎn)和邊的具體位置，良好的拓?fù)洳季炙惴軌蛴行У乇苊怙@示出來(lái)的拓?fù)浣Y(jié)構(gòu)圖中節(jié)點(diǎn)的重疊，能夠大大地減少拓?fù)浣Y(jié)構(gòu)圖中邊之間的交叉，能夠更加美觀大方地展示出要處理的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。2) 針對(duì)網(wǎng)絡(luò)時(shí)變數(shù)據(jù)在時(shí)空演化過(guò)程中可能出現(xiàn)的網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)結(jié)構(gòu)劇變等情況，提供穩(wěn)定的布局方式來(lái)避免大范圍的布局更新造成的認(rèn)知混亂和理解難度。網(wǎng)絡(luò)時(shí)變數(shù)據(jù)中包含的網(wǎng)絡(luò)節(jié)點(diǎn)種類(lèi)與數(shù)目在隨時(shí)間不斷變化，網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接也在不斷出現(xiàn)與消失，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在節(jié)點(diǎn)出現(xiàn)與消失的過(guò)程中不斷發(fā)生變化。穩(wěn)定的布局方式能夠保證在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)大范圍變化的過(guò)程中用戶(hù)的關(guān)注焦點(diǎn)不會(huì)發(fā)生突變，保持用戶(hù)認(rèn)知過(guò)程的連續(xù)性，降低對(duì)時(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é)的特征分析過(guò)程。借助可視分析技術(shù)，用戶(hù)可以觀察并分析不同時(shí)間粒度下網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的時(shí)變演化過(guò)程，逐層深入分析探究感興趣區(qū)域節(jié)點(diǎn)的內(nèi)部結(jié)構(gòu)及其在整個(gè)拓?fù)浣Y(jié)構(gòu)中的作用，對(duì)比觀察網(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ī)律的過(guò)程，提出一個(gè)自頂向下的VPI分析流程模型，包括視覺(jué)接收（vision）、過(guò)程感知（procedure）和交互參與（interaction）。該模型的主體思想是：提取網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征進(jìn)行幾何映射，用戶(hù)對(duì)繪制結(jié)果進(jìn)行觀察分析完成視覺(jué)接收，對(duì)于時(shí)變數(shù)據(jù)通過(guò)動(dòng)畫(huà)模擬等表達(dá)方式展現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)時(shí)變演化過(guò)程，從而幫助用戶(hù)思考?xì)w納，構(gòu)建對(duì)網(wǎng)絡(luò)數(shù)據(jù)時(shí)效性的基本理解；然后通過(guò)不斷迭代的交互反饋優(yōu)化繪制結(jié)果，并借助其他硬件輔助設(shè)備完善用戶(hù)對(duì)大規(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)的幾種常見(jiàn)分析思路。1) 由整體到局部，通過(guò)可視化呈現(xiàn)掌握整體網(wǎng)絡(luò)布局結(jié)構(gòu)，基于Foucs+Context理論實(shí)現(xiàn)迭代交互全方面展示用戶(hù)感興趣區(qū)域或節(jié)點(diǎn)的連接關(guān)系與運(yùn)行態(tài)勢(shì)。2) 由表面到內(nèi)部，可視化繪制結(jié)果給用戶(hù)直觀的視覺(jué)感知，借助交互操作與先進(jìn)的硬件設(shè)備洞察網(wǎng)絡(luò)拓?fù)渖顚觾?nèi)部結(jié)構(gòu)，完成對(duì)網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的立體剖析。3) 由生疑到解惑，對(duì)于生成的網(wǎng)絡(luò)拓?fù)淇梢暬尸F(xiàn)，用戶(hù)針對(duì)不同方面產(chǎn)生的問(wèn)題，通過(guò)基于視覺(jué)認(rèn)知的人機(jī)交互與硬件優(yōu)化，最終理解并解決復(fù)雜的網(wǎng)絡(luò)監(jiān)測(cè)、性能優(yōu)化、故障分析和安全評(píng)估等問(wèn)題。綜合近幾年網(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)展劃分為視覺(jué)感知增強(qiáng)、時(shí)變過(guò)程增強(qiáng)以及探索式交互增強(qiáng)3個(gè)方面。圖1是基于VPI模型的網(wǎng)絡(luò)拓?fù)淇梢暬诸?lèi)結(jié)構(gòu)的示意，本文按照該分類(lèi)策略系統(tǒng)地整理了近幾年大部分代表性網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化工作。

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

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

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

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

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

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

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

3.2 減少視覺(jué)混亂與遮擋

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

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

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

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

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

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

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

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

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

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

4.2 特征跟蹤

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

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

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

網(wǎng)絡(luò)拓?fù)淇梢暬惴ǔ艘曈X(jué)呈現(xiàn)部分，另外一個(gè)核心要素是用戶(hù)交互。交互是用戶(hù)通過(guò)與系統(tǒng)之間的對(duì)話(huà)和互動(dòng)操作和理解數(shù)據(jù)的過(guò)程。交互操作有效地緩解了有限的可視化空間和數(shù)據(jù)過(guò)載之間的矛盾，幫助拓展可視化中信息表達(dá)的空間，從而解決有限空間與數(shù)據(jù)量和復(fù)雜度之間的差距。同時(shí)交互能讓用戶(hù)更好地參與對(duì)數(shù)據(jù)的理解和分析，幫助用戶(hù)探索數(shù)據(jù)、提高視覺(jué)認(rèn)知。Shneiderman[31]早期提出可視化信息搜索的基本原則，歸納了幾種最基本交互操作，包括概覽、縮放、過(guò)濾、按需提供細(xì)節(jié)、關(guān)聯(lián)、記錄和提取。Kein[32]提出了5類(lèi)交互模式：投影、過(guò)濾、縮放、失真變形、鏈接與刷動(dòng)。Ward等[33]在按照交互操作分類(lèi)的基礎(chǔ)上，進(jìn)一步提出了更完善的框架，定義交互為操作符和操作空間的組合。其中，操作符包括3類(lèi)：導(dǎo)航、選擇和變形；操作空間包括6種：屏幕空間、數(shù)據(jù)值空間、數(shù)據(jù)結(jié)構(gòu)空間、屬性空間、對(duì)象空間和可視化結(jié)構(gòu)空間。大多可視化中交互技術(shù)都可以按照上面描述的操作符和操作空間表示。綜合近幾年網(wǎng)絡(luò)拓?fù)淇梢暬矫娴慕换パ芯?，主要的研究熱點(diǎn)如下。1) 焦點(diǎn)+上下文交互。致力于顯示用戶(hù)興趣焦點(diǎn)部分的細(xì)節(jié)信息，同時(shí)體現(xiàn)焦點(diǎn)和周邊的關(guān)系關(guān)聯(lián)，整合當(dāng)前聚焦點(diǎn)的細(xì)節(jié)信息與概覽部分的上下文信息。2) 直接交互。通過(guò)直觀的交互方式直接操作于可視化繪制結(jié)果，提高交互效率與交互結(jié)果的可預(yù)測(cè)性，降低用戶(hù)認(rèn)知困難、精力分散等交互障礙。3) 關(guān)聯(lián)性交互。借助可視分析技術(shù)，深入探究網(wǎng)絡(luò)數(shù)據(jù)的深層隱含信息與特征之間的關(guān)聯(lián)性，采用多視圖等表達(dá)方式幫助用戶(hù)同時(shí)觀察網(wǎng)絡(luò)的不同屬性，支持從不同角度和不同顯示方式觀察數(shù)據(jù)，提高對(duì)復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的認(rèn)知深度。4) 沉浸式模擬。它是虛擬現(xiàn)實(shí)技術(shù)與網(wǎng)絡(luò)拓?fù)淇梢暬夹g(shù)的有效結(jié)合，借助直觀的立體成像、三維交互、立體聽(tīng)覺(jué)和三維觸覺(jué)反饋等保證用戶(hù)在虛擬環(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)域的常用交互方式，其基本思想是將用戶(hù)關(guān)心的區(qū)域定義為焦點(diǎn)區(qū)域，采用高亮等方式顯示細(xì)粒度信息；其他區(qū)域作為上下文區(qū)域，通過(guò)聚合等操作顯示粗粒度信息。該概念被引入網(wǎng)絡(luò)拓?fù)淇梢暬泻?，在提高繪制效率的同時(shí)，能夠有效地處理龐大數(shù)據(jù)集中提取用戶(hù)感興趣部分的問(wèn)題，有利于解決三維映射阻塞現(xiàn)象，受到大量網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化研究人員的青睞。Robert等[34]開(kāi)發(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ī)分布在四周，從連線(xiàn)的多少和外網(wǎng)主機(jī)方塊大小可以很直觀地發(fā)現(xiàn)一些異?；钴S的內(nèi)外網(wǎng)主機(jī)，主機(jī)位置固定策略能夠保持良好的主機(jī)邏輯拓?fù)潢P(guān)系。支持“先概覽，然后縮放和過(guò)濾，最后根據(jù)需求詳細(xì)分析”的交互過(guò)程幫助用戶(hù)建立對(duì)網(wǎng)絡(luò)活動(dòng)模式的精準(zhǔn)理解。文獻(xiàn)[20]提出的可視化集成框架OnionGraph中，網(wǎng)絡(luò)節(jié)點(diǎn)的子集可以在分層的焦點(diǎn)+上下文交互模型下進(jìn)行靈活的分割和合并。通過(guò)交互式探索，用戶(hù)可以在網(wǎng)絡(luò)上創(chuàng)建多個(gè)分層的焦點(diǎn)，每個(gè)聚焦的子網(wǎng)絡(luò)都與獨(dú)立的抽象概況相關(guān)聯(lián)，從而實(shí)現(xiàn)對(duì)復(fù)雜網(wǎng)絡(luò)的多層次分析。Feng等[35]提供一種新的時(shí)變網(wǎng)絡(luò)繪制方法，采用超圖的概念保持網(wǎng)絡(luò)數(shù)據(jù)的時(shí)空一致性，同時(shí)支持多焦點(diǎn)+上下文的交互方式維持交互過(guò)程的動(dòng)態(tài)穩(wěn)定性，通過(guò)阻止節(jié)點(diǎn)尺寸和位置發(fā)現(xiàn)突變來(lái)保護(hù)用戶(hù)的思維地圖，從而提供可讀性更強(qiáng)的視覺(jué)效果，如圖7(a)所示（見(jiàn)彩插頁(yè)6）。魚(yú)眼變換[36]也是一種基于焦點(diǎn)+上下文技術(shù)的常用交互手段，它使用一種焦距極短并且視角接近于180°的鏡頭，在突出正前方物體的基礎(chǔ)上，覆蓋角度所及的范圍最廣。通過(guò)魚(yú)眼技術(shù)在網(wǎng)絡(luò)拓?fù)鋱D分析過(guò)程中可以根據(jù)用戶(hù)關(guān)注的焦點(diǎn)進(jìn)行有針對(duì)性的縮放，從而揭示局部區(qū)域內(nèi)節(jié)點(diǎn)的連接關(guān)系。Tominski等[37]采用魚(yú)眼樹(shù)形視圖和組合透鏡來(lái)支持對(duì)網(wǎng)絡(luò)拓?fù)湟晥D的可視化探索。如圖7(b)所示（見(jiàn)彩插頁(yè)6），通過(guò)魚(yú)眼扭曲算法實(shí)現(xiàn)對(duì)聚類(lèi)圖層次結(jié)構(gòu)的分析，組合透鏡技術(shù)促進(jìn)對(duì)大規(guī)模稠密拓?fù)洳季值男畔⒊尸F(xiàn)，其中，局部邊透鏡用于解決圖的邊遮擋問(wèn)題，鄰居透鏡用于呈現(xiàn)當(dāng)前聚焦節(jié)點(diǎn)的鄰接節(jié)點(diǎn)。Van等[38]將網(wǎng)絡(luò)拓?fù)渚垲?lèi)抽象成大顆粒的節(jié)點(diǎn)，同時(shí)邊也根據(jù)聚類(lèi)特征聚合為不同粗細(xì)的集束，當(dāng)用戶(hù)希望瀏覽具體的細(xì)節(jié)時(shí)，可通過(guò)透鏡將抽象結(jié)構(gòu)逐級(jí)細(xì)化，最終分解成準(zhǔn)確的結(jié)構(gòu)。如圖7(c)所示（見(jiàn)彩插頁(yè)6），當(dāng)透鏡接近顆粒時(shí)，顆粒開(kāi)始分解，完全被透鏡覆蓋的區(qū)域顯示具體而準(zhǔn)確的圖結(jié)構(gòu)。針對(duì)規(guī)模特別龐大的圖結(jié)構(gòu)，Gansner等[39]提出拓?fù)漪~(yú)眼技術(shù)，先計(jì)算出復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在不同尺度下簡(jiǎn)化后的結(jié)構(gòu)表達(dá)，當(dāng)用戶(hù)指定了關(guān)注區(qū)域后，不同層級(jí)的簡(jiǎn)化結(jié)構(gòu)表達(dá)被混合顯示，以達(dá)到從關(guān)注區(qū)域到外沿細(xì)節(jié)不斷減少的效果，最后在關(guān)注區(qū)域?qū)嵤~(yú)眼式的徑向放大，從而既保持足夠的細(xì)節(jié)信息，又不丟失原圖結(jié)構(gòu)粗略的輪廓。

5.2 直接交互

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

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

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

5.4 沉浸式模擬

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

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

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

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

7 結(jié)束語(yǔ)

本文首先介紹了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化基本理論，從網(wǎng)絡(luò)數(shù)據(jù)自身特點(diǎn)和用戶(hù)需求角度分析網(wǎng)絡(luò)拓?fù)淇梢暬幕咎攸c(diǎn)與要求。結(jié)合近年的研究工作，總結(jié)了目前網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化研究中存在的主要挑戰(zhàn)。文中介紹了感知增強(qiáng)類(lèi)網(wǎng)絡(luò)拓?fù)淇梢暬椒ǖ幕纠碚?，抽象領(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ī)律的過(guò)程，提出一個(gè)自頂向下的VPI分析流程模型，包括視覺(jué)接收、過(guò)程感知和交互參與，并以VPI模型為指導(dǎo)，從視覺(jué)感知增強(qiáng)、時(shí)變過(guò)程增強(qiáng)以及探索式交互增強(qiáng)3個(gè)方面分析目前網(wǎng)絡(luò)拓?fù)淇梢暬较蛑饕难芯窟M(jìn)展。其中，視覺(jué)感知增強(qiáng)類(lèi)網(wǎng)絡(luò)拓?fù)淇梢暬椒òú季址绞絻?yōu)化和減少視覺(jué)混亂與遮擋這2個(gè)方面，從不同角度提高視覺(jué)空間表現(xiàn)力，從而提供更準(zhǔn)確的視覺(jué)認(rèn)知。時(shí)變過(guò)程增強(qiáng)類(lèi)網(wǎng)絡(luò)拓?fù)淇梢暬〞r(shí)變過(guò)程動(dòng)畫(huà)和特征跟蹤，重點(diǎn)突出時(shí)變網(wǎng)絡(luò)數(shù)據(jù)的演化過(guò)程與復(fù)雜結(jié)構(gòu)，提高對(duì)動(dòng)態(tài)網(wǎng)絡(luò)的結(jié)構(gòu)感知、過(guò)程理解和時(shí)變認(rèn)知。探索式交互增強(qiáng)類(lèi)網(wǎng)絡(luò)拓?fù)淇梢暬ń裹c(diǎn)+上下文、直接交互、關(guān)聯(lián)性交互和沉浸式模擬，通過(guò)不同類(lèi)型的交互操作有效緩解了有限的可視化空間和數(shù)據(jù)過(guò)載之間的矛盾，幫助拓展可視化中信息表達(dá)的空間，實(shí)現(xiàn)從不同角度和不同顯示方式觀察數(shù)據(jù)，提高對(duì)復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的認(rèn)知深度。不同類(lèi)型的感知增強(qiáng)類(lèi)網(wǎng)絡(luò)拓?fù)淇梢暬椒ɑ驹怼⒑诵牟襟E與依賴(lài)條件各不相同，但都圍繞有效展現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征、各屬性間的相互作用及其復(fù)雜的時(shí)變網(wǎng)絡(luò)演化過(guò)程，為用戶(hù)提供良好的網(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ò)大，屬性信息的不斷增加，以及在用戶(hù)應(yīng)用需求方面精細(xì)化、實(shí)用化和普適性要求越來(lái)越高，給網(wǎng)絡(luò)拓?fù)淇梢暬牟煌芯糠椒◣?lái)新的發(fā)展機(jī)遇和挑戰(zhàn)。

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

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

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

[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ū)級(jí)網(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-），男，安徽安慶人，中國(guó)工程物理研究院博士生，主要研究方向?yàn)榭茖W(xué)可視化、可視分析。

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

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

2018-01-03；

2018-02-04

吳亞?wèn)|，wyd028@163.com

科技部“前沿科技創(chuàng)新”專(zhuān)項(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)