2002-community structure in social and biological networksnew

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

1、CommunitystructureinsocialandbiologicalnetworksMichelleGirvan1,2andM.E.J.Newman11SantaFeInstitute,1399HydeParkRoad,SantaFe,NM875012DepartmentofPhysics,CornellUniversity,ClarkHall,Ithaca,NY14853–2501(Dated:December7,2001)Anumberofrecentstudieshavefocusedonthest

2、atisticalpropertiesofnetworkedsystemssuchassocialnetworksandtheWorld-WideWeb.Researchershaveconcentratedparticularlyonafewpropertieswhichseemtobecommontomanynetworks:thesmall-worldproperty,power-lawdegreedistributions,andnetworktransitivity.Inthispaper,wehighl

3、ightanotherpropertywhichisfoundinmanynetworks,thepropertyofcommunitystructure,inwhichnetworknodesarejoinedtogetherintightly-knitgroupsbetweenwhichthereareonlylooserconnections.Weproposeanewmethodfordetectingsuchcommunities,builtaroundtheideaofusingcentralityin

4、dicestofindcommunityboundaries.Wetestourmethodoncomputergeneratedandreal-worldgraphswhosecommunitystructureisalreadyknown,andfindthatitdetectsthisknownstructurewithhighsensitivityandreliability.Wealsoapplythemethodtotwonetworkswhosecommunitystructureisnotwell-kn

5、own—acollaborationnetworkandafoodweb—andfindthatitdetectssignificantandinformativecommunitydivisionsinbothcases.I.INTRODUCTIONgraph(everyoneknowseveryoneelse)andhastypicalval-uesintherange0.1to0.5inmanyreal-worldnetworks.Manysystemstaketheformofnetworks,setsofIn

6、thispaper,weconsideranotherpropertywhich,asnodesorverticesjoinedtogetherinpairsbylinksorwewillshow,appearstobecommontomanynetworks,edges[1].Examplesincludesocialnetworks[2,3,4]thepropertyofcommunitystructure.(Thispropertyissuchasacquaintancenetworks[5]andcolla

7、borationnet-alsosometimescalledclustering,butwerefrainfromthisworks[6],technologicalnetworkssuchastheInternet[7],usagetoavoidconfusionwiththeothermeaningofthetheWorld-WideWeb[8,9],andpowergrids[4,5],andwordclusteringintroducedintheprecedingparagraph.)biologica

8、lnetworkssuchasneuralnetworks[4],foodConsiderforamomentthecaseofsocialnetworks—webs[10],andmetabolicnetworks[11,12].Recentre-networksoffriendshipsorotheracquaintancesbetweensearcho