王豐雪,陳家琪

(上海理工大學(xué) 光電信息與計算機工程學(xué)院,上?！?00093)

?

一種結(jié)合模擬退火和貪心策略的社團識別算法

王豐雪,陳家琪

(上海理工大學(xué) 光電信息與計算機工程學(xué)院,上海200093)

摘要為了提高復(fù)雜網(wǎng)絡(luò)社團識別的精度和速度,文中結(jié)合模擬退火和貪心策略識別社團結(jié)構(gòu)的優(yōu)勢,提出一種新的社團識別算法。該算法利用貪心策略引導(dǎo)模擬退火搜索最優(yōu)解過程中單個結(jié)點的無規(guī)則盲目移動,消除了大量無效移動,在搜索到全局最優(yōu)解的情況下,將搜索時間大幅縮減。實驗表明,SAGA具有強大的搜索能力和較快的模擬退火執(zhí)行速度,可獲得較高的模塊度,達到較為準(zhǔn)確的社團分割,且具有一定的應(yīng)用價值。

關(guān)鍵詞復(fù)雜網(wǎng)絡(luò);社團識別;SAGA算法;模擬退火;貪心策略

現(xiàn)實世界中的許多系統(tǒng)以網(wǎng)絡(luò)的形式存在,且具有較高的復(fù)雜性,如社交網(wǎng)、 生物信息網(wǎng)和萬維網(wǎng)等,因此復(fù)雜網(wǎng)絡(luò)的研究具有重要的理論價值和實際意義。研究表明,復(fù)雜網(wǎng)絡(luò)具有明顯的社團結(jié)構(gòu),即網(wǎng)絡(luò)中的結(jié)點連接情況宏觀上可劃分為各個集合,集合內(nèi)的結(jié)點間的連接很稠密,而集合與集合之間的結(jié)點連接很稀疏[1-2]。復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)與網(wǎng)絡(luò)的功能有著緊密的聯(lián)系,網(wǎng)絡(luò)社團結(jié)構(gòu)的檢測有助于理解網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和動力學(xué)行為,因此找出網(wǎng)絡(luò)的正確社團結(jié)構(gòu)并分析相關(guān)性質(zhì)具有重要意義[3-5]。

目前復(fù)雜網(wǎng)絡(luò)社團識別算法方面的研究較多,主要分為兩類:一類是分離法,即找出社團之間的邊,將其從社團中移除;另一類是聚合法,將聯(lián)系緊密的點聚合為一個社團,通過優(yōu)化某個社團劃分質(zhì)量指標(biāo)實現(xiàn)聚合。第一類算法的典型代表是GN分裂算法[6],該算法是復(fù)雜網(wǎng)絡(luò)社團識別研究領(lǐng)域的一種標(biāo)準(zhǔn)算法[7],但時間復(fù)雜度較高。第二類算法的典型代表是Louvain算法[8]、模擬退火網(wǎng)絡(luò)社團識別算法[9]和極值優(yōu)化模塊度識別法[10]等。

Louvain算法是基于貪心策略實現(xiàn)的,劃分速度相當(dāng)快,但不保證劃分結(jié)果的準(zhǔn)確度。模擬退火算法能獲得全局最優(yōu)的模塊度值,達到較準(zhǔn)確的社團劃分,但劃分速度相當(dāng)慢?；贚ouvain算法和模擬退火算法這種優(yōu)缺點互補關(guān)系,本文對貪心策略結(jié)合模擬退火識別網(wǎng)絡(luò)社團進行研究,提出一種新的社團識別算法SAGA(Simulated Annealing And Greedy)。該算法用貪心策略消除模擬退火算法中結(jié)點移動運動的盲目無規(guī)則性,使結(jié)點的每次均向模塊度增大的方向移動,縮短模擬退火算法獲取最優(yōu)值的時間。

1相關(guān)概念

1.1模塊度

模塊度Q是最常用的衡量社團劃分質(zhì)量的標(biāo)準(zhǔn),模塊度Q越大,表明社團劃分算法的劃分效果越好,劃分結(jié)果越符合網(wǎng)絡(luò)的客觀實際社團結(jié)構(gòu)。模塊度Q的計算公式如下

