论文导读 | 多层网络中的社区发现

导读

Reading Guide

社区发现(Community Detection)是网络分析领域的一项基本任务。早期的社区发现大多是应用在社交网络中,用于分析人们的社会关系。随着社区发现技术的不断发展,这一技术被应用到更多领域。例如在生物学中分析脑部各区域相互作用及其对脑功能的影响;在国际贸易领域识别不同区域组成的贸易运输结构以及寻找潜在的贸易伙伴等等。多层网络是指相同的一群个体在多种关系类型下组成的网络,每种关系构成多层网络中的一层图。显然,多层网络能够更加真实地拟合现实场景,多层网络社区发现的目的是发现多层网络中的社区结构。本文主要对近些年多层网络社区发现使用的方法进行介绍。

#1 引言Introduction

目前,多层网络社区发现算法按照处理多层网络的方法主要分为以下三类:基于映射函数的方法,基于层次聚合的方法以及基于多层结构的方法。基于映射函数的方法将多层通过映射函数压扁为单层网络,然后使用单层网络社区发现的方法;基于层次聚合的方法先在多层网络每一层寻找社区信息,然后将各层的信息聚合在一起;基于多层结构的方法从多层网络自身结构出发,直接发现社区结构。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

图1 多层网络社区发现算法分类

#2 在多维网络中寻找和表征社区

Berlingerio M, Coscia M, Giannotti F, Finding and Characterizing Communities in Multidimensional Networks. ASONAM. 2011.

动机

如今,大多数文献中所做的工作都仅限于对这种简化的单一维度的关系的研究,例如仅仅关注两个节点是否连接。然而,在现实世界中,这样的方法并不总是足以对所有可用信息进行建模,尤其是当参与者是用户时,他们多重偏好、多方面的行为和复杂的互动都对网络产生了影响。对这些问题进行更复杂的分析将有助于所有基于网络结构知识的技术的有效性。为此,在本文中,我们针对多维网络即一对节点之间可能存在多种类型连边的网络进行研究,反映了它们之间的各种维度交互。

方法

作者通过构造映射函数的方式对多层网络映射压缩(Mapping Flattening)进行社区发现。算法将由多维关系构成的多层网络通过映射函数压缩成一个单层网络,映射函数的构造一共包含三种方式:(1)基于单层节点的连接,即两个节点在任意一层连接记为映射后这两个节点相连;(2)基于不同层节点连边的数量,即两个节点在不同层中连边的数量构成映射后这两个节点的连边权重;(3)基于多层网络节点的邻域信息,使用两个节点邻居集合的Jaccard系数,即邻居的交集与并集的比值构成映射后这两个节点的连边权重。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

图2 通过映射函数压扁网络


对于压扁后的单层网络,可以使用任意的单层网络社区发现算法,但有对于压扁的有权网络,必须要求单层网络社区发现算法能够处理有权边。出于上述考虑,对于社区发现算法提出的唯一限制是选择一种能够处理边缘权重的算法。在实验中展示了三种单层网络社区发现算法:使用基于随机游走的算法、基于标签传播的算法和基于模块性的快速贪婪优化算法作为可能的单维社区发现算法的选择。

实验

设置:使用了两个多层网络数据集分别为GTD数据集和IMDb数据集,分别基于上述三种映射函数和三种单层社区发现方法进行了实验,比较发现的社区数量和模块度结果。

结果:对于三种映射函数方式(基于单层节点的连接、基于不同层节点连边的数量、基于多层网络节点的邻域信息),以及三种单层网络社区发现方式(基于随机游走的算法LP、基于标签传播的算法WT、基于模块性的快速贪婪优化FGM),将它们两两组合分别测试其在两个真实数据集上的社区数量C以及模块度结果Q。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

