论文部分内容阅读
图可视化是使用计算机图形技术辅助用户理解图结构的理论和技术。图可视化的基础是图布局算法,是指将图结构嵌入几何布局空间的算法。在图布局算法中,布局空间的选择会影响图可视化的视觉效果和交互性。
球面布局算法是图布局算法的一种,是指选择球面空间作为布局空间的图布局算法。球面布局算法在表现图结构的相似性方面优于二维布局算法,而在交互性和可读性方面优于三维布局算法。然而,目前对基于球面布局的图可视化方法的研究较少。本文根据图的稠密程度和顶点规模,分别提出两种基于球面布局的图可视化方法。
第一种方法是一种基于球面布局的小世界网络可视化方法VS3。小世界网络是一种稠密程度较高的图,具有明显的聚类特征。VS3由一种基于Linlog的球面布局算法和一种隐喻实现方法组成。基于Linlog的球面布局算法是以球面FDA算法为算法框架,采用Linlog算法的力模型;隐喻实现方法是指对布局中的聚类结构的视觉编码方法,用于帮助用户对小世界网络作出直观的解释。
VS3的实验结果表明该方法的球面布局结果能表现小世界网络的聚类特征和无边缘的特征,并且有利于用户对聚类的识别和对细节结构的观察。这一定程度上说明VS3适合对稠密程度较高的图的球面布局。
第二种方法是一种大规模图的球面布局算法BaryLayout,由四个步骤组成:首先,从图的顶点集中选择出一个枢纽集;其次,使用KK算法布局这个枢纽集,从而得到一个框架布局;然后,根据顶点集与枢纽集的距离矩阵构造出一个权值矩阵;最后,利用这个权值矩阵和框架布局得到图的一个完整布局。BaryLayout的时间复杂度和空间复杂度都是线性的,实现简单,而且也适用于二维布局。
BaryLayout的实验结果表明该方法能处理具有上万个顶点的图的二维布局和球面布局。其中,二维布局结果说明BaryLayout与FM3算法具有相似的布局效果,球面布局结果说明BaryLayout适合对稠密程度适中的大规模图的球面布局。