(1)

其中,NM是社團數(shù);L是網(wǎng)絡(luò)中的邊數(shù);ls是社團s內(nèi)的結(jié)點之間的邊數(shù),ds是社團s內(nèi)結(jié)點的度數(shù)之和。

1.2模擬退火

模擬退火算法應(yīng)用復(fù)雜網(wǎng)絡(luò)社團識別時,將溫度T當(dāng)作控制參數(shù),模塊度函數(shù)Q取反當(dāng)作內(nèi)能E。識別過程[11]:首先,在初始溫度下,將每個網(wǎng)絡(luò)結(jié)點初始化為一個獨立的社團,計算出這一初始網(wǎng)絡(luò)社團劃分狀態(tài)下的內(nèi)能。然后,逐漸降低溫度,每一溫度T下,執(zhí)行N2次結(jié)點從一個社團隨機地移動到其他社團的運動和N次兩個社團合并運動或一個社團分裂為二個社團的運動,從而獲得新劃分狀態(tài),計算新狀態(tài)的內(nèi)能,用Metropolis準(zhǔn)則決定是否接受生成的新狀態(tài),直至E趨于全局最小值。內(nèi)能E最小時對應(yīng)的社團劃分結(jié)果即為網(wǎng)絡(luò)的最優(yōu)社團劃分。Metropolis接受準(zhǔn)則的數(shù)學(xué)公式如下[12]

(2)

其中,Ei是當(dāng)前狀態(tài)的內(nèi)能;Ej是生成的新狀態(tài)的內(nèi)能;k為Boltzmann常數(shù)。

模擬退火識別網(wǎng)絡(luò)社團統(tǒng)計上能保證找到全局最優(yōu)值,缺點是搜索過程耗時過長。

1.3貪心策略

貪心策略是指在對問題求解時總是做出在當(dāng)前看來是最佳的選擇,即不從整體最優(yōu)上加以考慮,只做出某種意義上的局部最優(yōu)選擇。文獻[8]提出的Louvain社團識別法就基于貪心策略優(yōu)化模塊度來獲取網(wǎng)絡(luò)社團結(jié)構(gòu)的。Louvain算法劃分速度相當(dāng)快,但不保證劃分全局最優(yōu)性。

2SAGA算法

2.1算法思想

導(dǎo)致模擬退火識別網(wǎng)絡(luò)社團收斂速度相當(dāng)慢的原因:降溫過程的每一溫度下會執(zhí)行N2次某一單個結(jié)點從一個社團隨機地移動到其他社團的運動,N為網(wǎng)絡(luò)中的結(jié)點數(shù)。這每一溫度下的N2次結(jié)點的運動是隨機的,無方向性的,無引導(dǎo)的,必定包含很多未能使網(wǎng)絡(luò)社團劃分狀態(tài)對應(yīng)的目標(biāo)函數(shù)值更優(yōu)的結(jié)點運動。

針對這一問題,本文用貪心策略指導(dǎo)這每一溫度下的N2次的結(jié)點運動,除去這一運動過程的盲目性,即除去了很多于收斂到最優(yōu)模塊度值無用的結(jié)點移動,使每個結(jié)點的每次移動都向模塊度值增加的方向移動,使搜索過程更快地收斂到最優(yōu)模塊度值。具體策略是:對某個結(jié)點i的移動運動,首先計算其從所屬的社團移入鄰居節(jié)點j所屬的社團的模塊度增量,計算公式如下

ΔQ=ΔQout+ΔQin

(3)

其中,ΔQout為結(jié)點i從其所屬的社團移出時產(chǎn)生的模塊度增量,ΔQin為結(jié)點i移入其的鄰居節(jié)點時所屬的社團時產(chǎn)生的模塊度增量。ΔQout和ΔQin的表達式相似,將一個孤立結(jié)點放入一個社團C時所產(chǎn)生的模塊度增量計算公式如下

(4)

