基于量子模糊聚類算法的復雜網絡社團結構探測

牛艷慶

(中南民族大學 數學與統計學學院，武漢 430074)

基于量子模糊聚類算法的復雜網絡社團結構探測

牛艷慶

(中南民族大學 數學與統計學學院，武漢 430074)

研究了復雜網絡的社團結構特性，探討了復雜網絡的社團結構探測算法.針對現有算法中判斷社團結構時的主觀性問題，提出了量子模糊聚類算法，并將該算法用于復雜網絡社團結構的探測.實驗結果表明：該算法可以準確、有效地探測到網絡中實際存在的社團結構.

復雜網絡；社團結構；量子模糊聚類

復雜網絡是一個包含了大量個體以及個體之間相互作用的系統，通常把個體視為網絡中的節點，把個體間的相互作用視為網絡節點與節點之間的連接，這樣由大量的節點以及節點間的連接所構成的復雜系統，就稱為復雜網絡.近年來的研究表明，大量的真實網絡是由若干個群或團組成，這樣的群或團被稱為社團結構[1]，而且每個社團結構內部的節點之間的連接較為緊密，社團之間的連接卻稀疏得多.因而，社團結構是反應復雜網絡結構性質的重要特征.對于大量存在的具有社團結構的復雜網絡，采用一些恰當的方法，準確而有效地探測出其中的社團結構，是復雜網絡研究中的一個重要課題.

聚類分析方法[2]是一種無監督學習方法，通過選擇合適的參數，確定聚類中心和樣本的聚類數目，研究樣本的分布情況.我們以聚類分析的思想為基礎，提出了量子模糊聚類算法，用于復雜網絡社團結構的探測.在經典的空手道俱樂部網絡的實驗結果表明，該方法能夠準確并且有效地探測復雜網絡中的社團結構.

1 量子模糊聚類算法

1.1 量子模糊聚類算法的基本思想

模糊聚類方法[2]是應用模糊數學方法進行聚類的分析方法，因其算法設計簡單、解決問題范圍廣、易于計算機實現，被應用于很多領域.

針對模糊聚類方法在應用時存在的局限性，我們提出了量子模糊聚類算法，主要思想是在量子空間中對數據樣本進行聚類分析.該算法首先利用一個非線性映射，將原空間的待分類樣本映射到一個高維的特征空間(量子空間)中，使得樣本在量子空間中變得線性可分，然后在量子空間中進行聚類.這個非線性映射我們選取的是由薛定諤微分方程確定的量子勢能函數[3,4].由于這個量子勢能函數是連續和光滑的，那么在量子空間中，樣本的拓撲結構和順序將會被保持.因此，在原空間中聚在一起的點，在量子空間中也將會聚在一起，而且通過非線性映射，突出了不同類別樣本特征的差異，使得原來線性不可分的樣本點在量子空間中變得線性可分.利用該算法進行復雜網絡社團結構的探測可以減少聚類誤差，獲得較好的聚類效果.

(1)

其中V(·)為量子勢能函數[4]，即：

(2)

d為樣本空間的維數， E是能量特征值.假定minV=0，則E的取值為：

(3)

其中波函數φ(x)可以近似為：

(4)

我們利用函數V(·)將數據樣本映射到量子空間，D=(dik)為模糊隸屬度矩陣或劃分矩陣，X={x1,x2,…,xn}為數據樣本，ci為數據樣本的聚類中心，c為類別個數.利用拉格朗日乘數法可得：

(5)

其中i=1,2,…，c,k=1,2,…,n，V(ci)按照如下方法計算：

(6)

由u的任意性知：

(7)

故可得：

(8)

1.2 量子模糊聚類算法的迭代過程

根據以上公式的推導結果，我們可以得到量子模糊聚類算法的迭代過程為：

1) 設定聚類類別數c、加權系數p和核尺度參數σ，初始化模糊隸屬度矩陣D=(dik)，及給定一個足夠小的迭代截止誤差ε>0；

2) 根據(5)式更新模糊隸屬度矩陣或劃分矩陣D=(dik)；

3) 根據(8)式計算量子勢能函數在聚類中心ci處的值V(ci)；

4) 如果‖Dnew-Dold‖<ε，則終止迭代，得到要求的最優的聚類中心ci和最優劃分矩陣D=(dik)，否則轉到步驟2)繼續進行.

