Map-based Graph Visualization

地图形式的图可视化方式指将图中的社群用一段连续的区域表示,不同的社群构成了地图上不同的“国家”。这样的可视化方式既可以提高可视化美观度,吸引用户花更多的时间探索数据[1];又可以增强用户的对可视化内容的记忆,更准确回忆自己的发现结果[2]。

Emden等[3]首先提出了GMap算法,从关系型数据构建地图样式的可视化形式。包括如下4个步骤:

  • S1: 计算图数据的布局
  • S2: 对图数据进行聚类
  • S3: 构建地图
  • S4: 对地图染色

其中S1和S2是紧密相连的,对于常见的力导向布局方式,聚类算法推荐使用基于模块度的聚类方式,而对于降维方式的布局方法,KMeans、DBSCAN等几何布局方式更加适合。在得到了节点的布局和聚类后,GMap里采用了Voronoi地图的方式。首先利用节点的位置生成Voronoi网格,每个节点在空间中都占有相应的区域(图1a)。但是划分出的区域太规整,与现实世界地图不规则的形状有很大差异。可以通过在节点外围添加随机点的方式,创建更多的Voronoi网格,这样可以使节点的周围更加不规则(图1b)。为了控制区域的大小,可以在节点的周围添加矩形框,沿着矩形周围添加随机节点,可以控制每个节点占据区域的大小(图1c)。最后可以得到相应的地图(图1d)。

图1 根据节点位置创建Voronoi地图并生成地图

通过将同一个社群内的节点所占区域连接合并后,便可以构建一副“地图”,地图上不同的国家代表图数据中不同社群(图2)。

图2 由亚马逊上关于”1984”相关图书生成的地图

在得到了地图后,需要对地图进行染色,从而更好的区分不同的国家。根据4色理论,只需要4种颜色就可以保证地图上任何两个相邻的国家颜色不同。但是GMap算法生成的地图上,同一个国家的区域不一定是连续的(如图2中地图左侧零散的粉色区域),所以4色理论不在适用。为了得到一个染色方式,作者把地图上的每一个国家当成一个点,如果两个国家相邻,那么在它们之间添加一条连边,这样可以得到一个图。公式1列出了近似后的目标函数,Ci代表每个国家的颜色,算法的目的是为了使临近国家的颜色差异尽可能大。

公式1: 关于GMap算法染色的目标函数

相比于传统的点边图,地图的方式可以更加直接的展现原始图数据中的社群信息。但是GMap生成的地图不能保证同一个社群在空间上是连续的。这个问题可以通过在布局时候考虑节点的社群信息,增大同一个社群节点之间的权重解决。

图3 a. 计算机热点研究地图[4] b. 网络安全事件地图 [5]

GMap提出后,研究者绘制了各色各样的地图,如图3a有计算机科学中不同研究课题关系构成的地图,热力图展现当前时间的研究热点;图3b是网络中不同计算机连接构成的地图,热力图展现了当前时间网络中的发生的安全事件。

基于地图形式的图可视化方式具有较好的视觉效果,能够非常直观的展现数据中的群组信息。当面对动态图数据时,如何在动态地图中保持用户的认知还存在挑战。Hu等[6]提出了在动态地图中保持图布局、聚类以及染色稳定性的方法,但是并没有验证大规模图数据的效果。Mashimad等[7]在利用地图分析规模图数据演变时,利用了全部时间步数据生成地图,因而地图的拓扑、国家不会发生变化,并没有解决大规模动态地图国家的变化问题。

图4 a. D-Map 信息传播地图 b. E-Map 事件演变地图

北大大学可视化与可视分析研究组将地图的概念首次引入到社交媒体数据的分析中。研究组在2016年IEEE VAST会议上发表了D-Map[8],该工作针对一个中心用户,将所有直接或间接参与转发他的一系列微博的人群投影到一个六边形地图上,映射的过程表征其相似性与转发时间特征。通过多种交互与链接方法,D-Map可以将一个社交媒体用户的社交图景给展示出来,并且每个人都有自己独特的特征。紧接着在2017年IEEE VAST会议上发表了E-Map[9],通过从社交媒体中的信息里提取关键词,将关键词、社交媒体信息、用户转发行为分别映射到地图中的城市、城镇以及河流,从而构建一个结构化的语义空间。在这个空间内,复杂的用户发送及转发行为转化为空间的轨迹以及城市之间的联系。通过多层次的时空可视分析探索方法,用户可以在E-Map中发现事件发展与传播的规律、关键用户的行为模式,以及这些用户是如何影响事件的走向。

基于地图形式的可视化方式在文本,社交媒体等数据方面的应用还有许多的探索空间,难点在于如果构建利用地图上的隐喻构建有效、可理解的可视化形式。

参考文献:

[1] Bahador Saket, Carlos Scheidegger, and Stephen Kobourov. “Comparing Node‐Link and Node‐Link‐Group Visualizations From An Enjoyment Perspective.” In Computer Graphics Forum, vol. 35, no. 3, pp. 41-50. 2016.

[2] Bahador Saket, Carlos Scheidegger, Stephen G. Kobourov, and Katy Börner. “Map‐based Visualizations Increase Recall Accuracy of Data.” In Computer Graphics Forum, vol. 34, no. 3, pp. 441-450. 2015.

[3] Emden R. Gansner,  Yifan Hu, and  Stephen Kobourov. “GMap: Visualizing graphs and clusters as maps”. In Proceedings of IEEE Pacific Visualization Symposium (PacificVis 2010), pages 201-208, Taibei, Mar. 2-5, 2010.

[4] Daniel Fried and Stephen G. Kobourov. “Maps of computer science”. In Proceedings of IEEE Pacific Visualization Symposium (PacificVis 2014), pages 113-120, Yokohama, Japan Mar. 4-7, 2014.

[5] J. Joseph Fowler. Michael Schneider. Thienne Johnson. Carlos Acedo. Loukas Lazos. Paolo Simonetto, and Stephen Kobourov. “IMap: Visualizing network activity over Internet maps.” In Proceedings of the Eleventh Workshop on Visualization for Cyber Security, pages 80-87. ACM, 2014.

[6] Yifan Hu, Stephen G. Kobourov, and Sankar Veeramoni. “Embedding, clustering and coloring for dynamic maps”. In Proceedings of IEEE Pacific Visualization Symposium (PacificVis 2012), pages 33-40, Songdo, South Korea, Feb.28 – Mar.2, 2012.

[7] Daisuke Mashima, Stephen Kobourov, and Yifan Hu. “Visualizing dynamic data with maps.” IEEE Transactions on Visualization and Computer Graphics, 18(9): 1424-1437, 2012.

[8] Siming Chen, Shuai Chen, Zhenhuang Wang, Jie Liang, Xiaoru Yuan, Nan Cao and Yadong Wu. “D-Map: Visual Analysis of Ego-centric Information Diffusion Patterns in Social Media”. In Proceedings of IEEE Conference on Visual Analytics Science and Technology (VAST’16), pages 41-50, Baltimore, USA, Oct. 23-28, 2016.

[9] Siming Chen, Shuai Chen, Lijing Lin, Xiaoru Yuan, Jie Liang and Xiaolong (Luke) Zhang. E-Map: A Visual Analytics Approach for Exploring Significant Event Evolutions in Social Media. In Proceedings of IEEE Conference on Visual Analytics Science and Technology (VAST’17), Phoenix, USA, Oct. 1-6, 2017.

评论关闭。