本帖最后由 lecea 于 2016-11-1 11:06 编辑
多层图中的社区检测综述
论文标题：Community Detection in Multi-Layer Graphs: A Survey
论文作者：Jungeun Kim, Jaegil Lee
本文主要的贡献：
1）介绍了在多层图中的社区检测的背景；
2）对现有的几个社区检测算法的进行了分类与比较；
3）总结了现有算法的属性特征；
4）提出了进一步研究的方向。
背景
社区检测的目标：
把复杂的图分割成几个紧密相连的部分（社区），又叫网络聚类。
问题：
由于一个实体与关系的多个方面相关联，这就使得有一定的困难。
符号表示：
相关定义：
Definition 1.单层图
单层图是加权图（V,w）,其中V是一组顶点，w是边权重集：（V×V）→[0,1]，如下图所示。
顶点表示实体，边表示关系，边的权值表示关系的远近。
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}，如下图所示。
注：柱状多层图中，一个顶点在另一层上只能有一个顶点与之对应。
Definition 3.通用多层图
多层次图是一个多元组MLN = (L1, ..., Ll, IM)，其中Li = (Vi, wi), 图的层次i∈1,..., l，IM一个l×1的节点映射，且IMi,j :Vi × Vj → [0, 1]，如下图所示。
注：通用多层图中，一个图层中的顶点对应于另一个图层中的多个顶点。
Definition 4.异构信息网络
异构信息网络可以转换为通用多层图。区别在于通用多层图强调类似类型的实体之间的多种类型的关系，而异构信息网络强调通过不同关系连接的异构类型的实体。
现状和挑战：
对于单层图已经提出了许多优秀的社区检测的方法。Fortunato和Schaeffer的调查论文如下。
Community detection in graphs
Graph Clustering
但是对于多层图依然面临很多问题，比如如何利用和融合信息的多个方面，产生对顶点和关系的更好的认识，还有扩展性也是一个重大的挑战。
本文用到的数据集的相关信息：
现有算法
1. 在两层图中的社区检测
① 集群扩展（Cluster Expansion）
基于关系和文本属性的分层社区检测算法
主要思想是快速找到初始核心作为种子，并将核心扩展到社区。
② 矩阵分解(Matrix Factorization)
基于链路结构和边缘内容的社区检测算法
边缘诱导矩阵分解算法（EIMF），由两部分组成：
纯粹基于链路结构的EIMF：使用链接结构形成关联矩阵，然后通过矩阵分解来构造潜在边缘矩阵E，由最小化等式得到链路结构Γ与边缘矩阵E相比的近似误差。（E是k×m的矩阵，其中每列对应于边缘的k维特征向量，Γ是m×n的关联矩阵，Δ是关联矩阵的归一化，使得每一列的总和为1。）
将边缘内容并入EIMF中：方法1-优化方程
Oc(E)表示边缘矩阵E的近似误差，是边缘内容的相似性而不是链路结构，λ是表示链路结构和边缘内容重要程度的加权因子。方法2-避免调整参数λ。
③ 统一距离（Unified Distance）
基于结构和属性相似性的社区检测算法
SA-Cluster算法：
制定统一距离量度：在属性增强图中，采用RWR（重新开始的随机游走）方法，添加属性顶点以表示属性值，并且将原始顶点连接到对应的属性顶点。两个顶点之间的公共属性值越大，表示两个顶点之间的相似度越高，因为可以有更多的随机游走路径。下图为一个例子。
聚类：先进行k-medoids聚类，然后进行图聚类，权重在每次迭代中自调整。在第(t+1)次迭代中的属性ai的权重为。
④ 基于模型的方法（Model-Based Method）
基于图的结构和属性的社区检测算法
构建贝叶斯概率模型：该模型为所有可能的社区和属性图定义联合概率分布p(α,θ,φ,Z|X,Y)，其中X是n×n的邻接矩阵，Y 是n×t的属性矩阵，Z是n×1的簇向量，α表示每个簇的顶点分布，θ表示每个簇的属性分布，φ表示簇之间的边缘发生概率。基于该模型，找到具有条件X和Y的社区Z的最大后验（MAP）配置，由计算。
变分法求解该模型：变分分布q(α,θ,φ,Z)近似等于概率分布p(α,θ,φ,Z|X,Y)。如果将变分分布限制为一个分布式系列找全局最大值相当于在中找到局部最大值。
⑤ 模式挖掘（Pattern Mining）
基于结构相关模式挖掘的社区检测算法
SCPM算法：
利用频繁项集挖掘和quasi-clique挖掘揭示顶点属性和稠密子图之间的相互作用。如果包含给定的一组属性值的稠密子图中的顶点的比例高于阈值，则形成结构相关模式，并且应当保持高的结构相关性值。
过程总结如下流程图所示。
⑦ 图合并（Graph Merging）
使用图合并过程来组合结构和属性信息
CODICIL算法，由四步组成：
创建内容边缘：对于每个顶点vi，通过计算余弦相似性来计算与k个内容相似的邻居。然后，在顶点vi和其k个邻居之间形成内容边缘。
组合边缘：新创建的内容边缘集和原始拓扑边缘集相统一。
利用偏差采样边缘：对于每个顶点vi，利用余弦相似性与Jaccard相似性从其局部邻域中选择要保留的边缘。
聚类：可以应用任何常规社区检测算法。
具体流程如下图所示。
2.在多层图中的社区检测
① 矩阵因式分解（Matrix Factorization）
主要的思想是通过从多个图层中提取公共因子来融合不同的信息，然后可以通过一般的聚类方法使用它们。
具体地说是通过低秩矩阵因子分解近似的每个层(O是邻接矩阵或拉普拉斯矩阵，P是n×n特征向量矩阵，Λ是n×n特征值矩阵)。当考虑多个层时，O 扩展到,i=1...l。而且公共因子矩阵应该是由多个因素分解得到的，因此目标函数被定义为最小化等式(P是表示所有层的公共因子的n×n矩阵,是捕获第i层的n×n特性矩阵,是Frobenius范数,α是正则化参数)。一种改进方法是将全局最小值的问题转换为包含局部最小值的问题。总之，首先固定P并优化，然后固定并优化P。 重复该过程直到解收敛。
② 模式挖掘（Pattern Mining）
子图挖掘算法（subgraph mining algorithm）
算法首先将子图转换为其规范形式，然后通过使用具有修剪技术的DFS策略来枚举用于γ拟群的候选者,最后基于闭合检查方案选择闭合的γ拟群。
MiMAG
MiMAG主要是找到满足结构密度和边标签相似性两方面的簇(称为MLCS)。但是，因为MiMAG允许MLCS彼此重叠，所以列出所有MLCS产生的集群可能包含冗余信息。MiMAG优先选择包含更多顶点、更多边并且出现在更多层上的聚类。
算法的性质
性质1：多层（l≧2）适用性
介绍的所有算法都是为多层图中的社区检测问题而设计的，但是有一些算法仅支持两层图。
性质2：每层的重要性
由于在现实生活中关系的多个方面可能重要性不同，所以应考虑每个层的权重，基于层的特性来自动地发现每个层的重要性。
性质3：灵活层的参与
层系数可以随着社区的变化而变化。因此，捕获每个社区特有的最佳层系数非常重要。在这种情况下，算法可以自由地构建图层的子集。
性质4：算法不敏感性
有一些敏感的算法只能和特定的图聚类算法紧密耦合，这样限制了用户选择图聚类算法的自由度。因此，应用不敏感的聚类算法可以提高社区检测的质量。
性质5：没有层位置假设
有一些算法从特定层发现初始社区，然后通过扩展和优化其他层上的初始社区来发现最终社区，那些算法被认为具有局部性假设。换句话说，它假定所有隐藏的社区可以来源于当地区域的层。
性质6：与排序无关
社区检测的结果可能对处理层的顺序敏感。当算法使用专用策略顺序地处理层时通常发生限制。
性质7：重叠图层
社区可以在层之间以重叠的方式来定义。
下表说明了各个算法是否支持这七条性质。
现有算法存在的问题以及未来研究的方向
虽然前面介绍了一些多层网络聚类的算法，但是任存在一些问题，比如：
① 大多数算法是在假设多层图已经完全清理的前提下提出的。然而，在现实世界中，顶点和边缘可能是嘈杂和模糊的。因此，需要找到合适的方法来构建多层图，以提高社区检测过程的质量。
② 本文所提及的大多数算法仅适用于柱状多层图。但是，在现实世界中不同层顶点之间的关系并不是一一对应的。因此，可以考虑将算法扩展为一般的多层图。
③ 大多数研究使用的是相对较小的数据集，然而，在大数据时代，可用信息的数量迅速增长，当前的算法可能会不适用。因此，计算时间和存储器需求的可扩展性也成为进一步研究的方向。
④ 目前对于多层图的研究只是针对静态图。但是，图形中的社区是随时间变化的。因此，可以研究动态多层图的社区检测。
⑤ 还有一方面是作者最后没有总结的，就是在基于模型的方法和模式挖掘中提到的计算复杂度过大的问题。
总结
目前单层的社区检测已经有很好的算法，所以研究的重点在一般的多层网络。 |
发表于 2016-11-1 10:04:22
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
转播
分享
发表于 2016-11-1 20:27:17
楼主