那这样的地图是怎么生成的?GMap的主要步骤是: 1)先将网络图画在二维上;2)用聚类分析的方法把网络图中的节点归类;3)把各个类别中的点构造Voronoi Diagram,而Voronoi Diagram就是地图中的各个区域;4)给地图上色。

为 什么要有第一步呢?因为实际中的很多网络数据,比社交网络要复杂的多,并且基本上都是高维数据,也就是说每个节点包含多个数据。所以在把这些数据画在二维 上之前,需要对这些数据进行降维。具体的降维方法有PCA,  multidimensional scaling, LLE, isomap等等。当然也有我们多次提到过的“弹簧”模型(force-directed algorithm)。

对于第二步,我们前面的帖子介绍过了点聚类分析,这里就不重点展开了。

image courtesy of Emden Gansner, et al.

重 点是第三步。上面的示意图表示了这一步的主要流程。a) 经过第二步,我们已经有了分类,我们可以对于每种分类的点构造Voronoi Diagram。但是可能得到形式比较难看,不像真正的地图;b) 要把规则的Voronoi Diagram变得更加自然,我们可以在随机外面放些假象的点,这些点可以控制Voronoi Diagram的形状,看上去更象真的地图中的区域;c) 每个区域我们还要写个标签等等,而这些标签有大有小,根据每个区域的重要性。如果直接用b) 中的方法,那么有些区域中的标签就太大了。解决这个问题的方法是在这些标签的外框周围也随机放些假象点,然后再构造Voronoi Diagram,这样的话就能生成既自然又美观大方的地图区域了。

第四步给区域上色,不是很简单。因为第二步中聚类分析结果得到的点集在空间上可能并连成一块。这样会造成第三步生成的国家可能七零八落。这样的着色问题就比实际的地图要复杂的多。论文里提出了一种着色方法,这里限于篇幅,我们就不介绍了。有兴趣的同学可以看原文。

image courtesy of Emden Gansner, et al.

上 面这张图,显示了用GMap方法生成的关于美国电视节目的分类地图。地图中的每个国家对于于不同的节目类型,比如新闻,儿童,搞笑等等。放大到每个国家中 可以看到各个具体的聚类分析结果,每个聚类中网络图包含的节目都是很类似的。比如在地图的左下角有个国家叫Leftbank, 对于于新闻类,其中主要有CNN, MSNBC等等。有趣的是地图的右边偏下有个国家叫Rightbank, 也是属于新闻类,而其中的主要节点就是Fox。 熟悉美国媒体的同学们可能会猜出为什么新闻类会分出这样两个国家。

© 2011, 视物 | 致知. All rights reserved.

Related Posts: