復雜網絡社區劃分方法綜述

摘 要：復雜網絡在現實網絡表現為多種形式，本文將從2002年以來經典社區劃分方法入手，對復雜網絡社區劃分的研究現狀進行一個綜合簡單的描述和概括，試圖為社區劃分研究描繪出一個較為全面和清晰的輪廓，為該領域的后續研究提供有益的參照。

關鍵詞：復雜網絡；社區劃分；形式；綜述

中圖分類號：TU984.12 文獻標識碼：A 文章編號：1674-7712 （2014） 12-0000-02

復雜網絡在現實網絡表現為多種形式，如社會系統中的科學合作網、人際關系網，生物系統中的基因調控網、蛋白質大分子之間交互網和流行病傳播網、蛋白質交互網，科技系統中的電話網、因特網和萬維網等等。同時，復雜網絡更加普遍存在一些統計特征，如表達復雜網絡中節點服從冪律分布特征的“無標度特性”，反映網絡短路徑長度和高聚類系數特點的“小世界效應”和反映網絡中普遍在的同一社區中節點連接緊密、不同社區節點連接稀疏特征的“社區結構”等等 。一般認為社區結構（簇）是指復雜網絡中由具有相同或相似屬性構成的社區，不同的社區結構在特定的網絡中具有不同的性質和特征，如：人際關系網絡中由相同的興趣而形成的人群，蛋白質網絡中具有相似功能的蛋白質群等。

自從2002年，Girvan和Newman提出著名的社區挖掘GN（Girvan-Newman）算法[1]，此后很多復雜網絡社區挖掘方法相繼被提出，在新的理論、方法層出不窮，新的應用領域也不斷涌現的背景下。如何發現復雜網絡中的社區結構，已經成為最具挑戰的多學科交叉研究課題之一，吸引了來自生物、社會、物理、計算機、數學等多領域的研究者。

本文將從2002年以來經典社區劃分方法入手，對復雜網絡社區劃分的研究現狀進行一個綜合簡單的描述和概括，本文試圖為社區劃分研究描繪出一個較為全面和清晰的輪廓，為該領域的后續研究提供有益的參照。

一、社區挖掘方法

（一）基于模塊度的社區劃分

2002年，Girvan和Newman基于啟發式規則提出著名的社區挖GN（Girvan-Newman）算法[1]，該算法從社區間的連接邊介數入手，根據社區間邊介數應大于社區內部鏈接的邊介數，通過反復計算邊介數，移除邊介數最大的邊，自頂向下的方式建立一顆層次聚類樹的方法來劃分社區。其中邊介數定義為：網絡中經過每條邊的最短路徑的數目。通過在實際網絡中的應用發現該方法的劃分的結果精度高，但是計算速度較慢；對于一個具有m條邊，n個節點的網絡時間復雜度為O（mn2），并且該算法沒有對于社區在什么時候進行劃分提出一個有效的方法。

2003年，Tyler等人將采用蒙特卡洛方法[3]引入GN算法中，引入統計方法來估算其中部分節點的鏈接的近似邊介數，提出了一種近似的Gn算法，由于其實計算部分網絡而不是全部網絡，因此，該算法是以犧牲精度為代價來提高計算的精度。

2004年，Girvan和Newman針對GN算法中無衡量社區劃分標準的不足，引入的函數Q值模塊度計算。將次改進算法運用到了實際網絡跆拳道網絡中得到了很好的劃分結果。該模塊度定義為以后社區劃分的優劣提供了一個衡量的標準。該算法的缺點是算法的復雜度和之前相比并沒有什么改進。

于是同年，Newman又提出了基于模塊性優化的快速社區發現算法（FN算法[2]），該算法的過程和GN算法恰好相反，算法采用自底向上的層次聚類過程構成一顆層次聚類樹，在合并的過程中引入DQ，每次合并選擇使函數Q值增大最大或者減小最小的方向進行社區的合并操作，當最終社區合并為一個社區時，只要在對應Q值最大處斷開即可得到聚類的結果。通過對實際網絡劃分的應用，對于一個m條邊，n個節點的網絡，該算法的復雜度為O（mn+n2）。算法的時間復雜度得到了很大的改善。但是算法也具有很大缺陷，在于其求解是局部最優解，精度相較于GN算法低。雖然其后Newman、Clauster等人繼續對FN算法進行了優化，利用堆棧結構隊，提出了一種新的貪婪算法CNM算法。該算法的復雜度O（nlog2n），已經接近于線性復雜度，但是算法的局部最優解問題依舊沒有得到改善。

