基于粒子群優(yōu)化的復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘

白 云,任國(guó)霞

(西北農(nóng)林科技大學(xué)信息工程學(xué)院,西安712100)

基于粒子群優(yōu)化的復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘

白 云,任國(guó)霞

(西北農(nóng)林科技大學(xué)信息工程學(xué)院,西安712100)

為解決復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)挖掘的優(yōu)化問(wèn)題,根據(jù)復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的先驗(yàn)知識(shí),提出一種基于離散粒子群優(yōu)化的社區(qū)結(jié)構(gòu)挖掘算法。將粒子的位置和速度定義在離散環(huán)境下,設(shè)計(jì)粒子的更新規(guī)則,在不需要事先指定社區(qū)個(gè)數(shù)的前提下自動(dòng)判斷網(wǎng)絡(luò)的最佳社區(qū)個(gè)數(shù),給出局部搜索算子,該算子可以幫助算法跳出局部最優(yōu)解,提高算法的收斂速度和全局尋優(yōu)能力。實(shí)驗(yàn)結(jié)果表明,與iMeme-net算法相比,該算法能夠準(zhǔn)確地挖掘出復(fù)雜網(wǎng)絡(luò)中隱藏的社區(qū)結(jié)構(gòu),且執(zhí)行速度較快。

粒子群優(yōu)化;復(fù)雜網(wǎng)絡(luò);社區(qū)結(jié)構(gòu);社區(qū)挖掘;局部搜索;模塊密度

1 概述

網(wǎng)絡(luò)存在于人們生活中的每一個(gè)角落,如社交網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、金融網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等。現(xiàn)實(shí)中絕大多數(shù)復(fù)雜系統(tǒng)如電力系統(tǒng)、科學(xué)引文系統(tǒng)、航線運(yùn)輸系統(tǒng)、移動(dòng)通信系統(tǒng)等,都可以建模成由節(jié)點(diǎn)和邊組成的復(fù)雜網(wǎng)絡(luò)。目前,網(wǎng)絡(luò)在以空前的廣度、深度和速度改變?nèi)藗兊娜粘Ｉ罘绞胶徒涣鞣绞?同時(shí),網(wǎng)絡(luò)也影響著社會(huì)的政治、經(jīng)濟(jì)和文化的發(fā)展。

文獻(xiàn)［1］提出社會(huì)計(jì)算的概念,掀起了學(xué)術(shù)界研究的新高潮。社會(huì)計(jì)算是一種新的計(jì)算模式,計(jì)算對(duì)象是社會(huì)媒體數(shù)據(jù),其典型的處理思路是將媒體數(shù)據(jù)建模成復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)然后對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行分析。復(fù)雜網(wǎng)絡(luò)有很多特性,如小世界性［2］、無(wú)標(biāo)度特性等［3］,其中,社區(qū)特性［4］近年來(lái)被證明是復(fù)雜網(wǎng)絡(luò)最具典型的一個(gè)特性。所謂網(wǎng)絡(luò)社區(qū)指的是網(wǎng)絡(luò)的一些子塊,這些子塊內(nèi)部的連接比較密集而子塊與子塊之間的連接則比較稀疏。挖掘復(fù)雜網(wǎng)絡(luò)中隱藏的社區(qū)結(jié)構(gòu)特性對(duì)于復(fù)雜網(wǎng)絡(luò)分析具有及其重要的意義,目前已經(jīng)有大量的社區(qū)結(jié)構(gòu)挖掘算法被提出［5］。

在現(xiàn)存網(wǎng)絡(luò)社區(qū)挖掘算法里,優(yōu)化算法的核心

思想是將網(wǎng)絡(luò)社區(qū)挖掘看成一種優(yōu)化問(wèn)題,然后采用啟發(fā)式優(yōu)化算法對(duì)該問(wèn)題進(jìn)行求解。在啟發(fā)式算法中,粒子群優(yōu)化算法［6］以其原理簡(jiǎn)明、操作簡(jiǎn)單、參數(shù)少、收斂快等特點(diǎn)而聞名,被廣泛應(yīng)用于求解各種優(yōu)化問(wèn)題。粒子群優(yōu)化算法是受群居生物捕食和躲避捕食者行為的啟發(fā)而人工建模的優(yōu)化算法。然而,經(jīng)典粒子群優(yōu)化算法是為連續(xù)優(yōu)化問(wèn)題設(shè)計(jì)的,對(duì)于離散優(yōu)化問(wèn)題,經(jīng)典粒子群優(yōu)化算法無(wú)法求解。為此,本文提出一種離散粒子群優(yōu)化算法,并將其應(yīng)用于復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘。粒子的位置和速度被定義為離散形式,粒子的狀態(tài)更新方程被重新設(shè)計(jì),并充分利用了網(wǎng)絡(luò)的先驗(yàn)知識(shí)。為提高算法的全局搜索能力和收斂速度,設(shè)計(jì)局部搜索策略,該搜索策略較為充分地挖掘了網(wǎng)絡(luò)可以利用的信息,并在計(jì)算機(jī)模擬網(wǎng)絡(luò)數(shù)據(jù)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)。

