基于優(yōu)化的復雜網(wǎng)絡聚類方法綜述*

曾 成，孫雅倩，徐玉珠，張達敏

(貴州大學大數(shù)據(jù)與信息工程學院，貴州 貴陽 550025)

0 引言

聚類方法的分析在諸多領域是非常重要的，在復雜網(wǎng)絡研究方面也是相當關鍵的。分析中得到的數(shù)據(jù)簇(Cluster)稱之為群(Group)或社團(Community)。研究指出，在復雜網(wǎng)絡中，無論是大型還是小型的，簇內(nèi)部不同節(jié)點之間一定有著關聯(lián)。對復雜網(wǎng)絡里面的聚類特點進行分析研究，就可以得到網(wǎng)絡中節(jié)點與節(jié)點之間存在的某種關系［1－5］。

當前對于復雜網(wǎng)絡聚類算法的研究已有很多不同算法。這些算法可以分為兩種基本類別:首先是基于優(yōu)化的方法(Optimization Method);再者就是啟發(fā)式方法(Heuristic Method)［6－10］。其中基于優(yōu)化是把優(yōu)化這類問題運用到復雜網(wǎng)絡聚類上。后者則把對預定義設計啟發(fā)式規(guī)則這種方法在一定程度上應用于解決復雜網(wǎng)絡聚類問題。對于基于優(yōu)化的復雜聚類方法，細分為譜方法和局部搜索方法兩種。本文主要介紹一些著名學者研究的比較經(jīng)典的基于優(yōu)化的復雜網(wǎng)絡聚類方法，以及近年來一些新的改進算法及這類方法的實際應用。同時分析、總結(jié)了這些新型算法的優(yōu)缺點，提出現(xiàn)有研究中存在的問題以及對未來的展望［10－14］。

1 經(jīng)典的基于優(yōu)化聚類方法

1.1 譜方法

譜方法是將二次型優(yōu)化這個方法對被截的函數(shù)采用最小化預定義。被截的函數(shù)是指當一個網(wǎng)絡一分為二時它所分成的兩個子網(wǎng)間的連接程度的密度大小。當被分割出來的網(wǎng)絡的被截函數(shù)最小時，則就可以判斷這個分割是最優(yōu)的網(wǎng)絡分割。

1.1.1 基于Normal矩陣的譜平分法

基于經(jīng)典的譜分析法，Capocci等人在2005年研究了一個新的算法，即基于Normal矩陣的社團發(fā)現(xiàn)算法［15］。算法中 Nmoral矩陣 N=K－1A，式中 K是一個對角矩陣，kii=aij對應不同節(jié)點的度，網(wǎng)絡中節(jié)點的個數(shù)用n表示;A則為該網(wǎng)絡的連接矩陣?？梢灾溃仃嘚是半正定矩陣，其實特征值有n個且最大為1。如要獲得網(wǎng)絡的簇結(jié)構(gòu)則需要對各個不同特征向量里的元素進行對比。為此，可以設計一個連接參量來對社團的優(yōu)良進行判別:

其中，〈.〉是對各個不同的特征向量里的元素取平均值，節(jié)點i和j的連接度用rij來判別。效果的好壞取決于特征向量的平均值。

1.2 局部搜索方法

Kernighan－Lin算法(簡稱KL算法)、快速Newman算法(簡稱FN算法)和Guimera－Amaral算法(簡稱GA算法)在基于局部搜索優(yōu)化的方法是最具有代表性的算法。目標函數(shù)、候選解的搜索策略和最優(yōu)解的搜索策略是此算法里的三個基本部分。

1.2.1 Kernighan －Lin 算法

