基于角色的大图可视分析模型与方法研究

Visualization methods are fundamental to the analysis of the graph data. Typical usages can be found extensively in areas such as knowledge discovery and network security. In recent years of the big data wave, the visual analytics of large-volume high-complexity heterogeneous node-link graphs (big graph) pose new challenges to the research community. The state-of-the-art large graph layout algorithms cannot well support the real-time visualization and interactive analysis of the big graph. Meanwhile, the popular community-based graph visualization methods can neither resolve the visual clutters nor reveal graph semantics when the community structure is not prevalent. In this project, we propose to introduce the classical method of structural equivalence in the sociology research, based on the observations that various types of structural equivalence are common in big graphs of domains such as computer communications and online social networks. Through researches on fast algorithms to discover structural equivalences and the application of the lattice theory, we construct equivalence hierarchies among the graph nodes, based on which graph roles can be defined. We further propose to apply role-based graph compressions and establish a new model for big graph visual analytics. The advantages of our method are two-fold: (1) the visual complexity of the big graph can be significantly reduced, leading to better user consumability of the visualization; (2) coupled with the interaction methods on the transformed graph, the role semantics of the big graph are emphasized in the visualization, which brings additional help to speedup the visual analytics tasks for users. The ultimate goal of this project is to enable the efficient and effective visual analytics of a million-node graph in related areas.

可视化方法是关联图数据分析的核心手段,在知识发现、网络安全等领域均有广泛应用。近年，伴随图规模日益增长，大容量高复杂度异构关联图数据(大图)的可视分析带来新的挑战。经典图布局优化算法不能有效支持大图实时展示与交互分析。近期广泛采用的基于社区的图聚类可视化方法，对于大量社区结构不显著的大图数据仍难以解决视觉杂乱与真实语义表达的问题。 本项目紧密结合大图内在数据特征与外围应用需求开展研究，通过引入社会学网络结构等价理论，针对等价特性广泛存在的计算机流量网络、社会网络等大图数据，应用快速结构等价算法及格理论，抽取、归纳并压缩大图节点间多层次角色关系，提出并建立基于角色的大图可视分析模型。本方案一方面显著降低大图可视复杂度，有利于用户直观理解数据；另一方面配合变换后抽象大图交互方法，突出大图内在角色关系与语义表达，提升用户相关图分析能力。本项目长期目标为实现特定领域百万节点大图快速有效可视分析。

可视化方法是关联图数据分析的核心手段,在知识发现、网络安全等领域均有广泛应用。近年，伴随图规模日益增长，大容量高复杂度异构关联图数据(大图)的可视分析带来新的挑战。经典图布局优化算法不能有效支持大图实时展示与交互分析。近期广泛采用的基于社区的图聚类可视化方法，对于大量社区结构不显著的大图数据仍难以解决视觉杂乱与真实语义表达的问题。..本项目紧密结合大图内在数据特征与外围应用需求开展研究，在四年来取得了突出进展及高质量的研究成果。在大图可视分析模型基础理论方面，针对大图数据规模大、种类多、可视复杂度高等问题，分别提出了基于个人中心角色图结构、影响力角色图结构、异构网络角色图结构的可视摘要生成方法，以及新型大图可视化设计和多种用户交互模式。研究成果发表于TVCG, TKDE, VIS-15等国际顶尖期刊与会议。在大图可视分析算法方面，针对经典大图数据挖掘算法以直接计算问题答案为目标，其结果难以采用传统可视化形式展现的问题，深入研究了面向可视化的大图数据挖掘方法，并在相关大图结构数据、大图结构比较任务、大图数据结构化建模中得到验证。研究成果发表于TVCG, ICDM-14, ICDM-15等国际顶尖期刊与会议。在新型大图可视分析模型的应用系统原型方面，针对科技文献关联网络分析及人类脑部网络分析场景，研制了多套基于角色的大图可视分析实验系统，支持百万量级节点大图的可视分析。研究成果发表于TVCG, TKDD, ICDE-2016等国际顶尖期刊与会议。..2014年至今出版项目相关英文专著章节1份，发表相关论文20篇，其中国内外顶级与重要学术期刊和国际会议论文16篇，可视化与数据挖掘领域顶级IEEE/ACM Transactions文章6篇，SCI检索7篇，EI检索15篇。申请国内技术发明专利2项，培养研究生4名。