Community structure in social and biological networks

MichelleGirvan1,2andM.E.J.Newman1

2

arXiv:cond-mat/0112110v1 [cond-mat.stat-mech] 7 Dec 2001SantaFeInstitute,1399HydeParkRoad,SantaFe,NM87501

DepartmentofPhysics,CornellUniversity,ClarkHall,Ithaca,NY14853–2501

(Dated:December7,2001)

1

AnumberofrecentstudieshavefocusedonthestatisticalpropertiesofnetworkedsystemssuchassocialnetworksandtheWorld-WideWeb.Researchershaveconcentratedparticularlyonafewpropertieswhichseemtobecommontomanynetworks:thesmall-worldproperty,power-lawdegreedistributions,andnetworktransitivity.Inthispaper,wehighlightanotherpropertywhichisfoundinmanynetworks,thepropertyofcommunitystructure,inwhichnetworknodesarejoinedtogetherintightly-knitgroupsbetweenwhichthereareonlylooserconnections.Weproposeanewmethodfordetectingsuchcommunities,builtaroundtheideaofusingcentralityindicestofindcommunityboundaries.Wetestourmethodoncomputergeneratedandreal-worldgraphswhosecommunitystructureisalreadyknown,andfindthatitdetectsthisknownstructurewithhighsensitivityandreliability.Wealsoapplythemethodtotwonetworkswhosecommunitystructureisnotwell-known—acollaborationnetworkandafoodweb—andfindthatitdetectssignificantandinformativecommunitydivisionsinbothcases.

I.

INTRODUCTION

Manysystemstaketheformofnetworks,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)

2

fashion.ThisideaisdiscussedfurtherinSectionII.)Theabilitytodetectcommunitystructureinanetworkcouldclearlyhavepracticalapplications.Communitiesinasocialnetworkmightrepresentrealsocialgroupings,perhapsbyinterestorbackground;communitiesinaci-tationnetwork[19]mightrepresentrelatedpapersonasingletopic;communitiesinametabolicnetworkmightrepresentcyclesandotherfunctionalgroupings;commu-nitiesintheWebmightrepresentpagesonrelatedtopics.Beingabletoidentifythesecommunitiescouldhelpustounderstandandexploitthesenetworksmoreeffectively.Inthispaperweproposeanewmethodfordetectingcommunitystructureandapplyittothestudyofanum-berofdifferentsocialandbiologicalnetworks.Aswewillshow,whenappliedtonetworksforwhichthecom-munitystructureisalreadyknownfromotherstudies,ourmethodappearstogiveexcellentagreementwiththeexpectedresults.Whenappliedtonetworksforwhichwedonothaveotherinformationaboutcommunities,itgivespromisingresultswhichmayhelpusunderstandbettertheinterplaybetweennetworkstructureandfunc-tion.

II.

DETECTINGCOMMUNITYSTRUCTURE

Inthissectionwereviewexistingmethodsfordetectingcommunitystructureanddiscussthewaysinwhichtheseapproachesmayfail,beforedescribingourownmethod,whichavoidssomeoftheshortcomingsofthetraditionaltechniques.

A.

Traditionalmethods

Thetraditionalmethodfordetectingcommunitystruc-tureinnetworkssuchasthatdepictedinFig.1ishier-archicalclustering.OnefirstcalculatesaweightWijforeverypairi,jofverticesinthenetwork,whichrepre-sentsinsomesensehowcloselyconnectedtheverticesare.(Wegivesomeexamplesofpossiblesuchweightsbelow.)Thenonetakesthenverticesinthenetwork,withnoedgesbetweenthem,andaddsedgesbetweenpairsonebyoneinorderoftheirweights,startingwiththepairwiththestrongestweightandprogressingtotheweakest.Asedgesareadded,theresultinggraphshowsanestedsetofincreasinglylargecomponents(connectedsubsetsofvertices),whicharetakentobethecommu-nities.Sincethecomponentsareproperlynested,theycanallberepresentedusingatreeofthetypeshowninFig.2,inwhichthelowestlevelatwhichtwover-ticesareconnectedrepresentsthestrengthoftheedgewhichresultedintheirfirstbecomingmembersofthesamecommunity.A“slice”throughthistreeatanylevelgivesthecommunitieswhichexistedjustbeforeanedgeofthecorrespondingweightwasadded.Treesofthistypearesometimescalled“dendrograms”inthesociologicalliterature.

