基于粒子群優(yōu)化與模糊聚類的社區(qū)發(fā)現(xiàn)算法

孫延維，彭智明，李健波

(1.湖北第二師范學院基礎教育信息技術服務湖北省協(xié)同創(chuàng)新中心，湖北武漢430205;2.首都信息發(fā)展股份有限公司重慶分公司，重慶400014;3.重慶市教育考試院信息處，重慶401147)

0 引言

社交網(wǎng)絡(social network)是真實世界里人際交往關系的一個縮影，仍然具有社區(qū)結構這一普遍特性。發(fā)現(xiàn)社交網(wǎng)絡中的社區(qū)對探索人際關系模式有巨大的現(xiàn)實意義，而用什么樣的算法來挖掘社交網(wǎng)絡中的社區(qū)則是關鍵。

經(jīng)過科研人員的多年努力，社區(qū)發(fā)現(xiàn)算法的研究已經(jīng)獲得了重大進展。目前，出現(xiàn)了基于稠密子圖的社區(qū)劃分算法［1］，其時間復雜度較低，能適用于大規(guī)模網(wǎng)絡社區(qū)發(fā)現(xiàn)，但只能挖掘聯(lián)系非常緊密的小社區(qū);最小分割聚類算法［2］運行效率較高，但不具備動態(tài)識別網(wǎng)絡社區(qū)總數(shù)能力;基于快速展開的社區(qū)劃分方法［3］具有高效的運行速度，但在某些具有層次性特點的網(wǎng)絡中，不能發(fā)現(xiàn)網(wǎng)絡的社區(qū)結構;基于拓撲勢的社區(qū)發(fā)現(xiàn)方法［4］無須指定社區(qū)個數(shù)，但該算法劃分的社區(qū)結果受拓撲勢的影響;文獻［5］中提出的一種改進的GN(Girvan-Newman)算法解決了GN算法計算效率差的問題，但社區(qū)劃分的準確性較低。

在研究中發(fā)現(xiàn)，實際社交網(wǎng)絡節(jié)點的社區(qū)歸屬具有不明確性，如此會使社區(qū)的劃分結果不精準，與具體網(wǎng)絡的社區(qū)結構相距較遠。針對此問題，文獻［6］提出了改進的K-means模糊聚類的社區(qū)發(fā)現(xiàn)算法(k-meas algorithm for community structures detection based on fuzzy clustering，NKFCM))，且實驗結果說明該算法效果良好，但執(zhí)行效率較差。因此，本文提出改進的基于粒子群優(yōu)化與模糊聚類的社區(qū)發(fā)現(xiàn)算法(community detection algorithm based on particle swarm optimization and fuzzy clustering，PFCM)，該方法運用以云模型為執(zhí)行條件的粒子群算法自適應地決定最優(yōu)社區(qū)數(shù)與最佳社區(qū)核心，且能改善NKFCM運行時間代價較大的問題。

1 基于改進的K-means模糊聚類的社區(qū)發(fā)現(xiàn)算法(NKFCM)

NKFCM［6］包含了有序的算法流程，其描述如下:

1)對社區(qū)核心節(jié)點進行優(yōu)化，確定最佳社區(qū)個數(shù)。首先設定被發(fā)現(xiàn)的社區(qū)個數(shù)為k，有k個最佳聚類核心在k=［2，kmax］中被計算出來，一般取為網(wǎng)絡中的節(jié)點個數(shù);

2)依照最優(yōu)的核心節(jié)點，將網(wǎng)絡在擁有k個社團時的聚類目標值計算出來，當?shù)玫阶畲蟮木垲惸繕酥禃r，網(wǎng)絡含有的社區(qū)數(shù)目就被獲得，再將社團個數(shù)與優(yōu)化的聚類核心進行輸出;

3)利用模糊聚類算法(fuzzy c-meas algorithm，F(xiàn)CM)［6］劃分網(wǎng)絡社區(qū)，得到網(wǎng)絡的社區(qū)結構。

2 基于粒子群優(yōu)化與模糊聚類的社區(qū)發(fā)現(xiàn)算法(PFCM)