Kernighan和Lin等人在70年代初提出了KL算法［16］，這個方法在圖分割問題和復雜網(wǎng)絡聚類上都得到了很好的運用。KL算法是對極小化社團間相連個數(shù)與社團內(nèi)部相連個數(shù)之差進行優(yōu)化;對于其候選解這一搜索策略具體為:將網(wǎng)絡內(nèi)不同社團之間的節(jié)點進行隨機交換或者把節(jié)點進行轉(zhuǎn)移，改變到另外的社團。從解的最初開始，KL算法在迭代過程中都會經(jīng)歷得到、判斷、選擇，停止的條件，從目前的解出發(fā)搜索到更優(yōu)的候選解。KL算法在搜索時只選擇更優(yōu)的解，排斥所有較劣的解，所以它搜索到的解一般情況是局部最優(yōu)解而非全局最優(yōu)解。

1.2.2 快速Newman算法

2004年，Newman提出了快速復雜網(wǎng)絡聚類算法FN［17］，此方法是基于局部搜索的。其目的是將Newman和Girvan提出的網(wǎng)絡模塊性評價函數(shù)也就是Q函數(shù)進行極大化的優(yōu)化。Q函數(shù)的原始意義為社團內(nèi)真實相連的個數(shù)與隨機相連條件下社團內(nèi)期望相連個數(shù)的差，此函數(shù)可以用來定量的表示出網(wǎng)絡社團結(jié)構(gòu)的好與壞，它的形式如下:

1.2.3 Guimera －Amaral算法

與FN算法優(yōu)化目標相似的是，Guimera和Amaral在2005年提出了基于模擬退火算法(Simulated Annealing，SA)的復雜網(wǎng)絡聚類算法GA，并把這一方法在一定程度上運用于新陳代謝網(wǎng)絡研究中［18］。與KL算法相似的是，從解的最初開始，GA算法在迭代過程中都會經(jīng)歷得到、判斷、選擇，停止的條件是從當前解開始，一直搜索到找不到更優(yōu)的候選解。GA算法計算出候選解的具體方法是:將網(wǎng)絡內(nèi)不同社團之間的節(jié)點進行隨機交換或者把節(jié)點進行轉(zhuǎn)移，改變到另外的社團，然后對網(wǎng)絡社團合并或分解。GA采用的Metropolis準則定義如下:

其中，Ct=－Qt，p表示接受t+1時刻選解的概率;T表示t+1時刻的系統(tǒng)溫度。

1.2.4 GAS 算法

針對目前基于遺傳算法(GA)的社團檢測算法［19］大多存在尋優(yōu)能力弱并且收斂慢的問題，2010年提出來一種改進的GAS算法［8］?；凇班徑墓?jié)點更加偏向聚在同一個簇里面”的現(xiàn)象，該算法在傳統(tǒng)的基于0函數(shù)優(yōu)化的GA算法框架中增加了“局部搜索算子”。GAS算法在優(yōu)化Q函數(shù)過程中利用了節(jié)點的鄰居節(jié)點信息，與傳統(tǒng)算法相比，GAS算法搜索相對更快且更有效。

2 基于優(yōu)化聚類方法的改進

2.1 基于PSO的復雜網(wǎng)絡聚類算法

文獻［20］基于譜方法的基本原理，設計出了基于PSO聚類的復雜網(wǎng)絡社團結(jié)構(gòu)算法。此算法的基本思想是將復雜網(wǎng)絡聚類問題變成空間數(shù)據(jù)的聚類問題，為此首先可以運用的是譜方法里面的A－cut方法或N－cut方法;通過應用這兩種方法將復雜網(wǎng)絡里的社團結(jié)構(gòu)信息變成由非平凡特征向量組成的空間數(shù)據(jù)集。原來復雜網(wǎng)絡里的每一個節(jié)點被對應于這個空間數(shù)據(jù)集里面產(chǎn)生的每一個數(shù)據(jù)樣本。復雜網(wǎng)絡中節(jié)點的社團信息來自于對這個空間數(shù)據(jù)集里面的每一個數(shù)據(jù)樣本進行聚類，然后由此可以完成對復雜網(wǎng)絡的聚類。文獻［20］把粒子群優(yōu)化算法運用到復雜網(wǎng)絡聚類里，PSO聚類算法有效結(jié)合了譜方法里面的平均截方法和規(guī)范截方法，進而產(chǎn)生了更加優(yōu)異的復雜網(wǎng)絡聚類算法。讓譜方法的聚類精度與穩(wěn)定性在復雜網(wǎng)絡聚類里得到了大幅度提高。