2005年，Guimera和Amaral基于退火算法原理，提出了退火模塊性優化算法（SA）[3]。該算法的設計思想是在計算之前要給一個初始社區劃分，這個初始的社區劃分可以任意的，在初始社區的基礎上通過迭代不斷產生新的社區解，在迭代過程中同時計算相應Q值。SA算法不同與GN算法和FN算法的，SA算法在計算新的候選解時是將節點劃分到其他社區、通過社區之間交換節點，再次分解社區或者合并社區。并且該算法中應用了模擬退火策略的Metropolis準則來判斷該社區結果是否是當前的最優解。SA算法在實際的數據集上應用的結果中得到了十分好的結果，不足之處是每次迭代都要產生很多的候選結果，因此該算法的時間復雜度較高，運行效率較低。

2006年，Newman基于模塊度函數Q值，提出了優化函數Q的譜方法[4]。Newman通過引入譜圖理論研究模塊度優化。用圖拉普拉斯矩陣來表示模塊度函數Q，該矩陣又稱為模塊性矩陣；并證明了這個矩陣的第二大特征值的特征向量的正負二分結果，正好對應了模塊性優化的二分結果；通過在實際網絡上的應用，該算法的聚類結果接近實際網絡，但其時間復雜度仍較高，介于O（n2 log n）和O（n log n）之間。

2007年，楊博、Cheng和Liu等人[3]通過基于馬爾科夫隨機游走模型提出了網絡聚類算法算法（FEC算法）。該算法的假設是：開始從任意社區開始隨機游走，根據在整個網絡中的隨機游走到達該起始社區內節點的期望值，應大于到達起始社區外節點的期望值的思想。算法采用了啟發策略，綜合了兩種分簇標準（連接密度和連接符號）的復雜網絡社區發現聚類算法，理論上該算法既能很好的處理符號網絡，又能較精確的處理僅包含“正關系”的一般復雜網絡，對于噪聲高和網絡社區結構明顯的網絡社區劃分的結果也相當精確。實驗結果表明FEC算法在時間和精度方面有很好的性能。但是由于該算法需要采用隨機游走的步長作為參數，而對于這個步長參數，目前還沒有一個能夠有效針對不同網絡設置最優參數的方法，所以對于步長的設置最終會直接影響最終的聚類結果的精度，一般認為對于步長的取值在[6，20]之間較為合適。

2009年，Barber等人將算法LPA[4]轉化為一個函數優化問題，給出了目標函數。通過討論與研究該目標函數的特性，來進行社區的劃分，LPA在原理及實際應用方面的缺陷，需要注意，表示社區劃分質量的提高并不和目標函數值的增加相一致。因此，他們對目標函數進行了相應的改進，給出一個帶約束的標簽傳播LPAm算法。該算法的目標函數恰好是模塊度函數Q值，因此，改進后的算法對應了模塊性函數優化，解決了在文獻[2]中所提出的問題。

2011年，劉大有等人[3]從局部觀點出發，根據復雜網絡的規模不斷變大、且某些特性呈天然分布式特性的特點。并且針對單個節點社區劃分的歸屬，利用局部目標函數f，對模塊度函數Q進行了分析，提出了一種快速的社區挖掘算法（FNCA算法）。該算法證明了模塊度函數Q值會伴隨著網絡中任意節點的函數f的單調遞增，Q值呈現出單調遞增特性；在此理論的基礎上提出基于局部優化的近似線性的社區挖掘算法。在算法中，每個節點只利用網絡局部社區結構信息優化自身的目標函數f，通過節點之間的相互協同實現整個網絡的聚類過程，該算法能用于分布式網絡社區挖掘，又能用于分布式網絡社區網絡挖掘，通過對實際網絡社區劃分的結果分析，該算法的時間復雜度較低，精度較高。

（二）基于節點相似性的社區劃分

2006年Leicht，Holme P，Newman等人提出的LHN算法[7]，該算利用網絡鄰接矩陣A來定義矩陣SLHN=2lamtD-1（I-QA/lamt），其中任意一個元素代表兩個節點之間的相似度大小，lamt是鄰接矩陣A的最大特征值，D是由節點連接數組成的對焦矩陣，QA是一個介于[0，1]之間的參數，以保證矩陣逆的存在，該算法根據隨機游走理論，定義節點Vi和Vj間的平均通勤時間定義為：2m（lii+ljj-2lij），其中還lij表示矩陣L=（D-A）+的相應元素，該算法具有很高的計算復雜度，不適合大型網絡計算。

