基于分層的邊折疊節(jié)點(diǎn)鏈接法

摘 "要： 為兼顧網(wǎng)絡(luò)結(jié)構(gòu)地理空間特征的同時(shí)，減輕視覺混亂和密度位置信息丟失的問題，文中對(duì)節(jié)點(diǎn)鏈接方法進(jìn)行改進(jìn)，給出基于分層的邊折疊網(wǎng)絡(luò)可視化方法。首先，在對(duì)節(jié)點(diǎn)位置布局時(shí)，采用位置固定的節(jié)點(diǎn)鏈接法保證地理空間特征；其次，結(jié)合用戶交互，從邊折疊的角度改進(jìn)節(jié)點(diǎn)鏈接法，從而緩解常規(guī)節(jié)點(diǎn)鏈接法的遮擋交叉和信息丟失問題；最后，以中國航線網(wǎng)絡(luò)進(jìn)行實(shí)例驗(yàn)證。結(jié)果表明，與節(jié)點(diǎn)位置固定的節(jié)點(diǎn)鏈接法和基于力引導(dǎo)的節(jié)點(diǎn)鏈接法相比，改進(jìn)的節(jié)點(diǎn)鏈接法極大地降低了交叉點(diǎn)數(shù)量，能夠有效緩解邊遮擋引起的視覺混亂問題，提高網(wǎng)絡(luò)可視化的效果和準(zhǔn)確性。

關(guān)鍵詞： 航線網(wǎng)絡(luò)； 網(wǎng)絡(luò)結(jié)構(gòu)可視分析； 地理空間特征； 節(jié)點(diǎn)鏈接法； 視覺混亂； 邊折疊

中圖分類號(hào)： TN711?34； TP39 " " " " " " " " " " "文獻(xiàn)標(biāo)識(shí)碼： A " " " " " " " " " " 文章編號(hào)： 1004?373X（2024）21?0075?08

Node link method based on hierarchical edge folding

HE Huaiqing， SONG Miao， LIU Haohan

（College of Computer Science and Technology， Civil Aviation University of China， Tianjin 300300， China）

Abstract： In order to reduce the visual confusion and the loss of density and location information while taking into account the geospatial features of network structure， the node link method is improved and a hierarchical edge folding network visualization method is presented. When arranging node locations， the node link method with fixed position is used to ensure geospatial features. In combination with user interaction， the node link method is improved in the perspective of edge folding， so as to alleviate the occlusion intersection and information loss in the conventional node link methods. China′s route network is used for example verification. The results show that， in comparison with the node link method with fixed node location and the force?directed node link method， the improved node link method reduces the number of intersections greatly， effectively alleviates the visual confusion caused by edge occlusion， and improves the effect and accuracy of network visualization.

Keywords： route network; network structure visual analysis; geospatial feature; node link method; visual confusion; edge folding

0 "引 "言

隨著社會(huì)的不斷發(fā)展，航線網(wǎng)絡(luò)作為航空運(yùn)輸實(shí)現(xiàn)的載體，其規(guī)模呈現(xiàn)出不斷擴(kuò)大的趨勢(shì)，且網(wǎng)絡(luò)結(jié)構(gòu)越來越復(fù)雜。目前，我國民航業(yè)中還存在航線網(wǎng)絡(luò)布局不合理、資源浪費(fèi)等問題，需要對(duì)航線網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行優(yōu)化，以促進(jìn)民航運(yùn)輸持續(xù)發(fā)展，完善交通運(yùn)輸體系。為分析航線網(wǎng)絡(luò)結(jié)構(gòu)現(xiàn)狀，研究者們主要采用數(shù)理統(tǒng)計(jì)和網(wǎng)絡(luò)拓?fù)浞治鯷1?2]方法從航班、機(jī)場(chǎng)和航空公司[3?4]等角度進(jìn)行分析，對(duì)航線網(wǎng)絡(luò)賦予權(quán)重進(jìn)行建模分析。與可視分析相比，這些數(shù)據(jù)信息的模型化方法無法直觀展示航線網(wǎng)絡(luò)結(jié)構(gòu)特性，無法分析數(shù)據(jù)之間的關(guān)聯(lián)，優(yōu)化建議偏理想。

航線網(wǎng)絡(luò)是一種典型的復(fù)雜網(wǎng)絡(luò)，而已有的網(wǎng)絡(luò)可視化方法[5?6]在解決具有地理空間特征的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)時(shí)存在以下缺陷：

1） 最常用于網(wǎng)絡(luò)可視化的方法是基于力引導(dǎo)布局的節(jié)點(diǎn)鏈接法，包括最早由Eades等提出的FDA（Force?directed Algorithm）彈力模型，在此基礎(chǔ)上由Kamada等人引入胡克定律的KK模型，F(xiàn)ruchterman等人通過模擬原子間斥力、引力提出的FR模型等，近些年大部分力引導(dǎo)方法都是基于以上模型，從美學(xué)原則、數(shù)據(jù)規(guī)模、算法效率等角度進(jìn)行優(yōu)化[7?11]。在實(shí)際應(yīng)用中，航線網(wǎng)絡(luò)是一種地理空間數(shù)據(jù)，基于力引導(dǎo)的節(jié)點(diǎn)鏈接法難以表示其空間特征和屬性特征。