2.2 FNCA 算法

目前對于Q函數(shù)的聚類算法的研究絕大多數(shù)都是在全局的基礎上進行的，經(jīng)典的聚類方法都是要設計一種高效的搜索策略來改良Q函數(shù)，將其進行優(yōu)化。但是因為這些搜索策略在搜索過程中每進行一步都會用到全局的網(wǎng)絡拓撲信息，所以它們的搜索效率一般情況下是相對低的。針對這一問題，不同與已有方法，文獻［21］試圖從局部觀點出發(fā)，使網(wǎng)絡中每個節(jié)點獨立計算并優(yōu)化自身的局部函數(shù)，并Q函數(shù)進行分析，此函數(shù)是面向全局網(wǎng)絡的目標函數(shù)，由此可以推導出一個f函數(shù)(針對的是網(wǎng)絡里面的每一個節(jié)點的目標函數(shù))，此函數(shù)具有局部特征，并證明Q函數(shù)是跟著網(wǎng)絡中每一個節(jié)點的f函數(shù)呈單調(diào)遞增趨勢的，最后導出一個基于f函數(shù)的快速網(wǎng)絡聚類算法，即FNCA(Fast Network Clustering Algorithm)算法。

給定一個無向無權(quán)網(wǎng)絡N(V，E)，假設點集V被劃分(聚類)為若干個類簇。若網(wǎng)絡中任一結(jié)點i的標簽為r(i)，所屬的類簇為cr(i)，Q則函數(shù)可定義為:

網(wǎng)絡中所有節(jié)點的f函數(shù)之和用Q函數(shù)來表示。在其他節(jié)點標簽不變的情況下，如果由于網(wǎng)絡里面的任一節(jié)點標簽的變化讓其f函數(shù)值變大，那么這個變化就會直接引起Q函數(shù)值的變大。根據(jù)上述理論基礎，提出了一個基于局部優(yōu)化的快速網(wǎng)絡聚類算法，即FNCA算法。

2.3 聚類算法FEC的改進

經(jīng)典的FEC算法里面的發(fā)現(xiàn)簇(Finding Community，F(xiàn)C)算法對節(jié)點給出的隨機游走步數(shù)參數(shù)值提出了一定的要求，實驗最后的聚類結(jié)果受步數(shù)大小的影響。孔令旗［22］根據(jù)步數(shù)的經(jīng)驗值提出了一個區(qū)間，即［6，20］。其中區(qū)間開始的6代表復雜網(wǎng)絡里面不同節(jié)點之間的平均路徑長度(很大一部分網(wǎng)絡都會受六度分離理論的影響);區(qū)間結(jié)束的20則代表網(wǎng)絡的直徑(研究表明萬維網(wǎng)是目前最大的復雜網(wǎng)絡，它的直徑經(jīng)測試為19)。分析認為把步數(shù)的區(qū)間設置為10到20就可以覆蓋絕大部分網(wǎng)絡聚類分析［23］。孔令旗等人提出了“簇內(nèi)短回路豐富”這一啟發(fā)式策略。因為社團內(nèi)部的正連接相對緊密，且社團與社團之間的正連接比較疏散，同一社團內(nèi)頂點節(jié)點，通過正連接組成三角形和四邊形的概率要遠大于不同社團間的概率。研究提出的“簇內(nèi)短回路豐富”這一啟發(fā)式策略結(jié)合頂點度極值，將會很好的幫助選擇更“優(yōu)”的目標節(jié)點。

2.4 基于連接強度的復雜網(wǎng)絡聚類算法

