引用本文

贾承丰, 韩华, 吕亚楠, 张路. 基于Word2vec和粒子群的链路预测算法. 自动化学报, 2020, 46(8): 1703−1713 doi: 10.16383/j.aas.c180187

Jia Cheng-Feng, Han Hua, Lv Ya-Nan, Zhang Lu. Link prediction algorithm based on Word2vec and particle swarm. Acta Automatica Sinica, 2020, 46(8): 1703−1713 doi: 10.16383/j.aas.c180187

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180187

关键词

链路预测，特征提取，不平衡问题，深度学习，粒子群优化 

摘要

链路预测中普遍存在两大问题:特征提取困难和类别数据不平衡.本文借鉴文本处理中的深度学习特征提取算法和优化问题中的粒子群算法, 提出一种基于词向量的粒子群优化算法(Word2vec-PSO).该方法首先通过随机游走产生网络序列后, 利用Word2vec算法对节点序列特征提取.然后在有监督的条件下, 利用粒子群算法对提取好的特征进行筛选, 并确定重采样的参数来解决类别数据不平衡问题, 并分析了不同链路预测算法的计算复杂性.最后将本文的算法与基于相似性、基于深度学习、基于不平衡数据的3类链路预测算法, 在4个不同的时序网络中进行实证对比研究.结果表明, 本文提出的链路预测算法预测精度较高, 算法更加稳定且具有普适性.

文章导读

在大数据时代, 随着大量社交网络和信息网络的出现, 链路预测已经成为数据挖掘研究的一个重要方向.链路预测是指如何通过已知的网络节点以及网络结构等信息, 预测网络中尚未产生连边的两个节点之间产生连接的可能性[1-2].近年来, 基于网络节点相似性的链路预测算法被广泛研究. Liben-Nowell等[3]根据网络节点和路径的相似性, 最早提出了基于网络拓扑结构的相似性定义方法.由此开始, 各种基于节点相似性的指标层出不穷, 国内学者Zhou等[4]将9种节点相似性的指标应用于6个不同的网络中进行链路预测, 发现不同的网络对于各种相似性指标的敏感性不同.这是由于基于节点相似性的链路预测算法是一种无监督算法, 在不同的网络数据集中预测精度不稳定[4-5].

由于节点相似性算法稳定性不强、准确率不高, 许多研究学者转换思路, 将链路

预测问题看作是一种有监督的二分类问题, 利用机器学习算法进行训练、预测.要利用机器学习算法, 第一步就是要对网络进行特征提取. Benchettara等[6]将节点之间的相似性指标作为网络的特征进行提取, 然后利用贝叶斯算法、决策树算法对这些带有标签的节点对进行分类, 将训练出的模型对Facebook社交网络进行预测.因为提取的特征依旧由相似性指标组成, 特征的维度也是人为选取, 网络深层的结构性特性未被表征, 所以算法还是会存在对于不同的网络敏感性不同的问题, Popescul等[7]利用逻辑回归算法研究了论文著作网络中两位作者下一时刻合著一篇文章的可能性, 他利用到的网络特征是作者信息(也就是节点属性信息)和网络拓扑信息.但是在实际的链路问题中, 节点的属性信息是很难获取到的, 即使能得到, 节点的属性信息会有噪声, 甚至是虚假信息.例如电商平台的用户信息是保密的, 或者是注册者提供的虚假身份信息, 所以加入节点属性在实际操作中很难做到.在人工智能领域, 如果对象的特征难以直接提取, 一般会采用深度学习的方法进行特征提取. Liu等[8]利用受限玻尔兹曼机(Restricted Boltzmann machine, RBM)加上深度信念神经网络, 对复杂网络进行特征提取, 然后将特征以Logistic回归进行训练.由于训练RBM要利用到对比散度算法, 要进行吉布斯采样, 数据要服从高维高斯分布[9], 但是复杂网络的邻接矩阵是一个稀疏矩阵, 数据分布随机性较大, 这就导致需要多次采样, 无疑增加了训练成本. Kipf等[10]参照图像处理中的卷积神经网络的思想, 提出类卷积层, 对复杂网络特征提取.但正因为算法来源于图像, 卷积神经网络注重于图像的边缘[11], 在矩阵中也就是注重相邻元素数值差异大的部分.差异小的部分可能在池化层就直接合并了, 但是在复杂网络中, 每一条连边的信息都有着自己的作用, 少量连边信息的丢失, 可能会导致部分样本的特征没有被学习到, 从而影响最终分类器的准确率.另外, 上述算法在突破网络特征提取这一难题之后, 大多数研究方法, 就直接将网络的特征作为分类算法的输入[12-13].没有考虑现实网络中, 有连边的节点对数目远远小于无连边的节点对.传统的机器学习算法会因为类别数目的不平衡这一现象, 而导致决策出现偏差, 详细原因将会在下一节描述.针对复杂网络特征提取难和类别样本数目不平衡这两大问题.本文的工作主要如下: 1)将网络序列化为文本形式, 利用文本处理中的Word2vec算法对网络进行特征提取. 2)为了对上一步的特征进行筛选和处理不平衡问题, 引入粒子群算法对分类器进行优化. 3)在4个时序网络中进行链路预测, 分别对比节点相似性链路预测算法、深度学习提取特征方法、不平衡问题解决方法这三大类算法与本文算法的差异.

图 1  链路预测算法总流程

图 2  CBOW网络结构

图 3  PSO中解的表达形式

本文针对复杂网络特征提取难和类别样本数目不平衡这两大问题.主要做了以下工作并得到一些结论, 具体为: 1)将网络序列化为文本形式, 利用文本处理中的Word2vec算法对网络进行特征提取, 将抽象的点边关系的具体化、数值化. 2)利用粒子群算法对提取出的特征进行筛选, 并对原始数据进行重构, 解决了链路预测中的样本类别不平衡问题. 3)在4个时序网络中进行链路预测, 分别对比节点相似性链路预测算法、深度学习提取特征方法、不平衡问题解决方法这3大类算法与本文算法的差异. 3大类算法各有各的优势, 因为本文同时考虑到了特征提取和类别不平衡两个链路预测主要问题, 从综合角度来说, 算法理论更全面, 从大型网络的链路预测实验中, 也体现了本算法良好的预测表现.

本文借鉴的是文本处理中的深度学习算法, 将复杂网络对象类比为文本进行研究, 可以看出文本与网络的共性.从另一角度考虑, 一部分研究学者也将文本转化为了复杂网络进行研究.本算法还可以应用到文本网络中, 对文本进行链路预测, 从而实现文本语义识别、词性标注等一些自然语言处理问题.

作者简介

贾承丰

武汉理工大学理学院硕士研究生.主要研究方向为复杂网络, 机器学习. E-mail: 13986076510@163.com

吕亚楠

武汉理工大学理学院硕士研究生.主要研究方向为链路预测, 复杂网络. E-mail: lyn@whut.com

张路

武汉安天科技公司数据挖掘工程师.主要研究方向为自然语言处理, 机器学习. E-mail: 17838907371@163.com

韩华

博士, 武汉理工大学理学院教授.主要研究方向为系统预测, 复杂网络, 经济决策.本文通信作者. E-mail: hhua@whut.com