王本钰，顾益军，彭舒凡

中国人民公安大学 信息网络安全学院，北京100032

近年来，随着互联网技术的高速发展，社交网络的规模不断增加，社交网络分析任务也变得愈发重要，例如节点分类、链路预测等。节点分类任务可以对网络中的节点进行合理的划分，在现实生活中具有重要的应用价值，例如在社交平台中，通过用户的类别标签向用户推荐好友；在智能广告中，向可能感兴趣的用户精准投放广告。链路预测任务可以有效分析网络拓扑结构，预测网络丢失的边或者未来可能出现的边，在社交网络上应用前景广阔，例如社交平台用户拓展、电商营销等。各种各样新颖的技术被用在社交网络分析中来挖掘用户潜在属性，网络嵌入[1]就是其中一种。

网络嵌入旨在将高维稀疏数据映射到低维稠密向量空间，提取数据低维特征，以便于基于向量的机器学习方法进行下游网络分析任务。目前主流的网络嵌入方法可以分为基于网络结构信息的网络嵌入方法和基于网络结构信息和属性信息相结合的网络嵌入方法。

基于网络结构信息的网络嵌入方法利用网络拓扑结构捕获节点低阶甚至高阶相似性，进而获得网络节点的低维特征表示。Perozzi 等提出DeepWalk算法[2]，将自然语言处理（natural language processing，NLP）中word2vec模型[3]运用到算法生成的随机游走序列上，获得基于节点上下文结构的嵌入表示。Tang等提出大规模信息网络嵌入算法（large-scale information network embedding，LINE）[4]，结合网络一阶和二阶结构信息，最小化KL 距离（Kullback-Leibler divergence）获得网络嵌入结果。Cao等提出GraRep算法[5]，将LINE 算法的一阶和二阶结构信息推广到了高阶结构信息。Grover等提出node2vec算法[6]，结合深度优先搜索和广度优先搜索优化了DeepWalk中随机游走序列生成方式。Cao 等提出学习图表示的深度神经网络算法（deep neural networks for learning graph representations，DNGR）[7]，通过随机冲浪的方式获得节点高阶结构信息表示，然后通过栈式降噪自动编码器进行网络嵌入。Wang等提出深层结构网络嵌入算法（structural deep network embedding，SDNE）[8]，通过深度自动编码器获得网络嵌入结果。Ribeiro等提出struc2vec算法[9]，通过节点空间结构相似性定义节点相似性来获得网络嵌入结果。Wang 等提出Edge2vec 算法[10]，改进基于节点的网络嵌入方法，通过网络中的边来获得网络嵌入结果。由于网络结构信息稀疏，单一利用网络结构信息的网络嵌入方法在大型稀疏网络中实验效果并不是很好。而网络属性信息可以弥补结构信息稀疏的问题，因此近几年，基于网络结构信息和属性信息相结合的网络嵌入方法相继被提出。

基于网络结构信息和属性信息相结合的网络嵌入方法目的是融入属性信息以获得更好的网络嵌入结果。Yang等提出基于丰富文本信息的网络表示学习算法（network representation learning with rich text information，TADW）[11]，首次将文本信息特征引入了网络嵌入，完善了以往仅依靠结构信息的网络嵌入方法。Tu等提出用于关系模型的上下文感知网络嵌入算法（context-aware network embedding for relation modeling，CANE）[12]，认为网络中节点对于不同的邻居节点具有不同的交互关系。该算法首先利用卷积神经网络（convolutional neural network，CNN）对节点信息进行嵌入，之后对于邻居节点进行不同程度的嵌入，有效解决网络传播中“中间人”问题。Huang等提出了加速网络嵌入算法（accelerated attributed network embedding，AANE）[13]，通过联合矩阵分解获得属性网络的嵌入结果。Bandyopadhyay 等提出了基于离群点检测的属性网络嵌入算法（outlier aware network embedding for attributed networks，ONE）[14]，减小异常节点对于属性网络嵌入结果的影响。Hong等提出保留结构和属性信息的深度属性网络嵌入算法（deep attributed network embedding by preserving structure and attribute information，DANE）[15]，利用堆叠去噪自动编码器学习网络高阶结构信息和属性信息。实验证明，该算法取得了良好的效果。Nozza等提出了约束深度属性图嵌入算法（constrained deep attributed graph embedding，CAGE）[16]，利用节点低阶结构信息和属性信息相互制约获得更好的网络嵌入效果。

