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

王豐雪,陳家琪

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

?

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

王豐雪,陳家琪

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

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

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

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

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

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

1相關(guān)概念

1.1模塊度

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

(1)

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

1.2模擬退火

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

(2)

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

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

1.3貪心策略

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

2SAGA算法

2.1算法思想

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

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

ΔQ=ΔQout+ΔQin

(3)

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

(4)

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

2.2算法執(zhí)行流程

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

圖1　SAGA社團(tuán)劃分法流程圖

3實(shí)驗(yàn)和分析

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

表1　實(shí)驗(yàn)數(shù)據(jù)集

3.1實(shí)驗(yàn)環(huán)境

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

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

3.2實(shí)驗(yàn)結(jié)果和性能評(píng)價(jià)

3.2.1SAGA算法識(shí)別速度評(píng)價(jià)

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

表2　識(shí)別時(shí)間比較

注:-表示計(jì)算時(shí)間超過了24 h。

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

3.2.2SAGA算法識(shí)別精度評(píng)價(jià)

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

表3　模塊度Q比較

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

4結(jié)束語

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

參考文獻(xiàn)

[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

中圖分類號(hào)TP393.02

文獻(xiàn)標(biāo)識(shí)碼A

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

doi:10.16180/j.cnki.issn1007-7820.2016.02.003

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

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

收稿日期:2015- 07- 06