基于网络表示学习的非单一维度的社区发现算法

陈婉杰　盛益强

摘 要：針对现有的社区发现算法难以解决网络的多维性问题的现象，提出一种基于网络表示学习的非单一维度的社区发现算法。该算法从节点属性特征和网络结构特征两个维度考虑节点的差异性，首先根据节点属性相似度计算得到节点转移概率，结合小世界模型的六度分离理论设置网络节点随机游走路径的长度。依据转移概率选择节点的邻居节点，得到节点的游走路径，然后用神经网络模型训练节点的游走路径得到节点的网络特征向量，将节点网络特征向量的相似度重置为节点连接边的权重，在Louvain算法的基础上完成社区划分。最后，在Facebook和Giraffe两个数据集上进行了实验，选用基于初始网络结构的Louvain算法和基于单一维度的社区发现算法作为对比算法。实验结果表明，在Giraffe数据集中，相比于Louvain算法，基于节点属性的社区发现算法的模块度指标提升了2.7%，基于网络结构的社区发现算法的模块度指标提升了3.0%，提出的非单一维度的社区发现算法的模块度指标提升了3.7%。所提算法聚焦于网络的多维性，有效提升了社区发现算法的模块度。

关键词：节点属性;网络结构;可扩展性;社区发现;网络表示学习;节点差异性

中图分类号： TP391.4模式识别与装置文献标志码：A

Non-unidimensional community detection algorithm based on network representation learning

CHEN Wanjie1，2， SHENG Yiqiang 1，2*

（1. National Network New Media Engineering Research Center （Institute of Acoustics， Chinese Academy of Sciences）， Beijing 100190， China;

2. University of Chinese Academy of Sciences， Beijing 100049， China）

Abstract： Focusing on the issue that it is difficult for the existing community detection algorithms to solve the multidimensionality problem of the network， a non-unidimensional community detection algorithm based on network representation learning was proposed. The algorithm considered the difference of nodes from the two dimensions of node attribute feature and network structure feature. Firstly， the node transition probability was calculated according to the node attribute similarity. The length of the random walk path of the network node was set according to the six-degree separation theory of the small world model. After obtaining the walking path of the node by selecting its neighbor nodes according to the transition probability， the walking path of the node was trained by the neural network model to achieve the network feature vectors. The similarity of the network feature vectors of the node was reset as the weight of the connected edge， and the community partition was completed based on the Louvain algorithm. Finally， experiments were conducted on two datasets， Facebook and Giraffe with the Louvain algorithm based on the initial network structure and the unidimensional community detection algorithm as comparison algorithms. Experimental results show that on the Giraffe dataset， compared to the Louvain algorithm， the community detection algorithm based on the node attribute has the modularity increased by 2.7%， the community detection algorithm based on the network structure has the modularity increased by 3.0%， and the proposed non-unidimensional community detection algorithm has the modularity increased by 3.7%. The proposed algorithm focuses on the multidimensionality of the network and improves the modularity of the community detection algorithm effectively.

Key words： node attribute; network structure; extensibility; community detection; network representation learning; node difference

0 引言

随着互联网的飞速发展和移动终端的普及应用，复杂网络在生活中的很多领域均得到了快速的发展，如社交媒体领域、学术信息领域以及生物学领域等。随着网络规模的扩大，对复杂网络的分析也越来越重要，在真实世界的复杂网络中，通过网络中个体构成的社区来观察网络中节点的交互行为是清晰的，是全局化的，而通过个体行为观察节点之间的交互则通常是带有噪声和片面的。复杂网络中很多行为只能通过社区去发现，在个体层面难以观察到，这是因为个体行为往往具有很强的波动性，而社区行为一般相对稳定，不易改变，因此对复杂网络进行社区发现是有必要的。

识别复杂网络中个体所在的社区不仅具有一定的理论价值，也有着广泛的应用前景。例如电商平台通过识别出相似兴趣类别的用户社区，可以挖掘出潜在的购买者，当社区内成员点击或者购买了某一件商品后，便可为相同社区的其他用户推荐类似商品，从而可以提升商品推荐的准确率，更好地为用户服务。社交网络平台如微博、知乎、微信和Facebook等，用户存在点赞、关注以及评论等多种类型的互动关系，根据这些行为，社区发现可以获得网络的模块化结构，从而可以对具有相似特征的社区进行好友推荐，帮助用户发现更多的潜在好友。在信息传播领域中，发现社区的中心节点，合理地发挥中心节点的作用，不仅可以提高节点传播的影响力，加速信息传播，也可以在病毒出现时及时抑制病毒的进一步扩散。