2.1 粒子群算法原理介紹

粒子群優(yōu)化算法(particle swarm optimizer，PSO)［7-8］是一種演化的計算技術(evolutionary computation)，由Eberhart和Kennedy于1995年共同提出的，它源于對鳥群的行為研究演化而來［7］。粒子群算法是一種群體智能方法，其思想的初始來源是模仿鳥群活動，即把任意個體看作一個無體積和質(zhì)量的輕質(zhì)粒子。任何粒子都有各自的移動速度，可是每個粒子的移動速度卻受到其他粒子與自身移動歷史的影響，最優(yōu)解則通過個體之間共享信息與相互協(xié)作來尋找。假設存在一個s維的搜尋空間，空間中存在z個粒子，每個粒子目前所在的位置為psi=(psi1，psi2，…，pis)，且過去所在的最好位置為phi=(phi1，phi2，…，phis)，粒子群以前的最佳位置為pci=(pci1，pci2，…，pcis)。任何一個粒子目前移動的速度為qi=(qi1，qi2，…，qis)。算法首先初始化隨機選定的z個粒子，再迭代，在每一次迭代中，每個粒子的位置與速度［9］會按某種準則來更新。第k次迭代更新粒子位置與速度的準則分別為

(1)—(2)式中:w1，w2為加速系數(shù)，分別表示調(diào)整全局最優(yōu)粒子與個體最優(yōu)粒子按自己的方向移動的最大步長;θ為慣性因子;ram為一個在［0，1］的隨機數(shù)。(1)式等號右邊由3個部分構成。粒子維持本身慣性的能力是第1部分，當θ越大，粒子原來速度的權重值被接受的概率也越大;第2部分，即粒子的“認知”部分，表示粒子所通過的“學習”，也是粒子的認知能力;粒子之間有相互學習的能力，由第3部分表示，同時也象征了粒子間互相影響的“社會”作用［10］。

2.2 云模型介紹

本文采用云模型［11-12］作為粒子群算法執(zhí)行的前提條件。云模型是一個數(shù)學模型，用語言值描述了某個概念B與其定量表示之間的不確定轉(zhuǎn)換關系。設I為一個包含精確值的論域，B是I上對應的一個定性概念，對于I上的任意一個定量值v，?v，v∈I，都存在一個隨機數(shù)L=τB(v)，且L具有平穩(wěn)趨勢，也表示I在v上的確定水平，v在I上的分布就被定義為云模型，簡稱云［12］。云的數(shù)字特征有期望［11］Ev、熵［12］Em、超熵［12］Hε，即B整體上的定量特征由這3個參數(shù)表征出來。

期望Ev:最能代表B的點，且這些點都屬于某個數(shù)域空間。

熵Em:B的不確定性由Em展現(xiàn)出來，且存在3個方面能夠體現(xiàn)此種不確定性。①隨機性與模糊性的關聯(lián)關系被Em顯示;②Em表明了B在數(shù)域空間內(nèi)能夠承受的云滴［12］群大小;③Em還能表示B的粒度。一般，Em的值越小，云滴的鐘形開口［10］展開也越小，概念更微觀，隨機性、模糊性更小，進行明確的量化也更加容易。

超熵Hε:即Em的熵，當Hε越小，云滴的散布越小，云越稀薄。

粒子在查找最優(yōu)值的歷程中受慣性權重θ的影響，且θ需要自適應調(diào)節(jié)，θ的值越小，粒子在大范疇內(nèi)進行搜尋最優(yōu)越不利，在粒子接近最好值時，其速度則被要求減慢，直到靜止在最好值周邊。如此，粒子的“早熟”現(xiàn)象就可以被避免。利用在v前提下的云發(fā)生器［13］可以獲得每個粒子接受θ的概率φi(t)，φi(t)的值越大，粒子搜索最佳值的效率越高。

則

2.3 粒子群優(yōu)化與模糊聚類的社區(qū)發(fā)現(xiàn)算法(NFCM)

2.3.1 聚類核心初始化