FIG.2:Anexampleofasmallhierarchicalclusteringtree.ThecirclesatthebottomofthefigurerepresenttheverticesinthenetworkandthetreeshowstheorderinwhichtheyjointogethertoformcommunitiesforagivendefinitionoftheweightWijofconnectionsbetweenvertexpairs.

Manydifferentweightshavebeenproposedforusewithhierarchicalclusteringalgorithms.Onepossibledefini-tionoftheweightisthenumberofnode-independentpathsbetweenvertices.Twopathswhichconnectthesamepairofverticesaresaidtobenode-independentiftheysharenoneofthesameverticesotherthantheirini-tialandfinalvertices.Itisknown[20]thatthenumberofnode-independentpathsbetweenverticesiandjinagraphisequaltotheminimumnumberofverticesthatneedberemovedfromthegraphinordertodisconnectiandjfromoneanother.Thusthisnumberisinasenseameasureoftherobustnessofthenetworktodeletionofnodes[21].

Anotherpossiblewaytodefineweightsbetweenver-ticesistocountthetotalnumberofpathsthatrunbe-tweenthem(allpaths,notjustnode-independentones).However,sincethenumberofpathsbetweenanytwover-ticesisinfinite(unlessitiszero),ℓonetypicallyweightspathsoflengthℓbyafactorαwithαsmall,sothattheweightedcountofthenumberofpathsconverges[22].Thuslongpathscontributeexponentiallylessweightthanshortones.IfAistheadjacencymatrixofthenetwork,suchthatAijis1ifthereisanedgebetweenverticesiandjand0otherwise,thentheweightsinthisdefinitionaregivenbytheelementsofthematrix

󰀁∞W=

(αA)ℓ=[I−αA]−1.

(2)

ℓ=0

Inorderforthesumtoconverge,wemustchooseα

smallerthanthereciprocalofthelargesteigenvalueofA.Bothofthesedefinitionsoftheweightsgivereasonableresultsforcommunitystructureinsomecases.Inothercasestheyarelesssuccessful.Inparticular,bothhaveatendencytoseparatesingleperipheralverticesfromthecommunitiestowhichtheyshouldrightlybelong.Ifavertexis,forexample,connectedtotherestofanetworkbyonlyasingleedgethen,totheextentthatitbelongstoanycommunity,itshouldclearlybeconsideredtobelongtothecommunityattheotherendofthatedge.Unfortu-nately,boththenumbersofnode-independentpathsandtheweightedpathcountsforsuchverticesaresmallandhencesinglenodesoftenremainisolatedfromthenetwork

whenthecommunitiesareconstructed.Thisandotherpathologies,alongwithpoorresultsfromthesemethodsinsomenetworkswherethecommunitystructureiswellknownfromotherstudies,makethehierarchicalcluster-ingmethod,althoughuseful,farfromperfect.

B.

Edgebetweennessandcommunitystructure

Tosidesteptheshortcomingsofthehierarchicalclus-teringmethod,wehereproposeanewapproachtothedetectionofcommunities.Insteadoftryingtoconstructameasurewhichtellsuswhichedgesaremostcentraltocommunities,wefocusinsteadonthoseedgeswhichareleastcentral,theedgeswhicharemost“between”communities.Ratherthanconstructingcommunitiesbyaddingthestrongestedgestoaninitiallyemptyvertexset,weconstructthembyprogressivelyremovingedgesfromtheoriginalgraph.

Vertex“betweenness”hasbeenstudiedinthepastasameasureofthecentralityandinfluenceofnodesinnet-works.FirstproposedbyFreeman[2,23],thebetween-nesscentralityofavertexiisdefinedasthenumberofshortestpathsbetweenpairsofotherverticeswhichrunthroughi.Itisameasureoftheinfluenceofanodeovertheflowofinformationbetweenothernodes,especiallyincaseswhereinformationflowoveranetworkprimarilyfollowstheshortestavailablepath.

Inordertofindwhichedgesinanetworkaremost“be-tween”otherpairsofvertices,wegeneralizeFreeman’sbetweennesscentralitytoedgesanddefinetheedgebe-tweennessofanedgeasthenumberofshortestpathsbetweenpairsofverticesthatrunalongit.Ifthereismorethanoneshortestpathbetweenapairofvertices,eachpathisgivenequalweightsuchthatthetotalweightofallthepathsisunity.Ifanetworkcontainscommu-nitiesorgroupsthatareonlylooselyconnectedbyafewinter-groupedges,thenallshortestpathsbetweendiffer-entcommunitiesmustgoalongoneofthesefewedges.Thus,theedgesconnectingcommunitieswillhavehighedgebetweenness.Byremovingtheseedges,weseparategroupsfromoneanotherandsorevealtheunderlyingcommunitystructureofthegraph.

