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]在利用地图分析规模图数据演变时,利用了全部时间步数据生成地图,因而地图的拓扑、国家不会发生变化,并没有解决大规模动态地图国家的变化问题。

参考文献:

[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.

发表评论?

0 条评论。

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>