尽管现有的网络嵌入方法在不同场景下展示了其有效性，但是本文在研究中发现，现有网络嵌入方法应用于社交网络中仍存在以下几个问题：

（1）社交网络高阶结构信息利用不足。高阶结构信息可以充分体现节点间的连通能力，因此多数基于结构的网络嵌入方法都融入了网络高阶结构信息来提高网络嵌入效果。但是这些方法并没有去除环状路径和大度节点的影响，使得各节点与大度节点具有更高的相似性，网络嵌入效果不理想。

（2）未有效处理社交网络属性信息中存在的噪音。节点的属性信息可以弥补网络结构数据稀疏的问题，但是社交网络中节点属性信息大多基于用户随意设定的兴趣爱好，具有很大的主观性和不准确性并且属性网络中具有很多的异常节点。多数基于网络结构信息和属性信息相结合的网络嵌入方法并没有消除属性网络中存在的噪音，在社交网络中实验效果不尽如人意。

为了解决上述问题，本文提出了一种融合节点属性和无环路径的社交网络嵌入方法（social network embedding method combining loop-free path and attributes network embedding，LFNE）。本文的主要贡献有以下几点：

（1）给出计算社交网络节点间六阶内无环路径数量的数学表达式并提出基于节点间无环路径的相似性度量指标（similarity metrics based on loop-free path，SLP），消除环状路径、大度节点的影响，使得相似性指标可以更好地融合社交网络节点间的高阶路径信息，计算结果更加准确。

（2）结合SLP 指标改进社交网络节点属性相似度，充分考虑节点结构信息和属性信息的相关性，降低社交网络中节点属性信息存在的噪音。

（3）将各阶社交网络无环路径结构信息和节点属性信息融合，通过堆叠降噪自动编码器学习节点低维特征表示，不仅可以学习网络中数据分布情况，而且可以获得网络高度非线性特征。公开数据集上的节点分类和链路预测实验结果表示，LFNE算法可以获得更加全面的节点特征向量。

1 相关工作

1.1 网络基础知识

给定一个复杂网络G=(V,E)来表示社交网络，网络中个体的集合用节点集V={1,2,…,N} 来表示，|V(G)|=N，网络中个体的联系用边集E={e=(i,j)|1 ≤i,j≤N，i≠j}来表示，用i-j表示边e=(i,j)。

记网络G的邻接矩阵A∈RN×N，定义为：

记网络G的属性矩阵为W∈RN×F，F代表属性元素的个数。

令S(i)={j|j∈V(i≠j)∧(i,j)∈E}，称S(i)为节点i的邻居节点。

令di=|j|j∈V(i≠j)∧(i,j)∈E|，其中，集合内元素的个数用|*|表示，称di为节点i的度。

1.2 节点结构相似性指标

经典节点结构相似性度量指标主要是基于节点的公共邻居，例如CN 指标（common neighbours index）[17]、Salton指标[18]、HPI指标（hub promoted index）[19]、LHN-I 指标（Leicht-Holme-Newman index）[20]等，此类指标最主要的缺陷是没有关注节点间的高阶结构关系。

基于节点间连通能力的相似性度量指标在考虑了节点低阶结构信息的同时，也融入了节点间高阶结构信息，准确性更高，例如Katz 指标[21]、LP 指标（local path index）[22]、LS指标（local similarity index）[23]。

Katz 指标利用节点各阶连通路径来衡量节点间相似性，Katz 指标对于节点间高阶路径赋予更小的权重，对于节点间的低阶路径赋予更大的权值。在Katz指标的基础上，LP指标、LS指标被提出。

