复杂网络是由大量节点以及节点之间错综复杂的关系共同构成的网络结构^[1,2].除了小世界和无标度等特性外,复杂网络还呈现出明显的社区结构.所谓社区(community),是指网络中的节点聚集而成的子图.同一社区的节点之间连接紧密,不同社区的节点之间连接稀疏^[1,3].图 1所示的示例网络包含3个社区(虚线框出),其中,相同颜色的节点属于同一社区.现实世界的许多网络都具有社区结构,例如:在社交网络中,人与人之间建立朋友关系,形成了不同类型的朋友圈;在学术合作网络中,研究者们共同发表学术著作,形成各个研究领域的学术圈;在蛋白质网络中,蛋白质之间频繁地交互,形成了结构单元.于是,近年来,复杂网络中的社区发现问题得到社会学、生物学与计算机科学等多个学科的广泛关注和深入研究^[1,4-6],社区发现的研究成果也被成功应用于诸如好友推荐、个性化商品推介、蛋白质功能预测、舆情分析与处理等众多领域^[1,2].

社区发现致力于有效地寻找到复杂网络中准确的社区结构.目前,主流的社区发现方法有层次聚类方法(Radicchi^[7])、矩阵分块方法(MB-DSGE^[8])、骨架图方法(gCluSkeleton^[9])、标签传播方法(LPA^[10],HANP^[11])以及图嵌入方法(DeepWalk^[12])等,这些方法根据网络的拓扑结构,从不同的角度出发,解决复杂网络中的社区发现问题.

k-均值等经典的聚类算法是解决社区发现问题的一类基本方法^[13],然而在处理网络的高维相似度矩阵时,使用这些经典的聚类算法进行社区发现存在如下问题.

(1) 使用邻接矩阵作为网络的相似度矩阵,不能全面地反映每个节点的局部信息.网络中除了直接相连的节点之间存在相似关系外,不直接相连的节点之间也存在不同程度的相似关系.例如:可以经过s跳到达彼此的节点对之间存在一定的相似关系,使用邻接矩阵作为网络的相似度矩阵只能简单地呈现直接相连的节点之间的相似关系,无法表示不直接相连的节点之间的相似关系.所以,邻接矩阵丢失了许多节点对的相似关系信息,不能全面地反映每个节点的局部信息.邻接矩阵包含信息有限的问题,影响社区发现的准确性;

(2) 高维相似度矩阵不能反映网络拓扑结构的主要特征,对网络拓扑结构中的社区结构没有很好的表达能力,在使用k-均值等经典的聚类方法对高维相似度矩阵进行社区发现时,存在结果社区不准确的问题.

针对上述问题,本文提出了基于深度稀疏自动编码器的社区发现算法CoDDA(a community detection algorithm based on deep sparse autoencoder).CoDDA算法能够根据网络拓扑结构,实现较为准确的社区发现.本文的主要贡献有如下3点.

(1) 提出基于s-跳的预处理方法,对稀疏的邻接矩阵进行优化处理.预处理得到的相似度矩阵不仅可以表示直接相连的节点对之间的相似关系,也可以为不直接相连的节点对添加一定的相似关系;

(2) 基于深度稀疏自动编码器这一无监督的深度学习方法,对相似度矩阵进行特征提取.提取特征后得到的低维特征矩阵能够更好地反映网络拓扑结构的主要特征,提高k-均值等经典聚类算法的准确性;

(3) 在多个真实数据集上进行了大量实验.实验结果表明,本文提出的CoDDA算法可以得到更加准确的社区结构.

本文第1节介绍相关工作,包括已有的社区发现方法和深度学习方法.第2节给出基于跳数的相似度矩阵预处理操作的具体过程.第3节详尽阐述本文设计的深度稀疏自动编码器.第4节提出一种基于深度稀疏自动编码器的社区发现算法CoDDA.第5节在多个真实的数据集上,从不同方面对CoDDA算法的有效性进行验证.第6节总结全文.

1 相关工作

本节介绍网络中社区的定义,并总结目前主流的5类社区发现方法.介绍深度学习的主要思想,并简介目前主流的有监督和无监督的深度学习方法.

1.1 社区发现

给定一个网络,社区发现根据网络中节点间的相互关系,将所有节点聚合成一系列子结构,即社区^[1,3,14-17].与不同社区间节点之间的连接关系相比,同一社区内的节点之间通常具有较强的连接关系.目前,主流的社区发现算法分为层次聚类方法(Radicchi^[7],GN^[4],Newman^[18],CNM^[19])、矩阵分块方法(MB-DSGE^[8],OQC^[20])、骨架图方法(gCluSkeleton^[9])、标签传播方法(LPA^[10],HANP^[11],SLPA^[21])、图嵌入方法(Deepwalk^[12],LE^[22],GraRep^[23]).其中,图嵌入方法与本文提出的CoDDA算法的思路最相似,都是先对矩阵进行降维操作,再得到社区.

