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

白 云,任國霞

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

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

白 云,任國霞

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

為解決復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)挖掘的優(yōu)化問題,根據(jù)復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的先驗知識,提出一種基于離散粒子群優(yōu)化的社區(qū)結(jié)構(gòu)挖掘算法。將粒子的位置和速度定義在離散環(huán)境下,設(shè)計粒子的更新規(guī)則,在不需要事先指定社區(qū)個數(shù)的前提下自動判斷網(wǎng)絡(luò)的最佳社區(qū)個數(shù),給出局部搜索算子,該算子可以幫助算法跳出局部最優(yōu)解,提高算法的收斂速度和全局尋優(yōu)能力。實驗結(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ò)存在于人們生活中的每一個角落,如社交網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、金融網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等?，F(xiàn)實中絕大多數(shù)復(fù)雜系統(tǒng)如電力系統(tǒng)、科學(xué)引文系統(tǒng)、航線運(yùn)輸系統(tǒng)、移動通信系統(tǒng)等,都可以建模成由節(jié)點和邊組成的復(fù)雜網(wǎng)絡(luò)。目前,網(wǎng)絡(luò)在以空前的廣度、深度和速度改變?nèi)藗兊娜粘Ｉ罘绞胶徒涣鞣绞?同時,網(wǎng)絡(luò)也影響著社會的政治、經(jīng)濟(jì)和文化的發(fā)展。

文獻(xiàn)［1］提出社會計算的概念,掀起了學(xué)術(shù)界研究的新高潮。社會計算是一種新的計算模式,計算對象是社會媒體數(shù)據(jù),其典型的處理思路是將媒體數(shù)據(jù)建模成復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)然后對復(fù)雜網(wǎng)絡(luò)進(jìn)行分析。復(fù)雜網(wǎng)絡(luò)有很多特性,如小世界性［2］、無標(biāo)度特性等［3］,其中,社區(qū)特性［4］近年來被證明是復(fù)雜網(wǎng)絡(luò)最具典型的一個特性。所謂網(wǎng)絡(luò)社區(qū)指的是網(wǎng)絡(luò)的一些子塊,這些子塊內(nèi)部的連接比較密集而子塊與子塊之間的連接則比較稀疏。挖掘復(fù)雜網(wǎng)絡(luò)中隱藏的社區(qū)結(jié)構(gòu)特性對于復(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)化問題,然后采用啟發(fā)式優(yōu)化算法對該問題進(jìn)行求解。在啟發(fā)式算法中,粒子群優(yōu)化算法［6］以其原理簡明、操作簡單、參數(shù)少、收斂快等特點而聞名,被廣泛應(yīng)用于求解各種優(yōu)化問題。粒子群優(yōu)化算法是受群居生物捕食和躲避捕食者行為的啟發(fā)而人工建模的優(yōu)化算法。然而,經(jīng)典粒子群優(yōu)化算法是為連續(xù)優(yōu)化問題設(shè)計的,對于離散優(yōu)化問題,經(jīng)典粒子群優(yōu)化算法無法求解。為此,本文提出一種離散粒子群優(yōu)化算法,并將其應(yīng)用于復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘。粒子的位置和速度被定義為離散形式,粒子的狀態(tài)更新方程被重新設(shè)計,并充分利用了網(wǎng)絡(luò)的先驗知識。為提高算法的全局搜索能力和收斂速度,設(shè)計局部搜索策略,該搜索策略較為充分地挖掘了網(wǎng)絡(luò)可以利用的信息,并在計算機(jī)模擬網(wǎng)絡(luò)數(shù)據(jù)和真實網(wǎng)絡(luò)數(shù)據(jù)上進(jìn)行實驗。

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

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

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

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

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

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

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

3.1 粒子的編碼與解碼

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

本文采用的編解碼方式為基于字符串的編碼,因為這種編碼操作簡單而且解碼方便。本文采用的粒子編解碼方式如圖2所示。

圖2 粒子的編解碼示意圖

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

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

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

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

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

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

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

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

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

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

3.4 粒子的局部搜索策略

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

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

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

4 實驗結(jié)果與分析

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

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

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

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

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

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

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

圖5 本文算法與iMeme-net算法的實驗結(jié)果對比

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

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

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

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

［8]徐從東,陳 春.一種自適應(yīng)動態(tài)控制參數(shù)的粒子群優(yōu)化算法［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

白 云,任國霞.基于粒子群優(yōu)化的復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘［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)化計算;任國霞(通訊作者),副教授。

2014-04-08

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