2 網(wǎng)絡(luò)社區(qū)挖掘及粒子群優(yōu)化

在對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行分析時(shí),通常是將其建模成由節(jié)點(diǎn)和邊相互連接的圖,然后再對(duì)圖進(jìn)行分析。網(wǎng)絡(luò)社區(qū)挖掘就是要挖掘網(wǎng)絡(luò)中潛在的社區(qū)結(jié)構(gòu),所挖掘的社區(qū)結(jié)構(gòu)必須滿足社區(qū)內(nèi)部連接緊密,而社區(qū)與社區(qū)之間的連接則相對(duì)稀疏。網(wǎng)絡(luò)與社區(qū)挖掘示意圖如圖1所示。

圖1 網(wǎng)絡(luò)與社區(qū)挖掘示意圖

從圖1可以看出,網(wǎng)絡(luò)社區(qū)挖掘的本質(zhì)是圖的分割問(wèn)題,其可以轉(zhuǎn)化成數(shù)學(xué)優(yōu)化問(wèn)題,進(jìn)而可以采用優(yōu)化算法進(jìn)行求解。然而,很多圖的優(yōu)化問(wèn)題建模出來(lái)的數(shù)學(xué)函數(shù)都不具有可導(dǎo)性,甚至不具備連續(xù)性,因此,傳統(tǒng)數(shù)學(xué)方法很難求解這類問(wèn)題。為了求解這類優(yōu)化問(wèn)題,啟發(fā)式優(yōu)化算法被學(xué)者們提出。在啟發(fā)式優(yōu)化算法中,粒子群優(yōu)化算法脫穎而出并得到廣泛應(yīng)用［7-8］。粒子群優(yōu)化算法通過(guò)一組粒子來(lái)優(yōu)化一個(gè)問(wèn)題,每個(gè)粒子代表問(wèn)題的一個(gè)解,每個(gè)粒子通過(guò)自身的學(xué)習(xí)根據(jù)一些簡(jiǎn)單的規(guī)則來(lái)調(diào)整自己的飛行狀態(tài),從而使粒子向問(wèn)題的全局最好解靠近。

粒子i根據(jù)式(1)調(diào)整自己的飛行速度,再根據(jù)新的速度來(lái)調(diào)整自己的飛行軌跡,從而使粒子向最優(yōu)解區(qū)域靠近。

3 基于粒子群優(yōu)化的網(wǎng)絡(luò)社區(qū)挖掘算法

經(jīng)典粒子群優(yōu)化算法都是為連續(xù)優(yōu)化問(wèn)題而設(shè)計(jì)的,其狀態(tài)更新式(1)和式(2)無(wú)法直接應(yīng)用于離散問(wèn)題的求解。本文重新定義了粒子的狀態(tài)及其更新公式,提出一種離散粒子群優(yōu)化算法框架,并將其成功運(yùn)用于復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘。

3.1 粒子的編碼與解碼

編碼與解碼是將優(yōu)化問(wèn)題與優(yōu)化算法建立連接的橋梁。針對(duì)社區(qū)挖掘這個(gè)問(wèn)題,文獻(xiàn)［9］提出一種基于連接的編解碼方式,文獻(xiàn)［10］提出字符串的編解碼方式。

本文采用的編解碼方式為基于字符串的編碼,因?yàn)檫@種編碼操作簡(jiǎn)單而且解碼方便。本文采用的粒子編解碼方式如圖2所示。

圖2 粒子的編解碼示意圖

由圖2可見(jiàn),粒子的位置是一個(gè)整數(shù)序列,序列的每一位數(shù)字代表對(duì)應(yīng)位置節(jié)點(diǎn)的社區(qū)分類標(biāo)號(hào),在解碼時(shí),具有相同社區(qū)標(biāo)號(hào)的節(jié)點(diǎn)被劃分到同一個(gè)社區(qū)中。由此可見(jiàn),該編碼可以自動(dòng)判斷網(wǎng)絡(luò)到底劃分成幾個(gè)社區(qū),而不需要人工事先指定社區(qū)個(gè)數(shù)。

