基于网络嵌入的异质网络重叠社区发现算法

赵宇红，韩丽文

(内蒙古科技大学 信息工程学院，内蒙古 包头 014010) E-mail：zhaoyuhong35@163.com

1 引 言

真实世界中存在着各种各样的网络，这些网络中的实体可以抽象为节点，而实体间的联系可以抽象为边.为了挖掘这些节点和边的丰富信息，社区发现研究随之而生.社区发现，是指将网络中相似性高的节点划分到个同一社区中，使得社区内节点联系强于社区间联系.社区发现可以为个性化服务、信息推送、疾病传播中断、信息检索等提供数据.2009年之前对于社区发现的研究都集中在同质网络，即将所有的节点和边都看作是同一种.但是现实中的网络大多是异质的，即网络中有多种类型的节点和边，异质信息网络[1]包含更多的信息和更丰富的语义.另一方面，社区具有重叠性是真实社区的一个显著特征，某些节点并不仅存在于单一社区，可能同时属于多个社区，这些节点被称为重叠节点，它们所属的社区被称为重叠社区.对异质网络进行重叠社区发现，能够更加准确的描述网络真实的结构信息，因此研究异质网络重叠社区具有突出的现实意义.

随着社区发现的概念被提出，学者们相继提出了很多社区发现算法，如基于分裂的算法，基于派系过滤的算法，基于局部扩展的算法，基于标签传播的算法等.其中标签传播算法因接近线性的时间复杂度且不需要提前指定社区的个数而被广泛的应用于大规模网络的社区划分.扩展标签传播算法SLPA[2](Speaker-listener Label Propagation Algorithm)通过定义节点标签序列来存储节点历史标签信息，可以用于重叠社区的发现.但是SLPA算法忽略了网络中节点和链接的多样性，所以不适宜直接用于异质网络社区发现，且算法在标签传播过程中心节点的随机选取方法，造成了社区发现的结果不稳定.

元路径[3]是可以用来捕获异质网络丰富语义信息的独特属性.基于元路径的相似性度量是异质网络中相似性度量的一个重要方法，如PathSim算法、HeteSim算法和AvgSim算法等.但这些方法仅关注了路径中所包含的节点，并没有考虑是否覆盖了网络中所有类型的节点，这将降低相似性的度量精度，进而影响社区划分的质量.基于元路径的网络嵌入学习，可以深度学习、训练以获得更精确的相似性度量，也大大降低元路径对模型限制的程度.

在对现有异质网络社区发现算法的学习及问题分析的基础上，为解决上述问题，本文结合异质网络嵌入模型和节点排序方法对SLPA算法进行改进，在异质网络重叠社区下提出了一种基于网络嵌入模型的标签传播算法(Network Embedding-based Lable Propagation Algorithm，NELPA).该算法首先用节点排序方法来确定标签传播过程中心节点更新的顺序，然后通过结合元路径和Skip-gram模型，得到任意类型节点对间的相似性值，以该相似性值对标签传播进行指导，最终完成社区发现.

本文的贡献归结如下：

1)在异质网络中提出一种基于网络嵌入的相似性度量方法，该方法在构建元路径集合并学习元路径权重后，通过对不同元路径下的相似性度量进行加权融合.方法充分考虑了节点类型、节点关联及元路径所表达的不同语义，提高了节点相似性准确率；

2)提出了一种基于邻居节点影响力的节点排序方法SAIN(Sorting Algorithm based on the Influence of Neighbor-nodes)，通过引入节点相似性来改进LeaderRank算法，提升了排序算法的有效性；

3)将异质网络嵌入学习所获取的的节点相似性及节点排序SAIN方法，分别用于标签传播的判定依据及中心节点更新策略，克服了SLPA算法的局限性，提出了一种可用于异质网络重叠社区发现算法NELPA.

2 相关知识介绍

2.1 SLPA算法

