对关系网络中模糊重叠的群体进行可视化(Visualizing Fuzzy Overlapping Communities in Networks)

引言

图是我们可视化关系网络(Network)的主要手段,网络中的节点根据彼此之间的的联系紧密程度划分成许多聚类(这里称之为群体,Community),一个节点可以从属于一个或多个这种群体。比如人际关系网络中,这个群体是北大学生,那个群体是滑雪爱好者,还有一个是东北老乡会。群体之间会有很多的重叠(Overlap),这种重叠可以分为确切的(Crisp)和模糊的(Fuzzy)。确切重叠表示对于一个节点,我们可以明确地知道它是否从属于一个群体,而模糊重叠表示一个节点在一定程度上从属于一个群体,因此可以把确切重叠看作模糊重叠的特例,模糊重叠更符合结点和群体的实际关系。

针对一个网络,如何展示群体间的这种重叠关系,对我们分析网络的结构,发现特殊个体具有重要作用。现在已经有了较多的工作来可视化确切重叠,其中最主要的方法是对重叠节点染色,或者使用欧拉图,凸包等形式来表现群体间的关系,比如 Untangling Euler Diagrams[1]。但是可视化模糊重叠的工作很少,这篇来自2013年IEEE InfoVis的文章[2]就是针对网络模糊重叠的可视化提出来一套新颖的布局算法,并给出来两个案例研究。

fuzzy_01

图1 这篇工作通过不同级别的图来表现节点的模糊程度。
随着级别升高,具有较高不确定性的节点从群体中分离出来。

模型

针对一个关系网络,我们可以运用已有的聚类算法对网络进行划分,我们称之为群体(Community)。对于每一个节点和群体,有一个0~1取值的从属度(Belonging coefficient),记作 f。每个节点具有一个主导群体(Predominant),对应节点从属度最高的群体(如果有多个,就随机选一个)。对于最大从属度 f_max,我们定义 1-f_max 为节点的模糊度(Fuzziness)。

在此基础上,我们可以定义元图(Meta graph)。我们选定一个阈值 f_0,对于每一个群体,我们创建一个元节点(Meta vertex),对于所有以它为主导群体的节点,如果从属度超过 f_0,就把它留在元节点里,否则从元节点里分离出来,并连一条边。元节点之间,也建立起来元边(Meta edge),边的权重等于两个元节点内部节点互相连边的权重和。这样,我们就可以建立起来一个同时包含元节点和节点的混合图。对于不同的阈值,就可以建立起来一系列的元图。
当我们选择阈值为1时,那么元图就对应到原始图。

fuzzy_02

图2 元图示意图

如上图所示,当我们不断提高阈值时,就可以看到越来越多的节点从元节点中分离出来,从而知道哪些节点更加模糊。

可视化设计

为了在图中保持群体结构,作者提出了如下的布局算法:

  1. 提取出每个群体的核心节点,这些节点的模糊度为0,因此只从属于这一个群体。
  2. 提取出这些核心节点之间的边,得到每个群体的核心图。
  3. 对核心图进行布局。
  4. 把群体中的非核心节点加入到核心图中进行布局,只调整非核心节点的位置,保持核心图布局不变。
  5. 对所有布好局的群体,把它们合并起来。

为了表现模糊,作者针对节点和元节点分别设计了一种符号。对于节点,他们用渐变色区域的大小表示模糊程度,对元节点则使用外围的锯齿大小,这样用户在布局图中能很清楚的分辨出个体和群体。

图3 模糊度符号

图3 模糊度符号

案例分析

作者提供了两组案例,分别是学生接触关系网络和蛋白质相互作用网络。

图4 学生案例

图4 学生案例

第一个案例的数据来自一所小学10个班级的232名学生和10个老师,记录了这些人之间每天的相互接触。通过结果我们可以看出,大约有19%的学生和其他班级有接触。老师在所教的两个班级中接触均衡,基本布局在两个群体中间。而被聚类算法划分错群体的学生,因为网络关系复杂,所以会和其他班级学生混在一起。

图5 蛋白质案例

图5 蛋白质案例

第二个案例的数据是232种(作者喜欢这个数字:))可能引起癌症的蛋白质相互作用的关系网络。在上图中,C5,C6和C12有很强的模糊度,有好多蛋白质和这三个群体有关,并且起作用的程度各有偏重。这里,每一个群体代表了某种生理功能,比如C6代表细胞生长和死亡。另外我们可以看到,DMG连接起了C8和C13,它可能是这两种功能的桥梁。

总结

这篇文章对于网络中的群体模糊重叠问题设计了一套多层次的布局算法,在保留了每一个群体结构相对稳定的前提下,清楚展示了模糊个体在多个群体间的关系,为我们分析网络中的活跃结点和群体间的关系提供了有力帮助。但是作者没有提供很丰富的交互手段来对布局结果进行操作和调整。

参考文献

[1] Nathalie Henry Riche, and Tim Dwyer. Untangling Euler Diagrams. IEEE Transactions on Visualization and Computer Graphics, 16(6): 1090-1099, 2010
[2] Corinna Vehlow, Thomas Reinhardt, and Daniel Weiskopf. Visualizing Fuzzy Overlapping Communities in Networks. IEEE Transactions on Visualization and Computer Graphics, 19(12): 2486-2495, 2013

评论关闭。