李海威，韋天瀚

（1.廣東省財(cái)政數(shù)據(jù)信息中心，廣東廣州　510030；2.香港中文大學(xué)，香港）

基于Q函數(shù)優(yōu)化的加權(quán)有向復(fù)雜網(wǎng)絡(luò)模糊聚類算法設(shè)計(jì)研究

李海威1，韋天瀚2

（1.廣東省財(cái)政數(shù)據(jù)信息中心，廣東廣州510030；2.香港中文大學(xué)，香港）

研究加權(quán)有向復(fù)雜網(wǎng)絡(luò)中社團(tuán)的模糊聚類算法，在譜平分、FCM算法的基礎(chǔ)上，構(gòu)建新的適用于加權(quán)有向復(fù)雜網(wǎng)絡(luò)模糊劃分的Q函數(shù)，設(shè)計(jì)了復(fù)雜網(wǎng)絡(luò)模糊聚類算法，并針對(duì)FCM聚類算法結(jié)果不穩(wěn)定的現(xiàn)象進(jìn)行了算法上的改進(jìn)，使算法更適合于現(xiàn)實(shí)世界。通過(guò)實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了設(shè)計(jì)的算法，從總體上提高算法的劃分精確度，結(jié)果也趨向于穩(wěn)定。解決了從加權(quán)有向復(fù)雜網(wǎng)絡(luò)、模糊集中發(fā)現(xiàn)、劃分社團(tuán)的實(shí)際問(wèn)題。

復(fù)雜網(wǎng)絡(luò)；FCM算法；Q函數(shù)優(yōu)化；譜平分

0引言

許多研究表明，真實(shí)世界的大量網(wǎng)絡(luò)都具有社團(tuán)結(jié)構(gòu)的特征，復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)對(duì)實(shí)際系統(tǒng)有著重要的含義：在社會(huì)網(wǎng)絡(luò)中，不同的社團(tuán)結(jié)構(gòu)可使人們能深入了解他們與其他社團(tuán)結(jié)構(gòu)相區(qū)別的特質(zhì)或信仰（汪小帆，2009）；在萬(wàn)維網(wǎng)中，不同的社團(tuán)結(jié)構(gòu)可以表示不同主題的主頁(yè)集合（Gibson，1998；Flake，2002）；而在生物分子網(wǎng)絡(luò)中，不同的社團(tuán)結(jié)構(gòu)往往是不同的功能性模塊（Vespignani，2003）。而在產(chǎn)業(yè)R&D溢出網(wǎng)絡(luò)中，不同的社團(tuán)結(jié)構(gòu)代表著不同的產(chǎn)業(yè)集群（李海威，2011）。在復(fù)雜網(wǎng)絡(luò)演化的研究中，在同一社團(tuán)的節(jié)點(diǎn)很可能會(huì)逐漸連接在一起，而R&D溢出網(wǎng)絡(luò)中的節(jié)點(diǎn)表示不同的產(chǎn)業(yè)，因此在同一溢出集群的產(chǎn)業(yè)很可能由于R&D溢出而緊密關(guān)聯(lián)。R&D溢出網(wǎng)絡(luò)的聚類算法設(shè)計(jì)研究，是了解該網(wǎng)絡(luò)組織結(jié)構(gòu)和功能的重要方法，有助于理解R&D溢出內(nèi)部結(jié)構(gòu)的連接層次，對(duì)于如何科學(xué)地選擇產(chǎn)業(yè)園的進(jìn)園產(chǎn)業(yè)等具體問(wèn)題具有重要意義。

1　　算法設(shè)計(jì)