基于层次聚类的方法根据网络图的层次化特点发现社区,包括自顶向下的分裂层次聚类方法和自底向上的凝聚层次聚类方法.分裂层次聚类方法将网络图分解为不同层次的子图,并从中寻找符合条件的社区.典型的分裂层次聚类算法有Radicchi算法^[7]和GN算法^[4].Radicchi算法根据每条边所在的三角形数量计算边的聚集系数,并在每次迭代中删除聚集系数最小的边,直到生成符合条件的社区^[7].凝聚层次聚类方法从网络图中每个节点出发,将满足条件的节点合并为不同层次的子图,并从中寻找符合条件的社区.典型的凝聚层次聚类算法有Newman算法^[18]和CNM^[19]算法.矩阵分块方法通过重排网络图的邻接矩阵,将具有紧密连接关系的节点重新排列,并从中找出比较稠密的矩阵块,即社区.典型的矩阵分块算法有MB-DSGE算法^[8]和OQC算法^[20].MB-DSGE算法通过构建一棵完整的层次树,根据密度阈值找到社区结构^[8].骨架图聚类方法从网络图中提取出骨架图(skeleton graph),并根据骨架图得到社区,例如gCluSkeleton算法^[9].gCluSkeleton算法依据网络图的拓扑结构生成骨架图,将网络图包含的结构信息聚集到骨干网络中去,从冗杂的连接关系中提取出有效的社区结构.标签传播方法模拟社交关系在网络图中的传播过程生成社区,典型的标签传播算法有LPA算法^[10]、HANP算法^[11]和SLPA算法^[21].LPA算法首先为每个节点赋予唯一的标签,进而模拟社交关系在网络图中的传播过程;待标签分布稳定后,相同标签的节点被视为同一社区内的成员.在LPA的基础上,HANP算法通过添加节点偏好和衰减因子来控制标签的传播过程.图嵌入方法先对网络图的相似度矩阵进行降维操作,再计算社区结构,例如Deepwalk算法^[12]、LE算法^[22]和GraRep算法^[23].Deepwalk算法使用随机游走和skip-gram 模型得到网络图的表示矩阵,并计算出社区.

本文提出基于深度稀疏自动编码器这一无监督深度学习方法的社区发现算法CoDDA,提高了使用k-均值等经典聚类算法进行社区发现的准确性.

1.2 深度学习

深度学习方法^[24-27]的主要思想是:通过建立具有多个层次的神经网络,实现对输入数据的深层次表达,从而实现更好的分类与特征抽取.其中,前一个层次的输出为后一个层次的输入.使用深度学习方法可以让计算机自动地学习到人工方法难以发现的重要特征.一个具有两个隐藏层的深度神经网络如图 2所示.

深度学习方法在机器学习和人工智能等领域得到了充分的研究^[24,28].针对深度学习的理论研究、算法设计和应用系统在许多领域被广泛提出,例如语音识别、图像分类、自然语言处理等^[29,30].目前,主流的深度学习方法有自动编码器(autoencoder,简称AE)^[31]、限制玻尔兹曼机(restricted Boltzmann machines,简称RBM)^[32]、深度置信网络(deep belief network,简称DBN)^[33]、卷积神经网络(convolutional neural network,简称CNN)^[34]、循环神经网络(recurrent neural network,简称RNN)^[35,36]等.其中,AE,RBM,DBN是无监督的深度学习方法,CNN,RNN是有监督的深度学习方法.

AE是3层神经网络,将输入表达编码为一个新的表达,然后解码,通过反向传播方法训练网络,使输出表达等于输入表达.在RBM中,我们可以通过输入表达v和条件概率p(h|v)得到隐含层表达h;反过来,也可以通过隐含层表达h和条件概率p(v|h)得到一个新的输入表达.如此反复下去,通过调整参数,使输出表达等于输入表达.2006年,Hinton等人^[37-39]提出了DBN,在保证学习效果的同时,降低了学习隐藏层参数的难度.作为一个由多层RBM组成的神经网络,DBN使用非监督的逐层贪婪方法与反向传播方法训练获得权值.

1998年,Lecun等人^[40]提出的CNN提高了反向传播方法的训练性能.CNN是多层神经网络,包括卷积层(alternating convolutional layer)和池化层(pooling layer),每层包括多个二维平面,每个平面包括多个独立神经元.作为另一种多层神经网络,RNN的隐藏层之间的节点也存在有连接,并且隐藏层的输入不仅包括输入层的输出还包括上一时刻隐藏层的输出,通过这样的结构设计来处理序列数据.