設V={v1，v2，…，vm}包含m個節(jié)點，vm∈Rs表示一個節(jié)點，現(xiàn)在計算任意節(jié)點vi與vj之間的最短路徑D(vi，vj)

(8)式中:i=1，2，…，hmax，其中，hmax表示最佳社團數(shù);j=1，2，…，m;δ是一個能被調(diào)節(jié)控制的常數(shù)。(8)式反映了節(jié)點vi與節(jié)點vj在距離上的關系，當DISij的值越大，vi與vj間相隔的距離就越遠。

設定任意節(jié)點vi的關系度值計算函數(shù)為

(9)式中:δ是常數(shù)，表明了距離關系可以改變;vi與網(wǎng)絡中全部節(jié)點之間的距離之和確定了r(vi)值的大小，且r(vi)反映了vi周邊節(jié)點密集的程度。把網(wǎng)絡中全部節(jié)點的關系度值計算出來，并記為rk(vi)(j=1，2，…，hmax)。設表示網(wǎng)絡中第k個聚類核心的關系度值，則確定的函數(shù)為

設ξ是個可以變更的常數(shù)，且ξ≥0，若DISij≥ξ，就稱DISij是vj對于vi的有效半徑。對任何節(jié)點vi，當網(wǎng)絡中存在N個使DISij≥ξ的節(jié)點，則決定網(wǎng)絡聚類核心的公式為

(12)式中:樣本里的最大r(vi)值用表示，其值由(9)式計算;λ是常數(shù)。

選取聚類核心的流程為(10)—(12)式，迭代此過程m次，就能選擇出m+1個聚類核心。終止迭代應滿足(13)式。

2.3.2 粒子的編碼與適應度函數(shù)

1)粒子的編碼［10］方式。粒子種群的起始個體由已被優(yōu)化了的聚類核心組成。設與網(wǎng)絡節(jié)點相關的信息維數(shù)為s，則對粒子進行編碼的方式為

(14)式中，hij(i=1，2，…，hmax，j=1，2，…，s)代表第i個聚類核心的第j維編碼。如此每個粒子的信息就轉(zhuǎn)化為一個hmax×s維的數(shù)據(jù)。

2)適應度函數(shù)［10］。FCM算法獲得最小值的方法為迭代優(yōu)化目標函數(shù)值，且適應度函數(shù)的定義為

(15)式的函數(shù)值越小，表示劃分的聚類效果較差，聚類核心選取有較大的偏差，聚類質(zhì)量則不高。

2.3.3 算法的基本流程

1)網(wǎng)絡中每個節(jié)點的關系度值都由(9)式計算，則首個被預先挑出的聚類核心即為具有最大關系度值的節(jié)點h1，并計算h1的有效距離，確定h1的有效輻射點和數(shù)量，再依照(11)式更新網(wǎng)絡聚類核心;

2)更新后樣本的關系度值都依據(jù)(12)式計算，選出新的核心，做迭代運算，直到滿足停止條件取得聚類核心;

3)首先根據(jù)(14)式編碼hmax個社區(qū)核心，再將粒子的適應度值計算出來，然后對粒子群的其他相關參數(shù)進行初始化;

5)根據(jù)1)至4)得到的聚類核心數(shù)，即為網(wǎng)絡中包括的社團數(shù)目，作為FCM運行的開始條件，然后利用FCM劃分網(wǎng)絡社區(qū)，得到社區(qū)結果。

該算法的偽代碼如下:

粒子群算法確定最優(yōu)聚類核心與社區(qū)個數(shù)階段:

3 實驗結果與分析

3.1 實驗參數(shù)選取與演變計算

從(1)式可以知道，w1用來調(diào)整粒子朝本身最好位置方向移動的步長，w2用來調(diào)整粒子朝整體最佳位置移動的步長，且w1∈［0，2］，w2∈［0，2］。當步長bi∈［－bmax，bmax］時(bmax表示粒子一次能移動的最大步長)，才能確保粒子始終在查尋空間內(nèi)進行查找，并完成演變過程。