隨著復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)研究的不斷深入，現(xiàn)已發(fā)展出許多劃分復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的算法。這些算法可按照不同的標(biāo)準(zhǔn)分為不同種類：如按照社團(tuán)結(jié)構(gòu)形成過(guò)程進(jìn)行分類，算法可分為分裂算法、凝聚算法、搜索算法及其他算法（譜平分）等；按照算法的物理背景進(jìn)行分類，算法可分為基于網(wǎng)絡(luò)拓樸結(jié)構(gòu)、基于網(wǎng)絡(luò)動(dòng)力學(xué)和基于Q函數(shù)優(yōu)化及其他算法；根據(jù)節(jié)點(diǎn)是否只能屬于一個(gè)社團(tuán)進(jìn)行分類，又可分為硬聚類和模糊聚類。上述劃分社團(tuán)的算法在判斷標(biāo)準(zhǔn)、思路及步驟等方面各有不同，各有優(yōu)缺點(diǎn)，因此有些研究者進(jìn)行了對(duì)已有算法綜合的研究，并提出一些新的算法，如Newman（2006）綜合譜分析與Q函數(shù)算法等。

R&D溢出網(wǎng)絡(luò)是加權(quán)有向復(fù)雜網(wǎng)絡(luò)，且具有明顯的層次（李海威，2011）。而在上述算法中，譜平分方法對(duì)于社團(tuán)結(jié)構(gòu)較清晰的復(fù)雜網(wǎng)絡(luò)分析效率高，且理論基礎(chǔ)建立在拉普拉斯 （Laplace）矩陣之上，較適合R&D溢出網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分析。

根據(jù)Palla（2005）的研究發(fā)現(xiàn)，社團(tuán)結(jié)構(gòu)具有重疊性的重要特征。所謂重疊性是指復(fù)雜網(wǎng)絡(luò)中有部分節(jié)點(diǎn)同時(shí)屬于多個(gè)社團(tuán)，重疊性在實(shí)際網(wǎng)絡(luò)中體現(xiàn)得十分明顯。傳統(tǒng)的譜分析算法用標(biāo)準(zhǔn)化方法劃分社團(tuán)，也就是說(shuō)一個(gè)節(jié)點(diǎn)只能歸屬于一個(gè)社團(tuán)，但R&D溢出網(wǎng)絡(luò)由許多互相重疊的社團(tuán)構(gòu)成，也就是說(shuō)一個(gè)產(chǎn)業(yè)可能同時(shí)屬于多個(gè)社團(tuán)，因此模糊聚類方法劃分的社團(tuán)更能體現(xiàn)重疊性特征。

綜上所述，根據(jù)R&D溢出網(wǎng)絡(luò)特點(diǎn)，本文參照Newman（2006）及張世華等人（2007）的方法，綜合譜分析方法及模糊c-均值聚類方法劃分R&D溢出網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)，然后用Q函數(shù)優(yōu)化法選出最優(yōu)的劃分方法，進(jìn)行R&D溢出網(wǎng)絡(luò)的聚類算法設(shè)計(jì)研究。

1.1譜平分算法

譜平分方法是建立在鄰接矩陣基礎(chǔ)上的，主要思路是對(duì)鄰接矩陣形成的Laplace矩陣（或標(biāo)準(zhǔn)矩陣）的特征值、特征向量進(jìn)行分析，從而尋找社團(tuán)結(jié)構(gòu)（capocci，2005）。傳統(tǒng)的譜平分方法是基于Laplace矩陣，計(jì)算速度快，但前提條件是已知社團(tuán)個(gè)數(shù)。其在使用時(shí)有較大限制，因此，Capocci（2005）提出改進(jìn)算法。該算法與傳統(tǒng)譜平分算法不同，是基于標(biāo)準(zhǔn)矩陣N= K-1A。N的最大特征值總為1，其相應(yīng)的特征向量稱作平凡特征向量（trivial eigenvector）。Capocci等人（2005）還將譜平分算法擴(kuò)展至加權(quán)有向網(wǎng)絡(luò)。

1.2模糊c-均值聚類算法

模糊聚類方法中應(yīng)用最廣的是基于目標(biāo)函數(shù)的模糊c均值聚類算法FCM（Fuzzy c-mean），Bezdek （1981）提出并建立了模糊c均值聚類理論。模糊聚類問(wèn)題實(shí)質(zhì)上是數(shù)學(xué)集合論問(wèn)題。通常在實(shí)際應(yīng)用中，還需要定義相似性或相異性的劃分準(zhǔn)則（目標(biāo)函數(shù)），以及分析集合元素與模糊子集之間的相似度或失真度（目標(biāo)函數(shù)距離最?。瑥亩卸显鼐唧w隸屬于哪個(gè)模糊子集。而FCM則是建立在c均值目標(biāo)函數(shù)的基礎(chǔ)上。

