modularity and community structure in networks

《modularity and community structure in networks》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ModularityandcommunitystructureinnetworksM.E.J.NewmanDepartmentofPhysicsandCenterfortheStudyofComplexSystems,RandallLaboratory,UniversityofMichigan,AnnArbor,MI48109–1040Manynetworksofinterestinthesciences,includingavarietyofsocialandbiologicalnetworks,arefou

2、ndtodividenaturallyintocommunitiesormodules.Theproblemofdetectingandcharacterizingthiscommunitystructurehasattractedconsiderablerecentattention.Oneofthemostsensitivedetectionmethodsisoptimizationofthequalityfunctionknownas“modularity”overthepossibledivisions

3、ofanetwork,butdirectapplicationofthismethodusing,forinstance,simulatedannealingiscomputationallycostly.Hereweshowthatthemodularitycanbereformulatedintermsoftheeigenvectorsofanewcharacteristicmatrixforthenetwork,whichwecallthemodularitymatrix,andthatthisrefor

4、mulationleadstoaspectralalgorithmforcommunitydetectionthatreturnsresultsofbetterqualitythancompetingmethodsinnoticeablyshorterrunningtimes.Wedemonstratethealgorithmwithapplicationstoseveralnetworkdatasets.IntroductionManysystemsofscientificinterestcanberepres

5、entedasnetworks—setsofnodesorverticesjoinedinpairsbylinesoredges.ExamplesincludetheInternetandtheworldwideweb,metabolicnetworks,foodwebs,neuralnetworks,communicationanddistributionnetworks,andsocialnetworks.Thestudyofnetworkedsystemshasahistorystretchingback

6、severalcenturies,butithasexpe-riencedaparticularsurgeofinterestinthelastdecade,especiallyinthemathematicalsciences,partlyasaresultoftheincreasingavailabilityoflarge-scaleaccuratedatadescribingthetopologyofnetworksintherealworld.FIG.1:Theverticesinmanynetwork

7、sfallnaturallyintoStatisticalanalysesofthesedatahaverevealedsomeun-groupsorcommunities,setsofvertices(shaded)withinwhichexpectedstructuralfeatures,suchashighnetworktran-therearemanyedges,withonlyasmallernumberofedgessitivity[1],power-lawdegreedistributions[2

8、],andthebetweenverticesofdifferentgroups.existenceofrepeatedlocalmotifs[3];see[4,5,6]forreviews.Oneissuethathasreceivedaconsiderableamountofattentionisthedetectionandcharacterizationofcom-modelin