机器学习和生物信息学实验室联盟

标题: 多层图中的社区检测 [打印本页]

作者: lecea 时间: 2016-11-1 10:04
标题: 多层图中的社区检测
本帖最后由 lecea 于 2016-11-1 11:06 编辑

多层图中的社区检测综述

论文标题：Community Detection in Multi-Layer Graphs: A Survey
论文作者：Jungeun Kim, Jaegil Lee

本文主要的贡献：
1）介绍了在多层图中的社区检测的背景；
2）对现有的几个社区检测算法的进行了分类与比较；
3）总结了现有算法的属性特征；
4）提出了进一步研究的方向。

背景

社区检测的目标：
把复杂的图分割成几个紧密相连的部分（社区），又叫网络聚类。
问题：
由于一个实体与关系的多个方面相关联，这就使得有一定的困难。
符号表示：

[attach]2787[/attach]

相关定义：
Definition 1.单层图
单层图是加权图（V,w）,其中V是一组顶点，w是边权重集：（V×V）→[0,1]，如下图所示。

[attach]2788[/attach]

顶点表示实体，边表示关系，边的权值表示关系的远近。
Definition 2.柱状多层图
图L1=（V 1,w1）到图L2=（V2，w2）的节点映射是函数f：V1×V2→[0,1]。对于每个u∈V1，集合C（u）= {v∈V2 | f（u，v）> 0}是相对应u的V2的顶点集。柱状多层图由节点映射形式地定义为|C(u)|∈{0,1}，如下图所示。

[attach]2789[/attach]

注：柱状多层图中，一个顶点在另一层上只能有一个顶点与之对应。
Definition 3.通用多层图
多层次图是一个多元组MLN = (L1, ..., Ll, IM)，其中Li = (Vi, wi), 图的层次i∈1,..., l，IM一个l×1的节点映射，且IMi,j :Vi × Vj → [0, 1]，如下图所示。

[attach]2790[/attach]

注：通用多层图中，一个图层中的顶点对应于另一个图层中的多个顶点。
Definition 4.异构信息网络
异构信息网络可以转换为通用多层图。区别在于通用多层图强调类似类型的实体之间的多种类型的关系，而异构信息网络强调通过不同关系连接的异构类型的实体。
现状和挑战：
对于单层图已经提出了许多优秀的社区检测的方法。Fortunato和Schaeffer的调查论文如下。
Community detection in graphs
Graph Clustering
但是对于多层图依然面临很多问题，比如如何利用和融合信息的多个方面，产生对顶点和关系的更好的认识，还有扩展性也是一个重大的挑战。
本文用到的数据集的相关信息：

[attach]2791[/attach]

现有算法

1. 在两层图中的社区检测
①　集群扩展（Cluster Expansion）
基于关系和文本属性的分层社区检测算法
主要思想是快速找到初始核心作为种子，并将核心扩展到社区。

[attach]2809[/attach]

②　矩阵分解(Matrix Factorization)
基于链路结构和边缘内容的社区检测算法
边缘诱导矩阵分解算法（EIMF），由两部分组成：
纯粹基于链路结构的EIMF：使用链接结构形成关联矩阵，然后通过矩阵分解来构造潜在边缘矩阵E，由最小化等式[attach]2792[/attach]得到链路结构Γ与边缘矩阵E相比的近似误差。（E是k×m的矩阵，其中每列对应于边缘的k维特征向量，Γ是m×n的关联矩阵，Δ是关联矩阵的归一化，使得每一列的总和为1。）
将边缘内容并入EIMF中：方法1-优化方程[attach]2793[/attach]
Oc(E)表示边缘矩阵E的近似误差，是边缘内容的相似性而不是链路结构，λ是表示链路结构和边缘内容重要程度的加权因子。方法2-避免调整参数λ。
③　统一距离（Unified Distance）
基于结构和属性相似性的社区检测算法
SA-Cluster算法：
制定统一距离量度：在属性增强图中，采用RWR（重新开始的随机游走）方法，添加属性顶点以表示属性值，并且将原始顶点连接到对应的属性顶点。两个顶点之间的公共属性值越大，表示两个顶点之间的相似度越高，因为可以有更多的随机游走路径。下图为一个例子。

[attach]2795[/attach]

聚类：先进行k-medoids聚类，然后进行图聚类，权重在每次迭代中自调整。在第(t+1)次迭代中的属性ai的权重为[attach]2794[/attach]。
④　基于模型的方法（Model-Based Method）
基于图的结构和属性的社区检测算法
构建贝叶斯概率模型：该模型为所有可能的社区和属性图定义联合概率分布p(α,θ,φ,Z|X,Y)，其中X是n×n的邻接矩阵，Y 是n×t的属性矩阵，Z是n×1的簇向量，α表示每个簇的顶点分布，θ表示每个簇的属性分布，φ表示簇之间的边缘发生概率。基于该模型，找到具有条件X和Y的社区Z的最大后验（MAP）配置，由[attach]2796[/attach]计算。
变分法求解该模型：变分分布q(α,θ,φ,Z)近似等于概率分布p(α,θ,φ,Z|X,Y)。如果将变分分布限制为一个分布式系列[attach]2797[/attach]找全局最大值相当于在[attach]2798[/attach]中找到局部最大值。
⑤　模式挖掘（Pattern Mining）
基于结构相关模式挖掘的社区检测算法
SCPM算法：
利用频繁项集挖掘和quasi-clique挖掘揭示顶点属性和稠密子图之间的相互作用。如果包含给定的一组属性值的稠密子图中的顶点的比例高于阈值，则形成结构相关模式，并且应当保持高的结构相关性值。
过程总结如下流程图所示。