3.2 粒子的狀態(tài)更新方程

為了將粒子群優(yōu)化算法和社區(qū)挖掘相結(jié)合,本文重新定義粒子的狀態(tài)更新方程如下:

其中,ω是慣性權(quán)值常數(shù);符號(hào)⊕表示異或操作;函數(shù)ζ(x)是一個(gè)限界函數(shù),其目的是將變量x變?yōu)殡x散的二進(jìn)制形式,以便于其與位置向量進(jìn)行式(4)的操作,其具體定義如下:

式(4)中的?操作是粒子狀態(tài)更新的核心操作,該操作定義的好壞直接影響算法挖掘社區(qū)的性能以及算法的收斂情況。

對(duì)于一個(gè)網(wǎng)絡(luò)而言,2個(gè)沒(méi)有連接的節(jié)點(diǎn)屬于同一個(gè)社區(qū)的概率要小于2個(gè)有連接的節(jié)點(diǎn)的概率,基于該事實(shí),本文定義的?操作如下:

3.3 粒子的適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是用來(lái)評(píng)價(jià)粒子狀態(tài)好壞的,對(duì)于復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘問(wèn)題而言,適應(yīng)度函數(shù)評(píng)價(jià)的是網(wǎng)絡(luò)社區(qū)劃分的好壞。本文采用的適應(yīng)度函數(shù)為文獻(xiàn)［11］提出的模塊密度函數(shù)。

令Ω={c1,c2,…,ck}為網(wǎng)絡(luò)的一個(gè)劃分,1≤k≤N,N是網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù),定義L(c1,c2)=∑i∈c1,j∈c2aij,其中,aij為網(wǎng)絡(luò)的鄰接矩陣A′的元素,模塊密度定義如下:

其中,α是分辨率控制參數(shù),其范圍為［0,1］;ci′=Ω-ci,|ci|表示社區(qū)ci的節(jié)點(diǎn)個(gè)數(shù)。

3.4 粒子的局部搜索策略

由于粒子群優(yōu)化算法也是一種隨機(jī)搜索算法,因此也避免不了陷入局部最優(yōu)的情況,另外,由于現(xiàn)實(shí)的網(wǎng)絡(luò)都比較大,算法處理起來(lái)可能收斂很慢,為了提高算法的全局尋優(yōu)能力和收斂速度,本文設(shè)計(jì)了一種粒子局部搜索策略。該局部搜索策略是對(duì)文獻(xiàn)［12］提出的搜索策略的一種改進(jìn)。本文局部搜索策略的核心思想如圖3所示。

圖3 粒子的局部搜索策略示意圖

從圖3可以看出,本文局部搜索策略的核心思想是對(duì)被選擇進(jìn)行搜索的節(jié)點(diǎn)A分配到能夠使目標(biāo)函數(shù)增量最大的鄰居節(jié)點(diǎn)的社區(qū)中。文獻(xiàn)［12］的搜索策略是將節(jié)點(diǎn)A分配到能使目標(biāo)函數(shù)增量最大的其他社區(qū)中,而本文的做法則可以大大節(jié)省搜索空間,因?yàn)楸疚牡乃阉魇腔诠?jié)點(diǎn)的連接的,而對(duì)于一個(gè)大規(guī)模網(wǎng)絡(luò)而言,社區(qū)數(shù)目通常很大,但節(jié)點(diǎn)的平均度卻很小,即節(jié)點(diǎn)的連接是很稀疏的。

4 實(shí)驗(yàn)結(jié)果與分析

為了測(cè)試所提算法的社區(qū)挖掘性能,本節(jié)將對(duì)算法進(jìn)行對(duì)比實(shí)驗(yàn)測(cè)試。實(shí)驗(yàn)中采用了計(jì)算機(jī)模擬網(wǎng)絡(luò)數(shù)據(jù)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)。實(shí)驗(yàn)采用了文獻(xiàn)［12］的算法iMeme-net作為對(duì)比算法。本文算法參數(shù)設(shè)置為:分辨率控制參數(shù)α取值范圍為［0.2,1.0］;間隔為0.1;粒子群大小為50;迭代次數(shù)為50;社會(huì)系數(shù)和認(rèn)真系數(shù)均設(shè)置為1.494;慣性權(quán)值設(shè)為0.792。為了公平起見(jiàn),算法iMeme-net的種群大小和迭代次數(shù)都設(shè)為50,其他參數(shù)采用原文設(shè)置。

