关系网络 | 文献泛读之1: node-link 与 matrix

牵涉到关系网路可视化的种类，大致可以分成两个类型，一个是使用node-link（点线）、另一个是使用matrix（矩阵）。node-link（点线），可以呈现较多细节资讯，但容易使关系网络可视化变得很复杂；matrix（矩阵），可以大幅简化关系网路，并清楚呈现两两之间的关系，但同时也遗失了关系网路数据中的部分重要资讯，像是无法呈现地理资讯。这篇文章梳理了几篇论文，看历年来的学者们如何在node-link与matrix之间，透过不同的可视化设计方式来改善关系网络的易读性。

基本介紹

a.Node-link（点线）：由node（关系节点）、edge（关系线）构成。

b.Matrix（矩阵）：关系节点在矩阵图中是行与列，关系线是矩阵方块的颜色，若关系节点两两之间有连接，则对应到的方块会有颜色，例如右图中的中间红色直条，代表的是关系节点C3，任何与它有关系线连接的节点都有互相对应的蓝方块。

Node-link与matrix是两种常用来表达关系网络的可视化样式。

本文是关系网络系列文章的第三篇，概要总结了我在2017年秋季博士的课程Network science所学，文章提到的论文基本上是这门课程要求阅读的文献。修这门关系网络的课，是我第一次接触这个博大精深的领域，所以相关的知识积累不足；若想要深入了解这篇文章中提及的论文，可以在文末找到相对应的文献。

关系网络可视化运用范围非常广，任何呈现关系的数据皆会使用到，用来阐述人事物之间的相对关系，如：政治-呈现两党参议员之间的关系、城市规划-呈现城市与城市之间的经贸关系等等：

虽然node-link样式的关系网络可视化运用范围很广，但当数据量庞大的时候，对于一般未受专业训练的受众而言较难以理解[1]。本文梳理了一些改善易读性的论文，主要探讨视觉层面，具体的算法并不讨论。

