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

已有基于量子行走的社区检测算法存在计算开销过大或对时间参数过于敏感的问题。针对此问题，提出两阶段量子行走（two-stage quantum walk，TSQW）算法。TSQW算法第一阶段为无测量量子行走，此阶段融合节点的邻域拓扑信息将节点表达为向量，第二阶段利用K-means方法聚类上一阶段得到的节点向量以划分网络社区。通过仿真网络和空手道俱乐部网络的验证，该算法能够准确地检测网络社区结构。进一步，提出TSQW的扩展（TSQW-E）算法，该算法依据节点的社区信息增加或删除原始网络的连边并实现社区隐藏。根据互信息指标和调整兰德系数下的实验表现，TSQW-E算法使已有社区检测算法的平均识别精度分别下降0.491和0.58，对网络社区结构的破坏效果最好。

Two-stage quantum walk algorithm with application to community detection

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.