大规模复杂动态图可视化关键技术研究

Large-scale dynamic network data analysis is an important means to achieve network awareness and intervention. Faced with such a large scale, the complexity of dynamic graph data, showing how to get information more intuitive and easier to understand the challenges graph data analysis.The scale of the graph data to the graph visualization presented important research problems, such as visual clutter, layout, navigation, and evaluation criteria. To solve these problems, the focus of this project to explore three aspects of research: first to study the simplification and clustering methods for large-scale graph data, reducing the size of the large-scale graph data, while preserving the main structure of the graph. Secondly, parallel large-scale visual layout method based on the high scalability of the GPU and GPU cluster. Parallel multi-level k-way graph partitioning method to obtain high degree of parallelism while maintaining the quality of the high divide. Graph visual layout algorithm based on energy, not only can produce beautiful, be interpreted and readability of the graph layout, and access to local and global minimum energy. Finally, in order to overcome the disadvantage of of size of resolution of single monitor, emerging new technology for large, complex dynamic map navigation and interaction in large scale display environment. This user through the visualization of fragmented knowledge discovery to explore the implicit characteristics, the potential relevance and the relationship between mode.

大规模动态网络数据的分析是实现网络的认识和干预的重要手段。面对如此大规模的复杂动态图数据，如何把获得的信息以更直观、更容易理解的方法呈现是图数据分析面临的挑战。大规模图给图可视化提出重要的研究问题，例如可视混乱、布局、导航和评价标准等。针对这些问题，本项目重点探索三方面的研究内容：首先研究大规模图数据的简化和聚类方法，降低大规模图数据规模的同时保留图的主要结构。其次，研究基于GPU和GPU集群的高扩展性并行大规模图可视布局方法。并行的多层次k-way 图划分方法获得高并行度的同时维持高划分质量。基于能量算法的图可视化布局，不但可以产生美观、可解释和可读性强的图布局，而且获得局部和全局最小能量。最后，为了克服单体显示器显示尺寸和分辨率的不足，研究大屏幕投影环境中新型适合大规模复杂动态图导航和交互的新技术。这对帮助用户贯通零散的知识发现，发掘隐含特征、潜在关联性和关系模式有重要的意义。

随着信息技术的井喷式发展，基于大规模关系图数据的各类应用逐渐增多。大规模图除了节点和边的数据规模大之外，有些还附加高维节点或者边的属性信息，并且随时间动态变化。面对如此大规模的复杂动态关系图数据，如何以更直观和更容易理解的方法呈现给用户是数据分析非常有挑战的问题。本项目探讨社交网络关系数据可视清洗基础上，首先重点研究两种通用大规模关系图可视化方法，分别为基于线积分卷积大规模图可视化和基于散点图大规模多类别数据可视化。基于线积分卷积大规模图可视化通过边聚类、节点中心性分析、向量场重建以及可视化和交互技术能够处理图的数据规模达到57976个节点和236304条边。基于散点图大规模多类别数据可视化采用点密度估计、蓝噪声层次化多类别重采样和抽象可视化方法，不仅保留数据特征而且大大降低数据规模。该方法应用到NBA队伍投篮位置数据，有效地支持从不同角度对大规模数据点关系的可视检验和定量分析。然后围绕面向高性能计算集群、大规模电子交易和体育比赛等具体应用数据探讨复杂大规模动态关系数据可视化方法。高性能计算集群可视化中，我们采用集群度量视图和集群洞察视图结合的方式，在洞察视图中通过时间序列图、树图和节点度量卡表达集群机器节点的逻辑关联和每个节点的详细性能信息。实验证明我们的方法能够有效实时发现商业云平台运行过程中时间趋势和异常状态，其中大规模的集群包含1500个机器节点。不管是与工业界的方法还是学术研究对比，我们的系统都具有很大优势。在电子交易序列可视化，我们使用概率决策树学习器计算每条交易相对于分析目标关联性的显著值，并且对于每个交易提出Knotline的编码方式。基于该方法构建电子交易时间序列的可视分析系统VAET，该系统实现在包含2600万条在线电子交易数据发现卖家通过创建虚假交易积累信用的异常交易行为。总之，我们在动态大规模关系图数据的清洗、简化聚类、可视布局和交互上都做出探索，并且实现帮助用户发掘大规模数据中潜在的关联性和关系模式。