計(jì)算機(jī)模擬網(wǎng)絡(luò)數(shù)據(jù)來(lái)源于文獻(xiàn)［13］,該數(shù)據(jù)被稱為GN擴(kuò)展基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù),該網(wǎng)絡(luò)數(shù)據(jù)包含128個(gè)節(jié)點(diǎn),被平均分成4個(gè)社區(qū),網(wǎng)絡(luò)通過(guò)一個(gè)混合參數(shù)γ來(lái)控制社區(qū)內(nèi)部以及社區(qū)之間邊的連接。

對(duì)于網(wǎng)絡(luò)的真實(shí)社區(qū)劃分存在的情況下,為了評(píng)價(jià)算法挖掘出來(lái)的社區(qū)的好壞,本文采用文獻(xiàn)［14］提出的互信息指標(biāo)NMI來(lái)進(jìn)行評(píng)價(jià)。

給定網(wǎng)絡(luò)的2個(gè)社區(qū)劃分A和B,令C′為一個(gè)混淆矩陣,矩陣C′的元素Cij為劃分A中社區(qū)i和劃分B中社區(qū)j共同擁有的節(jié)點(diǎn)個(gè)數(shù),則劃分A和B之間的歸一化互信息NMI(A,B)的計(jì)算方式可以表示為:

其中,CA(CB)表示劃分A(B)中的社區(qū)個(gè)數(shù);Ci(Cj)表示矩陣C′的第i行(第j列)的元素之和;N為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)。

實(shí)驗(yàn)中,在每個(gè)網(wǎng)絡(luò)數(shù)據(jù)上每個(gè)算法獨(dú)立運(yùn)行30次。圖4和圖5記錄了算法在計(jì)算機(jī)模擬網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果。從圖4和圖5可以看出,本文算法在基準(zhǔn)網(wǎng)絡(luò)混合參數(shù)γ不大于0.35的情況下,可以較好地挖掘網(wǎng)絡(luò)的真實(shí)社區(qū)結(jié)構(gòu),和iMeme-net算法相比,在參數(shù)α=0.9時(shí),本文算法得到的NMI值明顯高于iMeme-net算法。表1記錄了本文算法和對(duì)比算法iMeme-net在真實(shí)網(wǎng)絡(luò)上進(jìn)行測(cè)試時(shí)得到的實(shí)驗(yàn)結(jié)果,其中,括號(hào)里面的為本文算法得到的結(jié)果;空手道網(wǎng)絡(luò)和海豚網(wǎng)絡(luò)的真實(shí)社區(qū)都為2個(gè)。

圖4 本文算法在模擬網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果

圖5 本文算法與iMeme-net算法的實(shí)驗(yàn)結(jié)果對(duì)比

表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果對(duì)比

從表1的實(shí)驗(yàn)數(shù)據(jù)可以看出,本文算法相對(duì)iMeme-net算法在目標(biāo)函數(shù)方面有明顯的提高。在分辨率控制參數(shù)α=0.3時(shí),本文算法得到了NMI為1的網(wǎng)絡(luò)劃分,即本文算法找到了網(wǎng)絡(luò)的真實(shí)社區(qū)結(jié)構(gòu)。本文算法在α=0.3時(shí)得到的空手道網(wǎng)絡(luò)和海豚網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)如圖6和圖7所示,其中,圓形和四方形分別表示不同的社區(qū)劃分。在科學(xué)家合作網(wǎng)上本文算法得到的目標(biāo)函數(shù)值明顯高于對(duì)比算法。可以看出,本文算法在挖掘網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)時(shí)是有效的,通過(guò)調(diào)節(jié)目標(biāo)函數(shù)中的分辨率控制參數(shù)可以得到不同的網(wǎng)絡(luò)社區(qū)劃分。

圖6 本文算法得到的空手道網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分

圖7 本文算法得到的海豚網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分

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

復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘?qū)ρ芯烤W(wǎng)絡(luò)隱藏的知識(shí)和運(yùn)行機(jī)制具有極其重要的作用。為此,本文提出一種離散粒子群優(yōu)化算法,并將其運(yùn)用于社區(qū)挖掘。從優(yōu)化的角度著手挖掘復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu),通過(guò)粒子群優(yōu)化算法優(yōu)化性能指標(biāo),從而尋找該指標(biāo)最優(yōu)時(shí)對(duì)應(yīng)的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu),并給出一種改進(jìn)的局部搜索策略。實(shí)驗(yàn)結(jié)果證明了其有效性。今后將研究如何提高粒子群優(yōu)化算法在大數(shù)據(jù)處理上的性能,以及多目標(biāo)粒子群優(yōu)化算法的設(shè)計(jì)。