SLPA算法通过定义节点标签列表，使节点可以保留历史标签信息，从而可用于重叠社区发现.该算法描述如下：

1)为每一个节点的标签列表初始化一个唯一的标签；

2)随机选择一个节点作为中心节点listener，该节点的邻居节点就为speaker；每一个speaker将统计自己的标签列表中各标签出现的次数，将出现次数最多的那个标签传递给listener；Listener将统计所有speaker传递过来的标签个数，将出现次数最多的那个标签加入到它的标签列表中.重复该过程直到所有的节点都更新完成；

3)重复上述过程，直到达到最大迭代次数，最后，根据阈值和标签信息将具有相同标签的节点划分到同一社区.

SLPA算法作为经典的标签传播算法LPA的改进版，继承了算法的效率及有效性，但仍存在如下问题：

1)算法假定网络中所有的节点和边都是一种类型，不适合直接应用于异质网络中；

2)随机选择listener，会造成每一次标签传播过程中节点更新顺序不同，影响算法的稳定性；

3)在listener选择由speaker传递过来的标签时，仅以标签出现次数作为相似性度量指标使得传播的准确性较低.

2.2 网络嵌入模型

网络嵌入旨在用低维的向量表示网络的结构或内容，用低维的连续特征表示原有的高维离散特征，不仅能获取数据之间的相似性而且能够缓解数据的稀疏性.并且由于低维的向量容易被机器学习算法处理，被有效的运用到社区发现领域.

DeepWalk是第一个被用于社区发现领域的网络嵌入模型，其主要思想是利用自然语言处理中的Skip-gram模型[4]来进行网络中节点的向量表示.Node2vec模型[5]改进了DeepWalk节点游走的方式，将广度优先搜索和深度优先搜索引入到随机游走序列生成过程中去，能够更好地反映网络结构.以上几种模型都是用于同质网络的嵌入模型.Dong Y[6]提出的metapath2vec和metapath2vec++模型通过基于元路径的随机游走得到异质网络节点序列，然后基于Skip-gram模型进行节点嵌入.HIN2Vec模型[7]的核心是一个神经网络模型，不仅能学习节点的嵌入向量，还可以学习元路径的嵌入向量.AttrHIN2Vec模型[8]利用基于元路径随机游走的节点属性信息和权重信息来捕获大规模异质网络中的潜在特征向量.张等人[9]考虑异质网络自身的聚类结果，利用随机梯度下降算法学习异质网络节点的低维嵌入表示.CNE[10]算法通过结合节点嵌入和社区嵌入，把社区嵌入表示为低维空间中的高斯分布，从而获得融合结构信息和属性信息的节点表示.

3 NELPA算法

3.1 相关概念

定义1.异质信息网络.对于一个信息网络G=(V，E，T，R)，其中V表示网络中节点的集合，E表示边集合，T是节点类型集合，R是边类型集合.当网络中的节点类型数量|T|>1或边类型数量|R|>1时，此时的信息网络称为异质信息网络.

定义2.网络模式.网络模式是带有对象类型映射τ：V→T和链接映射φ：E→R的异质网络G=(V，E，T，R)的元模板，记为TG=(T，R).

定义4.网络嵌入.通过将一个节点嵌入到一个新的嵌入空间中，使得相似的节点在嵌入空间中的距离相近，节点在嵌入空间中的向量表示就为该节点的嵌入向量.

3.2 NELPA算法的基本思想

本文提出的基于异质网络嵌入模型的标签传播算法NELPA，通过改进传统SLPA算法的中心节点更新方式，融合网络嵌入模型中多条元路径对应的节点相似性并将其运用到标签传播过程中，从而提升算法的稳定性和准确性，完成异质网络重叠社区发现.该算法主要包含两个部分：网络嵌入模块和NELPA模块.本文的算法框架如图1所示.

图1 NELPA算法框架图Fig.1 NELPA algorithm frame diagram

3.3 基于网络嵌入模型的节点相似性度量

