两阶段量子行走算法在社区检测中的应用  

Two-stage quantum walk algorithm with application to community detection

作　　者：梁文 闫飞[1] 陈柏圳 Liang Wen;Yan Fei;Chen Baizhen(School of Computer Science&Technology,Changchun University of Science&Technology,Changchun 130022,China;School of Information Engineering,Jiangxi University of Science&Technology,Ganzhou Jiangxi 341000,China)

机构地区：[1]长春理工大学计算机科学技术学院,长春130022 [2]江西理工大学信息工程学院,江西赣州341000

出　　处：《计算机应用研究》2023年第8期2329-2333,共5页Application Research of Computers

基　　金：吉林省科技发展计划资助项目(20210201075GX)。

摘　　要：已有基于量子行走的社区检测算法存在计算开销过大或对时间参数过于敏感的问题。针对此问题,提出两阶段量子行走(two-stage quantum walk,TSQW)算法。TSQW算法第一阶段为无测量量子行走,此阶段融合节点的邻域拓扑信息将节点表达为向量,第二阶段利用K-means方法聚类上一阶段得到的节点向量以划分网络社区。通过仿真网络和空手道俱乐部网络的验证,该算法能够准确地检测网络社区结构。进一步,提出TSQW的扩展(TSQW-E)算法,该算法依据节点的社区信息增加或删除原始网络的连边并实现社区隐藏。根据互信息指标和调整兰德系数下的实验表现,TSQW-E算法使已有社区检测算法的平均识别精度分别下降0.491和0.58,对网络社区结构的破坏效果最好。The existing quantum walk-based community detection algorithms consume massive computations and exhibit sensitivity to the time parameter.Therefore,this paper proposed a two-stage quantum walk(TSQW)algorithm.The first stage was a quantum walk model without observation,which represented each node as a vector via combing its neighbor information.In the second stage,TSQW used K-means to cluster the node vectors and divide the communities.TSQW algorithm could accurately detect the community structure for the simulated network and Karate club network.Moreover,this paper proposed a TSQW-E algorithm for community deception,which combined the community information of nodes to add or delete edges of the original network.Experimental outcomes under the normalized mutual information and the adjusted Rand index show that TSQW-E can reduce the average identification accuracy of existing community detection algorithms by 0.491 and 0.58 respectively,the effect on community deception is the best.

关 键 词：复杂网络 量子行走 社区检测 社区隐藏 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]