文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > A smart local moving algorithm for large-scale modularity-based community detection
侵权投诉

A smart local moving algorithm for large-scale modularity-based community detection

Eur.Phys.J.B(2013)86:471DOI:10.1140/epjb/e2013-40829-0

THEEUROPEAN

PHYSICALJOURNALB

RegularArticle

Asmartlocalmovingalgorithmforlarge-scalemodularity-basedcommunitydetection

LudoWaltmanaandNeesJanvanEck

CentreforScienceandTechnologyStudies,LeidenUniversity,2300Leiden,TheNetherlands

Received13September2013/Receivedin nalform7October2013

cEDPSciences,Societ`Publishedonline13November2013– aItalianadiFisica,Springer-Verlag2013Abstract.Weintroduceanewalgorithmformodularity-basedcommunitydetectioninlargenetworks.

Thealgorithm,whichwerefertoasasmartlocalmovingalgorithm,takesadvantageofawell-knownlocalmovingheuristicthatisalsousedbyotheralgorithms.Comparedwiththeseotheralgorithms,ourproposedalgorithmusesthelocalmovingheuristicinamoresophisticatedway.Basedonananalysisofadiversesetofnetworks,weshowthatoursmartlocalmovingalgorithmidenti escommunitystructureswithhighermodularityvaluesthanotheralgorithmsforlarge-scalemodularityoptimization,amongwhichthepopular“Louvainalgorithm”.Thecomputationale ciencyofouralgorithmmakesitpossibletoperformcommunitydetectioninnetworkswithtensofmillionsofnodesandhundredsofmillionsofedges.Oursmartlocalmovingalgorithmalsoperformswellinsmallandmedium-sizednetworks.Inshortcomputingtimes,itidenti escommunitystructureswithmodularityvaluesequallyhighas,oralmostashighas,thehighestvaluesreportedintheliterature,andsometimesevenhigherthanthehighestvaluesfoundintheliterature.

1Introduction

Theproblemofcommunitydetectioninnetworkshasre-ceivedalotofattentioninthenetworksciencelitera-ture[1].Communitiesareclustersofcloselyconnectednodeswithinanetwork.Apopularapproachtocom-munitydetectionisbasedontheideaofoptimizingamodularityfunction.Modularityfunctionswereintro-ducedbyNewmanandGirvan[2],andtheideaofde-tectingcommunitiesbyoptimizingamodularityfunctionwasproposedbyNewman[3].Nowadays,therearemanyvariantsofthemodularity-basedcommunitydetectionap-proach.Thesevariantsforinstancedealwithdirectedorweightednetworks[4,5],ortheyo eraresolutionparam-eter[6]thatmakesitpossibletocustomizethegran-ularitylevelatwhichcommunitiesaredetectedandtomitigatetheso-calledresolutionlimitproblem[7].Also,somevariantsofthemodularity-basedcommunitydetec-tionapproachusemodularityfunctionswithasomewhatmodi edmathematicalstructure[6,8,9].

OptimizingmodularityisanNP-hardproblem[10].Exactalgorithms[10–12]canbeusedonlyforsmallnet-works.Manydi erentheuristicalgorithmshavebeenpro-posedformodularityoptimization[1],forinstancebasedonagglomerativehierarchicalclustering[3,13],simulatedannealing[6,14],extremaloptimization[15],spectralop-timization[16,17],mean eldannealing[18],andconfor-a

e-mail:waltmanlr@cwts.leidenuniv.nl

mationalspaceannealing[19].However,mostoftheal-gorithmsproposedintheliteraturearesuitableonlyforsmallandmedium-sizednetworks.

Inthispaper,weintroduceanoptimizationalgorithmthatproduceshigh-qualityresultsevenforverylargenet-works(e.g.,withtensofmillionsofnodesandhundredsofmillionsofedges).Forsmallandmedium-sizednetworks,ouralgorithmcanbeconsideredmoreorlesscompetitivewiththebestalgorithmspresentlyavailable.Thealgo-rithmthatweintroducebuildsonideasfromexistingal-gorithmsforlarge-scalemodularityoptimization[20,21].Thesealgorithmswillbeusedasbenchmarksforassess-ingtheperformanceofouralgorithm.Werefertoourproposedalgorithmasasmartlocalmoving(SLM)algo-rithm.Asdiscussedindetailbelow,thisisbecauseouralgorithmreliesheavilyonawell-knownlocalmovingheuristic.Comparedwithexistingalgorithms,ourSLMalgorithmusesthislocalmovingheuristicinamoreso-phisticatedway,anditthereforeproducesmoreaccurateresults.

Thispaperisorganizedasfollows.InSection2,wediscusstwoexistingalgorithmsforlarge-scalemodular-ityoptimization.Wealsointroduceaniterativevariantofbothalgorithms.InSection3,wepresentoursmartlocalmovingalgorithm.WecomparetheperformanceofthevariousalgorithmsinSection4.We rstconsidersmallandmedium-sizednetworks,andwethenfocusonlargenetworks.WesummarizetheconclusionsofourresearchinSection5.

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email