丁轉(zhuǎn)蓮于2014年研究出了基于連接強度的種群初始化方法［24］，GA的初始種群對算法搜索效率具有一定的影響。相比于完全隨機的初始化，若初始種群已具有一定的聚類精度，同時種群的多樣性又能較好地得到保持，則有利于局部搜索策略的局部搜索能力充分發(fā)揮，且減少了不必要的迭代，加速了算法收斂。與現(xiàn)有基于GA的網(wǎng)絡聚類算法的隨機初始化種群的方法不同，本文提出了基于連接強度的種群初始化方法(JSPI)。JSPI主要思路為:計算每個節(jié)點與網(wǎng)絡已搜索到的社團的連接強度，并將該節(jié)點加入到連接強度最大的社團。

3 基于優(yōu)化聚類方法的應用

3.1 CNM算法在優(yōu)化RBF神經(jīng)網(wǎng)絡上的應用

在Newman提出的快速聚類算法的基礎上，Clauset、Newman和Moore等人將堆的數(shù)據(jù)結(jié)構(gòu)用在計算和更新復雜網(wǎng)絡的模塊度上，由此提出了一種新的貪婪算法，即CNM算法［25］，以此來優(yōu)化 RBF神經(jīng)網(wǎng)絡。此算法的復雜度僅有O(n log2n)，非常接近線性復雜性。文獻［15］根據(jù)CNM算法［25］提出了新的聚類算法，對數(shù)據(jù)集的先驗知識可以完全的置之不理，然后還能自動進行社團的合并及分割是它最重要的特點。文獻［26］的算法提出，合適的相似度量的選取最主要的是根據(jù)原始數(shù)據(jù)的特征來進行，此文獻算法相似度量在算法的思想上選取的是歐式距離:

然后，想要得到它們間的相似度矩陣R，則必須根據(jù)歐式距離來對數(shù)據(jù)對象間的相似度進行計算。本文將CNM聚類算法優(yōu)點充分的運用到對RBF神經(jīng)網(wǎng)絡的優(yōu)化上面，進而形成了基于CNM聚類的RBF算法，相比較于基于k－均值的RBF算法，此方法在提高網(wǎng)絡質(zhì)量和穩(wěn)定性上有了更好的改善，而且在精度上也得到了大大的提高。

3.2 在蛋白質(zhì)相互作用網(wǎng)絡中的應用

SCAN(Structural Clustering Algorithm for Networks)這種方法是由Mutlu Mete等人首先運用到復雜生物網(wǎng)絡上的，能夠很好地從復雜網(wǎng)絡中尋求出簇和每一個功能模塊，還能夠以結(jié)點的形式把所取結(jié)構(gòu)分類為不一樣的角色(比如Hubs和Outliers)。采用芽酵母蛋白質(zhì)交互網(wǎng)絡做了一個分析實驗，并且對比了其中的簇和原本的功能蛋白質(zhì)。這樣就證明了此算法的有效性，并且驗證了聚類結(jié)果，由此可以驗證預測的功能模塊有著很好的純度。經(jīng)過后來學者的分析得出，此算法屬于線性時間算法。后來，Mutlu Mete等人把SCAN算法與經(jīng)典的CNM算法做了一個對比分析，有效地檢測出了基因本體項(GO terms)所注釋的功能組有最小p值的前10個簇，從這能看出SCAN算法比CNM算法能更精確地分割網(wǎng)絡。

4 總結(jié)與展望