基于节点间连通能力的相似性度量指标虽然将节点的高阶结构信息考虑在内，但是节点各阶路径中存在环状路径，尤其是节点间的高阶路径中存在大量的环状路径，并且大度节点会经常出现在环状路径中，使得各个节点与大度节点具有更高的相似性，导致Katz指标、LP指标、LS指标不能准确衡量节点间连通能力，指标度量性能差。

1.3 无环路径算法

去除节点各阶路径中的环状路径，使得节点连通路径中各个节点互不相同，可以有效降低各个节点对于大度节点的依赖性，因此可以通过节点间无环路径来衡量节点间的连通能力。

Wu等[24]引入一个中间矩阵来计算节点间各阶无环路径数量。对于路径阶数小于等于5的情况，其给出准确的数学表达式。对于路径阶数大于等于6 的情况，由于6阶以上路径的复杂性，Chen等未能给出准确的数学表达式。

给定一个网络G的邻接矩阵A，Ak表示邻接矩阵A的k次幂。Ak给出了网络G中任意节点间各阶路径的数目（包含环状路径）。定义Pk表示网络G中各阶路径中无环路径的数量。

对于网络的一阶路径，即为网络的邻接矩阵，不存在环状路径，因此A1=P1。

对于网络的二阶路径，即为节点间的共同邻居，也不存在环状路径，因此A2=P2。

对于网络的三阶及以上路径，节点间路径中便可能会出现环状路径，为了便于计算三阶及以上节点间无环路径数量，Chen等引入了中间矩阵Qk。Qk表示在k-1 阶无环路径后加上一阶路径组成的k阶路径，定义如式（2）和式（3）所示：

同理，可以求得五阶无环路径数量，定义如下：

2 六阶无环路径算法

Lü等证明了基于节点间连通能力的相似性度量指标中路径的长度与网络节点间平均路径长度呈正相关[25]，因此基于节点间连通能力的相似性度量指标中路径的长度应近似于网络节点间平均路径长度。据数据分析报告，社交平台Twitter 中用户间平均路径长度为4.67，在Facebook 中为4.74，因此当前社交网络中节点平均路径长度近似为5。依据Lü等证明的理论，社交网络中基于节点间连通能力的相似性度量指标的路径长度应取值为5，因此为了使得基于节点间连通能力的相似性度量指标可以更好地融合社交网络节点间的高阶结构信息，需计算节点间六阶（路径长度为5）无环路径数量。然而Chen 等[24]只给出了计算节点间五阶（路径长度为4）内无环路径数量的数学表达式，未能给出计算节点间六阶（路径长度为5）无环路径数量的数学表达式，因此本文给出计算节点间六阶（路径长度为5）无环路径数量的准确数学表达式。

图1 六阶无环路径Fig.1 Loop-free 6-hop paths

3 LFNE算法

为了消除社交网络中环状路径、大度节点对于节点结构相似度的影响，降低网络属性信息存在的噪音，使得网络嵌入方法可以更好地融合社交网络高阶结构信息和属性信息，本文提出一种融合节点属性和无环路径的社交网络嵌入方法LFNE。LFNE主要包括4个步骤：根据基于节点间无环路径的相似性度量指标SLP 计算社交网络节点间的结构相似度生成结构概率矩阵；结合社交网络节点结构相似度计算节点间属性相似度生成属性概率矩阵；构建结构-属性概率矩阵；构建堆叠降噪自动编码器对矩阵进行特征提取，获取网络的低维特征表示。

3.1 节点结构相似性计算

为了使得相似性指标可以更好地融合社交网络高阶结构信息，本文提出了基于节点间无环路径的相似性度量指标SLP，定义如下：

其中，路径长度K由基于区域中心点距离（centers distance of zone，CDZ）[26]的最短路径算法计算网络平均路径长度确定，是节点间k阶无环路径数量，β(k)是减函数。在社交网络中，两个节点直接产生连接或者连通路径越短，则两个节点间的相似度会越高，联系越紧密。SLP指标中相较于高阶的节点路径信息会更多考虑低阶的节点路径信息。因此，引入权重衰减函数，当节点间路径增加时，路径权重会相应减小。本文使用指数函数作为SLP 指标的权重衰减函数，权重衰减函数如式（8）所示：