分析:对于GTD数据集,从社区发现方式角度出发,使用LP社区发现方法,基于单层节点的连接取得了最高的模块度,而在WT和FGM社区发现方式中,基于多层网络节点的邻域信息取得了最高的模块度;对于IMDb数据集,在三种社区发现方式中,基于不同层节点连边的数量都取得了最高的模块度。这说明不同的网络结构对于不同的映射函数的选择有不同的偏好,而且这种偏好还可能受到社区发现方式的变化而变化,在两个数据集中,FGM方式发现社区数量最少,LP方式发现社区数量次之,WT方式发现社区数量最多。

#3 通过异质交互分析发现社区

Tang L, Wang X, Liu H. Uncovering groups via heterogeneous interaction analysis,ICDM. 2009

动机

社交网络分析中理解人类集体行为的一项基本任务是确定参与者的社会地位或有凝聚力的子群体(也就是社区),其群体成员之间的互动比群体外的成员更频繁。在现实中,人们以各种形式的活动相互交互,导致同一组参与者之间形成多个网络,或一个多层网络,每个维度代表一种交互类型。当具有异构交互的多层网络可用时,如果仅使用一种交互类型,则可能不足以准确地提取参与者的组成员身份。在社交媒体中,由于用户的隐私问题,某些类型的交互可能是不完整的。因此,在多层网络中识别群体成为一项挑战性的任务,我们必须融合所有维度的信息进行联合分析,即处理多层网络下的社区发现任务。

方法

PMM算法全称为Principal Modularity Maximization,PMM算法对数据的处理利用了矩阵分解的思想,它使用了一个两阶段策略来识别多层网络中多维度共享的隐藏社区结构。首先通过模块化分析从网络的各个维度提取结构特征,然后将它们整合在一起,从而在多层网络之间找到隐藏的社区结构。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

图3 PMM算法结构

PMM算法的方法步骤为:

        第一步,结构特征提取,就是像单层网络那样运用模块度最大化的思想从每一层中找到社区划分矩阵S; 论文导读 | 多层网络中的社区发现

        第二步,跨层聚合社区划分矩阵,通过奇异值分解以及主成分分析对数据降维,使用kmeans算法得到最终的社区划分。
论文导读 | 多层网络中的社区发现

实验

设置:人工合成数据集一共含有350个节点,4层网络,整个多层网络被划分为3个社区,输入为该人工合成数据集4层网络的邻接矩阵,同时在网络的第二层中两个节点之间低概率的随机连接来引入噪声。算法方面,引入了AMM和TMM两种对比算法。

结果:在该合成数据集不引入噪声和引入噪声两种情况下测试PMM算法在各层的NMI结果,多层网络社区发现算法AMM,TMM,PMM的NMI指标。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

分析:在不引入噪声的情况下,PMM算法在各个单层上的NMI指标没有AMM算法和TMM算法高,这是由于单层网络无法涵盖多层网络的所有信息,导致算法在单层难以发现所有的社区结构,但对于多层的结果,PMM算法要优于AMM算法和TMM算法;在第二层引入噪声的情况下,可以明显看到AMM算法和TMM算法的NMI指标下降了非常多,PMM算法受噪声的影响NMI有所下降,但相比两种baseline方法,PMM算法具有更强的鲁棒性。

#4 多层网络中基于集成的社区检测

Tagarelli A, Amelio A, Gullo F. Ensemble-based community detection in multilayer networks. DMKD. 2017.

动机

多层网络中的社区检测问题近些年来受到人们的广泛关注。 现有方法可以大致分为三大类:扁平化方法,聚合方法和直接方法。在这项工作中,我们专注于多层社区检测的聚合方法。其中层特定社区结构的聚合是通过采用聚类集成方法来执行的。开展这项工作的动机源于希望将聚类集成范式引入多层社区检测问题。这样,不仅放宽了对确定多层社区结构的独特方法或设置的要求,而且可以有利地利用多个社区结构的可用性来学习多层网络的共识。

方法