CNN等有监督的深度学习方法主要用于分类问题,AE等无监督的深度学习方法在学习特征方面存在诸多优势.与CNN训练过程会丢失大量信息的特点不同,AE致力于在特征提取时尽可能地减少信息的丢失.本文尝试利用AE的这一特点,将相似度高的节点聚集,同时将相似度低的节点分开.

2 矩阵预处理

本节给出CoDDA算法在矩阵预处理阶段的详细过程.

给定一个网络图G=(V,E),V={v₁,v₂,…,v_n}是节点集合,E={e₁,e₂,…,e_m}是边集合,N(u)是节点u的邻居节点集合.邻接矩阵A=[a_ij]_n×n表示节点间的连接关系,矩阵对应元素的值表示边是否存在:如果v_i和v_j之间存在边,则a_ij=1;v_i和v_j之间不存在边,则a_ij=0.

通常,可以把邻接矩阵A作为网络的相似度矩阵来刻画网络中节点间的相似关系.然而,网络中除了直接相连的节点之间存在相似关系以外,不直接相连的节点之间也存在不同程度的相似关系.例如:经过有限跳数可以彼此到达的两个节点之间存在一定的相似关系.使用邻接矩阵作为网络的相似度矩阵只能简单地呈现直接相连的节点之间的相似关系,无法表示不直接相连的节点之间的相似关系.所以,邻接矩阵丢失了许多节点之间的相似关系信息,不能反映每个节点完整的局部信息.邻接矩阵包含信息有限的问题,影响社区发现的准确性.

因此,为了更充分地描述每个节点的局部信息,本节提出基于跳数的方法,根据网络的邻接矩阵A,计算节点间的相似关系,得到新的相似度矩阵.下面给出s-跳和本文提出的相似度矩阵的定义.

定义 1(s-跳). 给定一个网络图G=(V,E),u∈V,对点集内的任意节点u∈V,若节点u可以在最少经过s跳之后到达节点v,即:节点u到节点v的最短路径的长度是s,则称节点u可以经过s-跳(s-hop)到达节点v.

如图 3所示,在一个网络图中,节点v₁可以经过2跳(2-hop)到达节点v₄,可以经过3跳(3-hop)到达节点v₅,可以经过2跳(2-hop)到达节点v₆.

定义 2(节点相似度). 给定一个网络图G=(V,E),u,v∈V,u和v之间的相似度Sim(u,v)定义为

$sim\left( u,v \right)\text{=}{{\text{e}}^{\sigma \left( 1-s \right)}}$

(1)

其中,节点u经过s-跳到达节点v,s≥1.s称为衰减因子,s∈(0,1) .随着跳数s的增加,相似度不断减小.s控制了相似度的衰减程度,s越大,节点间相似关系衰减得越快.

定义 3(相似度矩阵X). 给定一个网络图G=(V,E),X=[x_ij]_n×n是与G对应的一个矩阵.如果使用公式(1) 计算X中对应两个节点v_i和v_j之间的相似度x_ij=Sim(v_i,v_j),v_i,v_j∈V,则称X为G的相似度矩阵.

使用跳数和衰减因子计算两个不直接相连的节点之间的相似关系,可以更好地反映社区的拓扑结构,提高社区发现的准确性.但是当跳数大于一定阈值时,两个不在同一个社区内的节点也会得到一定的相似度值,这使得社区结构的边界更加模糊.因此,设置跳数阈值S,只计算在S跳内可以相互到达的节点之间的相似度,保证在增强图的拓扑结构信息的同时,不影响社区边界的划分.实验部分对跳数阈值S和衰减因子s进行分析,研究不同的跳数阈值S和衰减因子s取值对结果的影响.

3 特征提取

本节给出CoDDA算法在特征提取阶段的具体过程.首先介绍稀疏自动编码器的定义,然后构建深度稀疏自动编码器,对n×n的相似度矩阵X进行特征提取,得到n×d的低维特征矩阵Y.特征矩阵Y能够显示更主要的图拓扑结构特征^[41].

3.1 稀疏自动编码器

定义 4(自动编码器). 自动编码器(autoencoder,简称AE)是一个3层的神经网络.AE对用户输入进行编码,然后解码得到输出,使用反向传播算法来训练网络,使得输出等于输入,得到编码结果.

自动编码器通过尽可能去复现输入数据的方法,去提取输入数据的特征.它是一种无监督的模型,训练样本没有类别标签,结构如图 4所示,形象表示如图 5所示.