网络的发展带来了信息的多样性，如今复杂网络包含的信息已不仅只是网络的结构信息，网络中的节点也具有丰富的属性，如Facebook数据集不仅包含网络中节点以及节点的连接边信息，还包含节点的属性信息，如年龄、性别、公司、生日、姓名等属性特征。有研究表明，实际网络中有直接连接关系的节点，通常其节点属性信息的相似度会更高[1-2]。为了验证该观点，以Facebook数据集和Giraffe数据集为例，可以看出，具有连接关系的节点属性相似度大于0.6、0.7和0.8的边的占比情况，如表1所示。Facebook数据集中有61%的连接边对应节点的属性相似度超过60%，Giraffe数据集中更有61%的连接边对应节点的属性相似度超过80%，这也论证了结合节点属性信息和网络结构进行社区发现的重要意义。

传统社区发现算法大多基于网络结构进行社区发现，面对网络的多维性问题，针对单个维度的社区发现算法研究已到达一定瓶颈。充分利用网络中节点的多维度特征，实现不同维度的信息的融合，不仅可以提高社区发现对当前网络的适应性，也可以充分利用网络节点不同维度层面的差异性，更好地挖掘节点的隐含特征。

随着信息化程度的提高，复杂网络规模越来越大。实际复杂网络中，大部分节点与网络中的其他节点之间的直接联系是非常有限的。选用合理的社区发现算法，充分利用节点属性与网络结构特征，在保证社区发现准确率的前提下，从网络中的局部节点结构便可挖掘出网络的隐含的特征信息，将极大地改善传统社区发现算法，从网络的全局信息挖掘网络潜在特征的低效問题，同时可以提高社区发现算法的可扩展性。

近几十年以来，社区发现作为网络科学中的一项基础研究，很多研究人员对社区发现算法进行了深入的探索，取得了很多突破性的成果。但随着网络的发展，针对目前社会网络结构中网络的特点，社区发现的研究面临着如下问题和挑战。

1）网络的多维性以及网络节点的差异性。

针对单一维度网络结构的传统社区发现算法因为信息的缺乏，在社区发现的效率和准确率上均受到了限制。随着信息化程度的提高，信息维度的增加使网络呈现出多维性，所谓网络的多维性是指网络中的节点之间边的连接关系有多种类型，而由这些节点及不同类型的边所组成的“维度”不同的网络就称为多维度网络。在各种复杂的网络尤其是社会网络中，不同节点之间也是有差异的，而传统社区发现算法，并没有考虑这一点，大多数网络分析的方法，忽略了节点之间的差异性，认为整个网络中所有的节点有着相同的地位。实际的网络中，不仅节点自身的属性特征有很大的差异性，每一个节点的隐含网络结构特征也都是不一样的。因此如何利用网络的多维度信息针对社区发现中网络节点的差异性挖掘节点的隐含特征，从而更好地完成社区划分是当前社区发现的研究面临的一个重要问题。

2）可扩展性。

当今网络发达，网络每时每刻都有新节点加入，复杂网络的规模越来越大，而现有的社区发现算法大多都基于全局信息去挖掘网络的隐含信息，例如：获取Girvan-Newman算法中依据“边介数”信息进行社区发现需要遍历整个网络;Kemighan-Lin算法为了完成社区划分必须要提前知道社区的个数或者平均规模等，在有新节点加入时，依然需要遍历整个网络去挖掘节点的隐含网络结构特征，从而造成算法的低效与浪费。而实际上，复杂网络尤其是社会网络大多是稀疏的，网络中的大部分个体与网络中的其他节点之间的直接联系是非常有限的，因此面对日益增长的节点规模，能否通过只依赖网络中的局部节点结构挖掘出网络的隐含的特征信息，在有新节点加入时，能否只对新节点所在的局部网络进行处理，增强算法的可扩展性是当前亟需要解决的一个问题。

针对现有社区发现算法难以解决网络的多维性问题、节点的差异性问题以及可扩展性问题，本文聚焦于网络多维性问题，提出了一种基于网络表示学习的非单一维度的社区发现算法。

该算法将节点属性信息作为先验信息，根据用户属性相似度重新计算节点之间转移概率，在node2vec算法的基础上，借助自然语言处理领域的特征学习方式，将文本的处理方式迁移至网络结构中。同时，结合小世界模型的六度分离理论设置网络节点游走路径的长度，通过对网络的局部结构进行分析，从而挖掘出局部网络的隐含特征。当网络中有新节点加入时，不需要遍历整个网络进行社区发现，只用计算与新节点有直接连接关系的节点之间的属性相似度，然后根据本文提出的算法在新节点附近按照根据属性相似度计算得到的概率进行游走。得到游走路径后，用神经网络模型训练得到节点的隐含特征向量，最后根据新得到的节点向量计算相似度后，使用Louvain社区发现算法完成社区划分。