[attach]2799[/attach]

⑦　图合并（Graph Merging）
使用图合并过程来组合结构和属性信息
CODICIL算法，由四步组成：
创建内容边缘：对于每个顶点vi，通过计算余弦相似性来计算与k个内容相似的邻居。然后，在顶点vi和其k个邻居之间形成内容边缘。
组合边缘：新创建的内容边缘集和原始拓扑边缘集相统一。
利用偏差采样边缘：对于每个顶点vi，利用余弦相似性与Jaccard相似性从其局部邻域中选择要保留的边缘。
聚类：可以应用任何常规社区检测算法。
具体流程如下图所示。

[attach]2802[/attach]

2.在多层图中的社区检测
①　矩阵因式分解（Matrix Factorization）
主要的思想是通过从多个图层中提取公共因子来融合不同的信息，然后可以通过一般的聚类方法使用它们。
具体地说是通过低秩矩阵因子[attach]2803[/attach]分解近似的每个层(O是邻接矩阵或拉普拉斯矩阵，P是n×n特征向量矩阵，Λ是n×n特征值矩阵)。当考虑多个层时，O 扩展到[attach]2804[/attach],i=1...l。而且公共因子矩阵应该是由多个因素分解得到的，因此目标函数被定义为最小化等式[attach]2805[/attach](P是表示所有层的公共因子的n×n矩阵,[attach]2806[/attach]是捕获第i层的n×n特性矩阵,[attach]2807[/attach]是Frobenius范数,α是正则化参数)。一种改进方法是将全局最小值的问题转换为包含局部最小值的问题。总之，首先固定P并优化[attach]2806[/attach]，然后固定[attach]2806[/attach]并优化P。重复该过程直到解收敛。
②　模式挖掘（Pattern Mining）
子图挖掘算法（subgraph mining algorithm）
算法首先将子图转换为其规范形式，然后通过使用具有修剪技术的DFS策略来枚举用于γ拟群的候选者,最后基于闭合检查方案选择闭合的γ拟群。
MiMAG
MiMAG主要是找到满足结构密度和边标签相似性两方面的簇(称为MLCS)。但是，因为MiMAG允许MLCS彼此重叠，所以列出所有MLCS产生的集群可能包含冗余信息。MiMAG优先选择包含更多顶点、更多边并且出现在更多层上的聚类。

算法的性质

性质1：多层（l≧2）适用性
介绍的所有算法都是为多层图中的社区检测问题而设计的，但是有一些算法仅支持两层图。
性质2：每层的重要性
由于在现实生活中关系的多个方面可能重要性不同，所以应考虑每个层的权重，基于层的特性来自动地发现每个层的重要性。
性质3：灵活层的参与
层系数可以随着社区的变化而变化。因此，捕获每个社区特有的最佳层系数非常重要。在这种情况下，算法可以自由地构建图层的子集。
性质4：算法不敏感性
有一些敏感的算法只能和特定的图聚类算法紧密耦合，这样限制了用户选择图聚类算法的自由度。因此，应用不敏感的聚类算法可以提高社区检测的质量。
性质5：没有层位置假设
有一些算法从特定层发现初始社区，然后通过扩展和优化其他层上的初始社区来发现最终社区，那些算法被认为具有局部性假设。换句话说，它假定所有隐藏的社区可以来源于当地区域的层。
性质6：与排序无关
社区检测的结果可能对处理层的顺序敏感。当算法使用专用策略顺序地处理层时通常发生限制。
性质7：重叠图层
社区可以在层之间以重叠的方式来定义。
下表说明了各个算法是否支持这七条性质。

[attach]2808[/attach]

现有算法存在的问题以及未来研究的方向

虽然前面介绍了一些多层网络聚类的算法，但是任存在一些问题，比如：
①　大多数算法是在假设多层图已经完全清理的前提下提出的。然而，在现实世界中，顶点和边缘可能是嘈杂和模糊的。因此，需要找到合适的方法来构建多层图，以提高社区检测过程的质量。
②　本文所提及的大多数算法仅适用于柱状多层图。但是，在现实世界中不同层顶点之间的关系并不是一一对应的。因此，可以考虑将算法扩展为一般的多层图。
③　大多数研究使用的是相对较小的数据集，然而，在大数据时代，可用信息的数量迅速增长，当前的算法可能会不适用。因此，计算时间和存储器需求的可扩展性也成为进一步研究的方向。
④　目前对于多层图的研究只是针对静态图。但是，图形中的社区是随时间变化的。因此，可以研究动态多层图的社区检测。
⑤　还有一方面是作者最后没有总结的，就是在基于模型的方法和模式挖掘中提到的计算复杂度过大的问题。

总结

目前单层的社区检测已经有很好的算法，所以研究的重点在一般的多层网络。

作者: xzeng 时间: 2016-11-1 20:27
非常好的论文报告，我基本读懂了。一个小建议：survey和review一般翻译为综述论文，而不是调查论文。

作者: xuanzhang 时间: 2016-11-1 21:01
赞一个！看的懂的报告才是好报告！基本都懂了，就是数学公式的部分还要自己去消化下

作者: lecea 时间: 2016-11-2 17:26

xuanzhang 发表于 2016-11-1 21:01
赞一个！看的懂的报告才是好报告！基本都懂了，就是数学公式的部分还要自己去消化下

向学姐学习{:249:}

欢迎光临机器学习和生物信息学实验室联盟 (http://123.57.240.48/)