基于分层的边折叠节点链接法

摘 "要： 为兼顾网络结构地理空间特征的同时，减轻视觉混乱和密度位置信息丢失的问题，文中对节点链接方法进行改进，给出基于分层的边折叠网络可视化方法。首先，在对节点位置布局时，采用位置固定的节点链接法保证地理空间特征；其次，结合用户交互，从边折叠的角度改进节点链接法，从而缓解常规节点链接法的遮挡交叉和信息丢失问题；最后，以中国航线网络进行实例验证。结果表明，与节点位置固定的节点链接法和基于力引导的节点链接法相比，改进的节点链接法极大地降低了交叉点数量，能够有效缓解边遮挡引起的视觉混乱问题，提高网络可视化的效果和准确性。

关键词： 航线网络； 网络结构可视分析； 地理空间特征； 节点链接法； 视觉混乱； 边折叠

中图分类号： 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 "引 "言

随着社会的不断发展，航线网络作为航空运输实现的载体，其规模呈现出不断扩大的趋势，且网络结构越来越复杂。目前，我国民航业中还存在航线网络布局不合理、资源浪费等问题，需要对航线网络结构进行优化，以促进民航运输持续发展，完善交通运输体系。为分析航线网络结构现状，研究者们主要采用数理统计和网络拓扑分析[1⁃2]方法从航班、机场和航空公司[3⁃4]等角度进行分析，对航线网络赋予权重进行建模分析。与可视分析相比，这些数据信息的模型化方法无法直观展示航线网络结构特性，无法分析数据之间的关联，优化建议偏理想。

航线网络是一种典型的复杂网络，而已有的网络可视化方法[5⁃6]在解决具有地理空间特征的复杂网络结构数据时存在以下缺陷：

1） 最常用于网络可视化的方法是基于力引导布局的节点链接法，包括最早由Eades等提出的FDA（Force⁃directed Algorithm）弹力模型，在此基础上由Kamada等人引入胡克定律的KK模型，Fruchterman等人通过模拟原子间斥力、引力提出的FR模型等，近些年大部分力引导方法都是基于以上模型，从美学原则、数据规模、算法效率等角度进行优化[7⁃11]。在实际应用中，航线网络是一种地理空间数据，基于力引导的节点链接法难以表示其空间特征和属性特征。

2） 位置固定的节点链接法是最基本的节点链接法，将位置属性作为节点布局（其他布局[12⁃13]通过模型和算法得到节点位置），虽然可以表示其地理空间特征，但在网络可视化时，复杂网络的小世界效应和集聚现象会有大量的边交叉和网络密集区域，除了导致严重的视觉混乱，还会有密度位置信息丢失问题。

3） 边绑定方法可以有效解决节点位置固定的情况下边导致的视觉混乱问题，但是对于航线网络，由于边绑定方法更专注于全局图分布而放弃了子图细节，无法对网络结构细节进行进一步分析。

4） 在数据处理阶段通过对节点聚类和边提取[14]操作降低网络复杂度，会导致信息丢失，而航线网络结构不允许丢失信息。

为兼顾精准表达航线网络信息和降低可视化视觉混乱程度，本文提出了基于分层的边折叠节点链接法，在基于位置固定的节点链接法上，考虑造成视觉混乱的主要因素进行改进。设计分层网络，通过对边数据筛选和连边趋势优化减少边交叉数量，同时结合用户交互，实现边的展开和折叠。实验对比本文方法、位置固定的节点链接法和基于力引导的节点链接法，结果表明，基于分层的边折叠节点链接法在网络可视化布局时，兼顾网络的地理空间特征的同时，极大地减少了交叉点数量，降低了视觉混乱程度，且布局速度各有优劣。最后，再对国内航线网络进行可视化探索评估，直观展示网络特点与不足，提出网络优化建议。

1 "相关工作

网络结构可视化方法相关研究与发展现状如下。

1.1 "网络结构可视化

