基于热点导航的大图数据迭代计算过程可视化关键技术研究

With the rapid growth of the requirements for large graphs processing, the visual presentation of large graphs is becoming a hot issue. With the visualization of the large graphs becomes a frontier in the field of information visualization, we will combine the graphs processing system and the visualization system. According to the advantages of visualization system, iterative computing process of graph algorithm can be observed interactively. In this project, we aim to study the reasonableness of the layouts, the significance of the hot-spots, and the interactivity of the visual presentation in the iterative analysis process of large graphs. We will propose a strategy of a tree structure hot-spots navigating based on the clusters, an algorithm of a tree structure hot-spots navigating based on the graph clustering, a large graph partition-oriented layout strategy based on improved force-directed placement, and a large graph visualization algorithm based on hot-spots navigating supporting iterative computing process. A visualization framework based on hot-spots navigation of large graphs will be designed. Finally, we will implement a prototype system based on all above-mentioned to display the iterative processing of large graphs interactively. This project can demonstrate the structures or the features and the hot-spots in the process of data mining analysis to the users by navigation, improve the user experience, and assist the users to fast achieve the expected goals of the algorithm. It can be used for guiding iterative calculation process of large graphs, which has the important theoretical significance and the wide practical application prospect.

随着对大图数据的分析处理要求的快速增长，对大图的视觉展示也成为了大家研究的热点问题。大图可视化逐渐成为了信息可视化领域的前沿课题。本课题将大图处理系统和可视化系统相结合，使用户可以利用可视化系统的优势，交互地观察图算法的迭代计算过程。针对大图迭代计算过程中的布局的合理性、热点区域的突出性、展示的交互性等问题，研究基于聚簇的热点导航树的构建策略和方法，设计面向分区的基于改进力导引模型的大图数据布局算法和基于热点导航的大图迭代计算过程可视化算法，最终设计一个能够基于热点导航的迭代计算过程展示的可视化系统框架，形成一个支持大图数据迭代计算过程展示的可视化原型系统。本课题可以将用户挖掘分析过程中的热点区域以导航的方式展示给用户，提高用户体验和辅助用户快速达到对算法运行的预期目标。可用于指导大图数据的迭代计算过程，具有重要的理论意义和实际应用前景。

图结构的应用非常广泛，如社交网络、交通网络等。大图数据由于其节点和边都很多，如何快速高质量地可视化是值得深入研究的问题。图数据可视化以图的形式来表示网络中的关联关系，使用户能够直观地观察和分析找出其中所蕴含的价值。本课题主要针对大图迭代计算过程中的布局的合理性、热点区域的突出性、展示的交互性等问题，研究大图数据的布局和可视化技术。本课题主要研究内容及成果包括：（1）面向大图数据可视化的分层策略，研究基于社区划分的分层布局模型。（2）基于聚簇的热点导航树的构建策略，研究Pregel并行处理模型下的限制标签传播距离的社区发现算法。（3）基于改进力导引模型的大图布局方法，使用去除游离节点等方法研究FR力导向算法的剪枝和预布局策略。（4）基于采样和过滤的大规模图数据的可视化，根据节点度分布情况研究采样策略并对非采样部分进行布局。（5）面向大图数据的可视化原型系统的构建。此外，我们还研究了一种基于改进初始图布局的属性图布局算法。基于上述研究成果，在国内外各种学术会议和期刊上发表了学术论文17篇，其中包括国际学术会议DASFAA2019、WISA2019和国际国内学术期刊JCST、“软件学报”和“计算机学报”等。被SCI收录8篇次、EI收录5篇次。包括课题负责人在内的3名教师参与了本课题的研究工作，协助培养了博士研究生1人（已毕业），培养了硕士研究生10人（8人已毕业，2人在读）。先后邀请国内外学者9人次来学校、学院和课题组做学术报告。希望这些成果为今后的实际应用推广奠定坚实的基础。