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

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

Node-centered Edge Clustering and Visualization Algorithm

The visualization of the associative relation between objects is mainly expressed by the edges of the graph. But a large number of edges will cause serious visual confusion due to the complexity of the associative relation between objects. Graph layout and edge bundling are both effective methods to solve the problem of visual confusion caused by complex edges. While the geo-location of some nodes has significant meaning, only edge bundling methods can be used to reduce the map load and reveal the potential association rules of graph. In the past, the edge bundling algorithms adjusted the position of the middle control points of the edge under the condition that the two end nodes of the edge were fixed. This would cause a large number of edges being gathered together, which would not only cause a secondary visual confusion, but also be difficult to reveal the potential rules of the graph at the node level. To solve this problem, this paper proposed a node-centered edge clustering and visualization algorithm. Firstly, the direction clustering algorithm was used to realize the clustering of direction edges. The direction clustering method proposed in this paper was about 13 times faster than K-means algorithm, and about 6 times faster than DBSCAN algorithm. Then, the interpolation of the control points was implemented for each edge. On this basis, FR model was used to prevent the occurrence of “excessive bending”. Finally, we adjusted the transparency of the edges so that the result of the visualization would be able to highlight the portion of the edge near the end nodes. The experimental results show that the value of the NCEB algorithm's map load (L) and the mid-point distance change (△d) were about half of the FDEB algorithm, which proved that the NCEB algorithm can move the binding position from the middle part of the edge to the node, thus not only solving the secondary visual confusion caused by traditional edge bundling methods, but also revealing the association rule and trend of the graph at the node level. The final distribution trend of the edge around the node was clear and readable, and the visualization result greatly reduced the map load, which effectively reduced visual errors and misunderstanding of information. The results of our experiments show that the proposed algorithm can reveal the potential associated trend of graphs at the node level and greatly reduce visual confusion.