兩階段量子行走算法在社區檢測中的應用

摘 要：已有基于量子行走的社區檢測算法存在計算開銷過大或對時間參數過于敏感的問題。針對此問題，提出兩階段量子行走（two-stage quantum walk，TSQW）算法。TSQW算法第一階段為無測量量子行走，此階段融合節點的鄰域拓撲信息將節點表達為向量，第二階段利用K-means方法聚類上一階段得到的節點向量以劃分網絡社區。通過仿真網絡和空手道俱樂部網絡的驗證，該算法能夠準確地檢測網絡社區結構。進一步，提出TSQW的擴展（TSQW-E）算法，該算法依據節點的社區信息增加或刪除原始網絡的連邊并實現社區隱藏。根據互信息指標和調整蘭德系數下的實驗表現，TSQW-E算法使已有社區檢測算法的平均識別精度分別下降0.491和0.58，對網絡社區結構的破壞效果最好。

關鍵詞：復雜網絡；量子行走；社區檢測；社區隱藏

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1001-3695（2023）08-013-2329-05

doi： 10.19734/j.issn.1001-3695.2023.01.0007

Two-stage quantum walk algorithm with application to community detection

Liang Wen Yan Fei Chen Baizhen

（1. School of Computer Science amp; Technology， Changchun University of Science amp; Technology， Changchun 130022， China; 2. School of Information Engineering， Jiangxi University of Science amp; Technology， Ganzhou Jiangxi 341000， China）

Abstract：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.

Key words：complex network; quantum walk; community detection; community deception

0 引言

量子算法的出現為圖像處理和機器學習等諸多領域的研究任務提供了新穎且高效的解決方案［1，2］。在諸多量子算法中，量子行走（quantum walks）顯得與眾不同，因可用于實現其他量子算法而被視為一種通用計算（universal computation）模型［3］，并逐漸成為信息安全通信［4］、空間搜索［3］和圖數據挖掘［5］領域的關鍵技術。

籠統地講，量子行走研究的是粒子在圖數據結構上的運動以及粒子在圖上測量結果的分布特點。當量子行走發生在以復雜網絡為代表的不規則圖上時，其主要應用為捕捉網絡中具有特殊含義的節點和邊。譬如，網絡的中心節點、關鍵邊和網絡中丟失的邊等［6］。2020年Wang等人［7］提出幺正膨脹演化的連續時間量子行走模型算法構造有向復雜網絡上的幺正演化，實驗表明該算法能有效地排序有向網絡的中心節點。2021年，國防科技大學團隊［8］設計了一種由Grover算符驅動的離散時間量子行走算法，該算法能以高精度評估網絡節點間的相似性。2022年，Liang等人［5］針對網絡關鍵邊識別問題提出復雜網絡上的Hadamard量子行走，并進一步將其應用于動態無人機通信網絡挖掘關鍵無人機節點。上述成果共同表明量子行走的測量結果可以有效地反映網絡拓撲結構特征，為量子行走在復雜網絡結構挖掘中的應用提供了有力支撐。

以上針對節點和邊的發現工作僅為微觀尺度上對網絡結構信息的挖掘，量子行走測量結果所捕捉的目標還可以是中觀尺度上具有高度聚集特征的子圖結構，即社區。目前，已知的基于量子行走的復雜網絡社區檢測方法有兩種。一種是由Mukai等人［9］提出的利用Fourier硬幣驅動的離散時間量子行走（discrete-time quantum walk）算法，以下簡稱Fourier量子行走。由于量子計算中的演化算符多為幺正矩陣，其特征值按實部和虛部分解后能以單位圓的形狀投射在一個單位復平面上。文獻［9］研究發現在極限行走步長下Fourier量子行走演化算符所分解出的特征值在單位圓上的分布較均勻，適宜挖掘復雜網絡的社區結構，并利用空手道俱樂部和美國航空航線網絡驗證Fourier量子行走在社區檢測中的有效性。另一項工作是Faccin等人［10］提出的基于連續時間量子行走（continuous-time quantum walk）的社區檢測算法。基于社區內部連接緊密的特點，文獻［10］中假設社區內節點的信息交互頻率更高，令某個時段內粒子在社區內節點上測量概率的變化幅值盡可能地大，而考慮到社區外部連接相對稀疏的特點，令同時段內粒子在社區間節點上測量概率的變化幅值盡可能地小，最后基于緊密性指標（closeness index）優化社區結構的劃分結果。

上述基于量子行走的社區檢測算法在應用層面存在諸多限制，例如前者因需仿真無限次演化而取平均導致計算開銷過大；而后者因無法確定最佳的時間參數導致社區檢測結果的不穩定。為減少量子行走反復測量帶來的計算消耗并提高量子行走對復雜網絡社區的檢測精度，本文提出兩階段量子行走（two-stage quantum walk， TSQW）算法。實驗表明該算法可以準確劃分網絡的社區結構。進一步，本文擴展TSQW算法并使其應用于社區隱藏，實驗表明擴展后的TSQW算法能夠有效避免其他社區檢測算法識別網絡的社區結構。

