绘制动态图的IGP模型

An IGP Model for Drawing Dynamic Graphs

针对可视化领域中动态图的绘制问题,提出一种新颖的可视化模型来绘制动态图.首先采用多层次方法生成初始静态图并对所有节点进行初始分区;当下一时刻的图数据来临后,先对新增节点使用重心合并排序算法的变体以确保其具有良好的初始位置,在此过程中,当有额外的附加边添加时,通过附加边长度调整算法重新调整附加边的大小以保证图的美观性;再引入“等级”的概念以提高图结构的稳定性,等级越高的节点越难以移动;最后对有变化的节点进行重新分区以简化力导向算法的排斥力计算,同时通过简化后的力导向算法优化布局.采用平均位移和总能量作为评价布局标准,用文中模型和力导向算法、节点牵制算法在Sync和Newcomb数据集上进行实验的结果表明,该模型具有较高的性能,可获得良好的布局效果.

Aiming at the problem of drawing dynamic graphs in the field of visualization,a novel visualization model is proposed to draw dynamic graphs.Firstly,the initial static graph is generated by a multilevel method and all nodes are initially partitioned.Secondly,after the graph data of the next moment come,the variant of SSBM(sorted sequential barycenter merging)algorithm is first used for the newly added nodes to ensure that they have a good initial position.In this process,when additional edges are added,the size of the additional edges is re-adjusted by the AER(additional edge resizing)algorithm to ensure the aesthetics of the graph.Then,the concept of“grade”is introduced to improve the stability of the graph structure,and the node with higher grade is more difficult to move.Finally,the nodes that have changed are repartitioned to simplify the repulsive force calculation of the force-directed algorithm,and the layout is optimized by the simplified force-directed algorithm.In this paper,the average displacement and total energy are used as the evaluation layout standard.And experiments on the Sync and Newcomb datasets using the IGP model and force-directed algorithm and node pinning algorithm show that the IGP model has high performance and good layout effect.