计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (16): 55-63.DOI: 10.3778/j.issn.1002-8331.1807-0151

• 理论与研发 • 上一篇    下一篇

ATSP:时态网络可视化的自适应时间片划分方法

曾敏,张俊,陈世祺,马硕,赵洋飞   

  1. 大连海事大学 信息科学技术学院,辽宁 大连 116026
  • 出版日期:2019-08-15 发布日期:2019-08-13

ATSP:Adaptive Time Slices Partition Method for Temporal Network Visualization

ZENG Min, ZHANG Jun, CHEN Shiqi, MA Shuo, ZHAO Yangfei   

  1. College of Information Science, Dalian Maritime University, Dalian, Liaoning 116026, China
  • Online:2019-08-15 Published:2019-08-13

摘要: 现有的时态网络可视化方法大多采用等量时间片来可视化网络的演变,不利于时态模式的快速挖掘和发现。为此,根据时态网络固有的特征提出自适应时间片划分方法(Adaptive Time Slice Partition method,ATSP)。在时态网络的两种表示方式(基于事件的表示方式和基于快照的表示方式)的基础上,构建了ATSP的基础模型,同时提出了一种改进模型用来描述事件间隔时间服从长尾分布的时态网络。为了实现时间片的不等量划分,针对探索任务的不同提出了基于时态模式的ATSP规则和基于中心节点的ATSP规则,并提出了实现算法——层次划分算法(Hierarchical Partition algorithm,HP)和增量划分算法(Incremental Partition algorithm,IP)。实验结果表明,ATSP方法比传统的时间片划分方法更能准确地表示网络的时态特征,且该方法应用于可视化时,能有效归纳并展示网络的特征,明显提高了视觉分析的效率。

关键词: 时态网络, 可视化, 时间片划分, 时态模式

Abstract: Isometric time slice is commonly used to visualize the evolution of the network for the existing temporal network visualization methods, which is not conducive to the rapid mining and discovery of temporal patterns. For this reason, this paper proposes an Adaptive Time Slice Partition(ATSP) method according to the inherent characteristics of the temporal network. On the basis of two representations of temporal networks(event-based representation and snapshot representation), an ATSP model is designed and an improved model to describe events whose interval obeys the long-tail distribution is established. At the same time, in order to achieve the unequal partitioning of time slices, this paper proposes two kinds of ATSP rules based on temporal patterns and center nodes, which respectively aims at different exploration missions. Meanwhile, the implementation algorithms including Hierarchical Partition algorithm(HP) and Incremental Partition algorithm(IP) are put forward. The results show that the ATSP method can represent the temporal characteristics of the network more accurately than the traditional time slice partitioning method. Moreover, the features of the network can be effectively summarized and displayed while the method is applied by visualization, and the visual analysis efficiency can be improved.

Key words: temporal network, visualization, time slices partition, temporal patterns