以节点为中心的关系边聚类与可视化算法

作者：张政,华一新,张亚军,曾梦熊,杨振凯

摘要：对象间的关联关系可视化主要是通过图的连边进行表达的,但是对象间的关联关系纷繁复杂,大量的连边交错会造成严重的视觉混乱,图布局和边捆绑都是解决复杂连边造成的视觉混乱问题的有效途径,然而某些节点的地理位置具有实际的含义,只能通过边捆绑方法来减少幅面载负量,进而揭示图的潜在关联规律。以往的边捆绑算法是在边的两端节点固定的前提下,调整边的中间控制点的位置,这样会使得大量边被聚集在一起,不仅会造成二次视觉混乱,且难以在节点级别揭示图的关联趋势。针对这一问题,本文提出了一种以节点为中心的关系边聚类与可视化算法。首先使用方向聚类算法实现隶属于同一个节点的连边的聚类,本文提出的方向聚类方法速度约是K-means算法的13倍,约是DBSCAN算法的6倍,然后对各个连边实现控制点的内插,在此基础上使用FR模型使得控制点位移,并通过弯曲度控制防止"过度弯曲"情况的出现,最后调整边的透明度,使得可视化的结果突出显示边靠近端点处的部分。实验结果表明,本文NCEB算法的幅面载负量L和中点距离变化量△d的约为FDEB算法的二分之一,证明本文算法可以将捆绑位置从边的中间部位移动到节点端,不仅解决了传统边捆绑算法造成的二次视觉混乱问题,而且使得节点周围的连边分布趋势清晰可读,且视觉负载大大降低,有效减少了视觉误差和信息误判。

发文机构：信息工程大学地理空间信息学院 苏州中科蓝迪软件技术有限公司

关键词：边捆绑方向聚类力引导视觉混乱弯曲度控制关联关系关系可视化全空间信息系统地图载负量edge bundlingdirection clusteringforce-directedvisual confusioncurvature controlassociative relationrelation visualizationpan spatial information systemmap load

分类号： TP3[自动化与计算机技术—计算机科学与技术]