任意一個粒子的方位由(2)式計算出來。在社交網(wǎng)絡的實際狀況下，對新的方位進行模擬，則將粒子的尋找界限約束在查詢空間內(nèi)，這樣就能使粒子離開查尋空間的不確定性得到規(guī)避。同時，將任意粒子vi(i=1，2，…，m)的適應度與整體通過的最佳位置pc作對比，若整體位置更差，則將其定義為現(xiàn)在的整體最優(yōu)位置。

3.2 PFCM算法對真實網(wǎng)絡的社區(qū)劃分

為了驗證本文算法的有效性，對2個經(jīng)典的真實社交網(wǎng)絡Zachary’s Karate Club［14］和海豚網(wǎng)絡(Dolphin network)［6］進行了具體測試，其社區(qū)劃分結果如圖1、圖2所示。

圖1中，三角形節(jié)點集表示一個社區(qū)，圓形節(jié)點集表示另一個社區(qū)。其中節(jié)點9的社區(qū)歸屬不正確，其他節(jié)點的劃分都與具體網(wǎng)絡相合。由于優(yōu)化的聚類核心都是節(jié)點1和節(jié)點34，則PFCM發(fā)現(xiàn)的社團結果與NKFCM劃分的結果［10］一樣，這也間接證實了PFCM發(fā)現(xiàn)社區(qū)結構具有穩(wěn)定性。

圖2中，白色正方形節(jié)點集表示一個社區(qū)，黑色正方形節(jié)點集表示另一個社區(qū)。節(jié)點8、節(jié)點40未被分配到準確的社團中，但考慮到節(jié)點8、節(jié)點40和2個社區(qū)的聯(lián)系都比較緊密，此劃分結果也是可以被接受的。

圖1 PFCM算法發(fā)現(xiàn)Zachary’s Karate Club社區(qū)結構的結果Fig.1 Community structure of Zachary’s Karate Club by PFCM

圖2 PFCM算法發(fā)現(xiàn)Dolphin社區(qū)結構的結果Fig.2 Community structure of dolphin network by PFCM

3.3 粒子演變代數(shù)與模塊度的關系

Newman與Girvan提出了衡量社區(qū)劃分質(zhì)量好壞的模塊度(modularity)［15］評價函數(shù)(又稱為Q函數(shù))。當一個社區(qū)劃分算法實驗獲得的Q值越高，則該算法發(fā)現(xiàn)的社區(qū)結構具有較好的結構性;反之則結構性較差。

第k次粒子演變效果與發(fā)現(xiàn)網(wǎng)絡社區(qū)獲得的Q值的關系如圖3所示。對圖3進行分析可得，在粒子的演變歷程中，社團劃分的效果越來越優(yōu)良，在第60代粒子演變附近，獲取的Q值逐步傾向平穩(wěn)，此時Q值的改變已不被粒子的演變所引導，這是由于在粒子經(jīng)歷充足的演變次數(shù)時，粒子所?？康娜肿詈梅轿徊粫僮兏?。

3.4 精確度與算法的質(zhì)量分析

為了驗證PFCM算法的準確性，將該算法與GN算法［16］、快速Newman算法(fast algorithm for detection community structure in networks，F(xiàn)N)［17］、NKFCM算法在真實網(wǎng)絡上進行了實驗，并做了準確性與Q值的對比，其分析結果如表1、圖4所示。

圖3 粒子演變代數(shù)k與模塊度Q值的關系Fig.3.Relationship of particle evolution algebra k and modularity Q’s value

表1 劃分的精確度與模塊度Q值比較Tab.1 Comparison of accuracy and modularity Q’s value

圖4 GN，F(xiàn)N，NKFCM，PFCM精確度和模塊度對比圖Fig.4 Comparison graph of accuracy and modularity for GN，F(xiàn)N，NKFCM，PFCM

通過對表1、圖4的分析可知，PFCM算法發(fā)現(xiàn)社交網(wǎng)絡社區(qū)結構的精確度與社區(qū)劃分獲得的模塊度值(Q值)都有較好的表現(xiàn)，表明PFCM算法劃分社區(qū)的精度較高。

3.5 算法的執(zhí)行效率分析與對比