网络结构可视化主要包含三个方面：网络布局、网络属性可视化和用户交互。布局作为核心要素确定图的结构关系，最主要的布局方法是：节点链接法和相邻矩阵。本文以航线网络具有地理空间特征的网络结构数据为例，需要清晰、直观地表示连边关系。相较于邻接矩阵，节点链接法能够层次清晰、直观地表达网络结构，易于理解图的拓扑结构，符合人们的视觉习惯，因此重点讨论节点链接法布局的研究进展。

最常用的节点链接法是由Eades提出的力引导及其改进算法[7⁃11]布局。该方法将节点和边视作弹簧和节点系统，通过力的分布迭代节点位置，人们常用网络可视化方法表示网络结构数据的拓扑信息，更关注节点和边的相对位置，其节点具体位置信息除布局外通常没有具体含义。在表示具有地理空间信息的复杂网络结构数据时，基于力引导的节点链接布局不能准确表达这部分信息。此外，基于多维尺度分析布局、弧长连接布局、环形布局等方法均有这一问题。

1.2 "网络可视化遮挡问题

解决网络可视化时的视觉混乱方法主要是对图进行稀疏表示，在数据处理阶段就减少图的复杂程度，方法主要有以下两种。

1） 布局拓扑简化法对数据压缩。对边的简化最早是由Prim提出的最小生成树问题，通过去除其他次要数据简化布局。文献[15]基于多级的图布局算法将大型和多维数据集表示为最小生成树。文献[16]根据边周围的密度局部聚类过滤边。这些布局拓扑简化方法对边采样，在降维和映射时会丢失信息，不适用于航线网络结构分析，因为航线网络结构不允许丢失信息。

2） 保留所有的数据对可视空间进行压缩。文献[17]通过图表示学习对大型网络节点聚类，聚类后的节点集合视为一个新的超点进行可视化。该方法在简化拓扑结构时有效果，但将节点聚类不能解决航线网络可视化由边交叉导致的遮挡。对可视空间压缩方法还有边绑定方法，该方法通过将靠近的边捆绑成束，从而减少边之间的交叉，在可视化领域被广泛认可[18⁃22]。如文献[22]基于边绑定方法对边进行模糊聚类，展示网络基本结构和边的大致走向。该方法适用于观察骨架走向，用于航线网络可视化时难以展示细节信息。

1.3 "网络分层

在以上方法的基础上，文献[23]提出了将网络结构分为不同层级进行可视化的思路：将网络分为结构层、群集层和主题层，为每一层设计不同的可视化编码方法，实现多层级的网络浏览。研究者们在此基础上进行改进和探索，提出了包括基于深度学习的网络可视化、动态网络可视化、多维网络可视化等方法。这些研究不仅提高了网络可视化的效果和准确性，还拓展了网络可视化的应用领域，如社交网络分析、生物网络分析等。

1.4 "具有地理空间特征的节点链接法

上述网络可视化布局算法没有考虑网络的地理空间特征。位置固定的节点链接法可以表示网络的地理空间特征，但网络中存在密集区域，会有点和边遮挡现象，形成严重的视觉混乱。边绑定方法可以有效解决节点位置固定的情况下边导致的视觉混乱问题，但会导致信息丢失。除了上述两种方法外，文献[24]为空间位置耦合的力引导算法（SCFDA）提供了新的解决思路，首次提出在布局时兼顾节点的空间位置，将地理特征作为约束条件。该方法在力引导的基础上进行优化，在对节点空间集聚网络（集聚半径较小）时有效，对于航线网络这类节点广泛分布且集聚特征不明显或集聚范围较大时，边界约束效果不突出。

本文基于对以上研究工作的分析和“可视化分层”的概念，针对航线网络可视化需要保留全局和展示细节的问题，提出基于分层的边折叠节点链接法。基于节点位置固定的节点链接法，通过数据筛选进行分层可视化，分解网络结构以减少重叠，对边的布局进行优化，减少边交叉混乱。

2 "本文方法

在节点位置固定的节点链接法的基础上，从数据压缩和连边趋势两方面进行改进，相对准确表达节点位置的同时缓解常规节点链接法的遮挡和交叉问题。具体做法是：对网络分层，对网络中的边分层可视化以实现边折叠效果，达到数据压缩的目的；进一步改进连边趋势，增加偏移量调整边位置以减少边交叉。由此得到基于分层的边折叠节点链接法，如图1所示。