其中，ω为权重衰减函数因子，ω∈(0,1)。借助权重衰减函数可以使得SLP 指标在融入节点高阶结构信息的同时会更多考虑节点低阶结构信息。

接着，对SLP 指标下节点相似度进行归一化处理，获得节点间结构概率矩阵，节点i和节点j的结构概率定义如下：

3.2 节点属性相似度计算

给定一个网络G的属性网络W∈RN×F，F是属性元素个数。通过余弦相似度公式将属性网络W转换成节点属性概率矩阵C，节点i和节点j的属性概率定义如下：

多数基于网络结构信息和属性信息相结合的网络嵌入方法应用于社交网络中的实验效果并不理想，分析原因是虽然节点的属性信息可以很好地弥补网络结构数据稀疏的问题，但是社交网络中节点属性信息大多基于用户随意设定的兴趣爱好，具有很大的主观性和不准确性，存在噪音，如图2所示。

图2 属性网络噪音示意图Fig.2 Schematic diagram of attribute network noise

节点v1和节点v7在网络结构上相距甚远，在SLP 指标下，两节点的结构相似度为0，节点v7对于节点v1是相对孤立点，但是节点v1和v7的属性信息相似，在先前的网络嵌入模型，没有考虑节点结构信息和属性信息的相关性，会认为这两个节点具有相似的网络嵌入表示。而实际上节点v7对于节点v1而言是属性异常节点，存在属性信息噪音，两节点具有相似的网络嵌入表示可能性相对较小，因此降低节点属性信息中的噪音对于社交网络嵌入具有重要意义。本文结合SLP 指标改进社交网络节点属性相似度计算方法，充分考虑节点结构信息和属性信息的相关性，降低社交网络中节点属性信息存在的噪音，解决大多数模型没有考虑节点结构信息和属性信息相关性的问题。本文改进的属性相似性度量指标定义如下：

其中，α的取值范围在[0,1]之间，用于判断节点j是否为节点i网络平均路径长度内可到达的节点，若节点j不是节点i网络平均路径长度内可以到达的节点，则两个节点的连通性较差，给予两个节点间属性相似度相对更小的权重。通过改进后的节点属性相似度计算方式可以有效降低属性网络中存在的噪音。

对节点属性相似度Bij进行归一化处理，获得节点属性概率矩阵，节点i和j的属性概率定义如下：

3.3 节点结构-属性相似度矩阵

给定一个网络G，节点结构-属性相似度矩阵X∈RN×N定义如下：

其中，λ的取值范围在[0,1]之间。λ用来平衡节点结构相似度和属性相似度对于节点相似度的影响程度。当λ为0时，节点相似度仅受到属性相似度的影响，当λ为1 时，节点相似度仅受到结构相似度的影响。λ的取值越大，节点相似度受结构相似度的影响越大。相应的，λ的取值越小，节点相似度受属性相似度的影响越大。

当获得节点的高维特征表示后，需要通过降维的方式获得低维特征表示，捕获高度非线性的网络结构。本文通过堆叠降噪自动编码器对节点结构-属性概率矩阵进行降维，获得低维特征表示。

3.4 堆叠降噪自动编码器

自动编码器可以高效提取数据特征，已广泛用于多个领域的表示学习任务中。传统自动编码器由输入层、隐藏层、输出层三部分组成。通过编码器将输入层数据映射到隐藏层空间，然后通过解码器将隐藏层空间数据映射成输出层的重构数据，通过减小输入数据和重构数据的误差来达到特征提取的目的。降噪自动编码器是基于传统自动编码器的一个变形。降噪自动编码器通过噪声污染训练数据，并通过训练来预测没有污染的原始数据，可以很好地增强自动编码器的鲁棒性。降噪自动编码器首先将原始输入数据xi∈RN中的一些单元置零加入噪音得到∈RN，然后通过编码器部分将映射到隐藏层空间得到hi∈Rd，之后通过解码器部分将hi映射成重构数据zi∈RN。通过优化度量xi和zi之间的损失函数来训练降噪自动编码器，定义如下：

