根据局部群簇信息自适应的解开小世界网络中的纠结 (Adaptive Disentanglement based on Local Clustering in Small-World Network Visualization)

社交网络是高度密集的小世界网络图。在小世界网络中,大部分节点不直接的连接,但是它们从任一其他节点经少数几步就可到达。采用已有的图布局算法布局小世界网络图,总是会得到一个类似毛团的视图。比如说,力导向算法针对网状结构的数据,总是可以得到不错的布局。但是,当数据是个小世界网络时,其效果也不好。这篇文章提出一个预处理方法,自动地选择最佳阈值,过滤掉小世界网络中不重要的边,得到最优的图骨架。最优的图骨架指其内部的图结构信息展示的最清晰。图1是直接采用力导向算法获得的布局,根本不能清晰地展示出图的内部结构。

图1 采用力导向布局算法获得的小世界网络布局

图1 采用力导向布局算法获得的小世界网络布局

针对这个现象,有很多工作研究如何减少网络中的混乱。边聚集(edge-bundling)[1] 是一个常见的减少边交叉的方法。但是这个方法针对小世界网络是无效的,因为它们只是将相近的边聚集在一起,但是没有处理点的分布;另一个方法是改变顶点之间的距离,比如如果两个顶点的度都比较高,其距离就会被布置的较远[2], 这个方法似乎会比较有效,因为它尝试改变顶点的分布。但其实这个方法针对顶点的度的分布斜率较大的网络才有效;放大局部的布局[3],可以帮助用户探索图局部结构信息,但是这种方法,需要用户手动的选择感兴趣的区域;还有一种常见的方法是采用聚类的方法计算出图中的聚类,然后将结果可视化出来[4],这个方法其实是将可视化问题转换成聚类检测算法上了;此外,还有一种方法是根据图的结构,进行图的简化[5]。这个方法的基本思想就是根据图中边的重要程度,过滤掉不重要的边,保持图中聚类的结构。这个结构,在这里,我们称为图的骨架(backbone)。

图2,是一个已有的图简化算法的流程图[5]。首先,输入一个图数据,然后根据图的结构,计算图中边的权重。之后,选择合适的阈值,根据边的权重,过滤掉不重要的边。最后,得到最优的图骨架。这个方法的问题在于如何选择阈值,使得最后的图骨架是最优的。采用手动调整的方式,并不合理。因为阈值跟最后的结果不是线性关系。阈值中很小的变化都有可能得到完全不同的结构。

图片 2

图2 已有的图简化算法的流程图[5]

针对这个问题,这篇文章提出一个预处理方法(图3是该方法的流程图)。这个方法可以自动的选择合适的阈值,使得最后得到的图骨架是最优的。那么,如何比较每个阈值得到的图骨架的优劣呢?作者提出采用平均聚集系数(average clustering coefficient) 来量化图骨架中图聚集结构是否清晰(下文简称为图骨架质量)。同时,他们还提出使用φ系数(phi coefficient) 来衡量平均聚集系数在量化图骨架质量上的效果。下面我将详细介绍这两种系数。

图片 3

图3 文章提出的方法的流程图

平均聚集系数用来衡量图骨架中图聚集结构是否清晰。它主要度量了顶点与其邻居连接的紧密程度。顶点v的局部聚集系数定义为:

屏幕快照 2016-04-29 下午8.39.44

其中closed triangles表示三个顶点是相互连接的;connected triplet表示三个顶点是连接的,但是并不要求其相互连接,也就是说它们可以是一条长度为2的路径。平均聚集系数是所有顶点的局部聚集系数的平均值。