该方法中数据输入是网络结构和节点位置坐标，输出是基于节点位置固定的节点链接法布局的详细图和基于分层的边折叠节点链接图，即概览图和焦点图。首先，通过数据筛选减小数据规模和调整位置，改进连边趋势，改善边交叉导致的视觉混乱；其次，选择焦点的交互操作将折叠边展开，展示详细的信息。

2.1 "分层网络设计

在对航线网络可视分析时，除了观察其整体趋势外不需要可视化全部航线。在观察细节时，选择一定范围内的机场和相关航线作为感兴趣区（这些被选定的机场节点集合作为焦点组）。为了尽可能降低视觉混淆，保留用户感兴趣区信息，需要对感兴趣区外的边进行折叠（不包含节点）。当被折叠的边在航线网络中占比较大时，能极大地减少数据规模，缓解网络可视化时的视觉混乱。根据边折叠的程度和类型，将网络结构分为不同层级，为每一层设计不同的边折叠方案，结合交互实现多层级的网络浏览。

分层网络结构设计如图2所示，各层网络可视化不同的边集合表示不同的边折叠程度。详细网络表示网络整体结构，不对边进行折叠；概览网络表示网络内部结构，折叠组间边；焦点网络可视化与感兴趣区有关的边，折叠其他组边关系。

1） 分层网络共三层，可以抽象为详细网络（包含网络所有信息、不折叠边、可视化网络整体结构和趋势）、概览网络（各组节点集合内部关系构成的网络，仅可视化组内边、折叠组外边）和焦点网络（由焦点组和其余组之间的关系构成的网络，仅可视化感兴趣区的组外关系，折叠与感兴趣区无关的组间和组内边）。

2） 分层网络中的节点类型有：焦点组内点集[n]和其他组点集[m]（集合[m]、[n]互为补集），其中，焦点组为交互选择的机场节点集合。

3） 分层网络中存在四种边关系集合[S1～S4]，分别是：[S1]表示焦点组内关系；[S2]表示焦点组⁃非焦点组关系；[S3]表示非焦点组内关系；[S4]表示非焦点组间关系。其中，[S4]数量远远大于[S2]，且为非焦点组。

点集和边集与各网络关系见表1，表中[m1～mK]为节点集合（集合数量和内容由网络节点的聚类结果确定）代表各节点组，共同构成网络节点全集；[S1～S4]为焦点组选择[m1]时的边集，各网络有表1中的关系（其中“√”表示网络包含该集合）。

2.2 "数据筛选

数据筛选对网络中的边数据压缩，将造成视觉混乱的主要边折叠，达到对密集区域稀疏化的目的。 采用K⁃means算法根据空间位置属性对网络节点进行聚类（由K⁃means聚类参数确定方法得到聚类系数[K]，[K]作为节点聚类数量），通过节点分组得到分层网络节点集和边集。依据交互选择焦点组，数据筛选得到焦点组的边关系，仅可视化这些边，达到对与焦点组无关边集[S4]折叠的目的，从而减少边交叉。

各层网络对边的具体数据筛选算法如下：

算法1：数据筛选算法

输入：图[G]

输出：分层图[G]=（详细图，概览图，焦点图）

//详细网络，经聚类和数据筛选后对网络节点划分为多个子集（节点组）

1. K⁃means算法根据节点经纬度聚类，得到每组节点集合；

2. 按照数据流模型进行交互选取焦点组；

3. 详细图⁃概览图⁃焦点图表示：

//详细图⁃概览图⁃焦点图数据选取和布局方法

布局：由经纬度表示节点位置的节点链接法；

数据：

节点集：所有网络均为全集；

边集：

1） 详细图：

//详细图包含网络所有信息，为图[G]全集所有边；

2） 概览图： " "//对组内关系可视化，折叠组间关系

根据边的起始节点所在组，筛选类型为[S1]（[m1]→[m1]）、

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