在k次迭代后可得到網(wǎng)絡的社區(qū)結構，PFCM算法的時間復雜度為O(k(m+m2))，k表示迭代次數(shù)，且k是常數(shù)，m表示網(wǎng)絡的規(guī)模;GN算法的時間復雜度為O(k(m3))，F(xiàn)N算法的時間復雜度為O(m(n+m))，n表示網(wǎng)絡的邊數(shù);NKFCM算法的時間復雜度為。因此，能夠得出后3者的時間復雜度較PFCM的時間復雜度而言，相對較差。

圖5是GN算法、NKFCM算法、FN算法、PFCM算法發(fā)現(xiàn)不同規(guī)模的真實網(wǎng)絡和計算機模擬網(wǎng)絡的社區(qū)結構所花費的時間比較。

分析圖5可知，GN算法、NKFCM算法在網(wǎng)絡節(jié)點數(shù)增多時，其執(zhí)行時間增長迅猛，因此，它們發(fā)現(xiàn)大規(guī)模的網(wǎng)絡社區(qū)的實用性較差。伴隨網(wǎng)絡規(guī)模的擴大，對比FN算法和PFCM算法的時間變化曲線，顯然，PFCM耗費的時間代價更小，其執(zhí)行效率更優(yōu);在圖3的分析說明中，當粒子演變到60代附近時，PFCM已相當靠近最好結果，此時，PFCM的時間復雜度為O(m+m2)，F(xiàn)N的時間復雜度為O(nm+m2)，無論從理論上分析還是從實際運行情況分析都能得出PFCM比FN執(zhí)行效率更高的結論。

圖5 GN，F(xiàn)N，NKFCM，PFCM算法在不同網(wǎng)絡規(guī)模中的執(zhí)行時間Fig.5 Runtime of GN，F(xiàn)N，NKFCM，PFCM with different network size

4 結束語

針對目前網(wǎng)絡已進入到大規(guī)模、大數(shù)據(jù)時代，使用更高效的算法來發(fā)現(xiàn)網(wǎng)絡社區(qū)結構是大勢所趨，因此，借鑒群體智能方法思想，引入粒子群算法，由粒子群優(yōu)化能得到整體最佳聚類核心，提出了基于粒子群優(yōu)化與模糊聚類的社區(qū)發(fā)現(xiàn)算法。首先對粒子優(yōu)化和演變的流程進行了闡述，接著敘述了算法的整個運作過程，最后將算法在實際社交網(wǎng)絡中做了測試，實驗結果表明，本文算法有較高的準確性。又以FCM，NKFCM，GN，F(xiàn)N算法的實驗結果來比較它們的性能，分析它們的時間復雜度，以不同規(guī)模的網(wǎng)絡對比其執(zhí)行時間，得出本文算法的執(zhí)行效率較高。因此，基于粒子群優(yōu)化與模糊聚類的社區(qū)發(fā)現(xiàn)算法具有可行性與有效性。

［1］FALKOWSKI T，BARTH A，SPILIOPOULOU M.DENGRAPH:A Density-based Community Detection Algorithm［C］//IEEE/WIC/ACM International Conference on Web Intelligence.Washington，DC，USA:IEEE，2007，2:112-115.

［2］楊博，劉大有，劉吉明，等.復雜網(wǎng)絡聚類方法［J］.軟件學報，2009，20(1):54-66.

YANG Bo，LIU Dayou，LIU Jiming，et al.Complex Network Clustering Algorithms［J］.Journal of Software，2009，20(1):54-66.

［3］TVINCEN D，BLONDEL，JEAN-LOUP G，et al.Fast unfolding of communities in large networks［J］.Journal of Statistical Mechanics:Theory and Experiment，2008，10(8):1-12.

［4］淦文燕，赫南，李德毅.一種基于拓撲勢的網(wǎng)絡社區(qū)發(fā)現(xiàn)方法［J］.軟件學報，2009，20(8):2241-2254.

JIN Wenyan，HE Nan，LI Deyi.Community Discovery Method in Netwoeks Based on Topologic Potential［J］.Journal of Software，2009，20(8):2241-2254.