EMCD算法的基本框架为:首先利用单层网络社区发现算法检测每一层的社区分布,然后根据两个节点在多层网络的所有层次中拥有共同社区标签的比例定义其在协相关矩阵中的连接权重,权重超过设定阈值则视作两个节点产生连接,最后由协相关矩阵的连接分布得到多层网络的共识社区。共识社区发现模型包括聚类共识社区发现C-EMCD,受限的共识社区发现CC-EMCD以及由模块度驱动的共识社区发现M-EMCD三种形式。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

图4 基于共识社区的社区发现

针对上述两种baseline方法,我们提出了一种基于模块度优化的改进模型,即模块度驱动的共识社区模型M-EMCD,该模型的基本结构如图所示:

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

图5 M-EMCD算法结构

M-EMCD可以看作是在CC-EMCD的输出后,通过模块度优化的思想对最后的结果进行改进,主要是通过模块度优化强化社区内部的连通性以及改变社区之间的连接来改善多层网络的共识社区结构。

实验

设置:7个不同类型的真实网络数据集,包括Aucs数据集、DBLP数据集、EU-Air数据集、FF-TW-YT数据集、Higg-Twitter数据集、London数据集和VC-Grader数据集

结果:在7个真实网络数据集上测试M-EMCD模型模型的模块度,社区数量以及对比C-EMCD模型以及CC-EMCD模型这两个baseline的模块度增益。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

分析:在7个真实网络数据集上,相较于两种baseline方法,M-EMCD模型都取得了最高的模块度结果,并且在各个数据集上的模块度结果都有显著的提升,这说明M-EMCD模型通过模块度的优化提升了多层网络社区发现的质量,改进了社区发现的结果。

#5 时间依赖、多尺度和多路复用网络中的社区结构

Mucha P J, Richardson T, Macon K, et al. Community structure in time-dependent, multiscale, and multiplex networks. science. 2010

动机

对于图或网络的研究在社会学和数学等领域有着悠久的传统,现在在学术和日常环境中无处不在。网络分析中的一个重要工具是检测称为社区(或内聚组)的细观结构,这些结构直观地定义为与缓存连接比与网络其余部分更紧密连接的节点组。量化社区的一种方法是通过质量函数将社区内边缘的数量与人们随机期望的数量进行比较。因此作者提出一种量化多层网络社区结构的评价指标,称为多层网络模块度,并基于多层网络模块度的优化设计了一种多层网络社区检测算法。

方法

(1) 多层网络随机游走

       多层网络的连接包括层内连接和层间连接,层间连接还按照是否仅连接相邻层分为相邻层层间连接和层间全连接(仅考虑不同层中相同实体对应的节点之间的纵轴连接)。根据切片结构是否允许从节点(j, r)移动到节点(i, s)的条件,我们得到了多切片的空模型,将切片内和切片间的移动概率考虑为:论文导读 | 多层网络中的社区发现

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

图6 多层网络上的随机游走

        从描述拉普拉斯动力学的指数线性(时间上)近似值减去一个条件联合概率,作者定义了多层网络模块度的计算公式:论文导读 | 多层网络中的社区发现

(2) Louvain算法

       louvain算法是单层网络的社区发现算法。该算法首先将网络中的每个节点看作一个个独立的社区,接着在每次迭代中通过随机游走遍历网络的所有节点,并尝试将每个节点加入其相邻节点所在的社区;然后衡量这次改变为模块度所带来的收益,如果模块度变小则取消本次移动,遍历结束后将具有相同社区标签的节点集合重新整合,具体而言就是将网络中每个社区看成一个节点以构建一个新的连接网络,新的网络节点之间的连边权重由原网络社区之间的连边数量决定,重复上述过程,直到任何的移动不再使模块度增大为止。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

图7 Louvain算法流程

GL算法将louvain算法中的随机游走的过程变成在多层网络上进行,为每一层各个节点都赋予一个独立的社区标签。