其中，W和b是编码器的权重矩阵和偏置向量，W′和b′是解码器的权重矩阵和偏置向量。f(·)是激活函数，本文中采用ReLU函数，定义如下：

损失函数采用交叉熵函数，定义如下：

为了获得输入数据更好的低维特征表示，本文使用堆叠降噪自动编码器，构建一个完整的深度降噪自动编码器来学习输入数据的低维特征表示。堆叠降噪自动编码器由若干个降噪自动编码器组成。在堆叠降噪自动编码器的训练过程中，每当训练完一个降噪自动编码器则去除其输出层及相关的参数，将隐藏层作为下一个降噪自动编码器的输入，依次连接训练每一个降噪自动编码器，形成一个堆叠降噪自动编码器。最后一个降噪自动编码器隐藏层表示即为输入数据的低维特征表示。

3.5 算法流程

融合节点属性和无环路径的社交网络嵌入方法LFNE具体方法流程见算法1。

算法1LFNE算法

输入：社交网络G，网络邻接矩阵A，节点属性矩阵W以及设置相关参数。

输出：低维特征矩阵Z。

首先，LFNE 算法的输入部分包括三部分：社交网络G，网络邻接矩阵A，节点属性矩阵W；计算结构-属性概率转移矩阵所需参数，包括路径权重参数β，节点间路径长度k，属性相似度权重参数α，结构-属性平衡参数λ；堆叠降噪自动编码器特征提取阶段所需参数，包括堆叠降噪自动编码器个数n，维度d，训练次数m。

算法1的第1行～第6行，首先通过矩阵A得到节点间基于无环路径的相似度Sslp，捕获社交网络高阶结构相似性，然后生成矩阵H。接下来通过矩阵W和Sslp得到节点间属性相似度B，充分利用社交网络结构信息和属性信息的相关性，然后生成矩阵M。最后，通过矩阵H和M得到矩阵X。

算法1 的第7 行～第11 行，构建了一个堆叠降噪自动编码器，输入矩阵X，学习X的低维特征表示，循环执行m次，最终得到X的低维特征矩阵Z。

3.6 时间复杂度

LFNE 算法中计算社交网络节点间的结构相似度需要通过无环路径算法计算节点间无环路径数量。在计算k阶无环路径数量时需知道k-1 阶无环路径的数量来根据式（5）计算Qk。因此计算k阶无环路径时需要计算k阶前每一阶无环路径的数量。Qk的计算是一个矩阵相乘的计算，目前计算两个大小为n×n的矩阵相乘的时间复杂度为O(n2.372)[27]，因此计算社交网络节点间的结构相似度的总时间复杂度为O((1+2+…+k)N2.372)=O(0.5(1+k)kN2.372)≈O(k2N2.372)，N为网络中节点数量。计算节点间属性相似度和构建结构-属性概率矩阵的时间复杂度为O(N)。对于构建堆叠降噪自动编码器获得网络的低维特征表示部分，时间复杂度为O(d|E|)，其中d为节点特征向量维度，|E|为网络中边的数量。由于复杂网络通常是稀疏的，|E|≪N2.372，LFNE 算法的时间复杂度为O(k2N2.372)。

4 实验

为测试本文算法的可行性与有效性，将LFNE算法在3 个真实社交网络数据集进行性能评价。首先介绍实验数据集、对比算法、实验评价指标和实验环境，之后进行参数分析实验，最后进行节点分类实验和链路预测实验。

4.1 实验数据集

实验中所用数据集具体信息如表1所示。

表1 真实网络数据集基本信息Table 1 Basic information of real network datasets

BlogCatalog[13]：一个在线博客社交网络。网络由5 196名博主和博主间关注产生的交互关系组成。博主发布的博客关键词作为博主的属性信息。根据博主的兴趣爱好，将博主分为6组。

