对关系网络图中的结点进行聚类是社群分析的一个重要方法，但对于特殊任务，比如寻找社群之间的公共结点，对边进行聚类则更加有效[1]。这篇EuroVis2015的文章[2]通过对偶邻接矩阵（Dual Adjacent Matrix）的方法，把结点邻接矩阵和边邻接矩阵合并到了一起，共同来进行网络图中的社群分析。

对偶图

在介绍他们的系统前，我们先来了解一下图的对偶图概念。

我们知道，图是由结点和边组成的网络数据结构，点边图和邻接矩阵是图可视化的两种重要方法（图1）。通过聚类算法，我们可以把结点划分成群组，如果把每个群组收缩为一个结点，群组结点之间的连边合并起来，就可以极大得减小图的规模（图2）。这是图可视化中比较常用到的技术。

图1：点边图和邻接矩阵

图2：群组图

如果我们把图的边看做是一个结点，把结点看作边，我们就可以个构造出一个图的对偶图（图3）。在这个例子中，边AB，AC，BC分别变成了一个结点，它们互相共享一个结点，因此它们之间各连了一条边。通过对偶图，我们就可以使用传统的结点聚类方法来研究图中的边聚类特性。在对偶图里，两个结点之间的连边代表了这两条边在原图中共享一个结点，因此只要观察一下两个边群组之间是否有边相连，就可以知道这两个群组有没有共享的结点。如图4所示，[AB,AC,…]群组和[GH,GI,HI]群组之间并没有公共结点。

图3：对偶图

图4：对边进行聚类合并

对偶邻接矩阵

对于关系网络图来说，传统的边代表了两个节点是否有连接关系，对偶图中的边这代表了两条关系是否包含公共结点，因此两种图的逻辑结构各有优势，如果把两种表现方式聚合在一起，就能提供更加丰富的图结构信息。本文作者就从邻接矩阵出发，把这两种逻辑结构放在了一起。他们设计了图5的矩阵结构。

图5：对偶邻接矩阵

图6：可视化设计

这个矩阵一共由4个矩阵拼合而成：右下象限是传统图的邻接矩阵，空心圆圈代表了一条（组）边；左上象限是对偶图的邻接矩阵，实心圆圈代表了一个（组）结点；左下和右上象限是对称的，代表了边群组和点群组之间的关联。以右上象限为例，横向看的话，圆圈对应了一个边群组所覆盖的点群组，比如[GH,GI,HI]边群组覆盖了[G]和[HI]两个点群组；纵向看的话，圆圈代表了一个点群组所属的边群组，比如[D]群组同时属于[AB,AC,…]，[DE,DF,EF]，[DG]三个边群组。通过这样一个矩阵结构，就可以把关系网络图中的点边关系都表现出来。

因此他们给出了如图6的可视化设计：使用绿色和黄色两个色系分别代表了边和点的密度，用户可以同时选择左上-右下对角线上的格点（代表了边群组或点群组），相应的行、列、交叉点就会用不同颜色高亮出来。在该示例中，用户选择了Ava群组，发现它只属于一个边群组，与它相连的另一个群组是Dalia。它们在结点矩阵的右边列出了该节点群组的代表元素，并用数字表示了该群组包含的其他节点数量。

案例分析

作者选取了20个国家从1948年到2000年的外贸数据，该数据统计了具有外贸关系的国家之间每一年的进出口额。他们根据地理区域把国家分成了4个群组，把两个国家间的外贸额看作是53维的向量，通过k_means方法分成了5类，每一类内部又分成了3类，形成了两级结构的边聚类。该数据的对偶邻接矩阵如图7所示。不难发现，边群组里的前3个群组覆盖的结点最多，群组间的共享结点也很多，说明这是国家间最主要的贸易模式。英国（EUR_UKG）的所有贸易都在这3类里面，但是美国（AME_USA）还包含第五类贸易模式。中国（ASI_CHN）和很多国家都有贸易往来，但是贸易模式只有第1类。第4类和第5类都包含了伊拉克（ARA_IRQ）。

图7：外贸数据

如图8所示，选中第2组和第4组，我们可以看到，第2组的贸易额（红色）随着时间推移都是在不断提高的（1970年以前数据缺失，看起来波动比较大），但是第4组在1990之后，贸易额出现了急剧的下跌。从选中蓝色结点往下看，可以看出该群组覆盖了伊拉克（ARI_IRQ）和日本（ASI_JPN）两个结点群组，其中伊拉克群组只有它自己，日本群组还包含3个国家。据此很容易推断，这是因为1990年发生的海湾战争，导致美国的盟友国家与伊拉克外贸关系发生中断。

图8：群组比较

总结

这篇文章提出了对偶邻边矩阵的模型，研究了它在关系网络图中社群结构分析的应用。该模型能够同时分析社群结点结构和社群交叉结构，对分析连接多个社群的关键节点很有价值。

参考文献

[1] Ahn Y.-Y., Bagrow J., Lehmann S.: Link communities reveal multiscale complexity in networks. Nature 466, 7307 (2010), 761–764.
[2] Kasper D., Nathalie H.-R., Michel A. W.: Dual Adjacency Matrix: Exploring Link Groups in Dense Networks. Computer Graphics Forum (2015).