FCM將n個(gè)向量xj∈X（1,2…,n）分成c個(gè)組Gi，并計(jì)算每組的聚類中心，使得c均值目標(biāo)函數(shù)達(dá)到最小。FCM通過(guò)分析每個(gè)給定元素的隸屬度來(lái)確定其屬于各分組的程度。隸屬度取值在［0，1］之間，每個(gè)元素的隸屬度總和等于1。至于加權(quán)指數(shù)m的選擇，Pal等人（1993）在聚類有效性實(shí)驗(yàn)中研究中得出m的最優(yōu)選取區(qū)間為［1.5，2.5］，不作特殊要求情況下可取區(qū)間中值2，因此本文取m=2。

1.3 Q函數(shù)優(yōu)化法

根據(jù)譜平分算法和FCM，我們可以得到多個(gè)網(wǎng)絡(luò)社團(tuán)劃分，但仍難以判斷劃分的社團(tuán)是否合理有效。因此，本文將參考Newman等人（2006）提出了Q函數(shù)優(yōu)化法，構(gòu)造適用于R&D溢出網(wǎng)絡(luò)的Q函數(shù)度量社團(tuán)劃分的合理性。fortunato（2010）歸納了加權(quán)無(wú)向圖、無(wú)權(quán)有向圖及加權(quán)有向圖的硬劃分（每個(gè)節(jié)點(diǎn)只屬于某個(gè)社團(tuán)）情況下的Q函數(shù)。Nicosia等人（2009）還分析了Q函數(shù)的兩個(gè)最重要的性質(zhì)：性質(zhì)1是當(dāng)所有節(jié)點(diǎn)都同屬于一個(gè)社團(tuán)的時(shí)候，Q=0；性質(zhì)2是Q值越高，則社團(tuán)結(jié)構(gòu)的劃分越合理。并證明了式（6-13）所定義的Q函數(shù)是滿足以上重要性質(zhì)的。

由于R&D溢出網(wǎng)絡(luò)為加權(quán)有向圖，因此本文在fortunato和Nicosia等人的研究基礎(chǔ)上，提出加權(quán)有向圖的模糊劃分Q函數(shù)為：

下面我們分析式（1）定義的Q函數(shù)的性質(zhì)：

1）在所有節(jié)點(diǎn)都同屬于一個(gè)社團(tuán)的情況下，聚類數(shù)為1，Q=0?？梢姸x的Q函數(shù)滿足性質(zhì)1。

2）若網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)特征較顯著時(shí)，若兩個(gè)節(jié)點(diǎn)同屬于一個(gè)社團(tuán)，這時(shí)該兩個(gè)節(jié)點(diǎn)的隸屬度大小是相近的，從而產(chǎn)生的Q函數(shù)值為最大值，也就是說(shuō)定義的Q函數(shù)滿足模塊性函數(shù)的第二個(gè)性質(zhì)。

綜上所述，式（1）滿足Q函數(shù)最重要的二個(gè)性質(zhì)，因此本文將用式（1）構(gòu)造的Q函數(shù)度量R&D溢出網(wǎng)絡(luò)社團(tuán)劃分的合理性。

1.4 R&D溢出網(wǎng)絡(luò)社團(tuán)算法

R&D溢出網(wǎng)絡(luò)社團(tuán)算法的思路是通過(guò)譜平分算法生成特征矩陣，然后運(yùn)用FCM聚類算法進(jìn)行聚類，并使模塊性指標(biāo)達(dá)到最大，最后選擇Q值最大的社團(tuán)劃分結(jié)果?；静襟E如下：

2）計(jì)算標(biāo)準(zhǔn)矩陣Y=D-1WWT。

3）計(jì)算Yx=λx下的最大的K個(gè)特征值，并將其所對(duì)應(yīng)的特征向量e1,e2,...,ek組成的矩陣Ek，其中K是社團(tuán)數(shù)量的上界。