Flickr[28]：一个在线图片分享网站。该网络是一个由7 575 名用户和用户间共享照片产生的交互关系组成的社交网络。用户发布的图像标签信息和用户的个人爱好作为用户的属性信息。根据加入的预定义组，将用户分为9组。

Email[28]：欧洲研究机构成员电子邮件通信网络。该网络由1 005 名研究人员和研究人员间通过电子邮件产生的交互组成的社交网络。研究人员的属性信息对应所属部门。

4.2 对比算法

将LFNE 算法与近几年代表性算法进行对比实验，其中DeepWalk[2]、node2vec[6]、DNGR[7]、SDNE[8]是基于网络结构信息的网络嵌入方法，TADW[11]、DANE[15]是基于网络结构信息和属性信息相结合的网络嵌入方法。

DeepWalk：通过随机游走方式获得节点的序列表示，然后通过word2vec模型[3]获得基于节点上下文结构的嵌入表示。

node2vec：结合深度优先搜索和广度优先搜索优化了随机游走序列生成方式，然后通过最大化保留节点网络邻域的可能性学习节点表示。

DNGR：通过随机冲浪获得节点高阶结构信息，然后通过栈式降噪自动编码器进行网络嵌入。

SDNE：通过深度自动编码器捕捉高度非线性的网络结构，然后通过联合优化节点一阶和二阶相似性保留网络局部和全局结构特征来获得节点的嵌入结果。

TADW：通过矩阵分解学习网络结构和属性信息获得节点的低维特征表示。

DANE：通过个性化随机游走模型学习网络高阶结构信息和属性信息获得全局信息矩阵，然后通过深度自动编码器学习节点全局信息获得节点的嵌入表示。

4.3 实验评价指标和实验环境

本文中使用的实验评价指标分别是Micro-F1[29]、Macro-F1[29]和AUC（area under the curve）[30]。Micro-F1 指标表示对于数据集建立全局混淆矩阵，计算相应的指标。Macro-F1指标表示对于数据集各个标签建立混淆矩阵，计算各标签下的Micro-F1 指标的算数平均值。Micro-F1和Macro-F1指标常用作评价节点分类任务效果，值越高，实验效果越好。Micro-F1和Macro-F1指标定义如下：

其中，P表示精确率，R表示召回率，M是标签数量。TPi表示将实际标签为i的样本预测为标签i的样本数量；FPi表示将实际标签为非i的样本预测为标签i的样本数量；FNi表示将实际标签为i的样本预测为非i标签的样本数量。

AUC指标表示ROC（receiver operating characteristic curve）曲线下所围成的面积大小，常用作链路预测实验的评价指标。在链路预测实验中体现为每次从网络中不存在边的集合和测试集边的集合中各自随机选择一条边进行比较，后者比前者分数高的概率。定义如下：

其中，n表示比较的次数，n′表示测试集中边链路预测值高于网络中不存在边的次数，n″表示测试集中边链路预测值等于不存在边的次数。一般认为，AUC的值越高，算法链路预测效果越好。

本文的实验环境为：处理器为Intel®CoreTMi7-8750H CPU@2.20 GHz，内存为16 GB，操作系统为Windows 10 64 bit。

4.4 参数设置

本文算法使用堆叠降噪自动编码器学习节点低维特征表示。为了使堆叠自动降噪自动编码器可以更好地获取节点低维特征表示，对于不同数据集采用不同的自动编码器结构。各数据集对应的自动编码器结构如表2所示。

表2 不同数据集下堆叠降噪自动编码器结构Table 2 Structure of stacked denoising autoencoder under different datasets

实验中采用的对比算法输出的节点向量维度和本文算法输出的向量维度一致。本文算法中SLP 指标参数ω参照文献[24]取值为0.3。堆叠降噪自动编码器模型使用Adam优化器进行训练，迭代次数设置为500，学习率为0.002。本文中需要被讨论的参数是节点间路径长度k、属性相似度权重参数α和结构-属性平衡参数λ。