2） 位置固定的節(jié)點(diǎn)鏈接法是最基本的節(jié)點(diǎn)鏈接法，將位置屬性作為節(jié)點(diǎn)布局（其他布局[12?13]通過模型和算法得到節(jié)點(diǎn)位置），雖然可以表示其地理空間特征，但在網(wǎng)絡(luò)可視化時(shí)，復(fù)雜網(wǎng)絡(luò)的小世界效應(yīng)和集聚現(xiàn)象會(huì)有大量的邊交叉和網(wǎng)絡(luò)密集區(qū)域，除了導(dǎo)致嚴(yán)重的視覺混亂，還會(huì)有密度位置信息丟失問題。

3） 邊綁定方法可以有效解決節(jié)點(diǎn)位置固定的情況下邊導(dǎo)致的視覺混亂問題，但是對(duì)于航線網(wǎng)絡(luò)，由于邊綁定方法更專注于全局圖分布而放棄了子圖細(xì)節(jié)，無法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)細(xì)節(jié)進(jìn)行進(jìn)一步分析。

4） 在數(shù)據(jù)處理階段通過對(duì)節(jié)點(diǎn)聚類和邊提取[14]操作降低網(wǎng)絡(luò)復(fù)雜度，會(huì)導(dǎo)致信息丟失，而航線網(wǎng)絡(luò)結(jié)構(gòu)不允許丟失信息。

為兼顧精準(zhǔn)表達(dá)航線網(wǎng)絡(luò)信息和降低可視化視覺混亂程度，本文提出了基于分層的邊折疊節(jié)點(diǎn)鏈接法，在基于位置固定的節(jié)點(diǎn)鏈接法上，考慮造成視覺混亂的主要因素進(jìn)行改進(jìn)。設(shè)計(jì)分層網(wǎng)絡(luò)，通過對(duì)邊數(shù)據(jù)篩選和連邊趨勢(shì)優(yōu)化減少邊交叉數(shù)量，同時(shí)結(jié)合用戶交互，實(shí)現(xiàn)邊的展開和折疊。實(shí)驗(yàn)對(duì)比本文方法、位置固定的節(jié)點(diǎn)鏈接法和基于力引導(dǎo)的節(jié)點(diǎn)鏈接法，結(jié)果表明，基于分層的邊折疊節(jié)點(diǎn)鏈接法在網(wǎng)絡(luò)可視化布局時(shí)，兼顧網(wǎng)絡(luò)的地理空間特征的同時(shí)，極大地減少了交叉點(diǎn)數(shù)量，降低了視覺混亂程度，且布局速度各有優(yōu)劣。最后，再對(duì)國內(nèi)航線網(wǎng)絡(luò)進(jìn)行可視化探索評(píng)估，直觀展示網(wǎng)絡(luò)特點(diǎn)與不足，提出網(wǎng)絡(luò)優(yōu)化建議。

1 "相關(guān)工作

網(wǎng)絡(luò)結(jié)構(gòu)可視化方法相關(guān)研究與發(fā)展現(xiàn)狀如下。

1.1 "網(wǎng)絡(luò)結(jié)構(gòu)可視化

網(wǎng)絡(luò)結(jié)構(gòu)可視化主要包含三個(gè)方面：網(wǎng)絡(luò)布局、網(wǎng)絡(luò)屬性可視化和用戶交互。布局作為核心要素確定圖的結(jié)構(gòu)關(guān)系，最主要的布局方法是：節(jié)點(diǎn)鏈接法和相鄰矩陣。本文以航線網(wǎng)絡(luò)具有地理空間特征的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)為例，需要清晰、直觀地表示連邊關(guān)系。相較于鄰接矩陣，節(jié)點(diǎn)鏈接法能夠?qū)哟吻逦?、直觀地表達(dá)網(wǎng)絡(luò)結(jié)構(gòu)，易于理解圖的拓?fù)浣Y(jié)構(gòu)，符合人們的視覺習(xí)慣，因此重點(diǎn)討論節(jié)點(diǎn)鏈接法布局的研究進(jìn)展。

最常用的節(jié)點(diǎn)鏈接法是由Eades提出的力引導(dǎo)及其改進(jìn)算法[7?11]布局。該方法將節(jié)點(diǎn)和邊視作彈簧和節(jié)點(diǎn)系統(tǒng)，通過力的分布迭代節(jié)點(diǎn)位置，人們常用網(wǎng)絡(luò)可視化方法表示網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的拓?fù)湫畔?，更關(guān)注節(jié)點(diǎn)和邊的相對(duì)位置，其節(jié)點(diǎn)具體位置信息除布局外通常沒有具體含義。在表示具有地理空間信息的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)時(shí)，基于力引導(dǎo)的節(jié)點(diǎn)鏈接布局不能準(zhǔn)確表達(dá)這部分信息。此外，基于多維尺度分析布局、弧長連接布局、環(huán)形布局等方法均有這一問題。

1.2 "網(wǎng)絡(luò)可視化遮擋問題

解決網(wǎng)絡(luò)可視化時(shí)的視覺混亂方法主要是對(duì)圖進(jìn)行稀疏表示，在數(shù)據(jù)處理階段就減少圖的復(fù)雜程度，方法主要有以下兩種。