本文的主要工作如下：

1）将节点属性信息作为先验信息，从节点属性和网络结构属性信息两个维度考虑了节点的差异性，改善了传统社区发现算法因为信息的缺乏只针对单一维度网络结构进行社区发现从而导致效率和准确率均受到限制的问题。

2）现有社区发现算法大多只考虑了边的连接性，即节点之间是否有直接连接关系，本文提出的算法可以计算出任意两个节点之间的加权相似度，不再局限只可以计算有连接关系的节点之间的相似度，因此一定程度上解决了社会网络的稀疏性问题。

3）从基于用户属性相似度的节点转移概率和基于六度分离理论设置的游走路径长度两个方面对随机游走算法进行约束，改善了传统随机游走算法在网络转移过程中具有较强随机性的缺点，提高了社区发现算法的准确率。

4）通过对网络的局部结构进行分析，即可挖掘出局部网络的隐含特征，提高了算法的可扩展性，改善了传统社区发现算法从全局网络角度考虑挖掘网络隐含特征造成的低效与浪费的问题。

实验结果表明，在Giraffe数据集中，相较于Louvain算法，基于节点属性的社区发现算法模块度指标提升2.7%，基于网络结构的社区发现算法模块度指标提升3.0%，本文提出的非单一维度的社区发现算法，模块度指标提升3.7%。

1 相关工作

随着复杂网络的发展，复杂网络分析中的社区发现问题成为一大研究热点，众多学者从不同的角度对该问题进行了深入的研究，下面介绍社区发现问题相关的经典算法以及当前该领域的一些新的研究方法。

Girvan等[3]提出了一种分裂的层次算法GN（Girvan Newman），基于边介数的相关概念对网络结构进行划分。边介数的定义是经过网络中某条边的任意两个点之间最短路径的数目，该算法通过迭代地移除网络中边介数最大的连接，以此完成划分。该算法优点是划分社区的结果很准确，但是缺点是算法时间复杂度在节点规模比较大时过高，因此不太适合处理大规模的网络结构图。Newman等[4]提出了模块度的概念，模块度主要作为评价社区划分质量的指标，可以用来衡量社区结构的强度，模块度越大，表示社区划分的结果越好，社区内部边越紧密。现在模块度在本身社区划分的结果是未知的情况下已经渐渐成为衡量社区发现的重要标准。Kernighan和Lin[5]提出了一种贪婪算法，也被称为Kernighan-Lin法，该算法把网络视为图结构，通过图分割的相关算法，不断迭代和交换不同社区内的节点，优化社区结构，调整社区之间连接边的数量，目的就是使社区内连接边的数量与社区之间连接边的数量的差值增大，从而获得社区划分的结果。该算法的缺点是如果划分社区之前不了解社区的实际规模，将无法知道使该方法结束的停止条件。为了改善前面提到的GN算法当节点规模变大时算法时间复杂度过高的缺陷，Newman[6]提出了一种快速分裂的层次算法FN（Fast Newman），该算法的思想是首先将网络的节点视为单个的社区，然后合并社区，合并的原则就是使模块度增量达到最大值时的两个社区作为新社区，不断地迭代调整直到整个网络被合并为一个单独的社区。FN算法在模块度达到最大时获得的划分结果成为社区发现的最终划分结果。该算法在保证社区划分质量的前提下，降低了算法的时间复杂度。 Blondel等[7]提出了Louvain算法，这是一种基于模块度的算法，该算法主要包括两个部分：第一部分是首先将每个节点视为单个的社区，尝试将单个社区加入可以让模块度增加最大的社区里面，一直遍历网络，直到网络中的节点都稳定下来;第二部分是压缩一个社区为一个节点，节点权重为原始社区内部节点权重的和，重复第一个过程，直到模块度成为一个稳定值。Louvain算法在网络规模比较大时依然可以取得很好的划分效果，而且时间复杂度很低，因此常被用于大规模网络中的社区划分。