节点间路径长度k体现了节点间的连通性，节点间路径长度过低会使得算法仅考虑节点局部结构信息，不能充分利用网络结构信息，导致节点相似度衡量不准确。而节点间路径长度过高会使得节点间连通路径间存在大量结构噪音信息。因此，确定合理的节点间路径长度，对于衡量节点间相似度至关重要。为充分体现节点间路径长度对于LFNE 算法的影响，实验中节点间路径长度k取值为1 至10，步长为1。六阶内节点间无环路径数量采用本文算法进行计算，六阶以上节点间无环路径数量采用文献[24]中的计算方法进行近似计算。节点间路径长度k影响实验中采用BlogCatalog、Flickr、Email 三个数据集进行链路预测任务，评价指标是AUC。实验中随机选取10%的连接数据和未连接数据作为测试，10%的连接数据作为验证，其余数据用作训练。实验结果如图3所示。

图3 参数k 对算法的影响Fig.3 Influence of parameter k on algorithm

实验结果表明，在BlogCatalog和Flickr大型社交网络数据集中，路径长度取值为6时，AUC值最高，链路预测效果最好，可以证明节点间六阶路径能充分体现大型社交网络中节点间的连通性，可以获得较好的实验效果。而对于Email数据集，路径长度取值为4时，链路预测效果最好。分析原因是节点间最佳路径距离与节点间平均距离呈正相关，由于Email数据集网络规模较小，节点间平均最短距离相对较小，故k取值较小时实验效果最好。

属性相似度权重参数α用于降低社交网络中节点属性信息存在的噪音，当α取值过高时，会使得网络节点中存在大量的属性噪音，当α取值过低时，不能充分考虑节点属性信息，因此确定合理的属性相似度权重参数α可以提高社交网络嵌入效果。实验中，α取0至1，步长为0.1，采用BlogCatalog、Flickr两个数据集进行节点分类任务，评价指标是Micro-F1分数和Macro-F1 分数，随机选取30%节点作为标记节点进行训练，其余节点用作测试。实验结果如图4所示。

图4 参数α 对算法的影响Fig.4 Influence of parameter α on algorithm

实验结果表明，当属性相似度权重参数α取值为0.3时，在BlogCatalog、Flickr数据集上节点分类效果最好。当参数从0.3 至1.0 时，属性信息存在的噪音影响越来越大，节点分类效果越来越差，可见降低节点属性信息中存在的噪音确实可以有效提高算法网络嵌入能力。而当参数小于0.3时，未能充分考虑节点属性信息，节点分类效果也变差。

结构-属性平衡参数λ用于平衡节点间结构相似度和属性相似度。实验中，λ取0.5 至1.0，步长为0.1，采用BlogCatalog、Flickr 两个数据集进行节点分类任务，评价指标是Micro-F1分数和Macro-F1分数，随机选取10%节点作为标记节点进行训练，其余节点用作测试。实验结果如图5所示。

图5 参数λ 对算法的影响Fig.5 Influence of parameter λ on algorithm

实验结果表明，当结构-属性平衡参数λ取值为0.7 时，在BlogCatalog、Flickr 两个数据集上节点分类效果最好。当参数从0.7 至1.0 时，节点相似度受节点属性相似度影响越来越小，节点分类效果越来越差，可见节点属性信息确实可以有效提高算法网络嵌入能力。而当参数小于0.7时，节点相似度受节点结构相似度影响越来越小，节点分类效果也变差。因此，当λ取值为0.7时效果最好。本文在后续的实验中，节点间路径长度k由CDZ 算法[26]计算网络平均路径长度确定，属性相似度权重参数α取值为0.3，结构-属性平衡参数λ取值为0.7。

4.5 节点分类

节点分类是社交网络分析一项重要任务，通过已被标记的节点来预测网络中未被标记的节点标签种类，常用于评价网络嵌入方法的性能。本文节点分类实验选取的数据集是BlogCatalog 和Flickr 数据集，评价指标是Micro-F1 分数和Macro-F1 分数。实验中首先通过各算法学习节点的低维特征表示，然后随机抽取10%至90%（步长为20%）节点作为标记节点进行训练，其余节点用作测试。实验结果如表3～表6所示。