2007年，Frey和Dueck通過3個迭代公式不斷的對兩個消息R和A進行更新，提出了近鄰傳播算法AP算法[6]，該算法又被稱為基于消息傳遞的聚類算法。AP算法的思想是將網絡中每個點都作為聚類中心節點，然后計算中心節點與其他節點的相互吸引信息R（i，k）和歸屬信息A（i，k），前者稱為點k對點i的吸引度，用來描述數據點k適用于作為數據點i的類社區代表程度，后者代表點i對點k的歸屬度，用來描述數據點i選擇數據點k作為其類代表的適合程度，當二者之和越大，點k作為最終聚類中心節點的可能性就越大。該算法在實際的網絡中應用顯示精度比K-means算法結果精度要好，時間復雜度為O（n2）。

2010年，AHn[6]等人基于邊的思想劃分鏈接的層次聚類社區劃分的方法。該算法的思想是：給定由節點k連接的一對邊eik和ejk，用jaccard指數來計算節點i和j之間的相似度S（eik，ejk），S（eik，ejk）=|n+（i） n+（j）|/|n+（i） n+（j）|，其中n+（i）為包含節點i及其鄰居節點的集合，n+（j）為包含節點j及其鄰居節點的集合。而后通過利用單鏈層次聚類方法，逐層的向上產生一棵連接社區的層次樹。最后定義一個用于劃分該層次樹的密度函數D，在相應位置斷開來獲得最優鏈接劃分。通過該算法在實際網絡劃分中的應用，該算法的時間復雜度為O（nk2），其中kmax是網絡中最大的節點的度數。

2011年，姜雅文等人針對GN算法的不足，提出一種基于節點相似度的節點分裂算法SCN[5]，該算法通過計算頂點間的相似度而非GN算法中的邊介數，針降低了算法時間復雜度。相比傳統算法的節點相似性計算和GN算法，在速度和精度上都有較為明顯的改善。該算法的時間復雜度介于O（n2）和O（n3）之間。

2011年，劉大有[5]等人提出基于集成網絡重疊社區挖掘算法（UEOC），該算法將原始網絡同對應的退火網絡轉換成一個集成網絡，針對集成網絡給出的Maekov游走方法，逐漸找出網絡社區，然后通過引入局部社區函數“導電率”，又被成為相似性函數；通過該函數作為社區劃分的標準，將已經找到的社區全部被抽取出來，通過在實際網絡中的應用發現該算法不但適合于普通網絡，而且適合于重疊網絡，且算法只需要一個無需先驗知識就能很容易被確定的參數。該算法的時間復雜度為O（Kn2），其中n 為網絡中節點的個數K為重疊社區個數。

二、結束語

本文主要是從兩個方面對現有的工作進行了綜述：（1）根據所采用的原理從模塊度與相似性兩個角度進行分類，并從中選擇了典型的算法進行介紹；（2）從算法辨識的精度和時間復雜度兩個方面進行定量分析、比較了一些典型方法的性能。

社區劃分的方法基本上都是在以上兩種思想的基礎上進行的，雖然社區劃分算法層出不窮，取得了很多讓人興奮的結果，但是社區劃分中依舊還有很多的問題沒有得到解決：

第一，關于社區的定義，現在大家公認的是Newman的模塊度定義，但是基于相似性、基于反社區的思想在實際應用中也取得了比較好的結果，加上對于現實網絡的高度復雜性，網絡中節點和邊的屬性等因素很少被考慮到社區劃分中，因此，現在很多各具特色的觀點，都尚難以達成共識，人們難以判斷一個方法的好壞，也無法控制大量新方法的產生。

第二，關于重疊網絡、層次網絡、二分網絡的劃分，目前對于既能發現重疊網絡，又能發現層次網絡的算法并不多見，并且大多數的都是在單部圖上面對網絡進行劃分；大量的算法在社區劃分中既沒有考慮到網絡本身所具有的各種屬性，也沒有考慮到網絡所具有的結構特征，因此，對于重疊網絡、層次網絡、二分網絡的劃分的研究將會繼續是一個熱點。

參考文獻：

[1]Clauset A，Newman M E J，Moore C.Finding community structure in very large network，Phys.Rev.E，2004（70）：066111.

[2]汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006（09）.

[3]劉大有，金弟，何東曉.復雜網絡社區挖掘綜述[J].計算機研究與發展，2012（09）.

[4]Santo Fortunato.Community detection in graphs，fortunato@isi.it，2012（11）.

[5]陽廣元，曹霞.國內社區發現研究進展[J].情報資料工作，2014（02）.

[6]Cheng SQ，Shen HW，Zhang GQ，Cheng XQ.Survey of signed network research.Ruan Jian Xue Bao/Journal of Software，2014（01）：1?15（in Chinese）.

[7]金弟，楊博.復雜網絡簇結構探測——基于隨機游走的蟻群算法[J].軟件學報，2012（03）：451-164.

[作者簡介]顧躍舉，男，遼寧遼陽人，武警遼寧省總隊網管中心助理工程師，研究方向：計算機系統應用于維護。