近年来，基于深度学习的发展，结合神经网络对图结构的分析也取得了很多成果：Deepwalk算法[8]首次将深度学习应用于图的网络结构分析，在根据随机游走得到节点的游走序列后，借助自然语言处理中word2vec算法[9-10]的思想，将节点游走序列类比于文本处理中的句子，将序列中的节点类比于文本处理中的单词，使用skip-gram模型[10]学习得到网络中节点的向量表示;node2vec算法[11]在Deepwalk的基础上进行了改进，Deepwalk算法在得到节点序列时就是普通的随机游走，而node2vec算法借助参数可以控制随机游走时更偏向于深度优先搜索还是广度优先搜索;大网络内聚集模型（CLuster Affiliation Model for BIGNetworks， BIGCLAM）算法[12]用一个非负向量作为一个节点的网络表示，该算法认为两个节点向量表示的内积越大，两个节点产生直接连接关系的可能性也就越大;结构化深度网络嵌入（Structural Deep Network Embedding， SDNE）算法[13]首次将深层神经网络模型用于节点的网络表示学习，模型的第一个模块是有监督的自编码神经网络对一阶邻居关系的建模，第二个模块是无监督的自编码神经网络对二阶邻居关系的建模，从而保留了网络的一级相似度和二级相似度。

无论是传统社区发现算法还是结合深度学习模型的网络表示学习算法，均是只考虑了图的网络结构信息，也有一些社区发现算法同时结合节点属性信息与网络结构特征。社交网络嵌入（Social Network Embedding， SNE）算法[14]中神经网络的输入向量是节点的ID与其他属性向量的拼接，通过训练模型，提取到网络节点的特征表示。也有学者提出了将原始无向无权网络结构和属性信息直接相融合，缺點是只考虑了节点之间边的存在性，没有进一步挖掘网络结构的隐含信息。Zhang等[15]提出了通过对节点属性信息进行K核映射[16]的思路，先得到节点属性的表示向量，然后通过Deepwalk算法将网络结构信息编码到节点属性表示向量中，实现了两者的融合。温雯等[17]提出了基于顶点信息为先验信息的图嵌入（Graph embedding by incorporating prior knowledge on Vertex Information， GeVI）算法，调整skip-gram模型的优化函数中条件概率分布为网络结构表示向量和节点属性特征向量的乘积，从优化函数角度实现了两方面信息的融合。Yang等[18]提出了和文本信息相关的深度随机游走（Text-Associated Deep Walk， TADW）算法，该算法首先证明了Deepwalk算法等价于上下文矩阵的分解，通过将节点属性特征嵌入矩阵分解，借助矩阵分解框架实现了节点属性信息和网络结构信息的融合。Huang 等[19]提出了加速属性网络嵌入（Accelerated Attributed Network Embedding， AANE）算法，通过对节点属性相似性矩阵进行矩阵分解得到节点的向量表示，并在优化函数中增加了基于节点连接关系的约束项。Yang等[20]提出了Planetoid模型，利用标签信息，将标签相同但不具有连接关系的节点连接在一起，从而学习出包含节点标签属性信息的图表示。基于节点文本信息的图嵌入（Context-Aware Network Embedding， CANE）算法[21]通过对具有直接连接关系的节点的文本信息利用卷积神经网络[22]进行编码，选择直接相连的节点彼此之间相关性最大的卷积结果作为节点的表示向量。相关主题模型（Relational Topic Model， RTM）算法[23]使用文档主题生成模型 LDA（Latent Dirichlet Allocation）[24]对文本进行建模，该算法认为有直接连接关系的节点有着相似的主题分布;基于潜在概率的文本网络嵌入（Probabilistic LAtent document Network Embedding， PLANE）方法[25]在RTM算法的基础上，采用可视化的方法学习得到文本的主题以及节点的表示，这两种方法要求网络中节点的内容必须是文本，因此如果不是文本类型的节点属性，则不能处理;除了这两种算法外，也有一些算法[26]依赖节点文本内容属性完成网络表示学习，它们均基于网络中节点的文本内容属性，而没有充分利用节点的除文本属性外的其他描述性属性特征。

分析以上算法，可以将其分为三种类型：第一种是只考虑文本内容属性信息未考虑网络节点描述属性特征的，这类算法的不足之处是无法处理非文本类型的节点属性特征，因此算法不具有普适性;第二种是只考虑了节点部分描述属性，例如SNE算法只考虑了节点的属性ID，没有考虑其他属性信息，同时网络结构中边的信息没有得到充分利用;其他结合节点属性信息的方法，大多是先得到节点属性表示向量，再与网络结构表示向量相融合，这种融合方式较为低效。为了提高节点通过网络表示学习所得向量的质量，可以考虑充分利用节点的描述型属性特征，使算法具有普适性。同时也可以先融合节点属性信息和网络结构信息再去训练得到节点表示的向量，使节点属性特征和网络结构特征可以更好地互相补充和制约，以提高节点网络表示学习所得向量的质量，可以更好地进行社区发现。

本文主要方法与上述研究的不同之处在于以下两点：

