關係網絡可視化 | 文獻泛讀之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,” BriefingsinBioinformatics 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.
本文作者