Thealgorithmweproposeforidentifyingcommunitiesissimplystatedasfollows:

1.Calculatethebetweennessforalledgesinthenet-work.2.Removetheedgewiththehighestbetweenness.3.Recalculatebetweennessesforalledgesaffectedbytheremoval.4.Repeatfromstep2untilnoedgesremain.Asapracticalmatter,wecalculatethebetweennessesusingthefastalgorithmofNewman[24],whichcalcu-latesbetweennessforallmedgesinagraphofnverticesintimeO(mn).Sincethiscalculationhastoberepeatedoncefortheremovalofeachedge,theentirealgorithm

3

runsinworst-casetimeO(m2n).However,followingtheremovalofeachedge,weonlyhavetorecalculatethebetweennessesofthoseedgesthatwereaffectedbytheremoval,whichisatmostonlythoseinthesamecompo-nentastheremovededge.Thismeansthatrunningtimemaybebetterthanworst-casefornetworkswithstrongcommunitystructure(oneswhichrapidlybreakupintoseparatecomponentsafterthefirstfewiterationsofthealgorithm).

Totrytoreducetherunningtimeofthealgorithmfurther,onemightbetemptedtocalculatethebetween-nessesofalledgesonlyonceandthenremovetheminorderofdecreasingbetweenness.Wefindhoweverthatthisstrategydoesnotworkwell,becauseiftwocommu-nitiesareconnectedbymorethanoneedge,thenthereisnoguaranteethatallofthoseedgeswillhavehighbetweenness—weonlyknowthatatleastoneofthemwill.Byrecalculatingbetweennessesaftertheremovalofeachedgeweensurethatatleastoneoftheremainingedgesbetweentwocommunitieswillalwayshaveahighvalue.

III.TESTSOFTHEMETHOD

Inthissectionwepresentanumberoftestsofouralgo-rithmoncomputer-generatedgraphsandonreal-worldnetworksforwhichthecommunitystructureisalreadyknown.Ineachcasewefindthatouralgorithmreliablydetectstheknownstructure.

A.Computer-generatedgraphs

Totesttheperformanceofouralgorithmonnetworkswithvaryingdegreesofcommunitystructure,wehaveappliedittoalargesetofartificial,computer-generatedgraphssimilartothosedepictedinFig.1.Eachgraphwasconstructedwith128vertices,eachofwhichwasconnectedtoexactlyz=16others.Theverticesweredividedintofourseparatecommunitieswithsomenum-berzinofeachvertex’s16connectionsmadetorandomlychosenmembersofitsowncommunityandtheremainingzout=z−zinmadetorandommembersofothercom-munities.Thisproducesgraphswhichhaveknowncom-munitystructure,butwhichareessentiallyrandominotherrespects.Usingthesegraphs,wetestedtheperfor-manceofouralgorithmastheratioofintra-communitytointer-communityconnectionswasvaried.TheresultsareshowninFig.3.Aswecansee,thealgorithmper-formsnearperfectlywhenzout≤6,classifyingvirtually100%ofverticesintotheircorrectcommunities.Onlyforzout>6doesthefractioncorrectlyclassifiedstarttofalloff.Inotherwordsthealgorithmperformsper-fectlyalmosttothepointatwhicheachvertexhasasmanyinter-communityconnectionsasintra-communityones.Thisisanencouragingfirstresultforthemethod.

4

fraction of vertices classified correctly1.0

0.5

0.0

012345678

number of inter−community edges zout

FIG.3:Thefractionofverticescorrectlyclassifiedbyourmethodasthenumberzoutofinter-communityedgesperver-texisvaried,forcomputergeneratedgraphsofthetypede-scribedinthetext.Themeasurementswithhalf-integerval-ueszout=k+1

inthe2000season.Inter-conferenceplayisnotuni-formlydistributed;teamsthataregeographicallyclosetooneanotherbutbelongtodifferentconferencesaremorelikelytoplayoneanotherthanteamsseparatedbylargegeographicdistances.