［5］朱小虎，宋文軍，王崇駿，等.用于社團發(fā)現(xiàn)的Girvan-Newman改進算法［J］.計算機科學與探索，2010，4(12):1101-1108.

ZHU Xiaohu，SONG Wenjun，WANG Chongjun，et al.Improved Algorithm Based on Girvan-Newman Algorithm for Community Detection［J］.Journal of Rrontiers of Computer Science and Technology，2010，4(12):1101-1108.

［6］QUN L，ZHIMING P，YI G，et al.A new K-means algorithm for community structures detection based on Fuzzy clustering［C］//IEEE International Conference on Granular Computing.［s.l.］:IEEE，2012(11):1-5.

［7］姚麗娟，羅可，孟穎.一種基于粒子群的聚類算法［J］.計算機工程與應用，2012，48(13):29-33.

YAO Lijuan，LUO Ke，MENG Ying.Clustering algorithm based on particle swarm optimization［J］.Computer Engineering and Applications，2012，48(13):150-153.

［8］謝秀華，李陶深.一種基于改進PSO的k-means優(yōu)化聚類算法［J］.計算機技術與發(fā)展，2014，24(2):34-38.

XIE Xiuhua，LI Taoshen.An Optimized k-means Clustering Alorithm Based on Improved Particle Swarm Optimization［J］.Computer Technology and Development，2014，24(2):34-38.

［9］HUA S，GA Z，RUI-SHENG W，et al.Identi?cation of overlapping community structure in complex networks using fuzzy c-means clustering［J］.Physica A，2007，374(1):483–490.

［10］邱新建，薛鳳鳳，山拜.一種采用粒子群優(yōu)化的聚類算法［J］.計算機工程與應用，2012，48(10):29-33.

QIU Xinjian，XUE Fengfeng，SHAN Bai.A kind of clustering algorithm applying particle swarm［J］，Computer Engineering and Applications，2012，48(10):29-33.

［11］王國胤，苗奪謙，吳偉志，等.不確定信息的粗糙集表示和處理［J］.重慶郵電大學學報:自然科學版，2010，22(5):541-544.

WANG Guoyin，MIAO Duoqian，WU Weizhi，et al.Uncertain knowledge representation and processing based on rough set［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2010，22(5):541-544.

［12］張光衛(wèi)，何銳，劉禹，等.基于云模型的演變算法［J］.計算機學報，2008，31(7):1082-1090.

ZHANG Guangwei，HE Rui，LIU Yu，et al.An Evolutionary Algorithm Based on Cloud Model［J］.Chinese Journal of Computers，2008，31(7):1082-1090.

［13］戴朝華，朱云芳，陳維榮，等.云遺傳算法及其應用［J］.電子學報，2007，35(7):1419-1424.

DAI Chaohua，ZHU Yunfang，CHEN Weirong，et al.Cloud Model Based Genetic Algorithm and Its Applications［J］.Acta Electronica Sinica.2007，35(7):1419-1424.

［14］CHEN D，SHANG M，LV Z，et al.Detecting overlapping communities of weighted networks via a local algorithm［J］.Physica A:Statistical Mechanics and its Applications，2010，389(19):4177-4187.

［15］王林，戴冠中，趙煥成.一種新的評價社區(qū)結構的模塊度研究［J］.計算機工程，2010，36(14):227-229.

WANG Lin，DAI Guanzhong，ZHAO Huancheng.Research on Modularity for Evaluating Community Structure［J］.Computer Engineering，2010，36(14):227-229.

［16］黃發(fā)良.信息網(wǎng)絡的社區(qū)發(fā)現(xiàn)及其應用研究［J］.復雜系統(tǒng)與復雜科學，2010，7(1):64-74.

HUANG Faliang.Studies on Community Detection and Its Application in Information Network［J］，2010，7(1):64-74.

［17］肖有誥，屠成宇.基于啟發(fā)式函數(shù)的分布式FN算法［J］.計算機系統(tǒng)應用，2012，21(10):122-125.

XIAO Youhao，TU Chengyu.Distributed FN Algorithm Based on Heuristic Function［J］，Journal of Computer Applications，2012，21(10):122-125.