以社区发现为导向的网络嵌入模型研究*

陈慧莹 寇 月 申德荣 聂铁铮

（东北大学计算机科学与工程学院 沈阳 110819）

1 引言

社交媒体网络包含了丰富的网络信息。联系紧密的个体及其关联关系形成了社交网络中的社区结构。传统的网络分析方法难以处理复杂多样的数据且易丢失丰富的节点信息。网络表示学习是将蕴含丰富信息的数据表示成简单低维的向量形式，并且同时直观高效的保留原有的特征信息。如图1所示，节点1与节点2、节点12原本分属两个不同的社区。若采用传统的网络嵌入方法，将可能导致三个节点被划分为同一个社区。原因在于忽略了节点固有的社区结构。对于同属于一个社区的节点，应该比隶属于不同社区的节点更加相似。因此，考虑节点所体现出的社区特征，可以提高社区划分的准确性。现有少数网络嵌入方法考虑了网络固有的社区结构。例如，文献［1］在网络嵌入时考虑了社区特征，但没有将社区特征与节点属性特征相结合。文献［2］也通过非负矩阵分解保持了社区结构，但其目标在于学习节点的嵌入表示，而非社区发现。针对以上不足，在学习节点的嵌入表示时，同时考虑节点属性特征和社区特征，并且将嵌入表示应用到社区发现中，以提高社区划分的准确性。贡献如下：

图1 具有社区结构的网络

1）提出了一种以社区发现为导向的网络嵌入模型（Community Detection-oriented Network Embedding，CDNE）。与传统模型不同，该模型同时考虑了节点属性特征和更高阶的隐含特征（即网络中固有的社区特征），同时体现了网络的局部特征与全局特征。

2）提出了一种基于CDNE的两阶段社区发现算法。第一阶段为合并社区；第二阶段基于待合并社区重新构建网络。通过两个阶段的交替迭代执行，来提高社区发现的准确性。

3）在真实数据集上设计对比实验，证明了该方法具有一定的优势。

2 相关工作

本节首先介绍了社区发现、网络表示学习的相关工作并作出了比较。

早期Girvan等提出了GN算法［3］，该算法采用边介数代表边的强弱，通过不断移除网络中边介数最大的边得到社区结构。Newman等提出基于模块度Q的区挖掘算法［4］，该算法应用了贪婪思想。Bagrow提出了一种局部社区结构发现算法［5］。2013年，Yang等提出CESNA算法［6］，有效提高社区划分的质量。Yang等提出了一个条件模型来进行链接分析以及一个歧视性模型来进行内容分析［7］。

传统的网络表示学习都是针对同质信息网络。异质信息网络中包括基于随机游走、分解和针对应用任务的网络表示学习。Yu［80］等作者提出了基于元路径［9］的Metapath2vec算法。Tang［10］等提出分解的思想，将异构文本网络中复杂的数据转化为简单高效的表现形式。Sun［11］等首先研究异质信息网络中同一类型顶点上的相似搜索方法Path-Sim。

本文提出的技术与上述不同之处在于：传统的社区发现算法极少考虑到网络中更高阶的社区结构对社区发现的重要性。因此提出一种以社区发现为导向的网络嵌入模型。此外，许多方法都采用传统的网络存储方式耗费了较高的存储资源，考虑的特征也很单一，因此本文通过网络嵌入将拓扑特征，属性特征以及社区特征有效地综合起来，应用到社区发现当中，提高划分的准确性。

3 问题定义

定义1（属性网络社区发现问题）旨在从图中G(V，E，W，S)找到T∈Rn×n个社区，其中T∈Rn×n表示T∈Rn×n个节点的集合，T∈Rn×n是边的集合，T∈Rn×n表示边T∈Rn×n的权重。S表示节点的属性矩阵。并且理想的社区发现结果需满足相同社区内的节点属性特征相似，不同社区内的节点属性相差较大。

定义2（网络嵌入）定义图T∈Rn×n，对所有节点T∈Rn×n，学习映射关系T∈Rn×n，将原节点表示成一个低维稠密的实数向量T∈Rn×n。

定义3（节点表示矩阵）节点表示矩阵T∈Rn×n，通过网络嵌入方法得到节点低维的向量表示T∈Rn×n。

4 以社区发现为导向的网络嵌入模型

为了充分利用并整合网络的多种特征，以提高社区发现的准确性，提出了一种以社区发现为导向的网络嵌入模型——CDNE。

4.1 CDNE模型的基本思想

模型有两大部分组成：保持社区特征的网络嵌入以及基于网络嵌入的社区划分（如图2所示）。网络中往往蕴含了大量的信息，其中节点也具有丰富的属性特征。同时，网络中也可能存在原有的一些社区结构。模型将这三种特征有机地结合起来，通过非负矩阵分解方法得到节点的低维表示。然后使用Louvain［12］社区发现算法完成社区划分。

图2 社区为导向的网络嵌入模型CDNE

4.2 保持社区特征的网络嵌入