1） 布局拓?fù)浜喕▽?duì)數(shù)據(jù)壓縮。對(duì)邊的簡化最早是由Prim提出的最小生成樹問題，通過去除其他次要數(shù)據(jù)簡化布局。文獻(xiàn)[15]基于多級(jí)的圖布局算法將大型和多維數(shù)據(jù)集表示為最小生成樹。文獻(xiàn)[16]根據(jù)邊周圍的密度局部聚類過濾邊。這些布局拓?fù)浜喕椒▽?duì)邊采樣，在降維和映射時(shí)會(huì)丟失信息，不適用于航線網(wǎng)絡(luò)結(jié)構(gòu)分析，因?yàn)楹骄€網(wǎng)絡(luò)結(jié)構(gòu)不允許丟失信息。

2） 保留所有的數(shù)據(jù)對(duì)可視空間進(jìn)行壓縮。文獻(xiàn)[17]通過圖表示學(xué)習(xí)對(duì)大型網(wǎng)絡(luò)節(jié)點(diǎn)聚類，聚類后的節(jié)點(diǎn)集合視為一個(gè)新的超點(diǎn)進(jìn)行可視化。該方法在簡化拓?fù)浣Y(jié)構(gòu)時(shí)有效果，但將節(jié)點(diǎn)聚類不能解決航線網(wǎng)絡(luò)可視化由邊交叉導(dǎo)致的遮擋。對(duì)可視空間壓縮方法還有邊綁定方法，該方法通過將靠近的邊捆綁成束，從而減少邊之間的交叉，在可視化領(lǐng)域被廣泛認(rèn)可[18?22]。如文獻(xiàn)[22]基于邊綁定方法對(duì)邊進(jìn)行模糊聚類，展示網(wǎng)絡(luò)基本結(jié)構(gòu)和邊的大致走向。該方法適用于觀察骨架走向，用于航線網(wǎng)絡(luò)可視化時(shí)難以展示細(xì)節(jié)信息。

1.3 "網(wǎng)絡(luò)分層

在以上方法的基礎(chǔ)上，文獻(xiàn)[23]提出了將網(wǎng)絡(luò)結(jié)構(gòu)分為不同層級(jí)進(jìn)行可視化的思路：將網(wǎng)絡(luò)分為結(jié)構(gòu)層、群集層和主題層，為每一層設(shè)計(jì)不同的可視化編碼方法，實(shí)現(xiàn)多層級(jí)的網(wǎng)絡(luò)瀏覽。研究者們?cè)诖嘶A(chǔ)上進(jìn)行改進(jìn)和探索，提出了包括基于深度學(xué)習(xí)的網(wǎng)絡(luò)可視化、動(dòng)態(tài)網(wǎng)絡(luò)可視化、多維網(wǎng)絡(luò)可視化等方法。這些研究不僅提高了網(wǎng)絡(luò)可視化的效果和準(zhǔn)確性，還拓展了網(wǎng)絡(luò)可視化的應(yīng)用領(lǐng)域，如社交網(wǎng)絡(luò)分析、生物網(wǎng)絡(luò)分析等。

1.4 "具有地理空間特征的節(jié)點(diǎn)鏈接法

上述網(wǎng)絡(luò)可視化布局算法沒有考慮網(wǎng)絡(luò)的地理空間特征。位置固定的節(jié)點(diǎn)鏈接法可以表示網(wǎng)絡(luò)的地理空間特征，但網(wǎng)絡(luò)中存在密集區(qū)域，會(huì)有點(diǎn)和邊遮擋現(xiàn)象，形成嚴(yán)重的視覺混亂。邊綁定方法可以有效解決節(jié)點(diǎn)位置固定的情況下邊導(dǎo)致的視覺混亂問題，但會(huì)導(dǎo)致信息丟失。除了上述兩種方法外，文獻(xiàn)[24]為空間位置耦合的力引導(dǎo)算法（SCFDA）提供了新的解決思路，首次提出在布局時(shí)兼顧節(jié)點(diǎn)的空間位置，將地理特征作為約束條件。該方法在力引導(dǎo)的基礎(chǔ)上進(jìn)行優(yōu)化，在對(duì)節(jié)點(diǎn)空間集聚網(wǎng)絡(luò)（集聚半徑較?。r(shí)有效，對(duì)于航線網(wǎng)絡(luò)這類節(jié)點(diǎn)廣泛分布且集聚特征不明顯或集聚范圍較大時(shí)，邊界約束效果不突出。

本文基于對(duì)以上研究工作的分析和“可視化分層”的概念，針對(duì)航線網(wǎng)絡(luò)可視化需要保留全局和展示細(xì)節(jié)的問題，提出基于分層的邊折疊節(jié)點(diǎn)鏈接法。基于節(jié)點(diǎn)位置固定的節(jié)點(diǎn)鏈接法，通過數(shù)據(jù)篩選進(jìn)行分層可視化，分解網(wǎng)絡(luò)結(jié)構(gòu)以減少重疊，對(duì)邊的布局進(jìn)行優(yōu)化，減少邊交叉混亂。

2 "本文方法