4）初始化k=2，并選擇e1,e2,...,ek組成的矩陣Ek，在歐式范數(shù)下標(biāo)準(zhǔn)化的行向量。

5）使用FCM算法對(duì)Ek進(jìn)行聚類，并劃分R&D溢出網(wǎng)絡(luò)為k個(gè)社團(tuán)。

6）依據(jù)事先確定的閾值u，在計(jì)算得出的模糊隸屬矩陣中確定社團(tuán)結(jié)構(gòu)，在本文中，閾值u為社團(tuán)個(gè)數(shù)的倒數(shù)（1/k）。

7）令k增1，重復(fù)步驟3，4，5，直到k=K。

8）對(duì)于R&D溢出網(wǎng)絡(luò)的K-1種劃分結(jié)果，計(jì)算其Q函數(shù)值。

由于采用FCM算法進(jìn)行聚類時(shí)，需生成值在0,1之間的隨機(jī)數(shù)來(lái)初始化隸屬矩陣，因此會(huì)導(dǎo)致單次聚類結(jié)果不穩(wěn)定，出現(xiàn)誤差。為減小聚類結(jié)果的誤差，對(duì)上述算法進(jìn)行改進(jìn)，具體如下：

1）設(shè)定執(zhí)行次數(shù)p，執(zhí)行上述算法m次，計(jì)算m 次Q函數(shù)值的平均值。

2）選擇Q函數(shù)平均值最大的劃分方式n。

3）初始化L=1，初始化零矩陣U0。

4）在選擇了最優(yōu)的劃分方式后，初始化k=n，執(zhí)行FCM算法，得到模糊隸屬矩陣UL。

5）對(duì)模糊隸屬矩陣UL的列按從大到小次序排序。

6）令UL=UL+UL-1。

7）令L增1，重復(fù)步驟4和5，直至L=p。

8）計(jì)算Up/p，得到模糊隸屬矩陣元素的平均值。

2　　實(shí)驗(yàn)結(jié)果

由于R&D溢出網(wǎng)絡(luò)關(guān)鄰矩陣D存在行為0的數(shù)據(jù)，因此D的逆矩陣不存在，即D為奇異。如果直接對(duì)D進(jìn)行標(biāo)準(zhǔn)化會(huì)出現(xiàn)錯(cuò)誤，因此需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，使其能夠運(yùn)用上述算法進(jìn)行模糊聚類。我們對(duì)w中的每個(gè)元素進(jìn)行極小量的偏移。使用MATLAB7.0軟件按上述算法設(shè)計(jì)程序，將R&D溢出網(wǎng)絡(luò)的關(guān)鄰矩陣W作為初始數(shù)據(jù)，代入到設(shè)計(jì)的程序中去運(yùn)行。運(yùn)行100次后發(fā)現(xiàn)：當(dāng)社團(tuán)數(shù)目k=3，加權(quán)指數(shù)m=2時(shí)，對(duì)應(yīng)的模塊性Q函數(shù)平均值為最大值。社團(tuán)數(shù)為3時(shí)Q函數(shù)平均值達(dá)到0.61，遠(yuǎn)超過(guò)Q函數(shù)值的下限0.3，劃分結(jié)果可信。這說(shuō)明將39個(gè)產(chǎn)業(yè)部門劃分為3個(gè)社團(tuán)是最優(yōu)的劃分結(jié)果，能夠充分體現(xiàn)社團(tuán)內(nèi)部的關(guān)聯(lián)較緊密，而社團(tuán)之間的關(guān)聯(lián)較稀疏的特點(diǎn)。而運(yùn)行100次得到的平均模糊隸屬矩陣與運(yùn)行1000次得到的平均模糊隸屬矩陣結(jié)果一致，表明算法運(yùn)行100次后結(jié)果趨于穩(wěn)定。通過(guò)以上實(shí)驗(yàn)得出本文設(shè)計(jì)的算法在加權(quán)有向復(fù)雜網(wǎng)絡(luò)社區(qū)劃分問(wèn)題上的有效性，其檢測(cè)結(jié)果穩(wěn)定。