第1层到第2层相当于一个编码(encode)过程.给定网络图G的相似度矩阵X={x₁,x₂,…,x_n},我们输入G的一个节点在X中对应的向量x_i∈Rⁿ后,自动编码器编码得到这个节点对应的低维向量h_i∈R^d.从第2层到第3层相当于一个解码(decode)过程.自动编码器将这个节点对应的低维向量h_i进行解码,得到与x_i具有相同维度的输出向量${{{x}'}_{i}}$.我们使用反向传播算法来训练网络,通过调整编码器和解码器的参数,最小化重构误差,使得输出向量${{{x}'}_{i}}$等于输入向量x_i.最后,我们把获得的编码层结果,即这个节点对应的低维向量h_i作为特征结果.

在自动编码器中,我们设定具体的训练过程如下.

我们将网络图G的相似度矩阵X作为自动编码器的输入矩阵,x_i∈R^n×1是相似度矩阵X的第i个节点对应的向量,我们将x_i作为自动编码器的第i个输入向量.将x_i输入到一个具有d个神经元的编码层,通过公式(2) 得到编码h_i∈R^d×1.

${{h}_{i}}={{s}_{f}}(W{{x}_{i}}+p)$

(2)

其中,s_f是编码器的一个激活函数,如sigmoid函数(sigmoid(x)=1/(1+exp(-x)).W∈R^d×n是权重矩阵,p∈R^d×1是编码层偏置向量.

得到编码h_i∈R^d×1 (即第i个节点对应的低维向量)后,我们将h_i输入到解码层,通过公式(3) 得到解码结果x_i'∈R^n×1作为输出信息:

${{x}_{i}}^{\prime }={{s}_{g}}(\tilde{W}{{h}_{i}}+q)$

(3)

其中,s_g是解码器的一个激活函数.$\tilde{W}={{W}^{T}}\in {{R}^{n\times d}}$是权重矩阵,$q\in {{R}^{n\times 1}}$是解码层偏置向量.

通过训练,自动编码器自动调整权重矩阵和偏置向量这4个参数$\theta \text{= }\!\!\{\!\!\text{ }W,\tilde{W},p,q\}$,最小化x_i和${{{x}'}_{i}}$的重构误差:

$\underset{W,\tilde{W},p,q}{\mathop{minimize}}\, \sum\nolimits_{i=1}^{n}{||{{s}_{g}}(\tilde{W}{{s}_{f}}(W{{x}_{i}}+p)+q)-{{x}_{i}}||}_{2}^{2}$

(4)

此外,我们使用KL散度,为自动编码器添加稀疏性限制:

$\sum\limits_{j=1}^{d}{KL\left( \rho ||\frac{1}{n}\sum\limits_{i=1}^{n}{{{h}_{i}}} \right)}$

(5)

其中,使用${{\rho }_{j}}$来表示隐藏层的平均活跃度${{\rho }_{j}}=\frac{1}{n}\sum\limits_{i=1}^{n}{{{h}_{i}}}$.$KL(\rho ||{{\rho }_{j}})$表示分别以${{\rho }_{j}}$和ρ为均值的两个变量之间的相对熵.ρ是一个接近于0的常量,例如取0.01.$KL(\rho ||{{\rho }_{j}})$的计算公式如下:

$KL(\rho ||{{\rho }_{j}})\text{=}\rho \log \frac{\rho }{{{\rho }_{j}}}+(1-\rho )\log \frac{1-\rho }{1-{{\rho }_{j}}}$

(6)

本文构建的自动编码器的重构误差可以总结为如下公式:

$L(\theta )=\sum\nolimits_{i=1}^{n}{||{{s}_{g}}(\tilde{W}{{s}_{f}}(W{{x}_{i}}+p)+q)-{{x}_{i}}||}_{2}^{2}+\alpha \sum\limits_{j=1}^{d}{KL\left( \rho ||\frac{1}{n}\sum\limits_{i=1}^{n}{{{s}_{f}}(W{{x}_{i}}+p)} \right)}$

(7)

其中,α是控制稀疏限制的权重因子.

3.2 深度稀疏自动编码器

本文构建的深度稀疏自动编码器由多层稀疏自动编码器构成,结构如图 6所示,前一层自动编码器的输出是后一层的输入.我们使用逐层贪婪的训练方法,依次训练深度稀疏自动编码器的每一层,进而训练整个深度神经网络.

本文基于深度稀疏自动编码器,实现对相似度矩阵X的特征提取.首先设置深度稀疏自动编码器的结构,包括层数T和每层的节点数{d⁽¹⁾,d⁽²⁾,…,d^(T)},其中,d⁽¹⁾=n;接着,我们将相似度矩阵X⁽¹⁾=X,X∈R^n×n作为深度稀疏自动编码器的第1层输入,将X⁽¹⁾输入到有d⁽²⁾个节点的自动编码器,提取训练得到的编码层结果${{X}^{(2)}}\in {{R}^{n\times {{d}^{(2)}}}};$然后,将矩阵X⁽²⁾输入到有d⁽³⁾个节点的自动编码器,提取训练得到的编码层结果${{X}^{(3)}}\in {{R}^{n\times {{d}^{(3)}}}};$继续循环操作,直到从最后一个自动编码器中提取出训练得到的编码层结果${{X}^{(T)}}\in {{R}^{n\times {{d}^{(T)}}}};$最后,输出深度稀疏自动编码器的低维特征矩阵X^(T).

4 基于深度稀疏自动编码器的社区发现算法

本节提出基于深度稀疏自动编码器的社区发现算法CoDDA,主要包括3个步骤:基于跳数的邻接矩阵预处理,即,使用广度优先遍历BFS,对邻接矩阵进行处理,得到相似度矩阵(已在第2节详细介绍);构建深度稀疏自动编码器对相似度矩阵进行特征提取,以得到特征明显的低维特征矩阵(已在第3节详细介绍);使用k-均值方法聚类得到社区.具体的算法流程见算法1.

　　算法 1. CoDDA.

　　输入:网络图G=(V,E)的邻接矩阵A∈R^n×n,社区个数k;跳数阈值S,衰减因子s;深度稀疏自动编码器的层数T,每层节点数d^(j),j=1,…T;d⁽¹⁾=n;

　　输出:社区结果{C₁,C₂,…,C_k}.

　　1.　FOR each x in V

　　2.　　将图G中每个节点初始化为未访问状态;

　　3.　　初始化队列Queue=∅;初始化跳数集合D=∅;

　　4.　　将x标记为访问中状态,初始化x的跳数为0,将x及跳数0写进跳数集合D,并将x入队列Queue;

　　5.　　WHILE Queue∅

　　6.　　　从队列Queue中取出节点 u;

　　7.　　　FOR each v in N(u)

　　8.　　　　IF u在x的(S-1) -跳内 andv处于未访问状态

　　9.　　　　　将v设置为正在访问状态;

　　10.　　　　　x到v的跳数等于x到u的跳数加1;

　　11.　　　　　将v及x到v的跳数写进跳数集合D;

　　12.　　　　　将v加入队列Queue;

　　13.　　　　End

　　14.　　　End

　　15.　　　将u设置为访问结束状态;

　　16.　　　End

　　17.　　　FOR each v inV

　　18.　　　　　根据跳数集合D及公式(1) 计算x和v的相似度Sim(x,v);

　　19.　　　End

　　20.　End

　　21.　得到基于跳数的相似度矩阵X;

　　22.　X⁽¹⁾=X;

　　23.　FORj=1 to T

　　24.　　建立一个稀疏自动编码器;

　　25.　　输入特征矩阵X^(j);

　　26.　　通过优化公式(7) 训练稀疏自动编码器;

　　27.　　得到隐含层的表示H^(j);

　　28.　　X^(j+1)=H^(j);

　　29.　End

　　30.　对低维特征矩阵${{X}^{(T)}}\in {{R}^{n\times {{d}^{(T)}}}}$运行k-均值,聚类得到结果社区Coms={C₁,C₂,…,C_k};

　　31.　Return 社区结果Coms={C₁,C₂,…,C_k}.

首先,CoDDA算法的输入包括3部分:图G=(V,E)的邻接矩阵A∈R^n×n,社区个数k;基于跳数的邻接矩阵预处理阶段需要的参数,即,跳数阈值S和衰减因子s;深度稀疏自动编码器特征提取阶段需要的参数,即,层数T和每层节点数d^(j),j=1,…T,d⁽¹⁾=n.

从算法1的第1行~第21行,使用基于跳数的邻接矩阵优化处理方法,生成相似度矩阵X.其中,从第5行~第16行,对图G中的每个节点x,使用BFS广度优先遍历的方法找到x在S跳内可达的节点v,将v及x和v之间的跳数写进跳数集合D.从第17行~第19行,计算x与点集V内其他节点的相似度:如果v在D内,那么使用公式(1) 计算得到结果Sim(x,v);否则,Sim(x,v)=0.

从第22行~第29行,对相似度矩阵X进行特征提取.循环执行T次,每次使用一个稀疏自动编码器从编码层提取出低维特征矩阵H^(j),令X^(j+1)=H^(j)作为下次循环的输入矩阵.循环结束,得到低维的特征矩阵X^(T)∈${{R}^{n\times {{d}^{(T)}}}}.$第30行对低维特征矩阵使用k-均值方法,聚类得到结果社区{C₁,C₂,…,C_k}.

5 实验结果与分析

本节使用真实数据集对CoDDA算法进行性能评价.我们首先介绍实验环境、数据集、评价标准和典型的比较算法,然后进行比较实验、可视化实验和参数实验.

5.1 实验准备

本文的实验环境设置为:Windows Server 2008操作系统,Intel Xeon 2.0GHz CPU,256GB内存.本文提出的算法及实验基于Java语言(JDK 1.7.0) 和Matlab(R2015b)编码实现.

使用4个真实数据集Strike,Football^[42],LiveJournal,Orkut^[43]进行实验.Strike是锯木工人关于罢工话题的通信网络;Football是2006年NCAA足球比赛的对阵关系网络;LiveJournal是用户之间可以标记朋友关系的在线博客网络;Orkut是一个免费的在线社交网络,用户可以建立朋友关系,同时还可以建立朋友群组.

从4个数据集中分别抽取3个、11个、8个、12个社区的节点及连接这些节点的边组成新的网络,用于本节的实验.详细信息见表 1,每个数据集包括网络拓扑结构和真实社区(ground-truth)信息.

本文构建的深度神经网络在不同数据集上的层数设置是不同的,详细信息见表 2.

对于小规模的数据集,选择层数小的深度神经网络即可达到很好的特征提取的效果.对于大规模数据集,按照2的幂次,依次降低深度神经网络中每层节点的个数.同时,在深度神经网络中,设置学习速率为lr=0.1,考虑稀疏性限制,设置r=0.01.这样的参数设置可以有效地利用深度自动编码器逐层贪婪训练的特点,保证在不同规模数据集上特征提取的准确性.

5.2 评价标准

根据真实社区$GT=\{{{{C}'}_{1}},{{{C}'}_{2}},...,{{{C}'}_{t}}\}$,判断结果社区Coms={C₁,C₂,…,C_k}的准确性,其中,t是真实社区(ground-truth)的数量,k是结果社区的数量.使用F_same^[10]和NMI(normalized mutual information)^[44]这2个通用的社区评价标准对社区的精确度进行分析,同时考虑到在许多真实数据集中通常难以获得真实社区的信息,因此,我们使用Q^[19]这一评价指标对社区的质量进行度量.

(1) F_same:是对社区结果与真实社区的交叉和近似程度的衡量指标,计算公式如下.

${{F}_{same}}=\frac{1}{2n}\left( \sum\limits_{i=1}^{k}{\underset{j}{\mathop{\max }}\,|{{C}_{i}}\cap {{{{C}'}}_{j}}|}+\sum\limits_{j=1}^{t}{\underset{i}{\mathop{\max }}\,|{{C}_{i}}\cap {{{{C}'}}_{j}}|} \right)$

(8)

其中,n是图G中节点的数量.

(2) NMI:归一化互信息,计算公式如下.

$NMI=\frac{-2\sum\nolimits_{ij}{{{N}_{ij}}\log \frac{{{N}_{ij}}{{N}_{t}}}{{{N}_{i.}}{{N}_{.j}}}}}{\sum\nolimits_{i}{{{N}_{i.}}\log \frac{{{N}_{i.}}}{{{N}_{t}}}+\sum\nolimits_{j}{{{N}_{.j}}\log \frac{{{N}_{.j}}}{{{N}_{t}}}}}}$

(9)

其中,N是混淆矩阵,每个元素N_ij代表了C_i和${{{C}'}_{j}}$的公共节点数,N_i.和N_.j分别代表了矩阵中第i行和第j列中元素的和,且${{N}_{t}}=\sum\nolimits_{i}{\sum\nolimits_{j}{{{N}_{ij}}}}.$

(3) Q:模块性(modularity)是使用最广泛的衡量社区质量的评价标准之一,计算公式如下.

$Q\text{=}\sum\limits_{i=1}^{k}{\left( \frac{E_{i}^{in}}{m}-{{\left( \frac{2E_{i}^{in}+E_{i}^{out}}{2m} \right)}^{2}} \right)}$

(10)

其中,$E_{i}^{in}$是社区C_i的内部边的数量,$E_{i}^{out}$是社区C_i的外部边的数量,m是图G中边的个数.

5.3 比较算法

将本文提出的算法CoDDA与已有的典型算法进行比较.比较算法详细信息如下.

(1) Radicchi算法:是一种分裂层次聚类算法,根据每条边所在的三角形数量计算边的聚集系数,每次迭代将删除聚集系数最小的边,直到产生不相连的子图作为社区结果;

(2) MB-DSGE算法:是一种矩阵分块算法,通过构建一棵完整的层次树,根据密度阈值找到社区结构;

(3) gCluSkeleton算法:是一种骨架图算法,依据网络图的拓扑结构生成骨架图,将网络图包含的结构信息聚集到骨干网络中去,从冗杂的连接关系中提取出有效的社区结构;

(4) LPA算法:是一种标签传播算法,模拟社交关系在网络中的传播过程.待标签分布稳定后,相同标签的节点被分到同一社区中;

(5) HANP算法:也是一种标签传播算法,是LPA算法的改进算法,通过添加节点偏好和衰减因子的方式,控制标签的传播过程;

(6) Deepwalk算法:是一种图嵌入算法,通过使用随机游走和skip-gram模型,得到图的低维矩阵表示,并计算出社区.

5.4 实验结果

通过比较实验和可视化实验,将已有的算法与本文提出的CoDDA算法进行对比,展示本算法的优势;通过参数实验,展示基于深度稀疏自动编码器的CoDDA算法的特征提取过程对社区准确性的贡献.

5.4.1 比较实验

为验证算法在社区准确性方面的优势,使用CoDDA算法和已有的典型算法进行比较,得到的社区评价指标F_same,NMI和Q的结果见表 3.

表 3的结果显示,CoDDA算法得到的社区比其他典型的算法更为准确.这是因为处理高维的邻接矩阵时,CoDDA使用基于跳数的预处理方法,有效地完善了节点的局部信息,并使用深度稀疏自动编码器对相似度矩阵进行特征提取,得到特征更加明显的低维特征矩阵,进而聚类得到更准确的社区.Deepwalk算法的效果不甚理想,这也与文献[23]中的情况吻合.

与基于层次聚类的Radicchi算法、基于矩阵分块的MB-DSGE算法、基于骨架图的gCluSkeleton算法、基于标签传播的LPA算法和HANP算法以及基于图嵌入的Deepwalk算法等比较算法不同,本文构建的由深度稀疏自动编码器构成的深度神经网络具有较好的特征表达能力.CoDDA算法采用逐层贪婪训练法进行训练,即:前一层自动编码器的输出作为后一层自动编码器的输入,这样通常能够获取到输入数据的层次型分解结构.例如,如果网络的输入数据是反映图的拓扑结构的相似度矩阵,那么网络的第1层会学习如何去识别网络中的重要节点,第2层会学习如何去组合这些重要节点,从而构成局部密集的子图,更高层会学习如何去组合这些密集子图,生成更形象且更有意义的子图,最终学得如何形成准确的社区.

CoDDA算法的运行主要分为离线和在线两个阶段,其中,离线阶段进行特征的提取,在线阶段进行k-均值聚类.我们对算法在线阶段的运行时间进行统计,不同数据集上CoDDA算法和比较算法的运行时间见表 4.实验结果表明,本文提出的CoDDA算法在时间上与目前主流的社区发现方法具有一定的可比性.

测试离线阶段特征提取过程的时间开销,结果见表 5.虽然在大数据集上的运行时间稍长,但这也符合深度学习的特点.并且,离线阶段进行的特征提取不会对在线阶段社区发现的效率产生影响.

5.4.2 可视化实验

针对Strike数据集和Football数据集,使用比较算法和CoDDA算法进行可视化分析.因为相比其他算法,Deepwalk算法效果不够理想,所以没有对其进行可视化实验.

对Strike数据集使用比较算法和CoDDA算法得到的社区和真实社区如图 7所示,相同颜色的节点属于相同社区,不同颜色的节点属于不同社区.

实验结果表明,本文提出的CoDDA算法得到的社区结果最接近真实的社区结果.如图 7(a)所示,Strike数据集含有的24个节点属于3个真实社区C₁,C₂和C₃.如图 7(b)所示,Radicchi算法将原本属于同一社区的节点分到了C₁和C₂两个社区.如图 7(c)所示,LPA算法将原本属于同一社区的节点分到了C₁和C₂两个社区,并将节点a错误地分到了另一个社区C₃,这显然是不合理的.如图 7(d)所示,HANP算法将原本属于同一社区的节点分到了C₁和C₂两个社区.如图 7(e)所示,MB-DSGE算法将原本属于同一社区的节点分到了C₁,C₂和C₃这3个社区,并将节点a错误地分到了另一个社区C₄;同时,将原本属于同一社区的节点分到了C₄和C₅两个社区,得到的社区与真实社区相差较大.如图 7(f)所示,gCluSkeleton算法将节点a错误地分到了另一个社区C₂.如图 7(g)所示,CoDDA算法得到的社区结果与真实社区完全一致.实验结果证实了本文提出的CoDDA算法的优势.

选择Football数据集的3个真实社区(社区结构最明显)的节点,使用比较算法和CoDDA算法得到的社区如图 8所示.因为社区结构明显,所以使用HANP算法、MB-DSGE算法、gCluSkeleton算法和CoDDA算法得到的社区与真实社区是一致的.但是,即使对于社区结构明显的节点,Radicchi算法仍将3个社区识别为同一个社区,LPA算法也将其中2个社区识别为同一个社区,这显然是不合理的.本文提出的CoDDA算法得到的结果与真实社区是一致的,这验证了CoDDA算法的准确性.

实验结果显示:不管是Strike数据集,还是社区结构明显的Football数据集,本文提出的CoDDA算法都能够得到准确的社区,证实了CoDDA算法优势的稳定性.另一方面,比较算法使用不同的数据集得到的社区存在不同程度的不稳定性.

5.4.3 参数实验

本节分析跳数阈值S、衰减因子σ和深度稀疏自动编码器的层数对实验结果的影响.比较CoDDA算法得到的社区与直接使用k-均值算法对相似度矩阵聚类得到的社区,来展示CoDDA算法中的基于深度稀疏自动编码器的特征提取操作可以有效提高社区结果的准确性.

(1) 跳数阈值S

针对Strike数据集,设置深度稀疏自动编码器各层的节点数是[24-16],衰减因子σ=0.5,分析不同跳数阈值S对NMI的影响.根据图 9所示,在跳数阈值S的不同取值下,对比直接使用k-均值算法对相似度矩阵进行聚类,CoDDA算法得到的结果社区都更为准确.实验结果显示,CoDDA算法基于深度稀疏自动编码器进行特征提取的操作可以很好地提高社区结果的准确性.

同时,随着跳数阈值S的增加,NMI呈现先增加后减小的趋势.这样的实验结果说明:考虑不直接相连但在一定跳数内可达的节点对的相似度,可以有效地反映每个节点局部的结构信息.但是如果跳数阈值过大,距离过远不在相同社区的节点之间也增加了一定的相似度值,这不利于社区边界的识别,使得社区准确性降低.对于小规模数据集Strike和Football,分别选择小的跳数阈值3-跳和1-跳;对于大规模数据集LiveJournal和Orkut,选择稍大的跳数阈值8-跳,以达到最优的结果.

(2) 衰减因子σ

针对Strike数据集,设置深度稀疏自动编码器每层的节点数[24-16],跳数阈值S=3,分析不同衰减因子σ的取值对实验结果的影响.根据图 10所示,相比直接使用k-均值算法对相似度矩阵的聚类操作,CoDDA算法在不同衰减因子取值下得到的结果社区更精确.从实验的角度展示了CoDDA算法中基于深度稀疏自动编码器进行特征提取的操作在社区准确性方面的贡献.

同时,随着衰减因子的增加,NMI整体呈现先增加后减小的趋势.因为衰减因子控制相似度随着跳数的增加的衰减程度,所以对于小规模数据集Strike和Football,选择稍大的衰减因子σ=0.5,以避免衰减因子过大时对社区边界产生的模糊作用;对于大规模数据集LiveJournal和Orkut,选择小的衰减因子σ=0.1,增强节点的局部特征,以达到最优的结果.

(3) 深度稀疏自动编码器的层数

针对LiveJournal数据集,设置跳数阈值S=8,衰减因子σ=0.1,分析不同层数的深度稀疏自动编码器对实验结果的影响,其中,1~6层对应的节点数分别为6 000,4 096,2 048,1 024,512和256.

根据图 11所示,CoDDA算法在3层深度稀疏自动编码器(每层节点是6000-4096-2048) 的设置下性能最好.随着深度稀疏自动编码器层数的增加,社区准确度先增加后减小.实验结果显示:深度稀疏自动编码器这一无监督深度学习方法可以提取出使社区结构更加明显的特征信息,提高结果社区的准确性.但是如果层数过高,会过滤掉一些特征信息,降低结果社区的准确性.因此,对于小规模数据集Strike和Football,分别选择稍低的训练层数[24-16]和[180-128];对于大规模数据集LiveJournal和Orkut,分别选择稍大的训练层数[6000-4096]和[30692-16384],以提供更准确的特征提取结果.

6 结束语

本文提出了基于深度稀疏自动编码器的社区发现算法CoDDA,尝试使用无监督深度学习的方法,根据网络拓扑结构,提高使用例如k-均值等经典的聚类方法进行社区发现的准确性.首先提出了基于s-跳数的邻接矩阵预处理方法,得到能够更好地反映节点局部信息的相似度矩阵;然后构建深度稀疏自动编码器,对相似度矩阵进行深度特征提取;最后,使用k-均值方法聚类得到社区.实验结果显示:与典型的社区发现算法相比,本文提出的CoDDA算法可以得到更准确的社区结构.并且,与直接使用高维相似度矩阵的k-均值方法相比,CoDDA 算法得到的社区结果更为准确.