搜索
arXiv:cond-mat/0112110v1[cond-mat.stat-mech]7Dec2001CommunitystructureinsocialandbiologicalnetworksMichelleGirvan1,2andM.E.J.Newman11SantaFeInstitute,1399HydeParkRoad,SantaFe,NM875012DepartmentofPhysics,CornellUniversity,ClarkHall,Ithaca,NY14853–2501(Dated:December7,2001)AnumberofrecentstudieshavefocusedonthestatisticalpropertiesofnetworkedsystemssuchassocialnetworksandtheWorld-WideWeb.Researchershaveconcentratedparticularlyonafewpropertieswhichseemtobecommontomanynetworks:thesmall-worldproperty,power-lawdegreedistributions,andnetworktransitivity.Inthispaper,wehighlightanotherpropertywhichisfoundinmanynetworks,thepropertyofcommunitystructure,inwhichnetworknodesarejoinedtogetherintightly-knitgroupsbetweenwhichthereareonlylooserconnections.Weproposeanewmethodfordetectingsuchcommunities,builtaroundtheideaofusingcentralityindicestofindcommunityboundaries.Wetestourmethodoncomputergeneratedandreal-worldgraphswhosecommunitystructureisalreadyknown,andfindthatitdetectsthisknownstructurewithhighsensitivityandreliability.Wealsoapplythemethodtotwonetworkswhosecommunitystructureisnotwell-known—acollaborationnetworkandafoodweb—andfindthatitdetectssignificantandinformativecommunitydivisionsinbothcases.I.INTRODUCTIONManysystemstaketheformofnetworks,setsofnodesorverticesjoinedtogetherinpairsbylinksoredges[1].Examplesincludesocialnetworks[2,3,4]suchasacquaintancenetworks[5]andcollaborationnet-works[6],technologicalnetworkssuchastheInternet[7],theWorld-WideWeb[8,9],andpowergrids[4,5],andbiologicalnetworkssuchasneuralnetworks[4],foodwebs[10],andmetabolicnetworks[11,12].Recentre-searchonnetworksamongmathematiciansandphysi-cistshasfocusedonanumberofdistinctivestatisticalpropertiesthatmostnetworksseemtoshare.Onesuchpropertyisthe“smallworldeffect,”whichisthenamegiventothefindingthattheaveragedistancebetweenverticesinanetworkisshort[13,14],usuallyscalinglog-arithmicallywiththetotalnumbernofvertices.Anotheristheright-skeweddegreedistributionsthatmanynet-workspossess[8,9,15,16,17].Thedegreeofavertexinanetworkisthenumberofotherverticestowhichitisconnected,andonefindsthattherearetypicallymanyverticesinanetworkwithlowdegreeandasmallnumberwithhighdegree,theprecisedistributionoftenfollowingapower-laworexponentialform[1,5,15].Athirdpropertythatmanynetworkshaveincommonisclustering,ornetworktransitivity,whichistheprop-ertythattwoverticesthatarebothneighborsofthesamethirdvertexhaveaheightenedprobabilityofalsobeingneighborsofoneanother.Inthelanguageofsocialnet-works,twoofyourfriendswillhaveagreaterprobabilityofknowingoneanotherthanwilltwopeoplechosenatrandomfromthepopulation,onaccountoftheircom-monacquaintancewithyou.ThiseffectisquantifiedbytheclusteringcoefficientC[4,18],definedbyC=3×(numberoftrianglesonthegraph)(numberofconnectedtriplesofvertices).(1)Thisnumberispreciselytheprobabilitythattwoofone’sfriendsarefriendsthemselves.Itis1onafullyconnectedgraph(everyoneknowseveryoneelse)andhastypicalval-uesintherange0.1to0.5inmanyreal-worldnetworks.Inthispaper,weconsideranotherpropertywhich,aswewillshow,appearstobecommontomanynetworks,thepropertyofcommunitystructure.(Thispropertyisalsosometimescalledclustering,butwerefrainfromthisusagetoavoidconfusionwiththeothermeaningofthewordclusteringintroducedintheprecedingparagraph.)Considerforamomentthecaseofsocialnetworks—networksoffriendshipsorotheracquaintancesbetweenindividuals.Itismatterofcommonexperiencethatsuchnetworksseemtohavecommunitiesinthem:subsetsofverticeswithinwhichvertex–vertexconnectionsaredense,butbetweenwhichconnectionsarelessdense.AfigurativesketchofanetworkwithsuchacommunitystructureisshowninFig.1.(Certainlyitispossiblethatthecommunitiesthemselvesalsojointogethertoformmeta-communities,andthatthosemeta-communitiesarethemselvesjoinedtogether,andsooninahierarchicalFIG.1:Aschematicrepresentationofanetworkwithcommu-nitystructure.Inthisnetworktherearethreecommunitiesofdenselyconnectedvertices(circleswithsolidlines),withamuchlowerdensityofconnections(graylines)betweenthem.2fashion.ThisideaisdiscussedfurtherinSectionII.)Theabilitytodetectcommunitystructureinanetworkcouldclearlyhavepracticalapplications.Communitiesinasocialnetworkmightrepresentrealsocialgroupings,perhapsbyinterestorbackground;communitiesinaci-tationnetwork[19]mightrepresentrelatedpapersonasingletopic;communitiesinametabolicnetworkmightrepresentcyclesandotherfunctionalgroupings;commu-nitiesintheWebmightrepresentpagesonrelatedtopics.Beingabletoidentifythesecommunitiescouldhelpustounderstandandexploitthesenetworksmoreeffectively.Inthispaperweproposeanewmethodfordetectingcommunitystructureandapplyittothestudyofanum-berofdifferentsocialandbiologicalnetworks.Aswewillshow,whenappliedtonetworksforwhichthecom-munitystructureisalreadyknownfromotherstudies,ourmethodappearstogiveexcellentagreementwiththeexpectedresults.Whenappliedtonetworksforwhichwedonothaveotherinformationaboutcommunities,itgivespromisingresultswhichmayhelpusunderstandbettertheinterplaybetweennetworkstructureandfunc-tion.II.DETECTINGCOMMUNITYSTRUCTUREInthissectionwereviewexistingmethodsfo