通过边标签挖掘多层图中的相干子图

bcdfg

论文标题Mining CoherentSubgraphs in Multi-Layer Graphs with Edge Labels

论文作者：来自德国的RWTH AachenUniversity团队

这篇文章做出的主要贡献有三：

a)        提出了通过边的标签对多层图进行聚类的范式。

b)        介绍了一个可以避免结果冗余的聚类方MLCS。

c)        提出了在聚类中使用最佳优先搜索算法MiMAG。

介绍一下基本背景：⑴图聚类，这个概念有点模糊，有的是针对子图，有的只是针对点集，这篇文章中针对点集。⑵多层图。点与点之间的关系可能有好几种，打个比方，点代表人的话，点和点之间的关系包括①两人是同一文章的作者②一人引用过另一人的文章，在这个例子中也就是说点和点之间存在两种边，把同种边相连的称为图的一层。⑶相干子图，强连通点集(在包含同一种边标签的图层中)，相干子图的关系不需要在每层图中都成立。

MLCS模型

将图表示为几个具有相同点集V的图Gi(多层图)，每层图包含一种相对应的边关系。Gi为无向无环图G i = (V,Ei ,li),E i ⊆ V × V,l i: E i → R，li为边标签函数

cluster model

对于每个图层来讲，使用quasi-clique模型来计算子图的密度，这个模型通过簇的内部联系定义了稠密图的概念。

quasi-clique模型的定义：即所有点入度的最小值与图的点数减一的比值，在这篇文章中，我们将满足0.5-quasi-clique的点集看成是稠密的，即这个比值大于0.5时，我们将这样的点之间的联系看作是紧密的。

一维MLCS簇的定义：在一个图层中，满足0.5-quasi-clique的同时，也满足任意两条边的边标签函数的距离函数小于一个值w。（一个簇至少要有3个点）

∀x, y ∈ Ei(O) : dist(li(x),li(y)) ≤ w

where the edge set Ei(O) is defined as Ei(O) ={(u, v) ∈Ei | u, v ∈ O}

边界值w仅当边标签是连续值是才需要

MLCS簇的定义：

每一层都可能会有极为相似的点集，所以会带来数据的冗余。又因为每一层子图的密度都不一样，这里取所有层中子图密度的均值来进行计算。

如图所示，在图层1和4中，设定w=1，点集O = {b,c,d,e,f} 是一个MLCS cluster，而在图层二中，O不是一个quasi-clique，在图层三中E3(O) 的边标签并不符合条件。

   

clustering model之如何处理数据冗余

如果把满足条件的簇全都用于计算，由于大量数据都十分相似，将会带来冗余数据。如下图所示

这里使用函数Q(C) ，因为一般我们想要的最优解是尽可能包括更多的点，然而更多的点就会带来维度下降以及密度下降，Q(C)就是用来平衡性能的一个质量函数。这篇文章中，Q(C)定义如下

冗余的定义

数据筛选MLCS clustering

给出图G以及所有的有效点集，如何去除冗余数据 。Result ⊆ A 满足以下条件，即最大化质量函数的前提下尽可能减小冗余。

figure2中得到的结果{C 1 ,C 3}.

算法

树的同步遍历

1.        对每一层的图找出一维MLCS簇。

2.        将一维簇整合成多维簇。

3.        移除冗余簇。

如图所示，对于每一个点集O存在一个候选点集candidate 用集合cando表示,如果O的候选点集中存在点V不能使重新构成的O’成为一个quasi-clique，就将他减掉。

在enum-tree的扩大集中，每个节点O（接下来的节点O均指的点集）有一个活跃维度集合（Activedimensions）So，表示的是所在图层（O还没有被剪枝剪掉）。O也有一个候选集合cando。在遍历过程中，对于O，我们需要检查O在它的活跃维度内是否构成了一个MLCS簇。潜在簇C=（O，S），S ⊆ So.

为了最大化质量函数，采用的是质量递减的方法来减少冗余。在这里，需要先做一个质量评估算出簇的最大质量上界。在遍历过程的每一步，都选择能带来最高质量的节点。

有一个重要的问题需要考虑，即使一个簇出现在目前的扩大集中，也不能将其直接加入到结果中。因为虽然选择了子树的最大质量，但是C本身可能会有一个较低的质量。因此，MiMAG用了一个队列来存放这些簇。简而言之就是树的遍历。

在队列中, subtree  ST = (O,So ,{cando,i| i ∈ S O })

剪枝的具体实现如果边集Ei (O) 存在两条边的标签距离大于w,他就不是一个有效集。

用这一性质来对候选集cando进行剪枝，如果一个点v ∈ cando,它不满足 E ‘ = E i(O)∪{(v,o) ∈E i | o ∈ O} ，即O’⊇ O∪{v}不能构成一个有效集，我们就将cando中的v剪掉。

子树的质量边界

如果一个簇是冗余的，我们，即使他的质量大于0，我们也可以直接将其置为-1.。为了验证数据是否冗余，这里计算一个重复度边界。

聚类边界。对于子树 ST =(O,So ,{cando,i | i ∈ So }), 对每个一维的MLCS簇X， i ∈ So, O ⊂ X ⊆ O ∪ cando,i边界应用如下

字数的质量上界函数

实验评估

就运行时间和聚类质量以及已经检测到的簇这三个指标与其他方法进行了对比。对两组数据进行了测试。

对实际数据的应用处理，通过对论文库的论文共同作者以及文章引用来进行运算，以及和其他方法的比较

总结

这篇文章介绍了通过边标签对多层图进行聚类的方法，能够将更多的信息加入计算，在运算过程中在原有图的基础之上引入的大量信息对挖掘相干子图起到了很大的作用。

将搜索树运用到运算中，减少冗余，算法效率上也得到了提升。

xzeng

花了很多时间写。辛苦了。