文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 互联网 > _Finding communities in linear time by developing the seeds
侵权投诉

_Finding communities in linear time by developing the seeds

PHYSICALREVIEWE84,036109(2011)

Findingcommunitiesinlineartimebydevelopingtheseeds

AliA.HakamiZanjani*andAmirH.Darooneh

DepartmentofPhysics,ZanjanUniversity,P.O.Box45196-313,Zanjan,Iran

(Received13October2010;revisedmanuscriptreceived9May2011;published14September2011)Wepresentanalternatemethodfor ndingthecommunitiesinacomplexnetwork.Weintroducetwoconceptsnamedtheseedofthecommunityandtheabsorptionpoweroftheseedincomplexnetworks.First,we ndtheseedsandthendevelopthembyconsideringtheirabsorptionpowertoachievethecommunities.Wecomparethemodularityandthecomputationalcomplexityofthisalgorithmwithsomeotherexistingmethods,andweshowthatthisalgorithmisveryfastandef cientincomparisonwithsomerecentlyfastalgorithms.DOI:10.1103/PhysRevE.84.036109

PACSnumber(s):89.75.Hc,89.70.Eg,89.75.Fb

I.INTRODUCTION

Manysystemsinnature,society,andtechnologythatcomprisemanyinteractingpartswiththeabilityofgeneratinganewqualityofmacroscopiccollectivebehaviorareknownascomplexsystems[1].Oneofthemostconvenientwaystorepresentcomplexsystemsisthroughnetworksorgraphs[2,3].Theentitiesofthesystemarerepresentedbytheverticesofthegraphandtheinteractionsbetweentheverticesarerepresentedbythelinks.Adiversityofreal-worldphenomenasuchassocialrelationships[4,5],biologicalandchemicalinteractions[6,7],spreadingofvirusesanddiseases[8,9],earthquakes[10–12],theInternetandtheWorldWideWeb[13–16],andlinguisticphenomena[17–19]canbemodeledwithcomplexnetworks—forareview,seeRef.[20].

Ourknowledgeaboutgraphscanbeobtainedfromstudyingboththeirrelativequantitiesonamicroscopiclevel(suchasvertexdegree,clusteringcoef cientofeachvertex,etc.)andthequantitiesonamesoscopiclevel(suchasbetweennessandmodularity)[21].The rstquantitiesarerelatedtothestateofasinglevertexorafewofthem,butthesecondquantitiesdependupontheconnectionsbetweenalargesetofvertices.Graphswhicharerepresentingrealsystemsdisplaylargeinhomogeneities,revealingamesoscopicleveloforderandorganization.Therearemanyverticeswithlowdegreeswhereassomeverticeshavelargedegrees.Ontheotherhand,thedistributionofedgesisnotonlyglobally,butalsolocallyinhomogeneous,withhighconcentrationsofedgeswithinspecialgroupsofvertices,andlowconcentrationsbetweenthesegroups.Wecallthisfeatureofrealnetworksthecommunitystructure[22,23].Communitiesare,roughlyspeaking,groupsofnodesthataredenselyconnectedtoeachotherbutonlysparselyconnectedwiththerestofthenetwork.Detectingsuchcommunitiesisofinterest,becausetheverticesofacommunityusuallysharecommonpropertiesorplaysimilarroleswithinthegraph.Wecanclassifytheverticesaccordingtotheirstructuralpositioninthecommunities.So,verticesinaspecialcommunitywhicharesharingalargenumberoflinkswithothernodesofthatcommunitymayhaveimportantfunctionsofcontrolandstabilitywithinthecommunity;verticeswhicharesettledattheboundariesbetweencommunitiesplayanimportantroleofmediation

*

hakami.zanjani@znu.ac.irdarooneh@znu.ac.ir

andleadtherelationshipsandexchangesbetweendifferentcommunities[23].

Alargenumberofalgorithmshasbeendevelopedfordetectingthecommunities.Spectralgraphpartitioning[24]andhierarchicalclustering[25]aretwotraditionalapproachesthatworkquitereliablyforspeci ctypesofproblems,butperformpoorlyinmoregeneralcases[26].ThemethodofGirvanandNewman[22],focusedontheconceptofbetweenness,markedthebeginningofanewerainthe eldofcommunitydetectionandopenedthistopictophysicists.FollowingthisworkofGirvanandNewman,aseriesofalgorithmsbasedontheideaofiterativelyremovingedgeswithahighcentralityscorehavebeenproposed.Suchmethodsusedifferentmeasuresofedgecentrality,suchastherandom-walkbetweenness,thecurrent- owbetweenness[27],andtheinformationcentrality[28].

Computationalcomplexity[23]forthemostofthesealgorithmsishigherthanO(n2),wherenisthenumberofvertices,andthismaketheminapplicableforlargenetworks.Inordertodealwithlargenetworks,Newmandevelopedafastmethoddirectlybasedontheoptimizationofthemodularity[29]withthetimecomplexityO(n2).Inalaterpaper,Clausetetal.improvedthismethodbyexploitingsomeshortcutsintheoptimizationproblemandusingmoreadvanceddatastructures[30].TherunningtimeofthismethodisO(nlog2n).Variousothermethodsbasedonspectralanalysis,statisticalinference,andmanydifferentideascanbefoundintheliterature—forreviewsseeRefs.[3,23,31–34].

Mostofthecurrentalgorithmshavesomedegreeofstochas-ticityandthecomputationalcomplexityofmoreaccuratemethodsisoftenhigh.Here,wepresentanalternatemethodthatisnotonlymoreaccuratebutalsofasterthanmostoftheexistingalgorithms.Itwillbeseenthattheexecutiontimeandcomputationalcomplexityofthisalgorithmisconsiderablylow,incomparisonwithrecentlyfastalgorithms.

Thebasicideaofsomeoftherecentlyfastalgorithmsisthelocaloptimizationofaproperty,suchas tnessfunction.Thesealgorithmsusuallybeginfromarandomvertexandextractacommunity,whichhasamaximumamountof tness;thatistosay,addinganewnodetothiscommunity,oreliminatinganynodefromthatwilllowertheamountofthe tnessofthatcommunity.Inthenextsteptheychooseanothervertex,whichisnotyetassignedtoanycommunity,andextractanothercommunityandsoforth[35,36].Insomeothermethodsthenetworktobestudiedisconsideredtobeacircuit,wherelinks

第1页

你可能喜欢

热门文档

相关文档

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