其中,∑in表示社團C內(nèi)邊的權(quán)值之和;∑tot表示連接到社團C內(nèi)的結(jié)點的邊的權(quán)值之和;Ki表示連接到結(jié)點i的邊的權(quán)值之和;Ki,in表示連接結(jié)點i和社團C內(nèi)的結(jié)點的邊之和;m為網(wǎng)絡(luò)內(nèi)所有邊的權(quán)值之和。之后,將結(jié)點i放入使模塊度增量最大且模塊度值為正數(shù)的社團中,若不存在這樣的模塊度值,則結(jié)點i繼續(xù)保留在其原來所在社團中。對每一溫度下要移動的N2個結(jié)點執(zhí)行此操作,N為網(wǎng)絡(luò)中的結(jié)點數(shù)。

2.2算法執(zhí)行流程

為便于更好地理解基于模擬退火和貪心策略的SAGA算法,在此給出SAGA網(wǎng)絡(luò)社團識別算法的整體流程圖。SAGA識別網(wǎng)絡(luò)社團流程如圖1所示。

圖1　SAGA社團劃分法流程圖

3實驗和分析

該實驗數(shù)據(jù)來自文獻[13]中提到的標(biāo)準(zhǔn)數(shù)據(jù)集海豚社群Dolphin網(wǎng)絡(luò),文獻[14]中提到的空手道俱樂部Karate網(wǎng)絡(luò),以及從Newman個人網(wǎng)站[15]下載的標(biāo)準(zhǔn)數(shù)據(jù)集美國政治書Polbooks網(wǎng)絡(luò)。這3個數(shù)據(jù)集的相關(guān)詳細信息如表1所示。

表1　實驗數(shù)據(jù)集

3.1實驗環(huán)境

硬件配置:IntelCorei5-3470CPU@ 3.20GHz,2.00GB內(nèi)存。

軟件環(huán)境:Windows7旗艦版操作系統(tǒng),Matlab2012b的編譯環(huán)境。

3.2實驗結(jié)果和性能評價

3.2.1SAGA算法識別速度評價

本文提出的SAGA社團識別算法是在模擬退火(SimulatedAnnealing,SA)社團識別算法上改進的,目的是在不改變SA較高識別準(zhǔn)確度的條件下,大幅度縮短SA快速的識別時間。因此,實驗設(shè)定SAGA和SA兩個算法搜索到相同的最優(yōu)模塊度Q值的情況下,比較兩個算法所花費的時間,計算SAGA與SA所花費的時間的百分比tSAGA/tSA。將SAGA和SA應(yīng)用在3個網(wǎng)絡(luò)數(shù)據(jù)集Karate、Dolphin和Polbooks上進行社團劃分,實驗結(jié)果如表2。

表2　識別時間比較

注:-表示計算時間超過了24 h。

表2所示,在獲取到相同的模塊度Q的條件下,Karate數(shù)據(jù)集上SAGA所需時間是SA所需時間的11.4%,Dolphin數(shù)據(jù)集上SAGA所需時間是SA所需時間的36.9%,表明由模擬退火和貪心策略結(jié)合的SAGA算法可大幅縮短SA獲取最優(yōu)值的時間,具有快速的識別速度。另外,在網(wǎng)絡(luò)的結(jié)點規(guī)模超過100個結(jié)點時,SAGA算法和SA算法在本文的實驗條件和實現(xiàn)方式下,其所需時間均超過24 h,表明SAGA算法和SA算法均只適合于規(guī)模較小的網(wǎng)絡(luò)社團劃分。

3.2.2SAGA算法識別精度評價

社團識別算法的識別精度主要依據(jù)算法運行后所獲得的模塊度Q值來確定,Q值越大表明算法的識別精度越高,Q值由式(1)計算而得。SAGA算法是在貪心策略社團識別上做的改進研究,目的是獲得比貪心策略社團識別法(Greedy算法)和Louvain社團識別法更優(yōu)的結(jié)果。因此,將SAGA算法、Greedy算法、Louvain算法應(yīng)用在Karate、Dolphin、Polbooks這3個標(biāo)準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集上進行社團劃分實驗,3個算法所獲模塊度Q如表3所示。

表3　模塊度Q比較

表3所示,在Karate、Dolphin、Polbooks數(shù)據(jù)集上,SAGA所獲的模塊度Q均大于Greedy算法、Louvain算法所獲的模塊度。表明SAGA算法確實擁有比較高的識別精度,能夠達到比較準(zhǔn)確的社團劃分。同時,也表明由模擬退火和貪心策略結(jié)合的SAGA算法能有效地避免貪心策略易陷入局部最優(yōu)的問題。