在節(jié)點(diǎn)位置固定的節(jié)點(diǎn)鏈接法的基礎(chǔ)上，從數(shù)據(jù)壓縮和連邊趨勢(shì)兩方面進(jìn)行改進(jìn)，相對(duì)準(zhǔn)確表達(dá)節(jié)點(diǎn)位置的同時(shí)緩解常規(guī)節(jié)點(diǎn)鏈接法的遮擋和交叉問題。具體做法是：對(duì)網(wǎng)絡(luò)分層，對(duì)網(wǎng)絡(luò)中的邊分層可視化以實(shí)現(xiàn)邊折疊效果，達(dá)到數(shù)據(jù)壓縮的目的；進(jìn)一步改進(jìn)連邊趨勢(shì)，增加偏移量調(diào)整邊位置以減少邊交叉。由此得到基于分層的邊折疊節(jié)點(diǎn)鏈接法，如圖1所示。

該方法中數(shù)據(jù)輸入是網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)位置坐標(biāo)，輸出是基于節(jié)點(diǎn)位置固定的節(jié)點(diǎn)鏈接法布局的詳細(xì)圖和基于分層的邊折疊節(jié)點(diǎn)鏈接圖，即概覽圖和焦點(diǎn)圖。首先，通過數(shù)據(jù)篩選減小數(shù)據(jù)規(guī)模和調(diào)整位置，改進(jìn)連邊趨勢(shì)，改善邊交叉導(dǎo)致的視覺混亂；其次，選擇焦點(diǎn)的交互操作將折疊邊展開，展示詳細(xì)的信息。

2.1 "分層網(wǎng)絡(luò)設(shè)計(jì)

在對(duì)航線網(wǎng)絡(luò)可視分析時(shí)，除了觀察其整體趨勢(shì)外不需要可視化全部航線。在觀察細(xì)節(jié)時(shí)，選擇一定范圍內(nèi)的機(jī)場(chǎng)和相關(guān)航線作為感興趣區(qū)（這些被選定的機(jī)場(chǎng)節(jié)點(diǎn)集合作為焦點(diǎn)組）。為了盡可能降低視覺混淆，保留用戶感興趣區(qū)信息，需要對(duì)感興趣區(qū)外的邊進(jìn)行折疊（不包含節(jié)點(diǎn)）。當(dāng)被折疊的邊在航線網(wǎng)絡(luò)中占比較大時(shí)，能極大地減少數(shù)據(jù)規(guī)模，緩解網(wǎng)絡(luò)可視化時(shí)的視覺混亂。根據(jù)邊折疊的程度和類型，將網(wǎng)絡(luò)結(jié)構(gòu)分為不同層級(jí)，為每一層設(shè)計(jì)不同的邊折疊方案，結(jié)合交互實(shí)現(xiàn)多層級(jí)的網(wǎng)絡(luò)瀏覽。

分層網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)如圖2所示，各層網(wǎng)絡(luò)可視化不同的邊集合表示不同的邊折疊程度。詳細(xì)網(wǎng)絡(luò)表示網(wǎng)絡(luò)整體結(jié)構(gòu)，不對(duì)邊進(jìn)行折疊；概覽網(wǎng)絡(luò)表示網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)，折疊組間邊；焦點(diǎn)網(wǎng)絡(luò)可視化與感興趣區(qū)有關(guān)的邊，折疊其他組邊關(guān)系。

1） 分層網(wǎng)絡(luò)共三層，可以抽象為詳細(xì)網(wǎng)絡(luò)（包含網(wǎng)絡(luò)所有信息、不折疊邊、可視化網(wǎng)絡(luò)整體結(jié)構(gòu)和趨勢(shì)）、概覽網(wǎng)絡(luò)（各組節(jié)點(diǎn)集合內(nèi)部關(guān)系構(gòu)成的網(wǎng)絡(luò)，僅可視化組內(nèi)邊、折疊組外邊）和焦點(diǎn)網(wǎng)絡(luò)（由焦點(diǎn)組和其余組之間的關(guān)系構(gòu)成的網(wǎng)絡(luò)，僅可視化感興趣區(qū)的組外關(guān)系，折疊與感興趣區(qū)無關(guān)的組間和組內(nèi)邊）。

2） 分層網(wǎng)絡(luò)中的節(jié)點(diǎn)類型有：焦點(diǎn)組內(nèi)點(diǎn)集[n]和其他組點(diǎn)集[m]（集合[m]、[n]互為補(bǔ)集），其中，焦點(diǎn)組為交互選擇的機(jī)場(chǎng)節(jié)點(diǎn)集合。

3） 分層網(wǎng)絡(luò)中存在四種邊關(guān)系集合[S1～S4]，分別是：[S1]表示焦點(diǎn)組內(nèi)關(guān)系；[S2]表示焦點(diǎn)組?非焦點(diǎn)組關(guān)系；[S3]表示非焦點(diǎn)組內(nèi)關(guān)系；[S4]表示非焦點(diǎn)組間關(guān)系。其中，[S4]數(shù)量遠(yuǎn)遠(yuǎn)大于[S2]，且為非焦點(diǎn)組。