该模块首先构建元路径集合，然后进行元路径权重学习，通过多条元路径的遍历得到节点序列，应用Skip-gram模型进行训练得到不同元路径下节点相似性，并对同一节点对间的相似性进行加权融合得到最终的节点相似性.

3.3.1 构建元路径集合

元路径是异质网络中节点关联的路径，能丰富的表达对象间的语义信息.不同元路径表达了不同的含义和不同的链接网络，也就导致网络分析结果的不同.为了更准确的度量节点相似性，本文采用多条元路径对网络进行遍历.通过给不同元路径赋予不同的权重，来表明不同元路径对网络嵌入表征学习的不同重要程度.

在构建元路径集合时，给定网络模式、源类型对象和目标类型对象后可构建出很多不同长度的元路径，但是绝大多数的元路径没有实际的语义信息，如果考虑全部的元路径会增加计算量和计算时间而且由于较长的元路径会降低相似性的精度.所以为了保证效率的同时诠释网络丰富且真实的信息，我们在设定元路径集合时，要保证能够覆盖所有类型的节点，介于上述，本文将元路径长度l设为2～5.从而构建元路径集合P={p1，p2，…，pr}，其中p为元路径，r为元路径条数.

3.3.2 基于边类型概率计算元路径权重

现有的确定元路径权重的方法大多是基于元路径实例数这一指标的.在大型网络中，各类型节点间的连边数量差别很大.如在DBLP数据集中，每一篇论文具有的关键词的数目远远超过论文作者数和论文所投稿的会议/期刊数目，即论文与关键字间的连边数目远远大于与其它类型节点的连边数，包含论文-关键字这种连边的元路径数目也远多于没有包含这类型连边的元路径.如果以元路径实例数作为元路径权重的一个指标，会导致包含这种极大数目边类型的元路径的权重远远超过其它元路径.为了消解这种极大边类型对元路径权重的过度影响，本文定义了边类型概率，如第k条元路径边类型概率指标Fk如公式(1)所示：

(1)

其中，ng表示第g种连边的数量，|R|为网络中边类型数，s为第k条元路径所包含的连边种类数.

第k条元路径的权重θpk定义如公式(2)所示：

(2)

其中，mpk是第k条元路径对应的路径实例数，lpk是第k条元路径的长度.由式(2)可以看出，基于边类型概率的元路径权重不仅考虑路径的数量，而且考虑组成每条路径的各段边的类型.

元路径权重归一化如公式(3)所示：

(3)

利用公式(3)对元路径集合P={p1，p2，…，pr}进行权重学习，构建相对应的元路径权重集合Wp={Wp1，Wp2，…，Wpr}，且Wp1+Wp2+…+Wpr=1.

3.3.3 异质信息网络的节点相似性

Skip-gram是一个最初应用在自然语言处理中的简单三层神经网络模型，模型基于输入的中心词来预测上下文单词出现的概率，结构如图2(b)所示.

图2 基于Skip-gram模型的相似性计算Fig.2 Similarity calculation based on skip-gram model

输入层输入中心词的向量表示，通过设置窗口大小来指定中心词的上下文词汇出现的最大数.如给定窗口大小为m，那么会选择中心词前后各m个词为中心词的上下文词汇.然后隐藏层将执行其权重矩阵和中心词向量的点积运算，点积运算的结果是每个输入词的嵌入词向量.输出层是一个softmax回归分类器，将计算其权重矩阵和输入词的嵌入词向量的点积，然后用softmax激活函数计算在给定上下文的情况下每一个词是输出单词的概率，即中心词与上下文单词共现的概率.

将Skip-gram模型应用到社会网络分析中，如何将异质网络结构转化成类似于语料库中连续的单词，本文基于给定的多条元路径对异质网络进行遍历，从而来得到异质网络节点序列.以图2(a)为例，在DBLP数据集中给定元路径APTPA.假设当前节点是A类型的a1节点，那么下一步将遍历寻找a1所有邻居中的P类型节点，直到找到邻居中所有的P类型节点后，这些P类型节点再继续寻找它们的邻居节点中所有T类型节点，如此反复迭代，直到遍历完整个网络.