本文對經(jīng)典和最新的基于優(yōu)化的聚類方法進行了對比分析，得出以下結(jié)論:雖然經(jīng)過各國學者的多年研究，但復雜網(wǎng)絡聚類問題還存在諸多亟待解決的問題:(1)網(wǎng)絡簇結(jié)構(gòu)的本質(zhì)含義一直沒有被理解透徹。包括網(wǎng)絡簇結(jié)構(gòu)的形成經(jīng)過;與網(wǎng)絡其他復雜現(xiàn)象的聯(lián)系如何;與網(wǎng)絡自身的哪一類內(nèi)在屬性相互關聯(lián);(2)現(xiàn)今研究的復雜網(wǎng)絡聚類方法只能同時滿足計算速度、聚類精度高、無監(jiān)督(即不依賴先驗知識、對參數(shù)不敏感)中的一種，存在著局限性。通過定性和定量分析，比較現(xiàn)有主要研究方法就可看出，具有很高時間復雜性的方法一般是聚類精度高的方法，但如果計算速度加快，那么精度就會降低，對參數(shù)和先驗知識的需求也會增加;(3)伴隨復雜網(wǎng)絡聚類方法的發(fā)展，其應用范圍也逐漸拓寬，這對復雜網(wǎng)絡聚類方法的要求也逐漸提高。如今的復雜網(wǎng)絡聚類方法已經(jīng)比較陳舊，也出現(xiàn)了很多相關問題，諸如動態(tài)復雜網(wǎng)絡聚類、高維復雜網(wǎng)絡聚類和分布式復雜網(wǎng)絡聚類等;設計出基于特殊類型的復雜網(wǎng)絡的新型復雜網(wǎng)絡聚類方法。

［1］汪小帆.復雜網(wǎng)絡理論及其應用［M］.北京:清華大學出版社，2006.4 －5.WANG Xiao－fan.Complex Network Theory and Its Application［M］.Beijing:Tsinghua University Press，2006:4－5.

［2］Duch J，Arenas A.Community Detection in Complex Networks using Extreme Optimization.Physical Review E，2005，72(2):027104.

［3］楊博，劉大有，LIU Jiming等.復雜網(wǎng)絡聚類方法［J］.軟件學報，2009，20(1):54 －66.YANG Bo，LIU Da － you，LIU Jiming，et al.Complex Network Clustering Method［J］.Journal of Software，2009，20(1):54 －66.

［4］潘幕，金杰，王崇駿等.社會網(wǎng)絡中基于局部信息的邊社團挖掘［J］.電子學報，2013，40(11):2255 －2263.PAN Mu，JIN Jie，WANG Cong － jun，et al.Local Information based Side Community Mining in Social Networks［J］.Journal of Electronic，2013，40(11):2255 －2263.

［5］Kim Y，Jeong H.Map Equation for Link Communities［J］.Physical Review E，2011，84(2):026110.

［6］HUANG Lei，WANG Guo，WANG Yang，et al.Link Clustering with Extended Link Similarity and EQ Evaluation Division［J］.PloS one，2013，8(6):e66005.

［7］LEI Xin，WU Shu，Ge Lei，et al.Clustering and Overlapping Modules Detection in PPI Network based on IBFO［J］.Proteomics，2013，13(2):278 －290.

［8］Lancichinetti A，F(xiàn)ortunato S.Benchmarks for Testing Community Detection Algorithms on Directed and Weighted Graphs with Overlapping Communities［J］.Physical Review E，2009，80(1):016118.

［9］Pizzuti C，Rombo S E.Algorithms and Tools for Protein－Protein Interaction Networks Clustering，with a Special Focus on Population － based Stochastic Methods［J］.Bioinformatics，2014，30(10):1343－1352.

［10］ZHOU Dong，Councill I，Giles CL.Discovering Temporal Communities from Social Network Documents.In:Shi Y，Clifton CW，eds.Proc.of the 7th IEEE Int’l Conf.on Data Mining.New York:IEEE Society，2007.745－750.

［11］JIN Dong.Genetic Algorithm with Local Search for Community Mining in Complex Networks［A］.Proceedings of the 22th International Conference on Tools with Artificial Intelligence(ICTAI’10)［C］.Arras，F(xiàn)rance:IEEE Press，2010.105 －112.

［12］Leskovec J.Statistical Properties of Community Structure in Large Social and Information Networks［A］.Proceedings of the 17th International Conference on World Wide Web(WWW’08)［C］.Beijing，China:ACM Press，2008.695－704.