點(diǎn)集和邊集與各網(wǎng)絡(luò)關(guān)系見表1，表中[m1～mK]為節(jié)點(diǎn)集合（集合數(shù)量和內(nèi)容由網(wǎng)絡(luò)節(jié)點(diǎn)的聚類結(jié)果確定）代表各節(jié)點(diǎn)組，共同構(gòu)成網(wǎng)絡(luò)節(jié)點(diǎn)全集；[S1～S4]為焦點(diǎn)組選擇[m1]時(shí)的邊集，各網(wǎng)絡(luò)有表1中的關(guān)系（其中“√”表示網(wǎng)絡(luò)包含該集合）。

2.2 "數(shù)據(jù)篩選

數(shù)據(jù)篩選對(duì)網(wǎng)絡(luò)中的邊數(shù)據(jù)壓縮，將造成視覺混亂的主要邊折疊，達(dá)到對(duì)密集區(qū)域稀疏化的目的。 采用K?means算法根據(jù)空間位置屬性對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行聚類（由K?means聚類參數(shù)確定方法得到聚類系數(shù)[K]，[K]作為節(jié)點(diǎn)聚類數(shù)量），通過節(jié)點(diǎn)分組得到分層網(wǎng)絡(luò)節(jié)點(diǎn)集和邊集。依據(jù)交互選擇焦點(diǎn)組，數(shù)據(jù)篩選得到焦點(diǎn)組的邊關(guān)系，僅可視化這些邊，達(dá)到對(duì)與焦點(diǎn)組無關(guān)邊集[S4]折疊的目的，從而減少邊交叉。

各層網(wǎng)絡(luò)對(duì)邊的具體數(shù)據(jù)篩選算法如下：

算法1：數(shù)據(jù)篩選算法

輸入：圖[G]

輸出：分層圖[G]=（詳細(xì)圖，概覽圖，焦點(diǎn)圖）

//詳細(xì)網(wǎng)絡(luò)，經(jīng)聚類和數(shù)據(jù)篩選后對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)劃分為多個(gè)子集（節(jié)點(diǎn)組）

1. K?means算法根據(jù)節(jié)點(diǎn)經(jīng)緯度聚類，得到每組節(jié)點(diǎn)集合；

2. 按照數(shù)據(jù)流模型進(jìn)行交互選取焦點(diǎn)組；

3. 詳細(xì)圖?概覽圖?焦點(diǎn)圖表示：

//詳細(xì)圖?概覽圖?焦點(diǎn)圖數(shù)據(jù)選取和布局方法

布局：由經(jīng)緯度表示節(jié)點(diǎn)位置的節(jié)點(diǎn)鏈接法；

數(shù)據(jù)：

節(jié)點(diǎn)集：所有網(wǎng)絡(luò)均為全集；

邊集：

1） 詳細(xì)圖：

//詳細(xì)圖包含網(wǎng)絡(luò)所有信息，為圖[G]全集所有邊；

2） 概覽圖： " "http://對(duì)組內(nèi)關(guān)系可視化，折疊組間關(guān)系

根據(jù)邊的起始節(jié)點(diǎn)所在組，篩選類型為[S1]（[m1]→[m1]）、

[S3]（[mi]→[mi]）邊集；

3） 焦點(diǎn)圖：

//對(duì)焦點(diǎn)組?非焦點(diǎn)組關(guān)系可視化，折疊非焦點(diǎn)組關(guān)系

篩選類型為[S2（m1→mi）]的邊關(guān)系；

4. 交互操作：

鼠標(biāo)點(diǎn)擊交互，選擇其他焦點(diǎn)組；

更新數(shù)據(jù)： //焦點(diǎn)圖邊集變化，非焦點(diǎn)組邊折疊

[S3]轉(zhuǎn)換為[S1]；[S4]轉(zhuǎn)換為[S2]；

2.3 "連邊趨勢(shì)改進(jìn)

本文選擇調(diào)整組間相對(duì)位置，保持組內(nèi)相對(duì)位置，調(diào)整連邊趨勢(shì)，這一方法能夠減少邊交叉的原因有以下幾點(diǎn)。

1） 對(duì)連邊趨勢(shì)調(diào)整的目的是令位置相近的連邊趨勢(shì)一致以緩解邊交叉。連邊趨勢(shì)可以由邊的斜率和角度表示，影響斜率的變量僅有坐標(biāo)；

2） 由于輸入數(shù)據(jù)為網(wǎng)絡(luò)節(jié)點(diǎn)的經(jīng)緯度坐標(biāo)，因此經(jīng)數(shù)據(jù)篩選，兩組內(nèi)點(diǎn)相對(duì)位置一致，邊斜率一致；

3） 部分不同簇中節(jié)點(diǎn)位置相鄰，通過增加一定偏移量，緩解邊交叉問題。

通過增加偏移量調(diào)整組間位置，如圖3所示（圖中，調(diào)整后的可視化節(jié)點(diǎn)坐標(biāo)=原經(jīng)緯度坐標(biāo)（[x0，y0]）+相對(duì)位置[（±x，]±[y]））。