实验

设置:实验数据集为Zachary Karate Club network数据集,一共有34个节点;多层网络模块度一共受到两个参数的控制,分别为层内分辨率参数ys和层间连边强度Cjsr(表示为w),分为将这两个参数设置为固定的值,其中将ys设置为[0.25, 0.5, …, 4],将w设置为[0, 0.1, 1]。

结果:记录在不同的层内分辨率参数ys和层间连边强度w下Zachary Karate Club network数据集的社区分布情况。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

分析:从实验结果来看,不同的层内分辨率参数ys和层间连边强度w会改变社区划分的数量,当层内分辨率参数ys越大,被发现社区的数量就越多;当层间连边强度w越小,被发现社区的数量也越多。

#6 挖掘多维网络中的社区结构

Boutemine O, Bouguessa M. Mining community structures in multidimensional networks. TKDD. 2017.

动机

在多维网络中识别社区继续以各种方式对现有算法提出挑战:(1)许多方法在处理具有稀疏或不相关维度的网络时会遇到困难,即节点被隔离或随机连接而没有任何明显社区结构的维度 (2) 缺乏系统的过程来明确识别每个社区的相关维度(3)迄今为止,文献中可用的绝大多数方法都依赖于一些需要适当调整的输入参数。为了克服上述困难,作者提出了一种基于标签传播的多层网络社区发现算法。

方法

MDLPA算法的全称为Multidimensional Label Propagation Algorithm,它是单层网络社区发现LPA算法在多层网络的扩展。MDLPA算法计算社区分布的过程主要分为两步:(1)将多层网络映射成一张有权有向的单层网络;(2)在映射后的单层网络上按照影响力最大的方式执行LPA算法。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

图8 LPA算法流程

LPA算法是一种基于图的半监督算法,它的基本思路是用已标记节点的标签信息预测未标记节点的标签信息。LPA算法具体的步骤如下:首先它为网络中所有节点初始化一个独一无二的社区标签;然后按照随机的顺序扫描所有的节点,每个节点的标签被更新为其最大数量的邻居所具有的标签;当所有节点的标签与其最大数量的邻居拥有的标签相同时,将网络中每一个具有相同标签的连通部分作为一个社区,获得单层网络的社区划分。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

图9 MDLPA算法流程

MDLPA算法首先将多层网络通过层间关系将多层网络映射成一张有权有向的单层网络,然后使用LPA算法获得社区划分。映射的具体方法是使用Jaccard系数定义了多层网络两个节点之间标签的传播权重,即:论文导读 | 多层网络中的社区发现

w(v, u)是单层网络上的有向边的权重,也被称为节点吸引权重,它是根据连接该对(v, u)的相关维度的数量估算,表示基于v的邻居在与u相同的维度内可以唯一达到的比例。分数越高,与v相关的维数越大,u在v上的吸引力就越高。

实验

设置:实验选取了合成数据集,该数据集由平均社区维度Ir控制,将设置为[0, 0.4]区间。

结果:对于不同的Ir 产生的多层网络,测试MDLPA算法,LPA-Bin-Aggr变体,LPA-Freq-Aggr变体,Clustering Ensemble算法,PMM算法和SC-ML算法在各种合成多层网络上的NMI,ARI,FMI指标。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

分析:由实验结果发现,MDLPA算法在各个数据集上都取得了较高的NMI,ARI,FMI指标,其次SC-ML算法的表现在Ir较小时不好,随着变大社区发现的效果逐渐提升,PMM算法的波动较大,PA-Bin-Aggr变体,LPA-Freq-Aggr变体,Clustering Ensemble算法这三种算法的结果较差。

#7 用于多层网络推理的改进深度嵌入

Song H, Thiagarajan J J. Improved Deep Embeddings for Inferencing with Multi-Layered Graphs. IEEE Big Data. 2019.

动机