Applyingouralgorithmtothisnetwork,wefindthatitidentifiestheconferencestructurewithahighdegreeofsuccess.Almostallteamsarecorrectlygroupedwiththeotherteamsintheirconference.Thereareafewindepen-dentteamsthatdonotbelongtoanyconference—thesetendtobegroupedwiththeconferencewithwhichtheyaremostcloselyassociated.Thefewcasesinwhichthealgorithmseemstofailactuallycorrespondtonuancesintheschedulingofgames.Forexample,theSunbeltconferenceisbrokenintotwopiecesandgroupedwithmembersoftheWesternAthleticconference.Thishap-pensbecausetheSunbeltteamsplayednearlyasmanygamesagainstWesternAthleticteamsastheydidagainstteamsintheirownconference.Naturally,ouralgorithmfailsincaseslikethiswherethenetworkstructuregen-uinelydoesnotcorrespondtotheconferencestructure.Inallotherrespectshoweveritperformsremarkablywell.IV.

APPLICATIONS

Intheprevioussectionwetestedouralgorithmonanumberofnetworksforwhichthecommunitystructurewasknownbeforehand.Theresultsindicatethatoural-gorithmisasensitiveandaccuratemethodforextractingcommunitystructurefrombothrealandartificialnet-works.Inthissection,weapplyourmethodtotwomorenetworksforwhichthestructureisnotknown,andshowthatinthesecasesitcanhelpustounderstandthemake-upofotherwisecomplexandtangleddatasets.Ourfirstexampleisacollaborationnetworkofscientists;oursec-ondisafoodwebofmarineorganismsintheChesapeakeBay.

A.

Collaborationnetwork

Wehaveappliedourcommunity-findingmethodtoacollaborationnetworkofscientistsattheSantaFeIn-stitute,aninterdisciplinaryresearchcenterinSantaFe,NewMexico(andcurrentacademichometoboththeauthorsofthispaper).The271verticesinthisnetworkrepresentscientistsinresidenceattheSantaFeInsti-tuteduringanypartofcalendaryear1999or2000,andtheircollaborators.Anedgeisdrawnbetweenapairofscientistsiftheycoauthoredoneormorearticlesduringthesametimeperiod.Thenetworkincludesalljournalandbookpublicationsbythescientistsinvolved,alongwithallpapersthatappearedintheinstitute’stechni-calreportsseries.Onaverage,eachscientistcoauthoredarticleswithapproximatelyfiveothers.

InFig.6weillustratetheresultsfromtheapplicationofouralgorithmtothelargestcomponentofthecollab-

5 Florida State North Carolina State Virginia Georgia Tech Duke North Carolina Clemson Maryland Wake Forest Central Florida Connecticut Akron Bowling Green State Buffalo Kent Miami Ohio Marshall Ohio Northern Illinois Western Michigan Ball State Central Michigan Toledo Eastern Michigan Navy Notre Dame Virginia Tech Boston College West Virginia Syracuse Pittsburgh Temple Miami Florida Rutgers Alabama Birmingham East Carolina Southern Mississippi Memphis Houston Louisville Tulane Cincinnati Army Vanderbilt Florida Kentucky South Carolina Georgia Tennessee Arkansas Auburn Alabama Mississippi State Louisiana State Mississippi Louisiana Tech Louisiana Monroe Louisiana Lafayette Middle Tennessee State Oklahoma State Texas Baylor Colorado Kansas Iowa State Missouri Nebraska Texas Tech Texas A&M Oklahoma Kansas State Fresno State Rice Southern Methodist Nevada San Jose State Texas El Paso Tulsa Hawaii Texas Christian North Texas Arkansas State Boise State Idaho Utah State New Mexico State Oregon State Southern California UCLA Stanford California Arizona State Arizona Washington Washington State Oregon Brigham Young New Mexico San Diego State Wyoming Utah Colorado State Nevada Las Vegas Air Force Illinois Northwestern Michigan State Iowa Penn State Michigan Ohio State Wisconsin Purdue Indiana MinnesotaAtlantic CoastConference USAPac 10Big EastIA IndependentsSECBig 10Mid AmericanSunbeltBig 12Mountain WestWestern AthleticFIG.5:Hierarchicaltreeforthenetworkreflectingthesched-uleofregularseasonDivisionIcollegefootballgamesforyear2000.Nodesinthenetworkrepresentteamsandedgesrep-resentgamesbetweenteams.Ouralgorithmidentifiesnearlyalltheconferencestructureinthenetwork.

