牛艷慶

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

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

牛艷慶

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

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

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

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

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

1 量子模糊聚類算法

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

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

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

(1)

其中V(·)為量子勢(shì)能函數(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為類別個(gè)數(shù).利用拉格朗日乘數(shù)法可得：

(5)

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

(6)

由u的任意性知：

(7)

故可得：

(8)

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

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

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

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

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

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

2 數(shù)值實(shí)驗(yàn)

我們將量子模糊聚類算法用于復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的探測(cè)，選取的實(shí)驗(yàn)數(shù)據(jù)為經(jīng)典的真實(shí)網(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)用于探測(cè)復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的方法中.該網(wǎng)絡(luò)包括34個(gè)節(jié)點(diǎn)和78條邊，分別表示的是空手道俱樂部的成員和俱樂部成員之間的相互聯(lián)系.由于俱樂部的兩個(gè)管理者之間產(chǎn)生分歧，導(dǎo)致這個(gè)俱樂部以這兩個(gè)管理者為中心，最終分裂為兩個(gè)社團(tuán).圖1為空手道俱樂部的網(wǎng)絡(luò)，其中節(jié)點(diǎn)1和節(jié)點(diǎn)34分別表示兩個(gè)管理者.

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

2.2 算法的評(píng)價(jià)指標(biāo)

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

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

(9)

2.3 結(jié)果與分析

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

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

3 結(jié)語

本文提出了量子模糊聚類算法，進(jìn)行社團(tuán)結(jié)構(gòu)的探測(cè).應(yīng)用于經(jīng)典的空手道網(wǎng)絡(luò)數(shù)據(jù)的實(shí)驗(yàn)表明，我們的算法可以準(zhǔn)確并且有效地探測(cè)到網(wǎng)絡(luò)中實(shí)際存在的社團(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-)，女，講師，博士，研究方向：智能計(jì)算，E-mail: niuyanqing2005@hotmail.com

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

O159

A

1672-4321(2015)03-0123-03