牛艷慶

(中南民族大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)學(xué)院，武漢 430074)

基于量子模糊聚類算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)探測

牛艷慶

(中南民族大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)學(xué)院，武漢 430074)

研究了復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)特性，探討了復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)探測算法.針對現(xiàn)有算法中判斷社團(tuán)結(jié)構(gòu)時的主觀性問題，提出了量子模糊聚類算法，并將該算法用于復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的探測.實驗結(jié)果表明：該算法可以準(zhǔn)確、有效地探測到網(wǎng)絡(luò)中實際存在的社團(tuán)結(jié)構(gòu).

復(fù)雜網(wǎng)絡(luò)；社團(tuán)結(jié)構(gòu)；量子模糊聚類

復(fù)雜網(wǎng)絡(luò)是一個包含了大量個體以及個體之間相互作用的系統(tǒng)，通常把個體視為網(wǎng)絡(luò)中的節(jié)點，把個體間的相互作用視為網(wǎng)絡(luò)節(jié)點與節(jié)點之間的連接，這樣由大量的節(jié)點以及節(jié)點間的連接所構(gòu)成的復(fù)雜系統(tǒng)，就稱為復(fù)雜網(wǎng)絡(luò).近年來的研究表明，大量的真實網(wǎng)絡(luò)是由若干個群或團(tuán)組成，這樣的群或團(tuán)被稱為社團(tuán)結(jié)構(gòu)[1]，而且每個社團(tuán)結(jié)構(gòu)內(nèi)部的節(jié)點之間的連接較為緊密，社團(tuán)之間的連接卻稀疏得多.因而，社團(tuán)結(jié)構(gòu)是反應(yīng)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)性質(zhì)的重要特征.對于大量存在的具有社團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)，采用一些恰當(dāng)?shù)姆椒ǎ瑴?zhǔn)確而有效地探測出其中的社團(tuán)結(jié)構(gòu)，是復(fù)雜網(wǎng)絡(luò)研究中的一個重要課題.

聚類分析方法[2]是一種無監(jiān)督學(xué)習(xí)方法，通過選擇合適的參數(shù)，確定聚類中心和樣本的聚類數(shù)目，研究樣本的分布情況.我們以聚類分析的思想為基礎(chǔ)，提出了量子模糊聚類算法，用于復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的探測.在經(jīng)典的空手道俱樂部網(wǎng)絡(luò)的實驗結(jié)果表明，該方法能夠準(zhǔn)確并且有效地探測復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu).

1 量子模糊聚類算法

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

模糊聚類方法[2]是應(yīng)用模糊數(shù)學(xué)方法進(jìn)行聚類的分析方法，因其算法設(shè)計簡單、解決問題范圍廣、易于計算機實現(xiàn)，被應(yīng)用于很多領(lǐng)域.

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

由u的任意性知：

(7)

故可得：

(8)

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

根據(jù)以上公式的推導(dǎo)結(jié)果，我們可以得到量子模糊聚類算法的迭代過程為：

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

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

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

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

2 數(shù)值實驗

我們將量子模糊聚類算法用于復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的探測，選取的實驗數(shù)據(jù)為經(jīng)典的真實網(wǎng)絡(luò)數(shù)據(jù)，即空手道俱樂部網(wǎng)絡(luò)數(shù)據(jù)[5].

2.1 空手道俱樂部網(wǎng)絡(luò)

Zachary W W[6]所研究的空手道俱樂部網(wǎng)絡(luò)被廣泛應(yīng)用于探測復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的方法中.該網(wǎng)絡(luò)包括34個節(jié)點和78條邊，分別表示的是空手道俱樂部的成員和俱樂部成員之間的相互聯(lián)系.由于俱樂部的兩個管理者之間產(chǎn)生分歧，導(dǎo)致這個俱樂部以這兩個管理者為中心，最終分裂為兩個社團(tuán).圖1為空手道俱樂部的網(wǎng)絡(luò)，其中節(jié)點1和節(jié)點34分別表示兩個管理者.

圖1 空手道俱樂部網(wǎng)絡(luò)Fig.1 Karate club network

2.2 算法的評價指標(biāo)

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

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

(9)

2.3 結(jié)果與分析

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

我們提出的基于量子模糊聚類算法的社團(tuán)探測方法的主要任務(wù)是通過最大化Q值，確定最優(yōu)核尺度參數(shù)σ，進(jìn)而確定聚類中心，最終找到社團(tuán)結(jié)構(gòu)的最優(yōu)劃分.

圖2 本文算法得到的空手道俱樂部網(wǎng)絡(luò)Fig.2 Karate club network by our algorithm

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

3 結(jié)語

本文提出了量子模糊聚類算法，進(jìn)行社團(tuán)結(jié)構(gòu)的探測.應(yīng)用于經(jīng)典的空手道網(wǎng)絡(luò)數(shù)據(jù)的實驗表明，我們的算法可以準(zhǔn)確并且有效地探測到網(wǎng)絡(luò)中實際存在的社團(tuán)結(jié)構(gòu).我們希望能將這一算法推廣到有權(quán)重和有方向的復(fù)雜網(wǎng)絡(luò)中.

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

[2] 胡寶清. 模糊數(shù)學(xué)理論基礎(chǔ)[M]. 武漢: 武漢大學(xué)出版社, 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

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

O159

A

1672-4321(2015)03-0123-03