3　　結(jié)束語(yǔ)

在實(shí)際的復(fù)雜網(wǎng)絡(luò)中，社團(tuán)往往是模糊集。本文在譜平分、FCM算法的基礎(chǔ)上，構(gòu)建新的適用于加權(quán)有向復(fù)雜網(wǎng)絡(luò)模糊劃分Q函數(shù)，設(shè)計(jì)了復(fù)雜網(wǎng)絡(luò)模糊聚類算法，并針對(duì)FCM聚類算法結(jié)果不穩(wěn)定的現(xiàn)象進(jìn)行了算法上的改進(jìn)，使算法更適合于現(xiàn)實(shí)世界。最后，通過(guò)實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了設(shè)計(jì)的算法，結(jié)果從總體上提高算法的劃分精確度，結(jié)果也趨向于穩(wěn)定。本文設(shè)計(jì)的算法解決了從加權(quán)有向復(fù)雜網(wǎng)絡(luò)、模糊集中發(fā)現(xiàn)、劃分社團(tuán)的問(wèn)題。

［1］Bezdek J C. Pattern Recognition with Fuzzy Objective Function Algorithms［M］. New York：Plenum Press，1981.

［2］Capocci A,Servedio V D P，Caldarelli G，Colaiori F. Detecting communities in large networks［J］. Physica A，2005（7），352：669-676.

［3］Flake G W，Lawrence S R，Giles C L，et a.l：Self-organization and identification of web communities［J］. IEEE Computer，2002，35（3）：66-71.

［4］Fortunato S. Community detection in graphs. Physics Report［J］. 2010，486（2）：75-174.

［5］Gibson D，Kleinberg J，Raghavan P. Inferringweb communities from link topology［C］.//Proceedings of the 9th ACM Conference on Hypertext and Hypermedia. Pittsburgh：ACM Press，1998：225-234.

［6］HE D，JIN D，Baquero C，et a.l：Link Community Detection Using Generative Model and Nonnegative Matrix. Factorization［J］．PLOS ONE，2014，9（1）：e86899．

［7］Girvan M，Newman M E J. Community structure in social and biological networks［J］. Proc Natl A cad SciUSA，2002，99（12）：7821-7826.

［8］Newman M E J. Finding community structure in networks using the eigenvectors of matrices［J］. Phys Rev E，2006，74（3）：36104.

［9］Newman M E J. Modularity and community structure in networks［J］. Proc Natl A cad SciUSA，2006，103（23）：8577-8582.

［10］Nicosia V，Mangnioni G，Carchiolo V，Malgeri M. Extending the definition of modularity to directed graphs with overlapping communities［J］. physics，2009（3）：1-22

［11］Pal N R，Bezdek J C，Tsao E C K. Generalized clustering networks and Kohonen's self-organization［J］. IEEE Trans，1993，4（4）：549-557.

［12］Palla G，Derenyi I，F(xiàn)arkas I，et al. Uncovering the overlapping community structure of complex networks in nature and society［J］. Nature，2005，435（7043）：814-818.

［13］Pizzuti C，Rombo S E．Algorithms and Tools for Protein-Protein Interaction Networks Clustering，with a Special Focus on Populationbased Stochastic Methods［J］. Bioinformatics，2014，30（10）：1343-1352．

［14］Vespignani A. Evolution thinks modular［J］. Nature Gen，2003，35 （2）：118-119.

［15］Zhang S H，Wang R S，Zhang X S. Identification of overlapping community structure in complex networks using fuzzy c-means clustering［J］. Physica A，2007，374（1）：483-490.

［16］李海威. R&D溢出與產(chǎn)業(yè)發(fā)展關(guān)系研究［D］.中山大學(xué)，2011.

［17］汪小帆，劉亞冰.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)算法綜述［J］.電子科技大學(xué)學(xué)報(bào)，2009，38（5）：537-543.

李海威（1979-），男，高級(jí)工程師，博士，研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、聚類算法研究；韋天瀚（1994-），男，香港中文大學(xué)信息工程學(xué)院在讀本科生。