高级检索
汤颖, 汪斌, 范菁. 节点属性嵌入的改进图布局算法[J]. 计算机辅助设计与图形学学报, 2016, 28(2): 228-237.
引用本文: 汤颖, 汪斌, 范菁. 节点属性嵌入的改进图布局算法[J]. 计算机辅助设计与图形学学报, 2016, 28(2): 228-237.
Tang Ying, Wang Bin, Fan Jing. An Improved Graph Layout Algorithm of Embedded Node Attributes[J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(2): 228-237.
Citation: Tang Ying, Wang Bin, Fan Jing. An Improved Graph Layout Algorithm of Embedded Node Attributes[J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(2): 228-237.

节点属性嵌入的改进图布局算法

An Improved Graph Layout Algorithm of Embedded Node Attributes

  • 摘要: 正文传统的图布局算法主要从网络的拓扑结构考虑生成符合美学标准的布局结果,但是由于没有考虑节点的属性,得到的布局结果不能准确反映节点属性的影响.为此,在传统力导引布局算法的基础上,提出基于属性数据嵌入的改进图布局算法.首先基于节点间的属性(包括数据属性和结构属性)定义节点属性距离;然后分别定义3个线性单调函数,将节点属性距离映射为力导引布局算法中万有引力、弹簧弹性系数和弹簧原长这3个参数,实现图布局算法中节点属性的嵌入;最后根据具体的节点属性设计并计算相应的属性距离函数和线性单调映射函数,得到与具体节点属性相关的图布局结果.实验结果表明,该算法生成的布局结果可充分体现相关节点属性对布局的影响,展现与节点属性相关的重要节点关系和子图结构.

     

    Abstract: The traditional graph layout algorithm mainly considers the topology of a graph to generate visually-aesthetic layout results. However without considering the node attribute, the traditional graph layout results can not accurately reflect the impact of the node attribute. Aiming at this problem, this paper proposed an improved graph layout algorithm based on the embedded node attributes. We first define the distance metric between nodes in the node attributes space(including data attribute and topology attribute of the node). Then we define three linear monotonic functions mapping node attribute distances to three force parameters of the force-directed layout algorithm, i.e. gravitation, spring elasticity coefficient and spring original length. According to specific node attributes, we design and calculate the corresponding attribute distance function and the linear monotonic mapping functions to obtain the node-attributes related graph layout results. Finally we apply our algorithm to visualize the Douban movie data and the real political blog data. The experimental results show that the layouts of this algorithm can fully reflect the influence of node attributes, revealing the important node relationships or interesting sub-graph structures associated with node attributes.

     

/

返回文章
返回