1）充分利用了节点的属性信息和网络结构信息，将网络结构转化为向量表示，采用将节点属性信息作为先验信息，根据用户属性相似度重新计算节点之间转移概率的方式引入节点属性信息，从而进一步挖掘网络结构的隐含信息。

2）本文提出的算法通过计算节点基于网络表示学习得到的特征向量，用特征向量之间的相似度重置原始网络，然后使用Louvain社区发现算法完成社区划分，避免了将原始无向无权网络结构和属性信息直接相融合，只考虑了节点之间边的存在性的缺点。

2 融合节点属性和网络结构的社区发现算法

基于node2vec网络表示学习算法，聚焦于网络的多维性，本文提出了一种同时考虑节点属性特和网络结构两个维度特征的社区发现算法。在node2vec算法的基础上，引入节点属性信息后，借助自然语言处理领域的特征学习方式，将文本的处理方式迁移至网络结构中，同时结合小世界模型的六度分离理论设置网络节点游走路径的长度，通过对网络的局部结构进行分析，从而挖掘出局部网络的隐含特征。当网络中有新节点加入时，不需要遍历整个网络进行社区发现，只用计算与新节点有直接连接关系的节点之间的属性相似度，然后根据本文提出的算法在新节点附近按根据属性相似度计算得到的概率进行游走，得到游走路径后，用神经网络模型训练即可得到节点的隐含特征向量，从而提高了算法的可扩展性。本文算法流程如图1所示。

该算法首先加载图的网络结构数据，记录图中节点以及节点的连接关系;然后根据节点属性特征计算节点之间相似度，用节点属性相似度初始化节点之间连边的权重;重构原始网络为无向有权网络，根据式（3）计算节点之间转移概率，根据转移概率采样选择当前节点的邻居节点，当前节点每个邻居节点被选中的概率等于式（3）计算的转移概率的值。结合小世界模型，设置适当的游走路径长度，得到新的网络结构图中每个节点的游走路径;利用skip-gram模型采用随机梯度下降法和反向传播算法对节点进行训练，生成每个节点最优的向量表示，根据网络节点的向量表示计算节点的相似度;最后使用社区发现算法完成社区的划分，并使用模块度对算法效果进行评估。

2.1 基于用户属性的节点转移概率

将用户属性用向量表示，计算用户属性之间相似度，如果节点属性为种类类型或者布尔型特征，选用Jaccard系数计算节点属性相似度，计算式如式（1）所示;如果节点属性为连续数值型，选用余弦相似度计算节点属性相似度，计算式如式（2）所示，将节点属性的相似度作为节点之间的权重，重构原始网络。

S=J（A，B）=|A∩B||A∪B|（1）

其中：S表示节点属性相似度;A表示样本A，B表示样本B，J（A，B）表示样本A和样本B交集个数和并集个数的比值。

属性特征如果是连续数值型特征，可选用余弦相似度作为衡量标准。余弦相似度计算式如式（2）所示：

S=cos（X，Y）=∑ni=1（Xi×Yi）∑ni=1（Xi）2×∑ni=1（Yi）2（2）

其中：S表示节点属性相似度;X表示样本X，Y表示样本Y，cos（X，Y） 表示样本X和样本Y的余弦相似度;n表示样本特征向量维度;Xi表示样本X第i维特征，Yi 表示样本Y第i維特征。

假设当前节点是v，访问邻居节点x的概率如式（3）所示：

p（v，x）=wv，xZ（3）

其中Z为归一化因子。wv，x 计算式如式（4）所示：

wv，x=S/p，dtx=0

1，dtx=1

S/q，dtx=2 （4）

其中：S为节点属性相似度;t表示上一个节点;v表示当前节点;x为要访问的邻居节点;dtx 表示节点t和节点x的最短距离;参数p控制重复访问刚刚访问过的顶点的概率，p只在dtx=0 时起作用，dtx=0 表示下一次要访问的节点正是之前刚刚访问过的顶点。 因此如果p值较大，则访问刚刚访问过的顶点的概率会变低;反之会变高。参数q则控制着游走的方向是向外还是向内，若q值较大，则随机游走倾向于访问和t接近的顶点，游走路径偏向于广度优先搜索;反之，如果q较小，则随机游走过程倾向于访问远离t的顶点，游走路径偏向于深度优先搜索。

2.2 结合小世界模型的随机游走

小世界模型也即六度分离理论，该理论的主要思想是在社会网络中，任意两个不认识的人都可以通过“朋友的朋友”建立起一种联系，这中间一般需要通过5个朋友。研究表明，除了社会网络以外，也有很多其他领域的网络有类似的“六度分离”结构，如金融经济领域中的商业网络结构、大自然生态系统中的食物链，甚至人类的脑神经元结构等都存在这样的现象。