Φ系数是皮尔森相关系数(Pearson`s correlation )中的一个变量,一般用于衡量两个变量之间的相似度。Φ系数在文章中用于衡量平均聚集系数在量化图骨架质量上的有效性。基本方法就是比较根据阈值过滤边得到的图骨架与真实图结构(ground-truth)之间的相似程度。首先,根据图骨架信息,得到矩阵X。基本方法是如果两个顶点之间有边,则相应的位置值为1,否则为0。然后根据图的真实结构,得到矩阵Y。基本方法是若两个顶点属于同一个聚类,那么矩阵相应的位置为1,否则为0。具体定义如下:

图片 01 图片 02

然后,根据下面的式子计算变量X和Y的相似度。

图片 03

其中, 参数a, b, c, d从下面的表中获得:

图片 04

a表示在矩阵X中值为1,在矩阵Y中值也为1的单元的数量;b表示在矩阵X中值为1,在矩阵Y中值为0的单元的数量。c, d的计算方法相似。

为了评估平均聚集系数在量化图聚集结构清晰程度上的效果,文章展示了两个评估例子,分别使用了真实网络数据和人造数据。

在评估中使用的真实网络数据,是关于美国100所高校学生在facebook上的社交关系。事实上,这个数据集一共包含100个小世界网络数据。在这些小世界网络中,顶点的数量分布在762到41,000,边的数量分布在16,000到1,600,000。同时,它们还有很多其他的属性,比如学生的性别,所在的宿舍区等。因为facebook中真实的社交网络结构,是不可能获得到的。为此,作者们根据顶点的宿舍属性,将网络进行分类。也就是说,如果顶点1和顶点2属于同个寝室区,那么它们是属于同一类的。否则,它们属于不同类。这个分类结果主要用于计算Φ系数。人造数据在效果评估中,被命名为PPM500。

在具体评估中,首先,我们来讨论用平均聚集系数量化图骨架质量的有效性。图4展示的是平均聚集系数与Φ系数之间的关联关系。

图片 4

 图4 平均聚集系数与Φ系数的关联关系。Y轴表示平均聚集系数或Φ系数值,x轴表示图中剩余边的百分比

我们可以发现,如果Φ系数比较大的话,两个曲线的峰值就会在x轴上,靠的非常近。比如Auburn71, Caltech36, Leihigh96, PPM500。两个曲线的峰值相聚的很近,说明,根据平均聚集系数,选择阈值,过滤掉不重要的边,是可以得到清晰的图骨架的。其他的图中,Φ系数的变化程度很小, 比如Havard1。这个现象表明,宿舍属性并不能很好的反映这些社交网络中的聚集信息。

图5和图6展示的是最后的图骨架采用力导向算法计算得到的视图。我们可以发现,在图5中,局部的聚集结构在(a)和(c)都展示的非常清楚。但是在哈佛大学的视图(b)中,我们不能看到局部结构信息。这有可能是由于哈弗大学只给一年级的学生提供宿舍导致的。

从图6,我们可以看到,在图中保留25%的边时,图结构信息展示的最清晰。当过多的边被删除时,图中结构就会被破坏。

图片 5

图5 fackbook100三个学校的学生在facebook上的社交网络。左下角的小图是图简化之前采用力导向算法获得的布局。大图表示图简化的结果。

图片 6

图6 人造数据图简化的结果示意图。从左到右,剩余的边所占的比重分别是100%, 34%,25%和5%

总的来说,这篇文章提出一个预处理方法,自动地选择最佳阈值,过滤掉小世界网络中不重要的边,得到最优的图骨架。最优的图骨架指其内部的图结构信息展示的最清晰。作者们提出采用平均聚集系数来评估图骨架的质量。同时,他们用Φ系数来衡量用平均聚集系数评估图骨架质量的有效性。

在小世界网络的图简化中,添加自动选择过滤阈值的预处理阶段,在图可视分析中,显得非常有用。采用这种方法,我们可以快速的获取某个大图的内部结构,方便用户获得感兴趣的结构,从而进行更为深入的研究。

参考文献:

[1] D. Holten and J. J. van Wijk, “Force-directed edge bundling for graph visualization,” Computer Graphics Forum, vol. 28, no. 3, pp. 983–990, 2009.

[2] K. Boitmanis, U. Brandes, and C. Pich, “Visualizing internet evo- lution on the autonomous systems level,” in Proceedings of the 15th International Symposium on Graph Drawing (GD 2007), ser. Lecture Notes in Computer Science, S. Hong, T. Nishizeki, and W. Quan, Eds., vol. 4875. Springer, 2007, pp. 365–376.

[3] F. van Ham and J. J. van Wijk, “Interactive visualization of small world graphs,” in Proceedings of the 10th IEEE Symposium on Information Visualization (InfoVis 2004). IEEE Computer Society, 2004, pp. 199–206. [Online]. Available: http://dx.doi.org/10.1109/INFVIS.2004.43

[4] F. Zaidi, A. Sallaberry, and G. Melanc ̧on, “Revealing hidden com- munity structures and identifying bridges in complex networks: An application to analyzing contents of web pages for browsing,” in Proceedings of the IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technologies (WI-IAT ’09). IEEE, 2009, pp. 198–205.

[5] A. Nocaj, M. Ortmann, and U. Brandes, “Untangling the hairballs of multi-centered, small-world online social media networks,” Journal of Graph Algorithms and Applications, vol. 19, no. 2, pp. 595– 618, 2015.

1 条评论。

  1. 请问作者公布源代码了么?