6

Agent-basedModelsMathematicalEcologyStatistical PhysicsStructure of RNAFIG.6:ThelargestcomponentoftheSantaFeInstitutecol-laborationnetwork,withtheprimarydivisionsdetectedbyouralgorithmrepresentedbydifferentvertexshapes.

orationgraph(whichconsistsof118scientists).Verticesaredrawnasdifferentshapesaccordingtotheprimarydivisionsdetected.Wefindthatthealgorithmsplitsthenetworkintoafewstrongcommunities,withthedivisionsrunningprincipallyalongdisciplinarylines.Thecom-munityatthetopofthefigure(diamonds)istheleastwelldefined,andrepresentsagroupofscientistsusingagent-basedmodelstostudyproblemsineconomicsandtrafficflow.Thealgorithmfurtherdividesthisgroupintosmallercomponentsthatcorrespondroughlywiththesplitbetweeneconomicsandtraffic.Thenextcom-munity(circles)representsagroupofscientistsworkingonmathematicalmodelsinecology,andformsafairlycohesivestructure,asevidencedbythefactthattheal-gorithmdoesnotbreakitintosmallercomponentstoanysignificantextent.Thelargestcommunity(representedbythesquares)isagroupworkingprimarilyinstatisti-calphysics,andissub-dividedintoseveralwell-definedsmallergroupswhicharedenotedbythevariousshad-ings.Inthiscase,eachsub-communityseemstorevolvearoundtheresearchinterestsofonedominantmember.Thefinalcommunityatthebottomofthefigure(tri-angles)isagroupworkingprimarilyonthestructureofRNA.Ittoocanbedividedfurtherintosmallersub-communities,centeredonceagainaroundtheinterestsofleadingmembers.

Ouralgorithmthusseemstofindtwotypesofcommu-nities:scientistsgroupedtogetherbysimilarityeitherofresearchtopicorofmethodology.Itisnotsurprisingto

Heterotrophic microflagellates Free bacteria in water column/DOC * Fish larvae American shad Striped bassy Alewife and blue herring Sea nettles Blue crab Atlantic menhaden Ctenophores American oyster ZooplanktonBacteria attached to suspended POC ¦ Other suspension feeders Phytoplankton Softshell clam Microzooplankton Bay anchovy Summer flounder Weakfish White perch Bluefish spp. (bivalve) Macoma Sea catfish Bacteria attached to sediment POC ¦ Hogchoker Other olychaetes Spot (Rag worm) Nereis Atlantic croaker Crustacean deposit feeders Benthic diatoms Meiofauna* Dissolved Organic CarbonBenthic Organisms¦Particulate Organic CarbonPelagic OrganismsUndeterminedFIG.7:HierarchicaltreefortheChesapeakeBayfoodwebdescribedinthetext.

seecommunitiesbuiltaroundresearchtopics;weexpectscientiststocollaborateprimarilywithotherswithwhomtheirresearchfocusiscloselyaligned.Theformationofcommunitiesaroundmethodologiesismoreinteresting,andmaybethemarkoftrulyinterdisciplinarywork.Forexample,thegroupingofthoseworkingoneconomicswiththoseworkingontrafficmodelsmayseemsurpris-ing,untilonerealizesthatthetechnicalapproachesthesescientistshavetakenarequitesimilar.Asaresultofthesekindsofsimilarities,thenetworkcontainstiesbe-tweenresearchersfromtraditionallydisparatefields.Weconjecturethatthisfeaturemaybepeculiartointerdis-ciplinarycentersliketheSantaFeInstitute.

B.Foodweb

WehavealsoappliedouralgorithmtoafoodwebofmarineorganismslivingintheChesapeakeBay,alargeestuaryontheeastcoastoftheUnitedStates.ThisnetworkwasoriginallycompiledbyBairdandUlanow-icz[26]andcontains33verticesrepresentingtheecosys-tem’smostprominenttaxa.Mosttaxaarerepresentedatthespeciesorgenuslevel,althoughsomeverticesrep-resentgroupsofrelatedspecies.Edgesbetweentaxain-dicatetrophicrelationships—onetaxonfeedingonan-other.Althoughrelationshipsofthiskindareinherentlydirected,wehereignoredirectionandconsiderthenet-worktobeundirected.