本文引入了节点的属性信息重构网络后，节点之间会有潜在的连接关系，本文认为被节点属性信息重构后的网络结构具有“六度分离”属性，因此结合小世界模型的思想，设置游走路径长度为l，其中3

2）基于节点属性相似度的社区发现（Community Detection based on Node Attribute Similarity， CD-NAS）算法[28]。该算法的特点是不考虑节点的网络结构特征，单一地根据节点的属性计算节点之间的相似度，然后将节点之间相似度作为节点之间连接权重，根据节点属性相似度进行社区发现。

3）基于网络结构特征相似度的社区发现（Community Detection based on Network Structure Feature Similarity， CD-NSFS）算法[11]，对网络结构特征的处理有两种方式，可以和基于初始结构的Louvain社区发现算法的处理方法一样即直接根据连接关系来处理，也可以先根据网络表示学习算法得到网络中节点的特征向量，然后根据节点的特征向量计算节点之间的相似度，然后根据节点网络结构特征相似度划分社区。

3.4 结果分析

将节点属性作为先验信息，先根据节点属性计算节点的相似度，Facebook数据集节点属性的相似度如表3所示，Giraffe数据集节点属性的相似度如表4 所示。

将节点属性相似度作为节点之间边的权重，重构原始网络，得到Facebook数据集节点用网络表示学习方法得到节点的特征向量一共100维，同时得到Giraffe数据集节点用网络表示学习方法得到节点的特征向量一共100维，利用t分布随机邻域嵌入（t-distributed Stochastic Neighbor Embedding， t-SNE）工具对节点特征向量进行降维处理。Facebook数据集根据网络表示学习算法得到的节点特征向量计算的相似度如表5所示，包含源节点、目标节点以及节点属性为先验信息的节点之间网络结构特征的相似度。

源节点目标节点节点属性相似度11460.94828137911890.85361916912290.97834576912010.97897261612040.9834241831600.98559850512150.9765135851350.9832997811910.98142946112380.966038461

Giraffe数据集根据网络表示学习算法得到的节点特征向量计算的相似度如表6所示，包含源节点、目标节点以及节点属性为先验信息的节点之间网络结构特征的相似度。

选用基于初始网络结构的Louvain算法进行对比实验，即：如果网络中节点有连边，权重设置为1;无连边，权重设置为0。对比实验选用的算法有：1）Louvain算法;2）只依赖用户属性特征的社区发现（CD-NAS）算法[28];3）只依赖网络结构特征的社区发现（CD-NSFS）算法[11];4）本文提出的基于网络表示学习的非单一维度的社区发现算法，也即将节点属性作为先验信息的基于网络表示学习的社区发现（Community Detection based on Network Representation Learning between nodes With Node Attribute as priori information， CD-NRLWNA）算法。Facebook数据集四种算法的模块度和运行时间对比结果如表7所示，Giraffe数据集四种算法的模块度和运行时间对比结果如表8所示。

从表7～8可以看出，无论是在Facebook数据集上，还是在Giraffe数据集上，本文提出的算法效果都是最好的。在Giraffe数据集上，相较于Louvain算法，基于节点属性的社区发现算法模块度指标提升了2.7%，基于网络结构的社区发现算法模块度指标提升了3.0%，而依据本文提出的非单一维度的社区发现算法，其模块度指标提升了3.7%。同时，因为网络节点规模和网络结构的复杂度不同，Facebook数据集运行时间均高于Giraffe数据集。和一般的加权融合节点属性和网络结构的社区发现算法不同的是，本文提出的算法在用网络表示学习算法學习节点的网络结构特征之前，先用节点属性作为先验信息，实验结果表明这种算法比基于单纯节点属性特征或基于网络结构特征进行社区发现算法效果都更好。

3.5 参数敏感性分析

在本节中，对本文提出的将节点属性作为先验信息的基于网络表示学习的社区发现算法进行了参数敏感性分析。本次实验选择Giraffe数据集测试，评价指标为模块度。本节分析了在算法中起重要作用的两个参数，分别是随机游走路径长度和特征维度，其他参数选用默认参数，每个节点的随机游走次数为num=50，超参数p=0.25、q=4，滑动窗口w=30，迭代次数n=5。

模块度随随机游走路径的变化如表9所示，模块度随特征维度的变化如表10所示。