圖3表示增加偏移量前后各節(jié)點(diǎn)集合位置變化。圖3a）表示將網(wǎng)絡(luò)進(jìn)行聚類后得到由凸包可視化表示的節(jié)點(diǎn)集合，圖3b）表示組內(nèi)節(jié)點(diǎn)位置關(guān)系不變，將各組與焦點(diǎn)組位置關(guān)系調(diào)整到九宮格內(nèi)。其中，相對(duì)位置由各組錨點(diǎn)位置調(diào)整前后變化確定，且當(dāng)選取不同的焦點(diǎn)組時(shí)，各節(jié)點(diǎn)組與焦點(diǎn)組位置關(guān)系不同。具體的連邊趨勢(shì)改進(jìn)算法如下。

算法2：連邊趨勢(shì)改進(jìn)算法

輸入：布局（[G]，pos1）

輸出：布局（[G]，pos2）

1. 經(jīng)數(shù)據(jù)篩選后，得到節(jié)點(diǎn)分組集合； " "http://參見算法1

2. 對(duì)聚類后的每組節(jié)點(diǎn)選取錨點(diǎn)；

3. 組間位置調(diào)整，組內(nèi)相對(duì)位置不變：

設(shè)置各組錨點(diǎn)偏移量參數(shù)，包括[xy]兩個(gè)方向，位置坐標(biāo)

表示為：pos1 = pos（[x0]±[x]′，[y0]±[y]′）

2.4 "焦點(diǎn)轉(zhuǎn)換

不同層次網(wǎng)絡(luò)對(duì)邊的可視化有所不同，對(duì)邊關(guān)系可視化表示為對(duì)邊的展開，未對(duì)邊可視化表示為對(duì)邊的折疊。結(jié)合選擇和焦點(diǎn)交互，實(shí)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)展開與折疊。

交互設(shè)計(jì)為：選擇焦點(diǎn)組，焦點(diǎn)圖以焦點(diǎn)組為中心展示邊集[S2]；通過交互轉(zhuǎn)換焦點(diǎn)，邊關(guān)系[S4]折疊與[S2]展開；對(duì)網(wǎng)絡(luò)進(jìn)行分層存儲(chǔ)，聚類后的點(diǎn)集和組內(nèi)邊作為內(nèi)層存儲(chǔ)，組間邊作為外層存儲(chǔ)。

基于分層的邊折疊節(jié)點(diǎn)鏈接法的整體算法如下。

算法3：基于分層的邊折疊節(jié)點(diǎn)鏈接法

//算法實(shí)現(xiàn)布局的改變

輸入：圖[G]=（N，E，pos）

輸出：圖[G]=（N，E，pos2）

1. 對(duì)詳細(xì)圖數(shù)據(jù)篩選得到分層網(wǎng)絡(luò)； "http://參見算法1

2. 調(diào)整概覽圖和焦點(diǎn)圖布局的連邊趨勢(shì)，改善視覺混亂表達(dá)； " //參見算法2

3. 通過交互設(shè)計(jì)選擇焦點(diǎn)組，對(duì)邊數(shù)據(jù)篩選實(shí)現(xiàn)邊的展開和折疊； //參見2.4節(jié)焦點(diǎn)轉(zhuǎn)換和2.2節(jié)算法1交互部分

3 "方法驗(yàn)證與結(jié)果分析

在國內(nèi)航線網(wǎng)絡(luò)數(shù)據(jù)集上對(duì)本文方法進(jìn)行驗(yàn)證，具體分為以下幾部分。

1） 驗(yàn)證改進(jìn)的節(jié)點(diǎn)鏈接法——基于分層的邊折疊節(jié)點(diǎn)鏈接法的有效性?？紤]到北京所在組航線密集度較高，以北京所在組為聚焦組。

2） 根據(jù)以上結(jié)果，分析網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)與不足，提出航線網(wǎng)絡(luò)優(yōu)化建議。

3.1 "數(shù)據(jù)集

航線網(wǎng)絡(luò)包括由機(jī)場(chǎng)表示圖的節(jié)點(diǎn)，航線表示網(wǎng)絡(luò)邊，經(jīng)數(shù)據(jù)處理后，國內(nèi)機(jī)場(chǎng)節(jié)點(diǎn)258個(gè)，節(jié)點(diǎn)間航線2 925條。

3.2 "航線網(wǎng)絡(luò)可視化實(shí)例

數(shù)據(jù)篩選階段的K?means聚類參數(shù)選擇經(jīng)多次實(shí)驗(yàn)，確定[K]為6，表示節(jié)點(diǎn)的聚類數(shù)量。連邊趨勢(shì)改進(jìn)算法中各組錨點(diǎn)結(jié)果如表2所示。

可視化案例以北京所在組為焦點(diǎn)，如圖4所示。詳細(xì)圖（見圖4a））展示全部的航線，精確表示機(jī)場(chǎng)位置與航線網(wǎng)絡(luò)；組內(nèi)關(guān)系概覽圖（見圖4b））利用凸包對(duì)各個(gè)組進(jìn)行范圍劃分和顏色編碼；焦點(diǎn)圖（見圖4c））表示組間關(guān)系。

相對(duì)于詳細(xì)圖，結(jié)合概覽圖與焦點(diǎn)圖觀察得到航線網(wǎng)絡(luò)根據(jù)經(jīng)緯度聚類后的各組細(xì)節(jié)信息。