1 兩階段量子行走算法

為規避量子行走測量結果存在震蕩的問題，并使得量子行走在復雜網絡結構挖掘任務上發揮應用價值，本章提出兩階段量子行走（TSQW）算法。在TSQW算法的第一階段，設計了一種無測量量子行走（quantum walk without observation），將復雜網絡的全部節點表示為向量，并融入節點的局部拓撲特征；第二階段使用K-means算法聚類第一階段得到的向量，聚類結果即TSQW算法檢測到的社區結構。兩階段量子行走算法的框架參考圖1。

1.1 用于節點向量表征的無測量量子行走

1.2 用于向量聚類的K-means社區檢測

2 TSQW算法在社區檢測中的應用

2.1 社區檢測及評價指標

2.2 TSQW算法在仿真網絡上的社區檢測

為驗證TSQW算法在社區檢測中的效果，本節給出一個具有明顯社區結構特征的仿真網絡，作為TSQW算法的測試數據，此仿真網絡如圖3所示。該網絡具有三個特征明顯的社區結構，TSQW算法的劃分結果必須準確劃分三個無重疊社區才能反映出其在社區檢測中的效果。

由于任意節點在TSQW算法中均以N維向量的形式表達，當全部向量投影在二維平面上，則TSQW算法對圖3網絡的社區檢測結果如圖4所示。在圖4中，每個散點均對應圖3網絡中的節點，根據圖中淺藍、淺紅、淺綠的三個色域以及節點的聚集情況可以發現，TSQW算法能夠準確劃分具有明顯社區結構的復雜網絡（見電子版）。

2.3 TSQW算法對Karate網絡的社區檢測結果

為進一步驗證TSQW算法在社區檢測中的效果，本節采用著名開源小世界網絡——Karate空手道俱樂部（Zachary’s Karate Club）作為測試數據，該網絡由34個節點和78條邊組成。由于該俱樂部存在是否提高收費的爭議而瓦解為兩個不同社區，兩社區分別由編號為33和編號為1的節點領導。Karate網絡帶有標準的真實社區數據，在圖5中分別以不同顏色區分（見電子版），其中編號為3和編號為10的節點較容易被社區檢測算法錯誤劃分，因為兩者的鄰域節點分別從屬于不同社區，且數量相同。

本節實驗的對比算法可分為兩組，第1組為非量子的經典社區檢測算法，包括Louvian［14］、Newman的模塊化算法（Newman’s modularity algorithm， NMA）、WalkTrap［15］、自旋玻璃（SpinGlass）［16］、信息熵編碼（Infomap）［17］、基于節點穩定性和鄰域相似性的社區發現算法（NSNSA）［18］以及改進布谷鳥搜索優化算法（ICSO）［19］；第2組為量子衍生群體智能算法，包括量子蟻群優化算法（quantum ant colony optimization algorithm， QACO）［20］、量子離散多目標的粒子群優化算法（quantum-behaved discrete multi-object particle optimization algorithm， QDM-PSO）［21］以及量子遺傳算法（quantum genetic algorithm， QGA）［22］。以模塊化函數Q和NMI指標為評價標準，上述算法同TSQW算法對Karate網絡的社區檢測結果參考表1。

根據表1，TSQW算法的社區檢測結果同Karate網絡真實社區數據完全相同，并且量子算法普遍優于非量子的經典算法。在表1中，NSNSA和ICSO算法均為較新穎的社區檢測算法，兩者的模塊度值雖然均與標準Q值相等或高度近似，但兩者的社區檢測結果與真實社區間差距極大，不及本文提出的TSQW算法。此外，無論非量子的經典算法還是量子衍生的社區檢測算法，它們在模塊化函數和NMI指標下的表現共同說明：對于具有真實社區數據的網絡而言，模塊化函數度量值的最大化并不意味著算法的社區檢測結果更貼合真實社區。具體而言，SpinGlass算法在全部對比方法中的模塊化函數度量值最高，但其對Karate網絡的社區劃分精度很低。同理，也可以解釋QACO算法雖準確劃分了Karate網絡的社區（根據其NMI指標），但其模塊化度量值（0.417）大于Karate網絡真實社區對應的模塊化函數度量值（0.371）。在表1的非量子經典算法中，前五種算法極具代表性，諸多社區檢測算法均基于其而設計改進算法，但此五者在NMI指標下呈現出的社區檢測精度均不及TSQW算法。相比之下，僅QACO和本文的TSQW算法能夠完全準確地劃分網絡的社區結構。

