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

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

中圖分類號： TN711?34； TP39 " " " " " " " " " " "文獻標識碼： A " " " " " " " " " " 文章編號： 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 "引 "言

隨著社會的不斷發(fā)展，航線網(wǎng)絡(luò)作為航空運輸實現(xiàn)的載體，其規(guī)模呈現(xiàn)出不斷擴大的趨勢，且網(wǎng)絡(luò)結(jié)構(gòu)越來越復(fù)雜。目前，我國民航業(yè)中還存在航線網(wǎng)絡(luò)布局不合理、資源浪費等問題，需要對航線網(wǎng)絡(luò)結(jié)構(gòu)進行優(yōu)化，以促進民航運輸持續(xù)發(fā)展，完善交通運輸體系。為分析航線網(wǎng)絡(luò)結(jié)構(gòu)現(xiàn)狀，研究者們主要采用數(shù)理統(tǒng)計和網(wǎng)絡(luò)拓撲分析[1?2]方法從航班、機場和航空公司[3?4]等角度進行分析，對航線網(wǎng)絡(luò)賦予權(quá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ù)時存在以下缺陷：

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

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

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

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

為兼顧精準表達航線網(wǎng)絡(luò)信息和降低可視化視覺混亂程度，本文提出了基于分層的邊折疊節(jié)點鏈接法，在基于位置固定的節(jié)點鏈接法上，考慮造成視覺混亂的主要因素進行改進。設(shè)計分層網(wǎng)絡(luò)，通過對邊數(shù)據(jù)篩選和連邊趨勢優(yōu)化減少邊交叉數(shù)量，同時結(jié)合用戶交互，實現(xiàn)邊的展開和折疊。實驗對比本文方法、位置固定的節(jié)點鏈接法和基于力引導(dǎo)的節(jié)點鏈接法，結(jié)果表明，基于分層的邊折疊節(jié)點鏈接法在網(wǎng)絡(luò)可視化布局時，兼顧網(wǎng)絡(luò)的地理空間特征的同時，極大地減少了交叉點數(shù)量，降低了視覺混亂程度，且布局速度各有優(yōu)劣。最后，再對國內(nèi)航線網(wǎng)絡(luò)進行可視化探索評估，直觀展示網(wǎng)絡(luò)特點與不足，提出網(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)可視化主要包含三個方面：網(wǎng)絡(luò)布局、網(wǎng)絡(luò)屬性可視化和用戶交互。布局作為核心要素確定圖的結(jié)構(gòu)關(guān)系，最主要的布局方法是：節(jié)點鏈接法和相鄰矩陣。本文以航線網(wǎng)絡(luò)具有地理空間特征的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)為例，需要清晰、直觀地表示連邊關(guān)系。相較于鄰接矩陣，節(jié)點鏈接法能夠?qū)哟吻逦?、直觀地表達網(wǎng)絡(luò)結(jié)構(gòu)，易于理解圖的拓撲結(jié)構(gòu)，符合人們的視覺習(xí)慣，因此重點討論節(jié)點鏈接法布局的研究進展。

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

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

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

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

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

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

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

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

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

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

2 "本文方法

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入：圖[G]

輸出：分層圖[G]=（詳細圖，概覽圖，焦點圖）

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

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

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

3. 詳細圖?概覽圖?焦點圖表示：

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

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

數(shù)據(jù)：

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

邊集：

1） 詳細圖：

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

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

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

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

3） 焦點圖：

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

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

4. 交互操作：

鼠標點擊交互，選擇其他焦點組；

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

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

2.3 "連邊趨勢改進

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

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

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

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

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

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

算法2：連邊趨勢改進算法

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

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

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

2. 對聚類后的每組節(jié)點選取錨點；

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

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

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

2.4 "焦點轉(zhuǎn)換

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 "方法對比

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

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

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

4 "結(jié) "語

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

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

參考文獻

[1] 張培文，杜福民，王雪，等.近十年中國客運航空網(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].計算機科學(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ò)的中國四大機場群多極航線網(wǎng)絡(luò)結(jié)構(gòu)特征分析[J].科學(xué)技術(shù)與工程，2023，23（18）：8002?8010.

[5] 楊卓，謝雅淇，陳誼，等.圖可視化布局方法最新研究進展綜述[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].計算機輔助設(shè)計與圖形學(xué)學(xué)報，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].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2020，32（6）：865?873.

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

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

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