［1]Lazer D,Pentland A S,Adamic L,et al.Life in the Network:The Coming Age of Computational Social Science［J］.Science,2009,323(5915):721-723.

［2]Watts D J,Strogatz S H.Collective Dynamics of‘Smallworld’Networks［J］.Nature,1998,393(6684):440-442.

［3]Barabási A L,AlbertR.EmergenceofScalingin Random Networks［J］.Science,1999,286(5439): 509-512.

［4]Girvan M,Newman M E J.Community Structure in Social and Biological Networks［J］.Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

［5]Fortunato S.CommunityDetectioninGraphs［J］.Physics Reports,2010,486(3):75-174.

［6]Kennedy J,Eberhart R.Particle Swarm Optimization［C］// Proceedings of IEEE International Conference on Neural Networks.Washington D.C.,USA:IEEE Press,1995, 1942-1948.

［7]鄔開(kāi)俊,魯懷偉.云環(huán)境下基于DPSO的任務(wù)調(diào)度算法［J］.計(jì)算機(jī)工程,2014,40(1):59-62.

［8]徐從東,陳 春.一種自適應(yīng)動(dòng)態(tài)控制參數(shù)的粒子群優(yōu)化算法［J］.計(jì)算機(jī)工程,2013,39(10):203-207.

［9]Pizzuti C.A Multiobjective Genetic Algorithm to Find Communities in Complex Networks［J］.IEEE Transactions on Evolutionary Computation,2012,16(3):418-430.

［10]Gong Maoguo,Cai Qing,Chen Xiaowei,et al.Complex Network Clustering by Multiobjective Discrete Particle Swarm Optimization Based on Decomposition［J］.IEEE Transactions on Evolutionary Computation,2014,18(1): 82-97.

［11]Li Zhenping,Zhang Shihua,Wang Ruisheng,et al.Quantitative Function for Community Detection［J］.Physical Review E,2008,77(3).

［12]Gong Maoguo,Cai Qing,Li Yangyang,et al.An Improved Memetic Algorithm for Community Detection in Complex Networks［C］//ProceedingsofIEEECongresson Evolutionary Computation.Washington D.C.,USA:IEEE Press,2012:1-8.

［13]Lancichinetti A,FortunatoS,RadicchiF.Benchmark Graphs for Testing Community Detection Algorithms［J］.Physical Review E,2008,78(4).

［14]Huberman B A.Finding Communities in Linear Time: A PhysicsApproach［J］.TheEuropeanPhysical Journal B——Condensed Matter and Complex Systems, 2004,38(2):331-338.

編輯 劉 冰

Complex Network Community Mining Based on Particle Swarm Optimization

BAI Yun,REN Guoxia
(College of Information Engineering,Northwest A&F University,Xi’an 712100,China)

In order to solve the problem of community mining optimization from complex network,according to the prior knowledge of the topology structure of complex network,a complex network community mining algorithm based on Particle Swarm Optimization(PSO)is proposed.In the proposed algorithm,particle’s position and velocity are redefined in discrete case,particle’s update principles is redesigned,the proposed algorithm can automatically determine the best community numbers without knowing it in advance.In order to improve the global search ability of the proposed algorithm,a local search operator is designed,and this operator can help the algorithm to jump out of local optimum and improves the convergence speed.Experimental results demonstrate that the proposed algorithm can efficiently dig out the community structures hidden behind complex networks,and the execution speed is much faster than that of iMeme-net algorithm.

Particle Swarm Optimization(PSO);complex network;community structure;community mining;local search;modularity density

白 云,任國(guó)霞.基于粒子群優(yōu)化的復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘［J］.計(jì)算機(jī)工程,2015,41(3):177-181.

英文引用格式:Bai Yun,Ren Guoxia.Complex Network Community Mining Based on Particle Swarm Optimization［J］.Computer Engineering,2015,41(3):177-181.

1000-3428(2015)03-0177-05

:A

:TP18

10.3969/j.issn.1000-3428.2015.03.034

白 云(1982-),女,碩士研究生,主研方向:數(shù)據(jù)挖掘,進(jìn)化計(jì)算;任國(guó)霞(通訊作者),副教授。

2014-04-08

:2014-05-16E-mail:rgx@nwsuaf.edu.cn