3 TSQW擴展算法在社區隱藏中的應用

鑒于TSQW算法在社區檢測中的優異表現，本章提出TSQW的擴展算法，用于修改網絡連邊信息達到隱藏網絡的社區結構的目的。

3.1 社區隱藏問題描述

3.2 TSQW的擴展算法

3.3 TSQW-E算法的社區隱藏實驗

本節實驗以Louvian、NMA、WalkTrap、Infomap以及SpinGlass算法作為式（9）中的社區檢測算法f，并選擇如下算法作為用于破壞網絡結構的社區隱藏對比方法，包括隨機（Random）算法、社區檢測攻擊（community detection attack，CDA）［23］算法、基于度的攻擊（degree based attack， DBA）［23］算法，其中Random和CDA算法因包含隨機性而重復運行10次后取均值。在使用上述社區隱藏算法后，將得到修改的復雜網絡，即式（9）中的G′。進一步，根據式（9）的描述關系可知，社區檢測算法f對網絡G′的社區檢測精度越小則社區隱藏效果越佳。本節實驗仍以Karate空手道俱樂部為測試網絡，并考慮對該網絡僅移除或添加5%的連邊或節點（78×5%≈4）。

基于NMI和ARI指標，上述社區隱藏算法及本節提出的TSQW-E算法的社區隱藏結果分別參考圖8和9。在圖8和9中，水平方向表示不同社區檢測算法，豎直方向表示破壞網絡社區結構的方法，每一個方塊表示網絡被破壞后某算法的社區檢測精度。當網絡結構未經破壞時，原始NMI值及ARI值默認為1，并用original標記。圖中右側色帶代表NMI和ARI度量值的高低，淺顏色代表高精度隱藏結果。

根據圖8和9的社區隱藏實驗結果可以發現，無論基于何種指標，本文提出的TSQW-E算法的社區檢測效果均為最佳。相比之下，Random算法因隨機地移除集合E中的邊，導致其隱藏效果在對比算法中最差；CDA算法雖以感知網絡社區結構作為移除網絡邊的前提，但其在節點選擇上沒有可依賴的啟發信息并具有隨機性，導致社區隱藏精度不穩定；DBA算法以最大度節點作為修改網絡的啟發信息，其在NMI和ARI指標下的隱藏效果整體上優于CDA算法。為量化不同算法的社區隱藏效果，此處逐一計算圖8和9中縱方向算法對經典社區檢測算法造成的精度損失，精度損失的值越大越能表明算法在社區隱藏任務上的有效性。以圖8中Random算法為例，Random算法使水平方向五種經典社區檢測算法的平均精度下降了1-（0.873+0.732+0.833+0.819+0.826）/5=0.183。依此類推，在NMI指標下，CDA、DBA以及TSQW-E算法使五種社區檢測算法的精度分別平均下降了0.252、0.328以及0.491；而根據圖9，在ARI指標下，三種對比算法和TSQW-E算法使社區檢測精度分別平均下降了0.229、0.328、0.330以及0.580。由此可見，無論采用何種評價指標，TSQW-E算法的社區隱藏效果在對比算法中最佳。

此外，社區隱藏效果的優劣同樣與所使用的社區檢測算法f存在明顯相關關系。以圖9中DBA算法的社區隱藏結果為例，分別使用Louvian算法和NMA算法計算社區序列時，兩者對由DBA算法修改后得到的網絡G′的社區隱藏結果差距較大，前者等于0.815而后者等于0.585。說明社區隱藏的效果高度依賴所使用的社區檢測算法f。而相比之下，本文提出的TSQW-E算法能有效地避免不同類型社區檢測算法準確識別網絡原有的社區結構。

4 結束語

本文提出一種用于社區檢測的兩階段量子行走算法，該算法的無測量量子行走能有效地融合節點的局部拓撲特征信息將節點向量化表達。相比已有量子行走算法，兩階段量子行走算法壓縮了態向量的維度并省略了測量過程，極大節省了計算過程中的空間占用。實驗表明，兩階段量子行走算法能在社區檢測和社區隱藏兩項應用中同時發揮顯著作用，具有高度靈活性和可擴展性。

本文的應用場景僅針對無重疊的社區檢測任務，未來計劃將量子行走擴展至高維的線圖上，線圖中的節點與原網絡中的邊相對應，而每條邊關聯兩個不同的節點。因此量子行走對線圖上每個節點的表征結果包含網絡連邊的信息，當基于連邊信息來劃分網絡的社區結構時，自然而然能夠得到重疊的社區結構。結合本文算法在無重疊社區檢測上的表現可以推斷，兩階段量子行走算法未來在重疊社區檢測中有望發揮新的積極作用。

參考文獻：

［1］Yan Fei，Li Nianqiao. QHSL： a quantum hue，saturation，and lightness color model ［J］. Information Sciences，2021，577： 196-213.