我们将基于元路径遍历得到的节点序列类比为自然语言处理中的语料库文本，其中每一个节点都看作是一个词，给定窗口大小即确定了中心节点的邻居范围，最终模型输出的概率即为中心节点vi与网络中任意节点vj在第k条元路径下的相似性概率值Spk(vi，vj)，其表述如公式(4)所示：

(4)

其中，Xvi表示节点vi的嵌入向量，·表示两节点间嵌入向量的点积运算，点积运算值越大，则两节点间的相似性就越大.为了保证输出值的非负性，且将其映射为0-1之间的数值，使用以e为底的指数函数.

3.3.4 基于元路径权重融合的节点相似性

此阶段基于元路径权重集合Wp={Wp1，Wp2，…，Wpr}对节点相似性进行加权融合.将不同元路径遍历得到的不同节点序列输入到Skip-gram模型进行训练得到的同一节点对间的相似性概率是不同的，基于任意一条元路径pk得到的节点对相似性Spk(vi，vj)缺失其它元路径的语义信息.因此，对不同元路径下相同节点间的相似性值进行加权融合可以得到更加准确的相似性值.本文提出了节点相似性融合方法，其表述如公式(5)所示：

(5)

其中，r为元路径条数.

3.4 NELPA算法

3.4.1 基于邻居节点影响力的节点排序算法SAIN

网络中节点的重要性是不同的，重要节点相较于其他节点更能影响网络的布局，能更大程度影响网络的流通性.现有的节点排序算法有很多，如度中心性、介数中心性、接近中心性、PageRank和LeaderRank[11]等.LeaderRank算法通过加入一个背景节点vg，得到一个与网络中所有的节点双向连接的强连通网络，该算法在衡量社会网络中节点的影响力等方面有着较好的表现.其表示如公式(6)所示：

(6)

(7)

其中，αi为节点vi的邻居节点，SAIN值越大节点重要性就越大，将SAIN值进行降序排列，得到节点更新顺序.

3.4.2 基于SLPA的改进的社区发现算法NELPA

1)为所有节点的标签列表初始化一个唯一的标签；

2)由公式(7)对网络中所有节点进行排序，选择当前未处理的SAIN值最大的节点为listener，其所有一阶邻居节点为speaker.Speaker将统计标签列表中各标签的个数，将个数最多的那个标签传递给listener.Listener将对比自己与每个speaker的相似性值Sim(vi，vj)，选择值最大的那个speaker所对应的标签加入标签列表中.若最大值speaker不止一个，那么将所有最大值speaker所对应的标签出现次数最多的一个加入到标签列表中.

3)重复第2步，直到达到最大迭代次数T.根据阈值和标签信息完成社区划分.

达到最大迭代次数后，每个节点都有T个标签，每种标签的概率反映了节点所属社区的关联强度，为了确定一个节点是否最终属于一个社区，要执行阈值化过程.如果某一标签的概率小于给定的阈值r，则把该类标签从节点序列中删除.阈值化后，具有相同标签的节点被分到一组，形成一个社区.如果一个节点包含多个标签，那么该节点属于多个社区，是重叠节点.

NELPA算法具体描述如下：

算法1.NELPA(T，r)

[n，Nodes]=loadnetwork(G)；

FORi=1：nDO

Nodes(i).Mem=i

END FOR

FORt=1：TDO

FORi=1：nDO

Listener=max(sorted(SAIN))

Speakers=Listener.getNbs()；

FORj=1：Speakers.lenDO

LableList(j)=Speakers(j).frequent()；

IFlen(MaxSim(LableList))=1：

w=Listener.MaxSim(LableList)；

ELSE