从表9可以看出，如果随机游走的长度取值过小，则随机游走得到的节点序列均是初始节点的邻居节点，不能有效地展现网络的实际结构，具有很大的局限性;随着游走长度的增加，模块度的值开始明显提高，但是当游走路径长度增加到一定程度时，模块度的值便不再增加，主要是因为算法在收集到节点的序列后，会像自然语言处理方法中对文本句子的处理一样，限定句子的长度，那么相应的序列长度也是固定的，当游走长度足够长时，已经足以获取网络的全局性特征，因此算法也相对稳定。此外，还可以看出，当模块度为10时，模块度最大，也验证了引入节点信息和小世界模型进行社区发现的必要性。

从表10可以看出，特征维度从20维到128维之间，模块度一直在增加;从128维到200维，特征维度基本不再变化。这是因为当特征维度到一定程度时，已经可以完全表示出网络结构的信息，如果特征维度继续增大，会造成信息冗余。特征维度如果过低，则不能有效地表示出网络的结构特征;但是特征维度如果设置过大，不仅会造成信息冗余，也会增加算法运行时间。因此设置一个合适的特征维度对算法效果有很重要的影响。

Facebook數据集和Giraffe数据集使用Louvain算法和根据将节点属性作为先验信息的基于网络表示学习的社区发现（CD-NRLWNA）算法得到的社区发现效果如图5～6所示，其中相同颜色的属于同一个社区。

从图5～6可以直观地看出，和Giraffe数据集相比，Facebook数据集得到的社区结构更明确，社区划分更清晰，这和前面得出的Facebook数据集模块度明显高于Giraffe数据集的结果也是一致的。另一方面，和Louvain算法效果进行对比，本文提出的算法不仅对于网络边缘一些节点的社区归属社区划分的结果更合理，同时社区划分的粒度更细，社区内部的结构更紧凑，更精确地发现了一些Louvain算法没有发现的潜在社区，如图中黑色圆圈标记所示，被Louvain算法识别为一个大社区的节点集合，用本文提出的算法可以被划分为更细粒度的社区，验证了本文算法的有效性。

4 结语

从节点属性和网络特征两个维度出发，聚焦于网络的多维性，本文提出了一种基于网络表示学习的非单一维度的社区发现算法。该算法将节点属性作为先验信息，然后基于node2vec算法，结合网络表示学习进行社区发现，最后使用模块度对算法效果进行评估。实验结果表明本文提出的算法能更好地挖掘节点的隐含特征，社区划分的结果更准确。

社区发现作为复杂网络分析中一个重要的研究课题，我们接下来的研究方向主要是进一步结合图神经网络的相关知识对节点属性信息和网络结构的融合进行研究。此外，现在网络中的节点不仅仅是代表一个人或者一个网页，节点之间的连接也不仅仅只代表节点的连接关系，如社交网络中节点用户可能有多种行为，如“点赞” “关注”或者“评论”，因此针对网络中节点角色的差异性如何把这些不同的信息结合起来，也是接下来的一个研究方向。

参考文献 （References）

[1]MCPHERSON M， SMITH-LOVIN L， COOK J M. Birds of a feather： homophily in social networks [J]. Annual Review of Sociology， 2001， 27： 415-444.

[2]AIELLO L M， BARRAT A， SCHIFANELLA R， et al. Friendship prediction and homophily in social media [J]. ACM Transactions on the Web， 2012， 6（2）： 373-382.

[3]GIRVAN M， NEWMAN M E J. Community structure in social and biological networks [J]. Proceedings of the National Academy of Sciences of the United States of America， 2002， 99（12）： 7821-7826.

[4]NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2004， 69（2 Pt 2）： Article No. 026113.

[5]KERNIGHAN B W， LIN S. A efficient heuristic procedure for partitioning graphs [J]. Bell System Technical Journal， 1970， 49 （2）： 291-307.