Applyingouralgorithmtothisnetwork,wefindtwowell-definedcommunitiesofroughlyequalsize,plusasmallnumberofverticesthatbelongtoneithercommunity—seeFig.7.Asthefigureshows,thesplitbetweenthetwolargecommunitiescorrespondsquitecloselywiththedivisionbetweenpelagicorganisms(ones

7

thatdwellprincipallynearthesurfaceorinthemiddledepthsofthebay)andbenthicorganisms(onesthatdwellnearthebottom).Interestingly,thealgorithmincludeswithineachgrouporganismsfromavarietyofdiffer-enttrophiclevels.Thiscontrastswithothertechniquesthathavebeenusedtoanalyzefoodwebs[28],whichtendtoclustertaxaaccordingtotrophiclevelratherthanhabitat.OurresultsseemtoimplythatpelagicandbenthicorganismsintheChesapeakeBaycanbeseparatedintoreasonablyself-containedecologicalsub-systems.Theseparationisnotperfect:asmallnumberofbenthicorganismsfindtheirwayintothepelagiccommu-nity,presumablyindicatingthatthesespeciesplayasub-stantialroleinthefoodchainsoftheirsurface-dwellingcolleagues.Thissuggeststhatthesimpletraditionaldi-visionoftaxaintopelagicorbenthicmaynotbeanidealclassificationinthiscase.

Wehavealsoappliedourmethodtoanumberofotherfoodwebs.Interestingly,whilesomeoftheseshowclearcommunitystructuresimilartothatofFig.7,someoth-ersdonot.Thiscouldbebecausesomeecosystemsaregenuinelynotcomposedofseparatecommunities,butitcouldalsobebecausemanyfoodwebs,unlikeothernet-works,aredense,i.e.,thenumberofedgesscalesasthesquareofthenumberofverticesratherthanscalinglin-early[27].Ouralgorithmwasdesignedwithsparsenet-worksinmind,anditispossiblethatitmaynotperformaswellondensenetworks.

V.

CONCLUSIONS

Acknowledgments

withwell-documentedstructureandfindtheresultstobeinexcellentagreementwithexpectations.Inaddi-tion,wehavegiventwoexamplesofapplicationsofthealgorithmtonetworkswhosestructurewasnotpreviouslywell-documentedandfindthatinbothcasesitextractsclearcommunitieswhichappeartocorrespondtoplausi-bleandinformativedivisionsofthenetworknodes.

Anumberofextensionsorimprovementsofourmethodmaybepossible.First,wehopetogeneralizethemethodtohandlebothweightedanddirectedgraphs.Second,wehopethatitmaybepossibletoimprovethespeedofthealgorithm.Atpresent,thealgorithmrunsintimeO(n3)onsparsegraphs,wherenisthenum-berofverticesinthenetwork.Thismakesitimpracticalforverylargegraphs.Detectingcommunitiesin,forin-stance,thelargecollaborationnetworks[6]orsubsetsoftheWebgraph[9]thathavebeenstudiedrecently,wouldbeentirelyunfeasible.Perhaps,however,thebasicprin-ciplesofourapproach—focusingontheboundariesofcommunitiesratherthantheircores,andmakinguseofedgebetweenness—canbeincorporatedintoamodifiedmethodthatscalesmorefavorablywithnetworksize.Wehopethattheideasandmethodspresentedherewillproveusefulintheanalysisofmanyothertypesofnetworks.Possiblefurtherapplicationsrangefromthedeterminationoffunctionalclusterswithinneuralnet-workstoanalysisofcommunitiesontheWorld-WideWeb,aswellasothersnotyetthoughtof.Wehopetoseesuchapplicationsinthefuture.

Inthispaperwehaveinvestigatedcommunitystruc-tureinnetworksofvariouskinds,introducinganewmethodfordetectingsuchstructure.Unlikepreviousmethodswhichfocusonfindingthestronglyconnectedcoresofcommunities,ourapproachworksbyusingin-formationaboutedgebetweennesstodetectcommunityperipheries.Wehavetestedourmethodoncomputergeneratedgraphsandhaveshownthatitdetectstheknowncommunitystructurewithahighdegreeofsuc-cess.Wehavealsotesteditontworeal-worldnetworks

TheauthorswouldliketothankJenniferDunne,NeoMartinez,MatthewSalganik,SteveStrogatz,andDougWhiteforusefulconversations,andJenniferDunne,SarahKnutson,MatthewSalganik,andDougWhiteforhelpcompilingthedataforthefoodweb,collaboration,collegefootball,andkarateclubnetworks,respectively.ThisworkwasfundedinpartbytheNationalScienceFoundationundergrantnumberDMS–0109086.