4結(jié)束語

本文對模擬退火和貪心策略進行結(jié)合研究,提出一新的社團識別算法SAGA。實驗結(jié)果表明SAGA具有強大的搜索能力和較模擬退火快速的執(zhí)行速度,在精度要求較高且時間要求較快的場合具有一定的應(yīng)用價值。另外,SAGA算法識別速度與精度受執(zhí)行貪心策略的結(jié)點運動數(shù)影響。如何找到一個普適準(zhǔn)則來計算此結(jié)點數(shù),使SAGA在任何網(wǎng)絡(luò)下都具有最優(yōu)識別性能,這有待于進一步研究。

參考文獻

[1]Guimera R,Danon L,Diaz-Guilera A,et al.Self-similar community structure in anetwork of human interactions[J].Physical Review E,2003,68(6):065103-065108.

[2]Hartwel L L H,Hopfield J J,Leibler S,et al.Frommolecular to modular biology[J].Nature,1999(402):C47-C52.

[3]Dorogovtsev S N,Mendes J F F.Evolution of networks:from biological nets to the internet and www[M].UK:Oxford University Press,2003.

[4]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.

[5]Newman M E J.Detecting community structure in networks[J].The EuropeanPhysical Journal B-Condensed Matter and Complex Systems,2004,38(2):321-330.

[6]Danon L,Diaz-Guilera A,Duch J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics-Theory and Experiment,2005(9):09008-09016.

[7]Arenas A,Danon L,Diaz-Guilera A,et al.Community analysis in social networks[J].The European Physical Journal B-Condensed Matter and Complex Systems,2004,38(2):373-380.

[8]Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics-Theory and Experiment,2008(6):10008-10017.

[9]Guimera R,Amaral L A N.Functional cartography of complex metabolic networks[J].Nature,2005,433(7028):895-900.

[10]Boettcher S,Percus A G.Optimization with extremal dynamics[J].Complexity,2002,8(2):57-62.

[11]Metropolis N,Rosenbluth A W,Rosenbluth M N,et al.Equations of state calculations by fast computingmachines[J].Journal of Chemical Physics,1953(21):1087-1092.

[12]Kirkpatrick S,Gelatt C D J,Vecchi M P.Optimization by simulated annealing[J].Science,1983,220(4598):671-680.

[13]Lusseau D,Schneider K,Boisseau O J,et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.

[14]Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.

[15]Newman Mark.Network data[EB/OL].(2014-12-28)[2015-01-09]http://www-personal.umich.edu/～mejn/netdata/.

A Community Detection Combining Simulated Annealing and Greedy Method

WANG Fengxue,CHEN Jiaqi

(School of Optical-Electrical and Computer Engineering,University of Shanghai for

Science and Technology,Shanghai 20093,China)

AbstractTo promote the accuracy and velocity of detection for the community structure in the network,this paper proposes the new community detection method of simulated annealing and greedy algorithm (SAGA),which combines the simulated annealing algorithm and greedy optimization.This algorithm uses greedy strategy to guide the irregular and blind movement of many single nodes in searching the optimal solution of the simulated annealing algorithm,thus removing many invalid movements and greatly reducing the search time to achieve the global optimal solution.The results show that SAGA has higher execution speed with better search ability to obtain higher modularity than the simulated annealing algorithm,and can be effectively used in certain applications.

Keywordscomplex network;community detection;modularity;simulated annealing;greedy optimization

中圖分類號TP393.02

文獻標(biāo)識碼A

文章編號1007-7820(2016)02-008-04

doi:10.16180/j.cnki.issn1007-7820.2016.02.003

作者簡介:王豐雪(1991—),女,碩士研究生。研究方向:復(fù)雜網(wǎng)絡(luò)社團識別。陳家琪(1957—),男,教授。研究方向:計算機網(wǎng)絡(luò)與信息安全等。

基金項目:上海市教委科研創(chuàng)新基金資助項目(12zz146)

收稿日期:2015- 07- 06