一种基于节点嵌入表示学习的社区搜索算法  

Community search algorithm based on node embedding representation learning

作　　者：赵卫绩[1,2] 张凤斌[1] 刘井莲[2,3] ZHAO Wei-ji;ZHANG Feng-bin;LIU Jing-lian(School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China;School of Information Engineering,Suihua University,Suihua 152061,China;School of Computer Science and Engineering,Northeastern University,Shenyang 110169,China)

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080 [2]绥化学院信息工程学院,黑龙江绥化152061 [3]东北大学计算机科学与工程学院,沈阳110169

出　　处：《控制与决策》2021年第8期1970-1976,共7页Control and Decision

基　　金：国家自然科学基金项目(61172168,61772122,61872074);黑龙江省省属高校基本科研业务费科研项目(YWK10236200141)。

摘　　要：针对已有社区搜索算法采用高维稀疏向量表示节点时间复杂度高的问题,提出一种基于节点嵌入表示学习的社区搜索算法CSNERL.节点嵌入技术能够直接从网络结构中学习节点的低维实值向量表示,为社区搜索提供了新思路.首先,针对已有节点嵌入算法存在较高概率在最亲近邻居间来回游走的问题,提出基于最亲近邻居但不立即回访随机游走的节点嵌入模型NECRWNR,采用NECRWNR模型学习节点的特征向量表示;然后,采用社区内所有节点的向量均值作为社区的向量表示,通过选择与当前社区距离最近的节点加入社区的方法实现一种新的社区搜索算法.在真实网络和模拟网络数据集上分别与相关的社区搜索算法进行实验对比,结果表明所提出社区搜索算法CSNERL具有更高的准确性.Considering that the existing community search algorithms represent nodes as high-dimensional sparse vectors and have high time complexity,a community search algorithm based on node embedding representation learning(CSNERL)is proposed.Node embedding techniques can learn low-dimensional vectorial representation of nodes from network structure directly,and provide a new solution to community search problems.Firstly,in view of the problem that the existing node embedding algorithm has a high probability to walk back and forth between the closest neighbors,a node embedding model based on closest-neighbor biased random walk with non-immediately revisiting(NECRWNR)is proposed.Based on this model,vectorial representation of nodes is learned and used as feature vectors of nodes in the downsteam data mining task.Then,vectorial representation of a community is defined as the average of the vectors for nodes in the community,and a new community search algorithm is designed by choosing those nodes which are nearest to the current community.The proposed algorithm is tested on both real-world and synthetic network datasets with the related community search algorithms.The experimental results show that the CSNERL algorithm is more effective at community search than baselines.

关 键 词：社区搜索 节点嵌入 网络表示学习 社区发现 局部社区发现 随机游走 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]