[1]S.H.Strogatz,Exploringcomplexnetworks.Nature410,

268–276(2001).

[2]S.WassermanandK.Faust,SocialNetworkAnalysis.

CambridgeUniversityPress,Cambridge(1994).

[3]J.Scott,SocialNetworkAnalysis:AHandbook.Sage

Publications,London,2ndedition(2000).

[4]D.J.WattsandS.H.Strogatz,Collectivedynamicsof

‘small-world’networks.Nature393,440–442(1998).[5]L.A.N.Amaral,A.Scala,M.Barth´el´emy,andH.E.

Stanley,Classesofsmall-worldnetworks.Proc.Natl.Acad.Sci.USA97,11149–11152(2000).

[6]M.E.J.Newman,Thestructureofscientificcollabora-tionnetworks.Proc.Natl.Acad.Sci.USA98,404–409

[7][8][9]

[10][11]

(2001).

M.Faloutsos,P.Faloutsos,andC.Faloutsos,Onpower-lawrelationshipsoftheinternettopology.ComputerCommunicationsReview29,251–262(1999).R.Albert,H.Jeong,andA.-L.Barab´asi,Diameteroftheworld-wideweb.Nature401,130–131(1999).

A.Broder,R.Kumar,F.Maghoul,P.Raghavan,S.Ra-jagopalan,R.Stata,A.Tomkins,andJ.Wiener,Graphstructureintheweb.ComputerNetworks33,309–320(2000).

R.J.WilliamsandN.D.Martinez,Simplerulesyieldcomplexfoodwebs.Nature404,180–183(2000).

H.Jeong,B.Tombor,R.Albert,Z.N.Oltvai,andA.-

8

L.Barab´asi,Thelarge-scaleorganizationofmetabolicnetworks.Nature407,651–6(2000).

[12]D.A.FellandA.Wagner,Thesmallworldofmetabolism.NatureBiotechnology18,1121–1122(2000).[13]I.PoolandM.Kochen,Contactsandinfluence.SocialNetworks1,1–48(1978).

[14]S.Milgram,Thesmallworldproblem.PsychologyToday2,60–67(1967).[15]A.-L.Barab´asiandR.Albert,Emergenceofscalinginrandomnetworks.Science286,509–512(1999).

[16]P.L.Krapivsky,S.Redner,andF.Leyvraz,Connectivityofgrowingrandomnetworks.Phys.Rev.Lett.85,4629–4632(2000).

[17]S.N.Dorogovtsev,J.F.F.Mendes,andA.N.Samukhin,Structureofgrowingnetworkswithpreferentiallinking.Phys.Rev.Lett.85,4633–4636(2000).

[18]M.E.J.Newman,S.H.Strogatz,andD.J.Watts,Ran-domgraphswitharbitrarydegreedistributionsandtheirapplications.Phys.Rev.E,026118(2001).

[19]

S.Redner,Howpopularisyourpaper?Anempiricalstudyofthecitationdistribution.Eur.Phys.J.B4,131–134(1998).

[20]K.Menger,ZurallgemeinenKurventheorie.Fundamenta

Mathematicae10,96–115(1927).

[21]D.R.WhiteandF.Harary,Thecohesivenessofblocks

insocialnetworks:Connectivityandconditionaldensity.SociologicalMethodology,inpress.

[22]L.Katz,Anewstatusindexderivedfromsociometric

analysis.Psychometrika18,39–43(1953).

[23]L.Freeman,Asetofmeasuresofcentralitybasedupon

betweeness.Sociometry40,35–41(1977).

[24]M.E.J.Newman,Scientificcollaborationnetworks:II.

Shortestpaths,weightednetworks,andcentrality.Phys.Rev.E,016132(2001).

[25]W.W.Zachary,Aninformationflowmodelforconflict

andfissioninsmallgroups.JournalofAnthropologicalResearch33,452–473(1977).

[26]D.BairdandR.E.Ulanowicz,Theseasonaldynamicsof

theChesapeakeBayecosystem.EcologicalMonographs59,329–3(19).

[27]N.D.Martinez,Constantconnectanceincommunity

foodwebs.AmericanNaturalist139,1208–1218(1992).[28]J.J.Luczkovich,personalcommunication.