2 數值實驗

我們將量子模糊聚類算法用于復雜網絡社團結構的探測，選取的實驗數據為經典的真實網絡數據，即空手道俱樂部網絡數據[5].

2.1 空手道俱樂部網絡

Zachary W W[6]所研究的空手道俱樂部網絡被廣泛應用于探測復雜網絡社團結構的方法中.該網絡包括34個節點和78條邊，分別表示的是空手道俱樂部的成員和俱樂部成員之間的相互聯系.由于俱樂部的兩個管理者之間產生分歧，導致這個俱樂部以這兩個管理者為中心，最終分裂為兩個社團.圖1為空手道俱樂部的網絡，其中節點1和節點34分別表示兩個管理者.

圖1 空手道俱樂部網絡Fig.1 Karate club network

2.2 算法的評價指標

模塊度函數Q的值是評價網絡中的社團結構是否明顯的重要指標[7]，可以將Q值的大小用于比較不同的探測算法.Q的取值為0≤Q≤1，Q越接近于1，說明算法得到了較好的劃分結果，該網絡具有明顯的社團結構.大量的研究表明，在實際網絡中，Q值通常位于0.3～0.7之間，過大或過小的Q值很少出現.

模塊度函數Q的計算方法[7]為：

(9)

2.3 結果與分析

Newman的最短路介數算法[8]中指出，最優聚類數目的確定依靠樹狀圖在不同位置處的截取，并依靠對應的模塊度函數Q的最大值選取相應的社團結構的分類.Newman算法選擇的最優聚類數目即社團結構的數目是k=4，對應的模塊度函數Q的最大值為Q=0.36654.雖然社團結構的數目為4時對應的模塊度函數Q的值為最大，但是這樣劃分得到的社團結構與實際的兩個社團結構不相符合.

我們提出的基于量子模糊聚類算法的社團探測方法的主要任務是通過最大化Q值，確定最優核尺度參數σ，進而確定聚類中心，最終找到社團結構的最優劃分.

圖2 本文算法得到的空手道俱樂部網絡Fig.2 Karate club network by our algorithm

我們提出的基于量子譜聚類算法的社團探測方法得到的最優的社團結構的數目k=2，對應的模塊度函數Q的值為Q=0.36235.圖2展示了由我們的算法得到的空手道俱樂部網絡的社團結構圖.從圖2可以看到，空手道俱樂部網絡被分為兩個社團，這符合實際情況，并且網絡中只有節點3和 14被錯誤的劃分，算法的準確率為94%.

3 結語

本文提出了量子模糊聚類算法，進行社團結構的探測.應用于經典的空手道網絡數據的實驗表明，我們的算法可以準確并且有效地探測到網絡中實際存在的社團結構.我們希望能將這一算法推廣到有權重和有方向的復雜網絡中.

[1] Newman M. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.

[2] 胡寶清. 模糊數學理論基礎[M]. 武漢: 武漢大學出版社, 2004: 162-169.

[3] Horn D, Gottlieb A. Algorithm for data clustering in pattern recognition problems based on quantum mechanics[J]. Physical Review Letters, 2002, 88(1): 1-4.

[4] Horn D, Axel I. Novel clustering algorithm for microarray expression data in a truncated SVD space[J]. Bioinformatics, 2003, 19(9): 1110-1115.

[5] Newman M. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.

[6] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33: 452-473.

[7] Newman M. Detecting community structure in networks[J]. European Physical Journal B, 2004(2): 321-330.

[8] Newman M, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.

Detecting the Community Structure in Complex Networks Based on Quantum Fuzzy Clustering Algorithm

NiuYanqing

(College of Mathematics and Statistics, South-Central University for Nationalities, Wuhan 430074, China)

Research in this paper aims to find some novel approaches to detecting the community structures in complex networks. To reduce the subjectivity in the existing algorithms, we detect community structure in complex networks based on quantum fuzzy clustering analysis method. The experimental results show that this method can give satisfactory results.

complex networks; community structure; quantum fuzzy clustering

2015-01-25

牛艷慶 (1979-)，女，講師，博士，研究方向：智能計算，E-mail: niuyanqing2005@hotmail.com

國家自然科學基金資助項目(11226267)；深圳市發展基金資助項目(JCYJ20130401160028781)

O159

A

1672-4321(2015)03-0123-03