1） 詳細(xì)圖表示機(jī)場(chǎng)和航線均存在密集區(qū)域，分布為東密西疏。結(jié)合數(shù)據(jù)流航線距離指標(biāo)得到短、中、長三種航線規(guī)模。

2） 概覽圖表示各組內(nèi)航線信息。圖中各組存在不同關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)和拓?fù)浣Y(jié)構(gòu)。烏魯木齊所在組有較強(qiáng)的核心節(jié)點(diǎn)影響力，但組內(nèi)其他節(jié)點(diǎn)間的連通性較差。北京所在組各機(jī)場(chǎng)節(jié)點(diǎn)間連接緊密，核心節(jié)點(diǎn)間網(wǎng)絡(luò)密度大，有較高的連通性。

3） 焦點(diǎn)圖得到不同組的組間結(jié)構(gòu)信息。連線數(shù)量表示城市的繁忙程度，焦點(diǎn)組與哈爾濱所在組之間的航線多為點(diǎn)對(duì)式，與烏魯木齊所在組的連接存在明顯樞紐節(jié)點(diǎn)，且存在大量組內(nèi)和組間航線連接同一樞紐節(jié)點(diǎn)，這些樞紐機(jī)場(chǎng)可能會(huì)成為瓶頸。

3.3 "關(guān)于網(wǎng)絡(luò)優(yōu)化的建議

對(duì)于網(wǎng)絡(luò)優(yōu)化的建議如下。

1） 對(duì)于東部地區(qū)，需要提升關(guān)鍵節(jié)點(diǎn)能力。對(duì)關(guān)鍵節(jié)點(diǎn)和同時(shí)有大量組內(nèi)與組間航線連接的樞紐節(jié)點(diǎn)進(jìn)行擴(kuò)建或升級(jí)，以提高其處理能力和容納更多航班的能力。

2） 西部地區(qū)機(jī)場(chǎng)分布稀疏，應(yīng)加強(qiáng)西部地區(qū)重要城市機(jī)場(chǎng)建設(shè)，增加航線提高西部網(wǎng)絡(luò)內(nèi)部的連通性。

3） 東部航線網(wǎng)絡(luò)密度較大，通過合理優(yōu)化航線，緩解樞紐節(jié)點(diǎn)壓力。當(dāng)前中國高鐵網(wǎng)絡(luò)建設(shè)非常完善，對(duì)于短距離航線采用高鐵替代選取非繁忙短距離航線進(jìn)行優(yōu)化。

3.4 "方法對(duì)比

將經(jīng)典方法的基于力引導(dǎo)的節(jié)點(diǎn)鏈接法、改進(jìn)前的節(jié)點(diǎn)位置固定的節(jié)點(diǎn)鏈接法和本文基于分層的邊折疊節(jié)點(diǎn)鏈接法應(yīng)用于航線網(wǎng)絡(luò)可視化，效果分別如圖5所示，從主觀、交叉點(diǎn)數(shù)量與時(shí)間復(fù)雜度三個(gè)方面對(duì)比三種方法，結(jié)果如表3所示。

本文方法與基于力引導(dǎo)的節(jié)點(diǎn)鏈接法和節(jié)點(diǎn)位置固定的節(jié)點(diǎn)鏈接法相比，在對(duì)有地理空間信息的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)可視化時(shí)，具有邊交叉數(shù)量較少、準(zhǔn)確表達(dá)地理空間信息和網(wǎng)絡(luò)結(jié)構(gòu)細(xì)節(jié)的優(yōu)點(diǎn)。

由于本文是基于交互的可視化方法，需要用戶通過交互驅(qū)動(dòng)，時(shí)間復(fù)雜度取決于用戶的交互時(shí)間，但在布局初始化時(shí)，時(shí)間復(fù)雜度與兩種方法相比沒有明顯增加。

4 "結(jié) "語

本文結(jié)合交互，通過改進(jìn)節(jié)點(diǎn)鏈接法布局，考慮地理空間特征的同時(shí)減輕網(wǎng)絡(luò)可視化時(shí)的視覺混亂現(xiàn)象，提高可視分析效果。在中國航線網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)例驗(yàn)證，分析網(wǎng)絡(luò)結(jié)構(gòu)，提出優(yōu)化建議。最后通過實(shí)驗(yàn)對(duì)比，改進(jìn)的節(jié)點(diǎn)鏈接法中交叉點(diǎn)數(shù)量最少，時(shí)間復(fù)雜度較小，能夠有效緩解邊遮擋引起的視覺混亂問題。局限之處在于，本文僅分析了靜態(tài)航線網(wǎng)絡(luò)結(jié)構(gòu)，后續(xù)將考慮動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)的研究，根據(jù)優(yōu)化建議增加航線對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響。

注：本文通訊作者為宋淼。

參考文獻(xiàn)

[1] 張培文，杜福民，王雪，等.近十年中國客運(yùn)航空網(wǎng)絡(luò)空間結(jié)構(gòu)演化及分析研究[J].世界地理研究，2021，30（6）：1253?1264.

[2] 胡軍，王雨桐，何欣蔚，等.基于復(fù)雜網(wǎng)絡(luò)的全球航空網(wǎng)絡(luò)結(jié)構(gòu)分析與應(yīng)用[J].計(jì)算機(jī)科學(xué)，2021，48（z1）：321?325.