［2］Li Nianqiao，Yan Fei. A single-qubit-based HSL color model for efficient quantum image security applications ［J］. Optical and Quantum Electronics，2022，54（11）： 1-39.

［3］Kadian K，Garhwal S，Kumar A. Quantum walk and its application domains： a systematic review ［J］. Computer Science Review，2021，41： 100419.

［4］李萌，尚云. 兩硬幣量子游走模型中的相干動力學［J］. 計算機研究與發展，2021，58（9）：1897-1905.（Li Meng，Shang Yun. Dynamics of coherence in quantum walk with two coins［J］. Journal of Compu-ter Research and Development，2021，58（9）： 1897-1905.）

［5］Liang Wen，Yan Fei，Iliyasu A M，et al. A Hadamard walk model and its application in identification of important edges in complex networks ［J］. Computer Communications，2022，193： 378-387.

［6］Chawla P，Mangal R，Chandrashekar C. Discrete-time quantum walk algorithm for ranking nodes on a network ［J］. Quantum Information Processing，2020，19（5）： 1-21.

［7］Wang Kunkun，Shi Yuhao Xiao Lei，et al. Experimental realization of continuous-time quantum walks on directed graphs and their application in PageRank ［J］. Optica，2020，7（11）： 1524-1530.

［8］Wang Xin，Lu Kai，Zhang Yi，et al. QSIM： a novel approach to node proximity estimation based on discrete-time quantum walk ［J］. Applied Intelligence，2021，51（4）： 2574-2588.

［9］Mukai K，Hatano N. Discrete-time quantum walk on complex networks for community detection ［J］. Physical Review Research，2020，2（2）： 023378.

［10］Faccin M，Migdal P，Johnson T H，et al. Community detection in quantum complex networks ［J］. Physical Review X，2014，4（4）： 041012.

［11］Paparo G D，Martin-delgado M A. Google in a quantum network ［J］. Scientific Reports，2012，2（1）： 1-12.

［12］Liang Wen，Yan Fei，Iliyasu A M，et al. A simplified quantum walk model for predicting missing links of complex networks ［J］. Entropy，2022，24（11）： 1547.

［13］韓忠明，劉雯，李夢琪，等. 基于節點向量表達的復雜網絡社團劃分算法 ［J］. 軟件學報，2019，30（4）： 1045-1061. （Han Zhongming，Liu Wen，Li Mengqi，et al. Community detection algorithm based on node embedding vector representation ［J］. Journal of Software，2019，30（4）： 1045-1061.）

［14］Blondel V D，Guillaume J，Lambiotte R，et al. Fast unfolding of communities in large networks ［EB/OL］. （2008-07-25）. http：//doi.org/10.1088/1742-5468/2008/10/p10008.

［15］Pons P，Latapy M. Computing communities in large networks using random walks ［C］// Proc of the 20th International Symposium on Computer and Information Sciences. Berlin： Springer，2005： 284-293.

［16］Reichardt J，Bornholdt S. Statistical mechanics of community detection ［J］. Physical Review E，2006，74（1）： 016110.

［17］Rosvall M，Bergstrom C T. Maps of random walks on complex networks reveal community structure ［J］. Proceedings of the National Academy of Sciences，2008，105（4）： 1118-1123.

［18］鄭文萍，劉美麟，楊貴. 一種基于節點穩定性和鄰域相似性的社區發現算法 ［J］. 計算機科學，2022，49（9）： 83-91. （Zheng Wenping，Liu Meilin，Yang Gui. Community detection algorithm based on node stability and neighbour similarity ［J］. Computer Science，2022，49（9）： 83-91.）

［19］Shishavan S T，Gharehchopogh F S. An improved cuckoo search optimization algorithm with genetic algorithm for community detection in complex networks ［J］. Multimedia Tools and Applications，2022，81（18）： 25205-25231.

［20］Pizzuti C. GA-Net： a genetic algorithm for community detection in social networks ［C］// Proc of the 10th International Conference on Parallel Problem Solving from Nature. Berlin： Springer，2008： 1081-1090.

［21］Li Lingling，Jiao Licheng，Zhao Jiaqi，et al. Quantum behaved discrete multi-objective particle swarm optimization for complex network clustering ［J］. Pattern Recognition，2017，63： 1-14.

［22］ Chen Jinyin，Chen Lihong，Chen Yixian，et al. GA-based Q-attack on community detection ［J］. IEEE Trans on Computational Social Systems，2019，6（3）： 491-503.

［23］李陽陽，焦李成，張丹，等. 量子計算智能 ［M］. 北京： 科學出版社，2019： 249-252.（Li Yangyang，Jiao Licheng，Zhang Dan，et al. Quantum computational intelligence［M］. Beijing： Science Press，2019： 249-252.）