资源描述：
《Finding community structure in very large networks.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、PHYSICALREVIEWE70,066111(2004)Findingcommunitystructureinverylargenetworks121,3AaronClauset,M.E.J.Newman,andCristopherMoore1DepartmentofComputerScience,UniversityofNewMexico,Albuquerque,NewMexico87131,USA2DepartmentofPhysicsandCenterfortheStudyofComplexSystems,UniversityofMichigan,An
2、nArbor,Michigan48109,USA3DepartmentofPhysicsandAstronomy,UniversityofNewMexico,Albuquerque,NewMexico87131,USA(Received30August2004;published6December2004)Thediscoveryandanalysisofcommunitystructureinnetworksisatopicofconsiderablerecentinterestwithinthephysicscommunity,butmostmethodsp
3、roposedsofarareunsuitableforverylargenetworksbecauseoftheircomputationalcost.Herewepresentahierarchicalagglomerationalgorithmfordetectingcommunitystructurewhichisfasterthanmanycompetingalgorithms:itsrunningtimeonanetworkwithnverticesandmedgesisOsmdlogndwheredisthedepthofthedendrogram
4、describingthecommunitystructure.Manyreal-worldnetworksaresparseandhierarchical,withm,nandd,logn,inwhichcaseouralgorithmrunsinessentiallylineartime,Osnlog2nd.Asanexampleoftheapplicationofthisalgorithmweuseittoanalyzeanetworkofitemsforsaleonthewebsiteofalargeon-lineretailer,itemsinthen
5、etworkbeinglinkediftheyarefrequentlypurchasedbythesamebuyer.Thenetworkhasmorethan400000verticesand23106edges.Weshowthatouralgorithmcanextractmeaningfulcommunitiesfromthisnetwork,revealinglarge-scalepatternspresentinthepurchasinghabitsofcustomers.DOI:10.1103/PhysRevE.70.066111PACSnumb
6、er(s):89.75.Hc,05.10.2a,87.23.Ge,89.20.HhI.INTRODUCTIONfewthousandverticeswithcurrenthardware.MorerecentlyanumberoffasteralgorithmshavebeenManysystemsofcurrentinteresttothescienti®ccommu-proposed[31±33].In[32],oneofusproposedanalgorithmnitycanusefullyberepresentedasnetworks[1±4].Ex-b
7、asedonthegreedyoptimizationofthequantityknownasamplesincludetheinternet[5]andtheWorldWideWebmodularity[21].Thismethodappearstoworkwellbothin[6,7],socialnetworks[8],citationnetworks[9,10],foodcontrivedtestcasesandinreal-worldsituations,andissub-webs[11],andbiochemicalnetworks[12,13].E
8、achofthesest