w=Listener.MaxSim(LableList).frequent()

END IF

Listener.Mem.add(w)

END FOR

END FOR

END FOR

FORi=1：nDO

Remove Nodes(i)lables seen with probability

END FOR

4 实验与分析

为验证本文提出的基于边类型概率的元路径权重确定方法的合理性、基于邻居节点影响力的节点排序算法SAIN的有效性和异质网络社区发现算法NELPA的社区聚类效果，进行了以下的实验.

4.1 数据集

本文数据集选取2个真实的异质网络，其详述如下：

1)DBLP数据集：本文实验采用DBLP数据集的子网络构建异质网络，包含作者(Author，A)、会议(Conference，C)、论文(Paper，P)和术语(Term，T)4种节点.

2)LastFM数据集：该数据集在fm在线音乐系统截取，包含音乐家(Artist，A)、用户(User，U)、音乐标签(Tag，T)3种节点.

2个数据集参数如表1所示.

表1 数据集参数Table 1 Data set parameter

4.2 评价指标

社区发现经典的评价指标模块度Q常被用来评价社区划分的好坏，由于本文算法涉及到重叠社区的发现，所以选取衡量重叠社区划分质量的扩展模块度EQ[12]作为评价指标.其表示如公式(8)所示：

(8)

其中，m是网络中连边总数，Qi、Qj为节点vi、vj所属的社区个数，Aij为网络邻接矩阵中的元素，ki、kj分别为节点vi、vj的度，Cy为第y个社区包含的节点集.EQ值取在0-1之内，值越大，意味着社区划分的结构性越强.

4.3 结果与分析

4.3.1 元路径选择与权重确定

为尽可能得到每个节点与其它所有节点间的的相似性，在选择元路径时，要能够涵盖异质网络中所有的节点类型.所以实验中，综合考虑节点类型和元路径语义及长度后，对于DBLP数据集指定APA、APAPA、APCPA、APTPA这4条元路径，LastFM数据集指定TAT、TUT、UAU、UTU这4条元路径.由给定的元路径集合对网络遍历之后，得到每一条元路径对应的实例数.计算得到边类型概率值后，再计算每条元路径的归一化权重值如表2中Wpk所示，表2中θ是只由元路径实例数和路径长度计算得到的每一条元路径所对应的权重值.

表2 元路径权重分配Table 2 Metapath weight allocation

在DBLP数据集中，对比每条元路径所对应的Wpk值和θ值可以发现元路径权重变化最明显的是APCPA和APTPA，这两条元路径所包含的不同边类型是P-T和P-C，P-T边的数量约是P-C边的8倍.APCPA的权重Wpk相较于θ提高了41.68%，而APTPA的权重Wpk相较于θ降低了45.44%.实际上，由期刊相连的两个作者的关系比那些通过术语相连的关系更可信，因为许多术语能够在不同的研究领域中使用，而作者通常更关注有限的研究主题.实验中的这两组数据能够明显的说明，本文提出的关于元路径权重确定的方法能够更好的反映实际的元路径权重.

而在LastFM数据集中，对比每条元路径所对应的Wpk值和θ值可以发现无明显变化，这是因为该数据集中各类型边数差距不是很大，导致边类型对元路径权重的影响很小.

由实验中Fk指标对两个数据集中元路径权重的影响可以得出以下结论：本文提出的边类型概率指标能够更好的优化元路径权重，由本文方法得到的元路径权重相较与传统只由路径数和路径长度确定的元路径权重更接近对现实世界的理解.

4.3.2 节点排序算法验证