[3] 王興隆，朱麗納，石宗北.多層航線聚合網(wǎng)絡(luò)建模及相關(guān)性分析[J].科學(xué)技術(shù)與工程，2020，20（3）：1243?1249.

[4] 張瑞，朱春彥，王瓊，等.基于復(fù)雜網(wǎng)絡(luò)的中國四大機(jī)場(chǎng)群多極航線網(wǎng)絡(luò)結(jié)構(gòu)特征分析[J].科學(xué)技術(shù)與工程，2023，23（18）：8002?8010.

[5] 楊卓，謝雅淇，陳誼，等.圖可視化布局方法最新研究進(jìn)展綜述[J].計(jì)算機(jī)工程與應(yīng)用，2023，59（16）：1?15.

[6] 周銳.復(fù)雜網(wǎng)絡(luò)可視化布局算法研究[D].綿陽：西南科技大學(xué)，2022.

[7] ZHONG F H， XUE M L， ZHANG J， et al. Force?directed graph layouts revisited： A new force based on the T?distribution [J]. IEEE transactions on visualization and computer graphics， 2024， 30（7）： 3650?3663.

[8] XUE M L， WANG Z， ZHONG F H， et al. Taurus： Towards a unified force representation and universal solver for graph layout [J]. IEEE transactions on visualization and computer graphics， 2023， 29（1）： 886?895.

[9] VENTURINI T， JACOMY M， JENSEN P. What do we see when we look at networks： Visual network analysis， relational ambiguity， and force?directed layouts [J]. Big data amp; society， 2021， 8（1）： 018488.

[10] SHENHAO A， RONGHUAN Y. Multi?layer network visualization based on force?directed algorithm [C]// 2021 2nd International Conference on Artificial Intelligence and Information Systems. New York： ACM， 2021： 1?8.

[11] MEIDIANA A， HONG S H， TORKEL M， et al. Sublinear time force computation for big complex network visualization [J]. Computer graphics forum， 2020， 39（3）： 579?591.

[12] AHMED A R， DE LUCA F， DEVKOTA S， et al. Graph drawing via gradient descent， （GD）2 [C]// Graph Drawing and Network Visualization： 28th International Symposium. Heidelberg： Springer， 2020： 3?17.

[13] BIEDL T C， MADDEN B， TOLLIS I G. The three?phase method： A unified approach to orthogonal graph drawing [J]. International journal on computational geometry and applications， 2000， 10（6）： 553?580.

[14] 張翔，倪瑜那，李松岳，等.大圖采樣方法綜述[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2022，34（12）：1805?1814.

[15] PROBST D， REYMOND J L. Visualization of very large high?dimensional data sets as minimum spanning trees [J]. Journal of cheminformatics， 2020， 12（1）： 12.

[16] NOCAJ A， ORTMANN M， BRANDES U. Adaptive disentanglement based on local clustering in small?world network visualization [J]. IEEE transactions on visualization and computer graphics， 2016， 22（6）： 1662?1671.

[17] ZHOU Z G， SHI C， SHEN X L， et al. Context?aware sampling of large networks via graph representation learning [J]. IEEE transactions on visualization and computer graphics， 2021， 27（2）： 1709?1719.

[18] BARTOLOMEO S D， RIEDEWALD M， GATTERBAUER W， et al. STRATISFIMAL LAYOUT： A modular optimization model for laying out layered node?link network visualizations [J]. IEEE transactions on visualization and computer graphics， 2022， 28（1）： 324?334.

[19] WU J T， SUN J X， XIE X Y， et al. Accelerating web?based graph visualization with pixel?based edge bundling [C]// 2023 IEEE International Conference on Big Data. New York： IEEE， 2023： 6005?6014.

[20] WANG Y H， XUE M L， WANG Y Y， et al. Interactive structure?aware blending of diverse edge bundling visualizations [J]. IEEE transactions on visualization and computer graphics， 2020， 26（1）： 687?696.

[21] ZHENG J X， PAWAR S， GOODMAN D F M. Further towards unambiguous edge bundling： Investigating power?confluent drawings for network visualization [J]. IEEE transactions on visualization and computer graphics， 2021， 27（3）： 2244?2249.

[22] WALLINGER M， ARCHAMBAULT D， AUBER D， et al. Edge?path bundling： A less ambiguous edge bundling approach [J]. IEEE transactions on visualization and computer graphics， 2022， 28（1）： 313?323.

[23] SCHULZ H J. Treevis.net： A tree visualization reference [J]. IEEE computer graphics and applications， 2011， 31（6）： 11?15.

[24] 張政，江南，張俊，等.空間位置耦合的地理社交網(wǎng)絡(luò)可視化布局算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2020，32（6）：865?873.

作者簡介：賀懷清（1969—），女，吉林長白山人，博士研究生，教授，研究方向?yàn)閳D形圖像與可視分析。

宋 "淼（1999—），女，河北保定人，碩士研究生，研究方向?yàn)閿?shù)據(jù)分析與可視化。

劉浩翰（1966—），男，黑龍江富錦人，碩士研究生，副教授，研究方向?yàn)閳D形圖像與可視分析。