语义增强的大规模多元图简化可视分析方法

Semantic-Enhanced Visual Abstraction of Large-Scale Multivariate Graphs

网络图可视化可以有效展示网络节点之间的连接关系,广泛应用于诸多领域,如社交网络、知识图谱、生物基因网络等.随着网络数据规模的不断增加,如何简化表达大规模网络图结构已成为图可视化领域中的研究热点.经典的网络图简化可视化方法主要包括图采样、边绑定和图聚类等技术,在减少大量点线交叉造成的视觉紊乱的基础上,提高用户对大规模网络结构的探索和认知效率.然而,上述方法主要侧重于网络图中的拓扑结构,却较少考虑和利用多元图节点的多维属性特征,难以有效提取和表达语义信息,从而无法帮助用户理解大规模多元网络的拓扑结构与多维属性之间的内在关联,为大规模多元图的认知和理解带来困难.因此,本文提出一种语义增强的大规模多元图简化可视分析方法,首先在基于模块度的图聚类算法基础上提取出网络图的层次结构;其次通过多维属性信息熵的计算和比较分析,对网络层次结构进行自适应划分,筛选出具有最优属性聚集特征的社团;进而设计交互便捷的多个关联视图来展示社团之间的拓扑结构、层次关系和属性分布,从不同角度帮助用户分析多维属性在社团形成和网络演化中的作用.大量实验结果表明,本文方法能够有效简化大规模多元图的视觉表达,可以快速分析不同应用领域大规模多元图的关联结构与语义构成,具有较强的实用性.

As an effective tool to show the relationships between network nodes,graph drawing has been widely used in various fields,such as the social network,knowledge map,co-citation network and biological gene network.With the growth of scale of network graphs,it has been a research focus in the field of graph visualization to simplify the presentations of large-scale graphs.A variety of simplification visualization methods have been proposed to reduce the visual clutters caused by a large number of crossovers between nodes and edges,such as the graph sampling,edge bundling and graph clustering.However,these methods mainly focus on the topology of network,without taking the multi-dimensional attribute information associated with network nodes into consideration.It is always difficult to extract meaningful semantic information to help users understand the inherent association between topologies and multi-dimensional attributes.At present,both addressing the topology-based tasks and attribute-based tasks at the same time is still an open research problem.To solve the difficulty of visualizing such multivariate networks arising from two conflicting goals:visualizing topology and visualizing node attributes,we propose a semantic-enhanced method in this paper for the visual abstraction of large-scale multivariate graphs.First,the hierarchal structure is extracted from the original network dataset by means of a modularity-based graph clustering to find such communities including a set of highly interconnected nodes.Then,agraph cut scheme is designed to restructure the hierarchy of networks by computing and comparing the information entropies of multi-dimensional attributes of communities,so that the communities with the best aggregation characteristic on one attribute at different scale will be well preserved and displayed in the resultant simplified visualizations.Thus,these communities both showing obvious aggregations on the topology and semantics are selected successfully.Next,several coordinated views are designed in a visual analytic system,enabling users to further analyze the roles of different attributes in the network evolution and community formation from different aspects.For example,a multi-scale force-directed layout is applied to create the abstract visualizations of a large-scale multivariate graph to show the community-centric topologies.Two kinds of visualizations namely non-nested and nested layouts are both provided to solve different analysis tasks for users.While a tree view is provided to help users identify the hierarchies among these communities,which are designed as a pie chart to compare the aggregation properties of multi-dimensional attributes.In addition,an attribute sankey view is designed to explore the difference between the semantic-enhanced community set formed by different single attribute,allowing users to observe the homophily’s effects varying with different attributes.Three alternative glyphs are designed for the blocks in the attribute sankey view to show the macro and micro attribute information.Finally,a set of experimental results shows that our method can effectively simplify the visualizations of large-scale multivariate graphs in different fields such as the microblog retweeting and paper citation,and help users explore the topological and semantic structures of graphs.The utility of our approach is also demonstrated by domain experts through an in-depth case study.