［13］汪小帆，劉亞冰.復雜網(wǎng)絡中的社團結(jié)構(gòu)算法綜述［J］.電子科技大學學報，2009，38(5).WANG Xiao－fan，LIU Ya－bin.Overview of Community Structure Algorithms in Complex Networks［J］.Journal of Electronic Science and Technology University，2009，38(5).

［14］Guimera R，Amaral Lan.Functional Cartography of Complex Metabolic Networks. Nature，2005，433(7028):895－900.

［15］郭陶.一種改進的加權(quán)復雜網(wǎng)絡聚類方法［J］.計算機科學，2012，39(6A).GUO Tao.An Improved Weighted Complex Network Clustering Method［J］.Computer Science，2012，39(6A).

［16］Newman MEJ.Detecting Community Structure in Networks.European Physical Journal(B)，2004，38(2):321－330.

［17］Newman MEJ.Fast Algorithm for Detecting Community Structure in Networks.Physical Review E，2004，69(6):066133.

［18］Reichardt J，Bornholdt S.Detecting Fuzzy Community Structures in Complex Networks with a Potts Model.Physical Review Letters，2004，93(19):218701.

［19］LI S Z，CHEN Y H，DU H F，et al.A Genetic Algorithm with Local Search Strategy for Improved Detection of Community Structure［J］.Complexity，2010，15(4):53－60.

［20］李峻金，向陽，牛鵬等，一種新的復雜網(wǎng)絡聚類算法［J］.計算機應用研究，2010，27(6).LI Jun － jin，XIANG Yang，NIU Peng，et al.A New Clustering Algorithm for Complex Networks［J］.Computer Application Research，2010，27(6).

［21］金弟，劉大為，楊博等，基于局部探測的快速復雜網(wǎng)絡聚類算法［J］.電子學報，2011，11(2540 －2545).JIN Di，LIU Da － wei，YANG Bo，et al.Fast and Complex Network Clustering Algorithm based on Local Detection［J］.Journal of Electronic，2011，11(2540 －2545).

［22］孔令旗，楊夢龍.符號網(wǎng)絡聚類算法FEC的改進［J］.計算機應用，2011，31(5).KONG Lin － qi，YANG Meng － long.Improvement of FEC for Clustering Algorithm of Symbol Network［J］.Computer Application，2011，31(5).

［23］Radicchi F，Castellano C，Cecconi F，et al.Defining and Identifying Communities in Networks［J］.Proceedings of the National Academy of Science，2004，101(9):2658－2663.

［24］丁轉(zhuǎn)蓮.基于優(yōu)化的復雜網(wǎng)絡聚類方法研究［D］.安徽:安徽大學，2014.DING Zhuan － lian.Research on Clustering Method of Complex Network based on Optimization［D］.Anhui:Anhui University，2014.

［25］Newman MEJ.Fast Algorithm for Detecting Community Structure in Networks［J］.Physical Review E，2004，69(6):066133.

［26］丁孝燕.復雜網(wǎng)絡聚類及其在神經(jīng)網(wǎng)絡中的應用研究［D］，廣西:廣西師范學院，2011.DING Xiao－ yan.Complex Network Clustering and Its Application in Neural Networks［D］.Guangxi:Guangxi Teachers Education University，2011.

［27］Mete M，TANG F，XU X，et al.A Structural Approach for Finding Functional Modules from Large Biological Networks［J］.BMC Bioinformatics，2008，9(9).

［28］Clauset A，Newman M，Moore C.Finding Community Structure in Very Large Networks［J］.Phys Rev E，2004，70.

［29］Havemann F，Glaser J，Heinz M，et al.Identifying O-verlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers:A Comparison of Three Approaches［J］.PloS one，2012，7(3):e33255.

［30］Solava R W，Michaels R P，Milenkovic T.Graphletbased Edge Clustering Reveals Pathogen－Interacting Proteins［J］.Bioinformatics，2012，28(18):i480 －i486.

［31］HE D，JIN D，Baquero C，et al.Link Community Detection Using Generative Model and Nonnegative Matrix Factorization［J］.PLOS ONE，2014，9(1):e86899.