近年来随着多层网络的出现,即每一层中具有不同关系结构的同一组节点,获得保持多视图关系的简洁嵌入变得至关重要。与单层情况不同,多层网络的节点嵌入技术必须适应分层(例如社区检测)和统一表示(例如节点分类)的提取。由于多层网络的固有挑战,包括关系类型的异质性和不同层中不同程度的稀疏性,单层方法的直接扩展是无效的。最后,关于增加层数的可扩展性是一个重要的设计标准。在本文中,我们设计了一种可扩展的嵌入方法,该方法首先直接在多层网络形成的超邻接矩阵上执行 M-DeepWalk 算法,并利用细化策略通过鼓励有凝聚力的社区形成来进一步微调嵌入。我们研究了我们的方法在链接预测、节点分类和社区检测问题中的应用。

方法

M-Deepwalk算法基于节点嵌入的思想,将多层网络中各层的每个节点使用一个向量进行表示。该算法首先将多层网络各层邻接矩阵拼接变成了一张超邻接矩阵,规定层间连边只存在于不同层相同节点之间,通过Jaccard系数表示层间连边的权重;然后再超邻接矩阵上使用deepwalk,最后将生成的节点嵌入通过一个预训练好的前向编码器输出原始维度嵌入进行训练,最后计算社区分布。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

图10 M-Deepwalk算法结构

左图所示过程是M-deepwalk算法构建超邻接矩阵的过程,对于一个多层网络,算法对于不同层节点之间的连边权重有如下定义:论文导读 | 多层网络中的社区发现

即不同层不同节点之间不存在连边,不同层相同节点之间连边权重使用Jaccard系数计算,具体而言获取这两个节点的一阶邻居节点集合,使用两个集合的交集除以并集。最后通过设定阈值将超邻接矩阵中的元素划分为二元表示。

        右图显示了模型的特征训练过程,输入数据是由deepwalk算法在超邻接矩阵中随机游走获取,通过编码解码器输出相同维度的特征表征,然后利用聚类损失和模块度优化计算最终的社区分布。同GL算法相同,M-deepwalk为每一层每个节点都进行了社区的划分。

实验

设置:实验数据集一共有三个,分别为LAZEGA数据集,C.ELEGANS数据集以及EU Airlines数据集。

结果:对于上述三个多层网络数据集,在划分为不同社区数量的情况下,对比M-deepwalk算法和GL算法之间的多层网络模块度结果。

论文导读 | 多层网络中的社区发现
论文导读 | 多层网络中的社区发现

分析:由实验结果可以看出,相较于GL算法,M-deepwalk在每个数据集划分不同社区数量的各种情况下,都取得了较高的模块度结果,特别是EU Airlines数据集,M-deepwalk算法与GL算法相比取得了很高的模块度提升,这说明M-deepwalk算法可以有效的发现多层网络中高模块化的社区结构。

#8 结语Conclusion

多层网络社区发现是社区发现领域一个新兴的方向,不少关于多层网络社区发现的算法在近些年来被提出,促进了该领域的发展。目前多层网络社区发现算法一共有以下三种分类:基于映射函数的方法;基于层次聚合的方法;基于多层结构直接发现的方法。上述论文所介绍的算法也都处于这三种分类当中。现有的方法大多数集中在多层网络本身的连接以及社区的拓扑结构中,较少关注到节点自身的表征。传统的社区发现算法将节点的存在表示为其所在的拓扑位置以及与其相连的邻居集合,以图神经网络为代表的深度学习模型将节点特征信息编码为高维的特征向量,这可能是多层网络社区发现领域未来一个新的研究方向。

来源:MINS,本文观点不代表自营销立场,网址:https://www.zyxiao.com/p/135969

发表评论

登录后才能评论
服务中心
服务中心
联系客服
联系客服
侵权联系 投诉举报
返回顶部
河南,挺住!郑州,挺住!一起为他们加油!!