除了不讨论算法，此文章的局限还包括了关系网络的可视化样式，只着重在node-link与matrix，其余的关系网络样式，如具有阶层结构的树图，以及3D可视化(，皆不在討論的范围内，如下图：

选择只探讨Node-link与Matrix的原因是，在课程中我们阅读的文献集中在这两个类别，其他类型的可视化论文并没有在阅读清单中。

—

Node-link 布局

虽然node-link的运用范围非常广，但存在一些问题。只要数据量一变大，可视化的易读性就会下降，对于一般未受过专业训练的使用者更是会有难以理解的问题。这种难以理解、看不出任何数据特征的关系网络可视化，又被戏称为发球（hairball）：

如何改善这种发球问题呢？在2002年的时候，一些绘制基本法则就已经被总结归纳出来[2]，如避免关系节点重叠、避免关系线重叠、避免关系节点跟关系线重叠等概念性的设计法则，用来改善关系网络可视化的易读性。

另外，有篇更早期的论文[3]，指出了关系网络可视化能够较容易被理解的前提是，符合这三个评价标准：极大化对称性、极小化关系线重叠、极小化弯曲。这三个评价标准，可以帮助判断选择合适的关系网络算法。在此论文中，极小化关系线重叠被实验证实，是最重要的评价标准，能够最有效提升关系网络可视化的易读性。

具体如何增加NL的易读性，基于这门课程要求阅读的文献，总结了四个方法：聚集关系节点，聚集关系线，融合关系节点&关系线，几何排列关系节点的位置。

1. 聚集关系节点

此类的关系网络，关系节点的绝对位置比较不重要，重要的是彼此之间的相对位置；在有限的绘图空间下，如何提升易读性、加强绘图效率，来方便使用者找出关系网络的特征[4]，是这一类算法的主要任务。

从一坨乱的发球中，看不出任何的数据特征，可知目前使用的算法无法帮助理解数据，此时可以使用其他算法来改变layout[5]：

2.聚集edges

此类关系网络，比较多运用在地图，因为关系节点代表在地图上的点，位置信息是相当重要的数据，不可轻易改变，所以关系节点是固定的；相对于聚集关系节点，增强关系线的易读性是重点。

2009年，有篇论文提出了用力导引的方式来聚集关系线[6]，如下图，（a）是没有使用这方法的可视化样式，（b）与（c）是使用这方法时候的样式，在视觉上的杂乱明显减少许多。（b）与（c）的差别在于（c）使用了更进一步控制关系节点的算法，在尽量维持原有捆绑数量的前提下，用来避免不符合连接规则的edges被捆绑在一起。

在2012年时，“地铁路线样式”的方法被提出[7]，此方法用来聚集关系线，可以避免不必要的节点与关系线的重叠。总而言之，这个方法可以使关系线平滑流畅，并同时让读者可以了解关系网络的全局网络结构，提供了全局分析与局部分析。这篇论文的算法让关系线有三个特色：不能重叠、水平排列并有间隔、极小化交叉。

a.原始的关系网络可视化，b.使用了这篇论文的算法后的可视化结果：

2017年，一篇论文总结了一些聚集关系线的算法（下图左a至e）[8]，并提出了一个更为有效的方式来聚集关系线——Confluent Drawing（下图右）。

此篇论文提出的Confluent Drawing算法，依照关系网络的连通性，把具有相同的关系节点的关系线被聚集成一束；而传统的方法是用空间上的相近性来聚集关系线，此时若关系线没有被明显区分，容易造成视觉上的错误解读。在这篇论文中的实验证明，与现有的聚集关系线的方法比较之下，读者在解读关系网络时会有比较好的理解，但跟上图的“地铁路线样式”聚集方法比较时，实验结果没有明显区别。

3.融合nodes&edges

这一小结讨论的方法是我们这门的课授课老师Cody Dunne在读博期间提出的[9]，这方法主要是简化关系网络的可视化，使用图形取代复杂的、纵横交错的关系网络。这个方法有一些优点，例如：节省绘制关系网络的空间、比较容易解读、揭示隐藏的关系。

下图是一个案例，展示美国2007年参议院共同投票的关系网络，左图是用原始方法绘制，右图使用此论文提出的方法绘制：

4.几何排列nodes的位置

此类方法是固定nodes的位置，并以几何图形呈现，如网格、圆形、直线、三角形[10]；edges可能融合或不融合:

弧线图，是一种比较常见的可视化方式，在2002年被 Martin Wattenberg（谷歌大脑People + AIResearch的头）提出[11]。一开始被用来可视化序列数据，序列数据通常有不断重复的特征。可视化方式是先把数据按照顺序排成一列，再把具有相同数据特征的段落用半透明的弧形关系线连接起来，所以这个弧线若越宽，代表该部分重复的数据越多。

在此篇论文中，弧线图的展示案例是音乐作品，如下图，使用弧线图可视化贝多芬《致爱丽丝》的音调：

与上一篇论文的作者相同，Martin Wattenberg 在2006年时提出了PivotGraph 的可视化方法[12]，使用网格来呈现关系网络数据。作者在论文中提到，这个方法适合用来呈现多元数据，例如使用不同颜色来表示不同类型的关系节点，可以让多维度的数据比较更直观。

更具体来说， PivotGraph除了把关系节点固定在网格之外，还聚合了同类型的关系节点、关系线。关系节点的大小、关系线的粗细来表示关系节点的多寡与关系线的密集程度。

2011年，Hive plots被提出[13]。论文中，除了想要改善Node-link关系网络的视觉杂乱之外，还探讨其他Node-link的问题：在Node-link中，不同的布局算法的产出结果很不一样，另外，细微变动数据也会产生跟原先很不一样的可视化结果。

关系网络的算法，当被运用在大量数据时，可能产出结果相当不一样的可视化：

在Hive plots中，关系节点放射状的排列在轴上，使用节点坐标系可以使可视化结果具有一致性，并更容易理解。

Hive plots解决的另外一个问题是稳健性，亦即在传统关系网络中，些微的改变会使可视化结果很不一样。如下图，同样是把关系线E1移除，传统的Node-link可视化会变得不一样（关系节点N1的位置移动了），但在Hive plots中仍维持可视化结果的一致性（关系节点N1的位置维持不变）。

以上是针对Node-link关系网络可视化的概要性讨论。数十年来关系网络的学者们，除了在node-link的基础上不断改进关系网络可视化的易读性，还使用了另外一种截然不同的可视化表现方式——Matrix矩阵，来改进node-link可视化的不足。接下来探讨matrix矩阵如何弥补node-link的缺失，以及两者如何相辅相成。

—

Matrix 布局

Matrix可视化，简化了node-link可视化的布局，关系节点被排列在矩阵的行与列，关系线被矩阵的方块颜色取代，若两个关系节点有关系线连接，则矩阵的方块有颜色，若两个关系节点没有关系线连接，则矩阵方块没有颜色。使用矩阵的方式来呈现关系网络让可视化较为整洁，但关系网络的路径却被隐藏了，无法从矩阵中去看出关系线的连接方式。

2004年，一篇研究论文展示了node-link可视化与matrix可视化在易读性上的各自优势[14]。

在此篇论文设计的实验中，当关系网络的关系节点大于20个的时候，matrix的表现会比node-link要好。只有在需要找出关系网络的路径时（路径查找），node-link的表现会比较好。

既然matrix跟node-link有各自不可取代的优势，以下两篇论文阐述了学者们如何结合这两种关系网络可视化来辅助可视分析。

社交网络的数据通常具有局部密集、全局稀疏的特性，这使得node-link样式的可视化变得难以阅读，因为局部的关系网络过于密集；但路径查找在社交网络中是主要的分析任务，matrix样式的可视化无法提供支持。在2007年，一个结合node-link与matrix的关系网络可视化样式被提出——MatLink[15]，整合了node-link与matrix，node-link叠合在matrix的边上，以动态交互的方式呈现关系线。

如下图，a.传统的node-link样式，在社交网络中通常无法让人解读，因为局部数据过于密集；b.传统的matrix无法让使用者执行路径查找的分析需求；c与d展示了MatLink的设计样式。

动态展示MatLink的交互：

另外一种结合node-link与matrix的关系网络可视化样式——NodeTrix[16]，在同一年（2007年）被提出，此可视化样式跟MatLink一样专注在社交网络分析。

NodeTrix，一样结合了node-link与matrix的优势，但在设计上与MatLin不同。在NodeTrix中，关系节点变成矩阵，亦即矩阵被关系线连接，用来展示各个矩阵之间的关系网络。

如下图，使用NodeTrix来展示Info-Vis共同作者关系网络：

动态展示NodeTrix的交互：

—

结论

node-link样式的可视化与matrix样式的可视化，有各自的优点与缺点。node-link样式的可视化可以展示关系网络的结构，但当数据量变大时，会变得难以解读；matrix样式的可视化可以节省绘图空间，且不易造成视觉杂乱，但在解读上没有node-link这么直观，而且无法展示关系网络的路径。在数十年的关系网络研究发展中，不断优化关系网络可视化的易读性的方法一直被提出，如何让使用者更能解读并分析关系网络是主要目标之一。此篇文章概要性的阐述了这个主题的几篇论文，总结了提高关系网络可视化易读性的几种方法。

关系网络是一门博大精深的领域，network science其中的science不是叫假的，相关的知识很广且深。在下面列出了几个关于关系网络的学习资源，提供对这领域感兴趣的人进一步探索学习。

下一篇文章，会以一篇论文为例，深入探讨NL跟Matrix运用到地图上的时候，在视觉设计上如何取舍，才能清楚表示可视分析。

—

学习资源

【博客】第十二周：社会网络分析分析——每周一讲多变量分析

http://shenhaolaoshi.blog.sohu.com/148753587.html

【微信公众号】干货丨【Day 22】复杂关系简单化、可视化，原来只需要两步...

https://mp.weixin.qq.com/s/CSNaOItuT6S-8QI_ANQrWw

【微信公众号】Love is All YouNeed | 无标度网络理论之父Barabási回应史上最严重质疑

https://mp.weixin.qq.com/s/zBBB7KiEf2p8CpOkxZs8FQ

【公開課】媒体大数据挖掘与案例实战

http://www.xuetangx.com/courses/course-v1:CUC+2018081701X+2018_T2/about

【案例】滴滴大数据眼中的中国城市生长

https://mp.weixin.qq.com/s/3UoB0PmQ0SV-FMsqNuzxQA

—

References

[1]Raga’ad M.Tarawneh, Patric Keller, and Achim Ebert, “A General Introduction To GraphVisualization Techniques,” Visualization of Large and Unstructured DataSets: Applications in Geospatial Planning, Modeling and Engineering -Proceedings of IRTG 1131 Workshop 2011, 2012, 151--164,https://doi.org/10.4230/OASIcs.VLUDS.2011.151.

[2]Kozo Sugiyama, GraphDrawing And Applications For Software And Knowledge Engineers (218: WorldScientific, 2002), https://doi.org/10.1142/4902.

[3]Helen Purchase, “WhichAesthetic Has the Greatest Effect on Human Understanding?,” Graph Drawing1353 (1997): 248–61, https://doi.org/https://doi.org/10.1007/3-540-63938-1_67.

[4]Stefan Hachul andMichael Jünger, “An Experimental Comparison of Fast Algorithms for DrawingGeneral Large Graphs,” Graph Drawing 3843 (2005): 235–50,https://doi.org/https://doi.org/10.1007/11618058_22; Stefan Hachul and MichaelJünger, “Large-Graph Layout Algorithms at Work: An Experimental Study,” Journalof Graph Algorithms and Applications, 2007, 345–69.

[5]Hachul and Jünger,“Large-Graph Layout Algorithms at Work: An Experimental Study.”

[6]Danny Holten andJarke J. van Wijk, “Force-Directed Edge Bundling for Graph Visualization,” EuroVis’09Proceedings of the 11th Eurographics, June 10, 2009, 983–98.

[7]Sergey Pupyrev etal., “Edge Routing with Ordered Bundles,” Computational Geometry 52(February 2016): 18–33,https://doi.org/https://doi.org/10.1016/j.comgeo.2015.10.005.

[8]Benjamin Bach etal., “Towards Unambiguous Edge Bundling: Investigating Confluent Drawings forNetwork Visualization,” IEEE Transactions on Visualization and ComputerGraphics 23, no. 1 (January 2017): 541–50,https://doi.org/10.1109/TVCG.2016.2598958.

[9]Cody Dunne and BenShneiderman, “Motif Simplification: Improving Network Visualization Readabilitywith Fan, Connector, and Clique Glyphs Nodes and Links Are Replaced withCompact and Meaningful Glyphs,” CHI ’13 Proceedings of the SIGCHI Conferenceon Human Factors in Computing Systems, May 27, 2013, 3247–56,https://doi.org/10.1145/2470654.2466444.

[10]Charles D. Stolperet al., “GLO-STIX: Graph-Level Operations for Specifying Techniques andInteractive eXploration,” IEEE Transactions on Visualization and ComputerGraphics 20, no. 12 (December 31, 2014): 2320–28,https://doi.org/10.1109/TVCG.2014.2346444.

[11]Martin Wattenberg,“Arc Diagrams: Visualizing Structure in Strings,” IEEE Symposium onInformation Visualization, 2002. INFOVIS 2002., October 28, 2002,https://doi.org/10.1109/INFVIS.2002.1173155.

[12]Martin Wattenberg,“Visual Exploration of Multivariate Graphs,” CHI ’06 Proceedings of theSIGCHI Conference on Human Factors in Computing Systems, April 22, 2006,811–19.

[13]Martin Krzywinskiet al., “Hive Plots—rational Approach to Visualizing Networks,” Briefings inBioinformatics 13, no. 5 (September 1, 2012): 627–44,https://doi.org/10.1093/bib/bbr069.

[14]M. Ghoniem, J.-D.Fekete, and P. Castagliola, “A Comparison of the Readability of Graphs UsingNode-Link and Matrix-Based Representations,” IEEE Symposium on InformationVisualization, 2004.

[15]Nathalie Henry andJean-Daniel Fekete, “MatLink: Enhanced Matrix Visualization for AnalyzingSocial Networks,” Human-Computer Interaction – INTERACT 2007, 2007, 288–302,https://doi.org/https://doi.org/10.1007/978-3-540-74800-7_24.

[16]Nathalie Henry, Jean-Daniel Fekete, and Michael J.McGuffin, “NodeTrix: A Hybrid Visualization of Social Networks,” IEEETransactions on Visualization and Computer Graphics,10.1109/TVCG.2007.70582, 13, no. 6 (November 5, 2007): 1302–9.

—

本文作者