3） 焦点图：

//对焦点组⁃非焦点组关系可视化，折叠非焦点组关系

筛选类型为[S2（m1→mi）]的边关系；

4. 交互操作：

鼠标点击交互，选择其他焦点组；

更新数据： //焦点图边集变化，非焦点组边折叠

[S3]转换为[S1]；[S4]转换为[S2]；

2.3 "连边趋势改进

本文选择调整组间相对位置，保持组内相对位置，调整连边趋势，这一方法能够减少边交叉的原因有以下几点。

1） 对连边趋势调整的目的是令位置相近的连边趋势一致以缓解边交叉。连边趋势可以由边的斜率和角度表示，影响斜率的变量仅有坐标；

2） 由于输入数据为网络节点的经纬度坐标，因此经数据筛选，两组内点相对位置一致，边斜率一致；

3） 部分不同簇中节点位置相邻，通过增加一定偏移量，缓解边交叉问题。

通过增加偏移量调整组间位置，如图3所示（图中，调整后的可视化节点坐标=原经纬度坐标（[x0，y0]）+相对位置[（±x，]±[y]））。

图3表示增加偏移量前后各节点集合位置变化。图3a）表示将网络进行聚类后得到由凸包可视化表示的节点集合，图3b）表示组内节点位置关系不变，将各组与焦点组位置关系调整到九宫格内。其中，相对位置由各组锚点位置调整前后变化确定，且当选取不同的焦点组时，各节点组与焦点组位置关系不同。具体的连边趋势改进算法如下。

算法2：连边趋势改进算法

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

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

1. 经数据筛选后，得到节点分组集合； " "//参见算法1

2. 对聚类后的每组节点选取锚点；

3. 组间位置调整，组内相对位置不变：

设置各组锚点偏移量参数，包括[xy]两个方向，位置坐标

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

2.4 "焦点转换

不同层次网络对边的可视化有所不同，对边关系可视化表示为对边的展开，未对边可视化表示为对边的折叠。结合选择和焦点交互，实现网络结构的动态展开与折叠。

交互设计为：选择焦点组，焦点图以焦点组为中心展示边集[S2]；通过交互转换焦点，边关系[S4]折叠与[S2]展开；对网络进行分层存储，聚类后的点集和组内边作为内层存储，组间边作为外层存储。

基于分层的边折叠节点链接法的整体算法如下。

算法3：基于分层的边折叠节点链接法

//算法实现布局的改变

输入：图[G]=（N，E，pos）

输出：图[G]=（N，E，pos2）

1. 对详细图数据筛选得到分层网络； "//参见算法1

2. 调整概览图和焦点图布局的连边趋势，改善视觉混乱表达； " //参见算法2

3. 通过交互设计选择焦点组，对边数据筛选实现边的展开和折叠； //参见2.4节焦点转换和2.2节算法1交互部分

3 "方法验证与结果分析

在国内航线网络数据集上对本文方法进行验证，具体分为以下几部分。

1） 验证改进的节点链接法——基于分层的边折叠节点链接法的有效性。考虑到北京所在组航线密集度较高，以北京所在组为聚焦组。

2） 根据以上结果，分析网络结构特点与不足，提出航线网络优化建议。

3.1 "数据集

航线网络包括由机场表示图的节点，航线表示网络边，经数据处理后，国内机场节点258个，节点间航线2 925条。

3.2 "航线网络可视化实例

数据筛选阶段的K⁃means聚类参数选择经多次实验，确定[K]为6，表示节点的聚类数量。连边趋势改进算法中各组锚点结果如表2所示。

可视化案例以北京所在组为焦点，如图4所示。详细图（见图4a））展示全部的航线，精确表示机场位置与航线网络；组内关系概览图（见图4b））利用凸包对各个组进行范围划分和颜色编码；焦点图（见图4c））表示组间关系。

相对于详细图，结合概览图与焦点图观察得到航线网络根据经纬度聚类后的各组细节信息。

1） 详细图表示机场和航线均存在密集区域，分布为东密西疏。结合数据流航线距离指标得到短、中、长三种航线规模。