在该部分实验中，用PageRank算法、LeaderRank算法和本文提出的SAIN算法对DBLP数据集中的会议/期刊类节点进行排序，取排序结果前10的节点，排序结果如表3所示.为了对排序算法的结果进行初步评估，我们在计算机科学知识发现网上(AMine)根据CCF Level对DBLP数据集中的会议/期刊进行分类，A类会议的档次高于B类会议.发现3种算法给出的排名靠前的会议基本为A类会议，靠后的是B类会议.但是数据集中的CVPR和WWW这两个A类会议并没有排在前10，而一些B类会议却排在了前10.这是因为排名算法更多考虑的是网络的拓扑结构(节点的连边情况)而忽略了会议的影响因子，即排序算法更多关注的是在会议上所发表的论文数目，而并非是论文被引数所占论文的比例.

表3 DBLP数据集会议/期刊类节点排序Table 3 DBLP data set meeting/journal node sorting

本文采用传染病SIR模型[13]来评估排序算法的好坏，选定初始感染节点，拟合病毒传播过程，以一段时间后感染节点的数目衡量初始感染节点的传播影响力.若一个排序算法的结果使得网络传播速度快于其它算法，说明由该排序算法得到的排序结果使得节点具有好的传播影响力，即可以说明该排序算优于其它排序算法.图3显示了以每种排序算法排序前10的节点为初始感染源进行SIR传播的过程，其中时间步长(t)为横坐标，累计感染数(N)为纵坐标.由图3可见，本文提出的SAIN算法较PageRank算法和LeaderRank算法有着更快的增长速度和更高的被感染的饱和人数，说明由SAIN排序算法得到的重要节点对整个网络进行传播时，其速度更快范围更广.即在识别高影响力节点方面，SAIN较PageRank算法和LeaderRank算法更有效.

图3 SAIN与LeaderRank、PageRank算法对比验证Fig.3 Comparison and verification of SAIN，LeaderRank and PageRank algorithms

4.3.3 社区发现准确性验证

为了验证NELPA算法的准确性，本文选择原始SLPA算法以及近几年效果较好的一些异质网络社区发现算法作为对比算法.表4所示为不同算法在数据集DBLP和LastFM上得到的社区聚类效果，用EQ进行评价.

表4 NELPA算法和对比算法在不同数据集的EQ值比较Table 4 Comparison of EQ values between NELPA algorithm and comparison algorithm in different data sets

各算法参数设置如下：SLPA算法实验最大迭代次数T设为100，标签阈值r设为0.35.HCD_all[14]算法在两个数据集上选择表2给出的所有元路径进行元路径融合实验.HIN2Vec算法设定以每个节点为起始游走节点的游走步长为1280，向量维度为128.Metapath2vec算法在DBLP数据集上指定单条元路径APCPA，LastFM数据集上指定UTU，以每个节点为起始节点游走次数为1000次，随机游走序列长度为100，窗口大小为7，向量维度为128.本文NELPA算法使用表2列出的所有元路径，窗口大小为7，向量维度为128.

由表4可知，本文提出的NELPA算法的EQ值高于其它算法.这是因为NELPA算法不仅在标签传播算法中通过融合多条具有不同权重的元路径来体现网络的异质性，而且以节点相似性和标签数同时作为标签传播的依据提升了算法的准确性.因此，本文提出的NELPA算法对不同类型的异质网络具有良好的表征学习能力，可有效的提高异质网络重叠社区发现的模块度，得到的社区聚类效果更好.

5 总结与展望

本文研究了异质信息网络中的重叠社区发现问题，提出了一种基于网络嵌入的标签传播算法NELPA.首先，考虑了不同的元路径的权重，通过构建网络嵌入模型学习并完成了单条元路径下节点相似性度量并进行了多路径加权融合，提升了节点相似性准确度，并用该相似性来指导标签传播过程.其次，提出一种新的节点排序方法SAIN，并用于节点更新顺序策略，加速了标签传播速率且提高了传播的稳定性，提升了社区发现的准确性.实验结果表明，本算法对不同的网络具有良好的表征学习能力，可有效的应用于网络社区发现领域.但是，NELPA只是基于静态网络的，现实中的网络是动态变化的，所以，未来可以进一步考虑时间因素，用于动态异质网络社区发现.