什么是节点链接法、邻接矩阵法、混合布局法?

2024年4月2日10:26:46什么是节点链接法、邻接矩阵法、混合布局法?已关闭评论

图可视化是指将图数据通过计算机图形学和图像处理技术,转化成图形或图像,完成信息展示、交互等功能。图可视化作为信息可视化的子领域,通过展示元素、关系,帮助用户获取数据的洞悉能力,已被广泛地应用在流程图、社交网络、因特网、蛋白质网络等关系数据中。

最常用的布局方法主要包括节点链接法(Node Link)、邻接矩阵法(Adjacency Matrix)、混合布局法(Hybrid Layout)三类。三者之间没有绝对的优劣,在实际应用中我们可以针对不同的数据特征以及可视化需求选择不同的可视化表达方式。

(一)节点链接法

节点链接法具体表现为顶点表示信息实体,边表示信息实体间的关联关系。这样的表达清晰直接,具有较高的可读性,方便用户理解,是最直接的一种可视化方法。

图可视化中的节点链接法对于图中各顶点的位置布局并没有要求,只要将图中的顶点和顶点之间的关系表达清楚即可。为了实现布局的实用性和美观性,创建网络数据可视化的图形需要遵循以下4条准则:连接边的交叉要尽可能少;顶点和边的位置要尽可能均匀;整体布局对称,边长尽量统一;连接边要尽量平滑。

此外,对于图形整体而言,其纵横比、所有连接边的数量和,也是要考虑的重要因素。节点链接法因其能够对网络结构、用户交互关系进行明朗的表达,在网络数据可视化领域得到了主要应用。目前,节点链接法已经产生力引导布局、多维利用尺度分析布局和弧长链接图等多个变种。图13-25和图13-26分别是利用力引导布局和弧长链接图绘制的人物图谱。

图13-25 力引导布局绘制的人物图谱

图13-26 弧长链接图绘制的人物图谱

(二)邻接矩阵法

邻接矩阵法的主要思想是用一个 × 的矩阵来表示网络中的各顶点及顶点关系。矩阵中的一行一列对应一个信息实体,矩阵的位置( )描述了第 个信息实体和第 个信息实体之间的关系。

邻接矩阵法能很好地表达一个两两关联的网络数据(即完全图),而节点链接法不可避免地会造成极大的边交叉,造成视觉混乱;而在边的规模较小的情况下,邻接矩阵法不能呈现网络的拓扑结构,甚至不能直观地表达网络的中心和关系的传递性,此时节点链接法较优。

邻接矩阵法的另一个优点就是能够利用矩阵形式,即矩阵的对称性,清楚地表达网络关系的方向性。对角线对称矩阵表示网络关系是无向的,而非对称矩阵则可以表达有向关系网络。邻接矩阵法可以用来描述书籍中的人物图谱关系等,如图13-27所示,是基于邻接矩阵法对《悲惨世界》中的人物图谱进行可视化的结果。

图13-27 邻接矩阵绘制的《悲惨世界》人物图谱

同时,邻接矩阵的自身性质决定了其可视化效果往往具有稀疏性,空间利用率不高。这是因为,并不是所有的顶点之间都存在着关联关系,体现在矩阵上,就是稀疏矩阵。为了解决这一问题,通常还要采用高维嵌入(High-Dimensional Embedding)方法和最近邻旅行商问题估计(Nearest-Neighbor TSP Approximation)方法对稀疏的邻接矩阵进行排序。

总体来说,邻接矩阵法解决了布局不均匀,边与边可能交叉的问题,适用于深层次的挖掘,但在对网络结构、网络关系的表达上不够清晰明朗,而且,一旦网络结构中的顶点数目规模较大,邻接矩阵就不能保证在有限的屏幕空间将所有的顶点都清晰地表达出来。

(三)混合布局法

通过对以上两种网络数据可视化方法的介绍,我们不难看出,节点链接法适用于节点规模大但边关系较为简单,并且能从布局中看出图的拓扑结构的网络数据,而邻接矩阵法则更适用于节点规模小,但边关系复杂的数据。这两种数据的特点是用户选择布局的首要区分原则。

但在实际生活中,网络数据集并不是一味显示一种特征的,任何一种单一的图可视化方法都不能使其进行很好地表达,因此需要一种新的具备两者优点的网络数据可视化方法——混合布局法。使用混合布局法时,针对局部数据,用户能自由、灵活地选择可视化方法。由于混合布局法综合了节点链接法以及邻接矩阵法两种方法,因此混合布局法又被称为点阵法。如图13-28所示,利用混合布局法对信息可视化学术圈学者的合作关系进行可视化。

  • 版权声明:本篇文章(包括图片)来自网络,由程序自动采集,著作权(版权)归原作者所有,如有侵权联系我们删除,联系方式(QQ:452038415)。