网络图中边集束优化问题

Problems of network simplification by edge bundling

网络规模增大和复杂度提高造成的节点遮挡覆盖和边交叉阻塞等问题成为网络可视化研究的热点.针对网络中出现的视觉凌乱问题,以空间位置和群组关系为出发点,从网络中独立的边和群组两个层次,以边汇合的角度研究边集束技术,将网络中临近的边集聚成束以降低视觉复杂度,提出和改进了分段力导引算法(FDA)简化模型和群组边相容的网络图边集束模型.其中分段集束模型,提出以二次样条曲线表示网络边,通过样条控制点进行迭代汇聚的方法,实现了网络中边的集束;针对分段集束模型中部分连线过度弯曲问题,提出通过CNM聚类算法将网络进行群组划分,在群组结构的基础上对组内连线应用边相容原则,根据连线的匹配系数计算其集束程度的方法,网络图集束后曲线扭曲变形减少,曲线过渡更加平滑.选取国内航空网络作为案例,通过两种边集束模型进行网络图简化,分析结果表明,国内机场的群组结构具有地理属性的相近性,航空网络在整体上呈现出明显的十字脉络,东西走向和南北走向的航线分别汇聚集结成束,表现了航空网络建设在南北和东西方向的总体趋势.本集束简化算法适用性广,绘制的网络图具有良好的视觉效果和可读性.

Node occlusion and edge congestion problems, which are caused by the increment of network scale and complexity, had become a hot spot in network visualization research. To solve the visual clutter problem in network, edges close to each other in network were bundled by curving them. The bundling started from node position and group division, laying emphasis on edge bundling technique through edge convergence, edges bundled close to each other in network to reduce visual complexity. A segmental forced directed algorithm （FDA） simplification model and a group based consistent edge bundling network model were proposed and improved. In segmental FDA bundling model, quadratic spline was used to display line in network, control points of spline were produced by iteration to implement edge bundling. To solve the problem of excessive bending of some edges in segmental FDA bundling model, network was divided into different groups by CNM cluster algorithm. Lines in the same group were applied with edge consistent principle on basement of network group structure, and bundling level was calculated by the matching coefficient of edges. After edge bundling, the phenomena of curve＇ s distortion decreased and curves became smoother. Domestic airline network data was chosen as experimental subject, and the network was simplified by two bundling models, and then the simplification result was analyzed. Experimental result shows that positions of nodes in the same group stand close to each other, and airline network shows distinct crossing skeleton. Airlines have north-south and westeast orientation bundle independently, which reveals the whole trends of airline network construction in these two directions. The bundling simplification algorithm introduced mentioned above has a wide applicability, and network visualized by this algorithm has good visual effect and readability.