PIWI：基于社群结构的图的可视分析

---

社群结构是真实网络中一个重要的特征。这个特征表现为团簇内的顶点紧密相连，团簇间的连接很少。与社群相关的图可视分析任务，比如探索社群之间的关系，分析基于属性的结构关系，根据感兴趣的结构或属性选择相应的顶点等，是从网络发现、获取信息过程中，常见的任务。在这个工作，我们实现了一个新颖的可视分析工具，PIWI。该工具能够支持用户高效的进行前面列举的、与社群相关的图可视分析任务。通过无交叉、直观、有丰富信息的可视化视图，结合丰富的交互方式，PIWI支持用户在上千个顶点的图中高效地探索分析图信息。

我们将通过在真实网络中的可视分析、探索过程，介绍PIWI的可视化形式和交互方式，从而分析该系统的有效性。

我们分析的数据，是2011年2月11日到2011年4月25日期间，纽约时报上1078篇世界新闻文章。我们从这些文章中提取出标签，作为图中的顶点；提取标签之间出现在同一篇文章的情况，作为图中的边。这是一个有1200个顶点（下文称之为“标签”）和7042条边的图，我们称之为NYT图。在这个图中，顶点表示标签，两个标签之间的连边，表示这两个标签至少同时出现在同一篇文章过。

图1 NYT图社群检测结果。一共有12个社群，每一行表示一个社群。蓝线下面社群信息是通过滚动滑块获得的。

初始化后，系统会将图中社群信息展示给用户。社群检测时可以选择PIWI内嵌的检测算法，也可以自行导入外部的社群检测程序。图1展示了NYT图的社群结构。在这个初始化中，我们导入了叫作AdjCluster的图分割算法。这个算法将NYT图分为12个社群（如图1）。

在图1中，一个云标签，展示的是一系列相关的标签。其中它们的大小表示它们的受欢迎度。用户可以根据标签的字母顺序或其大小，对这些标签进行排序。在PIWI中，一个标签云展示的是同个社群中的所有标签。图1右侧的点图，是根据用户感兴趣的属性，采用无交叠的方式，来展示标签之间的社群关系信息。其中，每个小方块表示一个标签，颜色表示其所属的社群。从左往右，第一个点图－－成员图，展示的某个社群所有的标签。第二个点图－－D1图，展示的是与该社群中的标签直接相连的所有标签。第三个图－－D2图展示的是与该社群中的标签路径长度为2的所有标签。同样的方式，第三个点图－－Dn图定义为展示与该社群中的标签路径长度为n的所有标签。用户可以根据任务需要，设置相应的路径长度。

图2，用户在分析社群间的关联关系

PIWI系统支持一系列新颖的交互方式。我们将通过一个实际的任务来分析，如何使用该系统。这个任务是分析特定的社群与其它社群之间的关系。在NYT图中，某个社群中的“核能量”，“福岛第一核电厂（日本）”标签引起用户的关注。她想要分析这个社群与其它社群的关系。为此，她刷新了选择状态，然后点击选择该社群的D1图。现在，所有与该社群中的标签直接相连的标签都被选中了。然后，她选择了“Sort Cluster”按钮，将社群根据其含有的被选中的标签数量，进行降序排序。现在，所有的社群，根据与她感兴趣的社群的相关程度，从上往下依次排布。

之后，该用户发现在一个相关的社群中，有“法国”，“俄罗斯”， “德国”这些标签（如图2（3））。这个社群为什么会跟之前感兴趣的那个社群相关呢？为探索这个问题，她将选择状态更新为“感兴趣”，然后选择了该社群的D1图。现在，只有与两个社群中的标签，路径长度都为1的标签被高亮（如图2（b））。为更好的分析这些被选中的标签，用户将其它标签从选择区域中删除了。之后，用户点击了“查看边”按钮。通过图2（7），她发现一些感兴趣的文章，比如标题为“Japan’s nuclear crisis strokes fear in Europe”的文章。她点击文章的标题，通过查看原文进一步分析这些标签的关系。

在这篇文章中，我们提出一个新颖的可视分析系统－－PIWI。这个系统支持用户从社群结构的角度，探索分析多变量大图。系统中的标签云和点图从语义、属性角度展示了图的社群结构信息。

文章

引用

Jing Yang, Yujie Liu, Xin Zhang, Xiaoru Yuan, Ye Zhao, Scott Barlowe, and Shixia Liu. PIWI: Visually Exploring Graphs Based on Their Community Structure.IEEE Transactions on Visualization and Computer Graphics, 19(6):1034-1047, 2013.