李海威，韋天瀚

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

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

李海威1，韋天瀚2

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

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

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

0引言

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

1　　算法設計

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

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

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

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

1.1譜平分算法

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

1.2模糊c-均值聚類算法

模糊聚類方法中應用最廣的是基于目標函數(shù)的模糊c均值聚類算法FCM（Fuzzy c-mean），Bezdek （1981）提出并建立了模糊c均值聚類理論。模糊聚類問題實質(zhì)上是數(shù)學集合論問題。通常在實際應用中，還需要定義相似性或相異性的劃分準則（目標函數(shù)），以及分析集合元素與模糊子集之間的相似度或失真度（目標函數(shù)距離最?。?，從而判定集合元素具體隸屬于哪個模糊子集。而FCM則是建立在c均值目標函數(shù)的基礎上。

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

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

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

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

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

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

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

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

1.4 R&D溢出網(wǎng)絡社團算法

R&D溢出網(wǎng)絡社團算法的思路是通過譜平分算法生成特征矩陣，然后運用FCM聚類算法進行聚類，并使模塊性指標達到最大，最后選擇Q值最大的社團劃分結(jié)果。基本步驟如下：

2）計算標準矩陣Y=D-1WWT。

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

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

5）使用FCM算法對Ek進行聚類，并劃分R&D溢出網(wǎng)絡為k個社團。

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

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

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

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

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

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

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

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

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

6）令UL=UL+UL-1。

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

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

2　　實驗結(jié)果

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

3　　結(jié)束語

在實際的復雜網(wǎng)絡中，社團往往是模糊集。本文在譜平分、FCM算法的基礎上，構(gòu)建新的適用于加權有向復雜網(wǎng)絡模糊劃分Q函數(shù)，設計了復雜網(wǎng)絡模糊聚類算法，并針對FCM聚類算法結(jié)果不穩(wěn)定的現(xiàn)象進行了算法上的改進，使算法更適合于現(xiàn)實世界。最后，通過實驗數(shù)據(jù)驗證了設計的算法，結(jié)果從總體上提高算法的劃分精確度，結(jié)果也趨向于穩(wěn)定。本文設計的算法解決了從加權有向復雜網(wǎng)絡、模糊集中發(fā)現(xià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ā)展關系研究［D］.中山大學，2011.

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

李海威（1979-），男，高級工程師，博士，研究方向為復雜網(wǎng)絡、聚類算法研究；韋天瀚（1994-），男，香港中文大學信息工程學院在讀本科生。