摘要： 针对传统标签传播算法准确率较低的问题,提出一种基于深度游走模型的改进标签传播算法。以社会网络作为深度游走模型的输入,通过深度随机游走的方式对网络中的节点进行采样得到随机序列,并基于SkipGram模型对其进行神经网络训练。运用层次Softmax对SkipGram模型进行求解,得到节点的特征向量后在邻居节点之间计算节点相似度,将其作为标签传播概率的权重进行标签的传播迭代,最终得到社区发现的结果。在6个真实网络数据集和合成数据集上进行实验,结果表明,与传统标签传播算法相比,该改进算法具有较高的准确率,尤其对于节点个数在100以上的真实网络,Q值提高10%以上。

关键词: 深度游走模型, 随机序列, 特征向量, SkipGram模型, 节点相似度, 传播迭代

Abstract: Aiming at the problem of low accuracy in traditional Label Propagation Algorithm(LPA),an improved label propagation algorithm based on DeepWalk model is proposed.Firstly,the algorithm takes the social network as the input of the DeepWalk model,samples the nodes in the network to get random sequences by means of a deep random walk,and uses SkipGram model to train the samples in neural network.Secondly,computes the kernel part of SkipGram model by hierarchical Softmax and obtains the feature vector of the nodes,and then calculates the similarity between the nodes.Finally,takes the similarity of the nodes as the weight during the label propagation procedure,and then gets the results of community detection.Experimental results on 6 real network dataset and synthetic dataset show that,compares with the traditional label propagation algorithm,the improved algorithm gets the higher accuracy,and especially when the nodes’ number is more than 100 in real network dataset,the Q shows 10% rise in improved algorithm.

Key words: DeepWalk model, random sequence, feature vector, SkipGram model, node similarity, propagation iteration

中图分类号: 

• TP391