[6]NEWMAN M E J. Fast algorithm for detecting community structure in networks [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2004， 69（6 Pt 2）： Article No. 066133.

[7]BLONDEL V D， GUILLAUME J L， LAMBIOTTE R， et al. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008： Article No. P10008.

[8]PEROZZI B， AL-RFOU R， SKIENA S. Deepwalk： online learning of social representations [C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York： ACM， 2014： 701-710.

[9]MIKOLOV T， SUTSKEVER I， CHEN K， et al. Distributed representations of words and phrases and their compositionality [C]// Proceedings of the 2013 International Conference on Neural Information Processing Systems. New York： Curran Associates Inc.， 2013： 3111-3119.

[10]MIKOLOV T， CHEN K， CORRADO G， et al. Efficient estimation of word representations in vector space [EB/OL]. [2019-05-20]. https：//arxiv.org/abs/1301.3781.

[11]GROVER A， LESKOVEC J. Node2vec： scalable feature learning for networks [C]// Proceeding of the 22nd ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York： ACM， 2016： 855-864.

[12]YANG J， LESKOVEC J. Overlapping community detection at scale： a nonnegative matrix factorization approach [C]// Proceedings of the 6th ACM International Conference on Web Search and Data Mining. New York： ACM， 2013： 587-596.

[13]WANG D， CUI P， ZHU W. Structural deep network embedding [C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York： ACM， 2016： 1225-1234.

[14]LIAO L， HE X， ZHANG H， et al. Attributed social network embedding [J]. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（2）： 2257-2270.

[15]ZHANG D， YIN J， ZHU X， et al. User profile preserving social network embedding [C]// Proceedings of the 26th International Joint Conference on Artificial Intelligence. Menlo Park： AAAI， 2017： 3378-3384.

[16]RAHIMI A， RECHT B. Random features for large-scale kernel machines [C]// Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. New York： Curran Associates Inc.， 2008： 1177-1184.

[17]溫雯，黄家明，蔡瑞初，等.一种融合节点先验信息的图表示学习方法[J].软件学报，2018，29（3）：786-798.（WEN W， HUANG J M， CAI R C， et al. Graph embedding by incorporating prior knowledge on vertex information [J]. Journal of Software， 2018，29（3）： 786-798.）

[18]YANG C， LIU Z， ZHAO D， et al. Network representation learning with rich text information [C]// Proceeding of the 24th International Joint Conference on Artificial Intelligence. Menlo Park： AAAI， 2015： 2111-2117.

[19]HUANG X， LI J， HU X. Accelerated attributed network embedding [C]// Proceedings of the 2017 SIAM International Conference on Data Mining. Philadelphia： SIAM， 2017： 633-641.

[20]YANG Z， COHEN W W， SALAKHUTDINOV R. Revisiting semi-supervised learning with graph embeddings [C]// Proceeding of the 33rd International Conference on Machine Learning. New York： JMLR， 2016： 40-48.

[21]TU C， LIU H， LIU Z， et al. CANE： context-aware network embedding for relation modeling [C]// Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics. Stroudsburg： Association for Computational Linguistics， 2017： 1722-1731.

[22]YANG H W， HSU H C， YANG C K， et al. Differentiating between morphologically similar species in genus Cinnamomum （Lauraceae） using deep convolutional neural networks [J]. Computers and Electronics in Agriculture， 2019， 162： 739-748.

[23]CHANG J， BLEI D M. Relational topic models for document networks [C]// Proceedings of the 12th International Conference on Artificial Intelligence and Statistics. Florida： PMLR， 2009： 81-88.

[24]GYAMFI K S， BRUSEY J， HUNT A， et al. A dynamic linear model for heteroscedastic LDA under class imbalance [J]. Neurocomputing， 2019， 343： 65-75.

[25]LE T M V， LAUW H W. Probabilistic latent document network embedding [C]// Proceedings of the 2014 IEEE International Conference on Data Mining. Piscataway： IEEE， 2014： 270-279.

[26]LI H， WANG H， YANG Z， et al. Variation autoencoder based network representation learning for classification [C]// Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics， Student Research Workshop. Stroudsburg： Association for Computational Linguistics， 2017： 56-61.

[27]李南星，盛益强，倪宏.基于LM算法的MLP模型及其應用[J].网络新媒体技术，2018，7（1）：59-63.（LI N X， SHENG Y Q， NI H. A multilayer perceptron model based on Levenberg-Marquardt algorithm with its applications [J]. Journal of Network New Media， 2018， 7（1）： 59-63.）

[28]LUSSEAU D， SCHNEIDER K， BOISSEAU O J， et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations ： can geographic isolation explain this unique trait？ [J]. Behavioral Ecology and Sociobiology， 2003， 54（4）： 396-405.

This work is partially supported by the Special Fund for Strategic Pilot Technology of Chinese Academy of Sciences （XDC02070100）.

CHEN Wanjie， born in 1993， M. S. candidate. Her research interests include data mining， intelligent processing.

SHENG Yiqiang， born in 1978， Ph. D.， associate research fellow. His research interests include intelligent networking， data mining.

收稿日期：2019-06-14;修回日期：2019-09-10;录用日期：2019-09-23。

基金项目：中国科学院战略性科技先导专项课题（XDC02070100）。

作者简介：陈婉杰（1993—），女，河南南阳人，硕士研究生，主要研究方向：数据挖掘、智能处理; 盛益强（1978—），男，北京人，副研究员，博士，主要研究方向：智能网络、数据挖掘。

文章编号：1001-9081（2019）12-3467-09 DOI：10.11772/j.issn.1001-9081.2019061009