2） 概览图表示各组内航线信息。图中各组存在不同关键节点个数和拓扑结构。乌鲁木齐所在组有较强的核心节点影响力，但组内其他节点间的连通性较差。北京所在组各机场节点间连接紧密，核心节点间网络密度大，有较高的连通性。

3） 焦点图得到不同组的组间结构信息。连线数量表示城市的繁忙程度，焦点组与哈尔滨所在组之间的航线多为点对式，与乌鲁木齐所在组的连接存在明显枢纽节点，且存在大量组内和组间航线连接同一枢纽节点，这些枢纽机场可能会成为瓶颈。

3.3 "关于网络优化的建议

对于网络优化的建议如下。

1） 对于东部地区，需要提升关键节点能力。对关键节点和同时有大量组内与组间航线连接的枢纽节点进行扩建或升级，以提高其处理能力和容纳更多航班的能力。

2） 西部地区机场分布稀疏，应加强西部地区重要城市机场建设，增加航线提高西部网络内部的连通性。

3） 东部航线网络密度较大，通过合理优化航线，缓解枢纽节点压力。当前中国高铁网络建设非常完善，对于短距离航线采用高铁替代选取非繁忙短距离航线进行优化。

3.4 "方法对比

将经典方法的基于力引导的节点链接法、改进前的节点位置固定的节点链接法和本文基于分层的边折叠节点链接法应用于航线网络可视化，效果分别如图5所示，从主观、交叉点数量与时间复杂度三个方面对比三种方法，结果如表3所示。

本文方法与基于力引导的节点链接法和节点位置固定的节点链接法相比，在对有地理空间信息的网络结构数据可视化时，具有边交叉数量较少、准确表达地理空间信息和网络结构细节的优点。

由于本文是基于交互的可视化方法，需要用户通过交互驱动，时间复杂度取决于用户的交互时间，但在布局初始化时，时间复杂度与两种方法相比没有明显增加。

4 "结 "语

本文结合交互，通过改进节点链接法布局，考虑地理空间特征的同时减轻网络可视化时的视觉混乱现象，提高可视分析效果。在中国航线网络数据集进行实例验证，分析网络结构，提出优化建议。最后通过实验对比，改进的节点链接法中交叉点数量最少，时间复杂度较小，能够有效缓解边遮挡引起的视觉混乱问题。局限之处在于，本文仅分析了静态航线网络结构，后续将考虑动态网络结构的研究，根据优化建议增加航线对网络结构的影响。

注：本文通讯作者为宋淼。

参考文献

[1] 张培文，杜福民，王雪，等.近十年中国客运航空网络空间结构演化及分析研究[J].世界地理研究，2021，30（6）：1253⁃1264.

[2] 胡军，王雨桐，何欣蔚，等.基于复杂网络的全球航空网络结构分析与应用[J].计算机科学，2021，48（z1）：321⁃325.

[3] 王兴隆，朱丽纳，石宗北.多层航线聚合网络建模及相关性分析[J].科学技术与工程，2020，20（3）：1243⁃1249.

[4] 张瑞，朱春彦，王琼，等.基于复杂网络的中国四大机场群多极航线网络结构特征分析[J].科学技术与工程，2023，23（18）：8002⁃8010.

[5] 杨卓，谢雅淇，陈谊，等.图可视化布局方法最新研究进展综述[J].计算机工程与应用，2023，59（16）：1⁃15.

[6] 周锐.复杂网络可视化布局算法研究[D].绵阳：西南科技大学，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].计算机辅助设计与图形学学报，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] 张政，江南，张俊，等.空间位置耦合的地理社交网络可视化布局算法[J].计算机辅助设计与图形学学报，2020，32（6）：865⁃873.

作者简介：贺怀清（1969—），女，吉林长白山人，博士研究生，教授，研究方向为图形图像与可视分析。

宋 "淼（1999—），女，河北保定人，硕士研究生，研究方向为数据分析与可视化。

刘浩翰（1966—），男，黑龙江富锦人，硕士研究生，副教授，研究方向为图形图像与可视分析。