表3 BlogCatalog数据集节点分类Micro-F1分数Table 3 Micro-F1 of node classification on BlogCatalog dataset

表4 BlogCatalog数据集节点分类Macro-F1分数Table 4 Macro-F1 of node classification on BlogCatalog dataset

表5 Flickr数据集节点分类Micro-F1分数Table 5 Micro-F1 of node classification on Flickr dataset

表6 Flickr数据集节点分类Macro-F1分数Table 6 Macro-F1 of node classification on Flickr dataset

根据实验结果，LFNE算法学习出的节点低维特征向量在各数据集上相较于其他算法可以获得更好的节点分类效果。TADW、DANE、LFNE等融合节点属性的网络嵌入方法相较于DNGR、SDNE等仅考虑节点结构信息的网络嵌入方法取得了更好的节点分类效果，在各个数据集上都有较大幅度的提升，可以证明属性信息可以改进社交网络的网络嵌入学习效果。DANE 算法融入了节点间高阶结构信息，而TADW 算法仅考虑节点低阶结构信息，实验结果表明DANE 算法相较于TADW 算法在BlogCatalog、Flickr 数据集上节点分类Micro-F1 分数分别平均提升1.5%、1.8%。可以证明高阶结构信息可以改进社交网络的网络嵌入效果。由于DANE算法并没有消除环状路径和大度节点对于结构信息的影响，提升效果并不显著。而LFNE 算法相较于DANE 算法在BlogCatalog、Flickr 数据集上节点分类Micro-F1 分数平均提升4.3%、4.1%，Macro-F1分数平均提升4.5%、3.9%，可以证明消除环状路径和大度节点可以使得算法更好地融合高阶结构信息，获得更好的网络嵌入效果。

4.6 链路预测

链路预测亦是社交网络分析的一项重要任务，根据已有的网络连接预测节点间潜在或者未来的连接过程。链路预测也常用于评价网络嵌入学习方法的性能。本节链路预测实验选取的数据集是BlogCatalog、Flickr和Email，评价指标是AUC。实验中随机选取10%的连接数据和未连接数据作为测试，10%的连接数据作为验证，其余数据用作训练。实验结果如图6所示。

图6 不同算法链路预测AUC指标结果Fig.6 AUC index results of link prediction with different algorithms

根据实验结果，TADW 和DANE 等融合结构和属性信息的网络嵌入方法相较于单一融合结构信息的SDNE、DNGR算法在BlogCatalog、Email并没有取得更好的链路预测效果。在BlogCatalog 数据集上TADW 算法的链路预测效果最差，DNGR 算法相较于TADW 算法AUC 指标提升30.2%，可以证明社交网络中属性信息确实存在噪音。而本文提出的LFNE 算法在各个数据集上都取得了不错的链路预测效果，在BlogCatalog、Flickr、Email 数据集上相较于DNGR 算法AUC 指标分别提升5.2%、15.9%、3.9%。实验表明，LFNE算法充分考虑节点属性信息和结构信息的相关性，降低社交网络属性信息存在的噪音，可以获得更好的链路预测效果。

5 结束语

本文提出了一种融合节点属性和无环路径的社交网络嵌入方法LFNE。该算法可以消除环状路径和大度节点对于节点相似性的影响并且有效降低节点属性信息中存在的噪音，提高社交网络嵌入效果。实验结果表明，该算法具有可行性和有效性。但是本文仍有几个方面不足：首先，对于无环路径数量计算方面，本文虽然拓展到了六阶无环路径数量计算，但是并没有找到一个普适性的算法可以计算更高阶的无环路径数量。其次，对于网络嵌入方面，本文考虑的是节点的结构信息和属性信息，并没有考虑节点之间的交互信息。下一步将尝试找到一个普适性的算法计算更高阶的无环路径数量，提高无环路径算法的可拓展性，并尝试将节点间的交互信息融入网络嵌入中获得更好的网络嵌入效果。

附录1