在原始网络中，从宏观上看，网络本就存在其固有的社区结构，某些节点属于同一潜在的社区结构。

图3 网络嵌入

1）保持社区特征的学习

首先，找到关系矩阵进行分解来获得节点在低维空间中的映射。定义了模块化矩阵B∈Rn×n，满足式（1），其中Ki，Kj代表的是点i，j的度数，e代表的是边的数目。

其中h=[hi]∈Rn是社区成员隶属度向量。将社区成员隶属度表示为矩阵H∈Rn×k。因此有约束t r(HT H)=n，得到了式（2）：

2）保持属性特征的学习

社区不仅具有紧密连接的结构，而且同一社区应该具有相似的属性。不同的社区也偏好不同的属性。定义节点的余弦属性相似度矩阵T∈Rn×n。

如式（3），通过分解属性相似度矩阵ΔQ来得到节点表示矩阵U∈Rn×n，另引入一个辅助非负矩阵Ci即第i行表示一个社区的表示向量。因此进行联合建模，联合损失函数如式（4）：

此外，通过控制非负参数α，β的大小来调节两种特征的贡献程度。目标函数的优化采用M-NMF中的迭代更新规则进行优化。

5 基于网络嵌入的两阶段社区发现算法

基于CDNE模型，首先提出一种社区发现算法，该算法在Louvain算法的基础上进行改进。

5.1 第一阶段：合并社区

Louvain算法具有快速、准确的优点。但该算法忽略了网络中固有的社区结构，只考虑节点间的链接关系。针对它存在问题，本文考虑将节点属性和社区特征应用到Louvain算法中，实验证明在真实网络中可以提高社区划分的准确性。

学习到节点的嵌入后，计算节点i与j向量的余弦相似度S(i，j)并作为节点间边的权重。每个节点都当做社区，遍历所有节点，将当前节点i分别加入每个邻居节点所在的社区并计算加入前后模块度的变化。根据模块度增量ΔQ最大值将该节点i分配至对应的邻居节点社区，直至网络中所有节点的分配稳定得到初步划分好的网络。

5.2 第二阶段：重构网络

这时将社区当做一个新节点重构网络，分别计算这些新节点之间的连边的权重，其值为先前网络中跨社区之间连边的相似度之和。重复阶段一直到节点的社区分配基本稳定，得到融合社区特征和节点属性特征的网络社区近似最优划分。

5.3 算法描述

基于网络嵌入的两阶段社区发现算法过程如下。

算法1 基于嵌入的社区发现算法输入 属性网络G；

输出 G的社区划分结果partition

1 For each node｛u，v｝∈E

2 Calcualte node similarity Cs；

3 End

4 Initialize each node into individual communities and calculating modularity，denoted by Q；

5 For each i in｛v｝

6 Calculate the neighbors｛k｝of node i；

7 For（j in neighbors｛k｝）

8 Delete node i from the pre_community；

9 Add node i into communoty of neighbor j

10 CalculateΔQ；

11 Choose the maximumΔQ and add the node i into the new community ofΔQ；

12 Calculate Q；

13 End

14 Regard each community as a new node and repeat the above steps；

15 Return the result；

6 实验与结果

6.1 实验数据集

本文在Cornell、Wisconsin和Texas三个数据集上进行实验，三个数据集统计信息如表1所示。

表1 实验数据集的统计信息

|V|代表节点数，|E|代表边数，s代表属性数量，k代表社区数量；AS代表社区的平均大小。

6.2 评价指标

NMI是一种常用的评价社区发现算法精度的指标。模块度是根据社区内部节点和边的疏密程度来量化社区结构的质量。

6.3 对比算法

基于初始结构的Louvain算法。SCI算法［13］提出了一种非负矩阵分解模型。SNMF［14］是一种基于非负矩阵分解的社区发现算法。PCL-DC［15］是一种综合链接和内容的社区发现算法。

6.4 对实验结果与分析

1）参数敏感性分析

以下在Cornell数据集上进行了CDNE的参数敏感性分析。α，β分别控制节点属性、社区特征的贡献度；由图可知，当α=1，β=2时可取到NMI最大值为0.368。

2）对比算法实验结果分析

本文将CDNE与四种基线算法做了性能比较。采用NMI和模块度两种评价指标来衡量。图5中结果表明CDNE算法都明显要优于其他算法。相比较可知，通过网络嵌入融合社区特征与节点属性特征有效地提高了社区发现的准确性。

图4 Cornell中参数α，β对NMI的影响

图5 对比算法实验结果分析

7 结语

针对现有的社区发现算法的不足，本文提出了一种以社区发现为导向的网络嵌入模型（CDNE），充分考虑了网络中的社区特征，节点属性信息，利用非负矩阵分解将三者有机地融合起来。此外本文提出基于网络嵌入的两阶段社区发现算法。采用Louvain算法进行社区划分，融合社区特征和节点属性特征的同时有效地提高了社区发现的准确性。