NETWORKS

Thispageintentionallyleftblank

Networks

AnIntroduction

M.E.J.Newman

UniversityofMichigan

and

SantaFeInstitute

1

3

GreatClarendonStreet,OxfordOX26DP

OxfordUniversityPressisadepartmentoftheUniversityofOxford.

ItfurtherstheUniversity’sobjectiveofexcellenceinresearch,scholarship,

andeducationbypublishingworldwidein

OxfordNewYork

AucklandCapeTownDaresSalaamHongKongKarachi

KualaLumpurMadridMelbourneMexicoCityNairobi

NewDelhiShanghaiTaipeiToronto

Withofficesin

ArgentinaAustriaBrazilChileCzechRepublicFranceGreece

GuatemalaHungaryItalyJapanPolandPortugalSingapore

SouthKoreaSwitzerlandThailandTurkeyUkraineVietnam

OxfordisaregisteredtrademarkofOxfordUniversityPress

intheUKandincertainothercountries

PublishedintheUnitedStates

byOxfordUniversityPressInc.,NewYork

?M.E.J.Newman2010

Themoralrightsoftheauthorhavebeenasserted

DatabaserightOxfordUniversityPress(maker)

Firstprinted2010

Allrightsreserved.Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmitted,inanyformorbyanymeans,withoutthepriorpermissioninwritingofOxfordUniversityPress,orasexpresslypermittedbylaw,orundertermsagreedwiththeappropriate

reprographicsrightsorganization.EnquiriesconcerningreproductionoutsidethescopeoftheaboveshouldbesenttotheRightsDepartment,OxfordUniversityPress,attheaddressabove

Youmustnotcirculatethisbookinanyotherbindingorcover

andyoumustimposethesameconditiononanyacquirer

BritishLibraryCataloguinginPublicationData

Dataavailable

LibraryofCongressCataloginginPublicationData

Dataavailable

TypesetbySPIPublisherServices,Pondicherry,India

PrintedinGreatBritain

onacid-freepaperby

CPIAntonyRowe,Chippenham,Wiltshire

ISBN978–0–19–920665–0(Hbk.)

CONTENTS

Preface

x

1 Introduction 1

ITheempiricalstudyofnetworks

15

2

Technologicalnetworks

17

2.1

TheInternet.............................

18

2.2

Thetelephonenetwork.......................

28

2.3

Powergrids.............................

31

2.4

Transportationnetworks......................

32

2.5

Deliveryanddistributionnetworks................

33

3

Socialnetworks

36

3.1

Theempiricalstudyofsocialnetworks..............

36

3.2

Interviewsandquestionnaires...................

39

3.3

Directobservation..........................

46

3.4

Datafromarchivalorthird-partyrecords............

47

3.5

Affiliationnetworks.........................

53

3.6

Thesmall-worldexperiment....................

54

3.7

Snowballsampling,contacttracing,andrandomwalks....

58

4

Networksofinformation

63

4.1

TheWorldWideWeb........................

63

4.2

Citationnetworks..........................

67

4.3

Otherinformationnetworks....................

72

5

Biologicalnetworks

78

5.1

Biochemicalnetworks.......................

78

5.2

Neuralnetworks...........................

94

5.3

Ecologicalnetworks.........................

99

v

CONTENTS

IIFundamentalsofnetworktheory

107

6

Mathematicsofnetworks

109

6.1

Networksandtheirrepresentation................

109

6.2

Theadjacencymatrix........................

110

6.3

Weightednetworks.........................

112

6.4

Directednetworks..........................

114

6.5

Hypergraphs.............................

122

6.6

Bipartitenetworks..........................

123

6.7

Trees.................................

127

6.8

Planarnetworks...........................

129

6.9

Degree................................

133

6.10

Paths.................................

136

6.11

Components.............................

142

6.12

Independentpaths,connectivity,andcutsets..........

145

6.13

ThegraphLaplacian........................

152

6.14

Randomwalks............................

157

7

Measuresandmetrics

168

7.1

Degreecentrality..........................

168

7.2

Eigenvectorcentrality........................

169

7.3

Katzcentrality............................

172

7.4

PageRank...............................

175

7.5

Hubsandauthorities........................

178

7.6

Closenesscentrality.........................

181

7.7

Betweennesscentrality.......................

185

7.8

Groupsofvertices..........................

193

7.9

Transitivity..............................

198

7.10

Reciprocity..............................

204

7.11

Signededgesandstructuralbalance...............

206

7.12

Similarity...............................

211

7.13

Homophilyandassortativemixing................

220

8

Thelarge-scalestructureofnetworks

235

8.1

Components.............................

235

8.2

Shortestpathsandthesmall-worldeffect............

241

8.3

Degreedistributions........................

243

8.4

Powerlawsandscale-freenetworks...............

247

8.5

Distributionsofothercentralitymeasures............

261

8.6

Clusteringcoefficients.......................

262

vi

CONTENTS

8.7

Assortativemixing.........................

266

IIIComputeralgorithms

273

9

Basicconceptsofalgorithms

275

9.1

Runningtimeandcomputationalcomplexity..........

278

9.2

Storingnetworkdata........................

282

9.3

Theadjacencymatrix........................

283

9.4

Theadjacencylist..........................

286

9.5

Trees.................................

290

9.6

Othernetworkrepresentations..................

298

9.7

Heaps.................................

301

10

Fundamentalnetworkalgorithms

308

10.1

Algorithmsfordegreesanddegreedistributions........

308

10.2

Clusteringcoefficients.......................

310

10.3

Shortestpathsandbreadth-firstsearch..............

315

10.4

Shortestpathsinnetworkswithvaryingedgelengths.....

329

10.5

Maximumflowsandminimumcuts...............

333

11

Matrixalgorithmsandgraphpartitioning

345

11.1

Leadingeigenvectorsandeigenvectorcentrality........

345

11.2

Dividingnetworksintoclusters..................

354

11.3

Graphpartitioning.........................

358

11.4

TheKernighan–Linalgorithm...................

360

11.5

Spectralpartitioning........................

364

11.6

Communitydetection........................

371

11.7

Simplemodularitymaximization.................

373

11.8

Spectralmodularitymaximization................

375

11.9

Divisionintomorethantwogroups...............

378

11.10

Othermodularitymaximizationmethods............

380

11.11

Otheralgorithmsforcommunitydetection...........

382

IVNetworkmodels

395

12

Randomgraphs

397

12.1

Randomgraphs...........................

398

12.2

Meannumberofedgesandmeandegree............

400

12.3

Degreedistribution.........................

401

vii

CONTENTS

12.4

Clusteringcoefficient........................

402

12.5

Giantcomponent

..........................

403

12.6

Smallcomponents..........................

408

12.7 Pathlengths............................. 419

12.8

Problemswiththerandomgraph.................

423

13

Randomgraphswithgeneraldegreedistributions

428

13.1

Generatingfunctions........................

429

13.2

Theconfigurationmodel......................

434

13.3

Excessdegreedistribution.....................

445

13.4

Clusteringcoefficient........................

449

13.5

Generatingfunctionsfordegreedistributions..........

450

13.6

Numberofsecondneighborsofavertex.............

451

13.7

Generatingfunctionsforthesmallcomponents.........

456

13.8

Giantcomponent

..........................

460

13.9

Sizedistributionforsmallcomponents..............

465

13.10Power-lawdegreedistributions.................. 470

13.11Directedrandomgraphs......................

473

14

Modelsofnetworkformation

486

14.1

Preferentialattachment.......................

487

14.2

ThemodelofBarabasi′andAlbert.................

500

14.3

Furtherpropertiesofpreferentialattachmentmodels

.....

503

14.4

Extensionsofpreferentialattachmentmodels..........

514

14.5 Vertexcopyingmodels....................... 534

14.6

Networkoptimizationmodels...................

541

15

Othernetworkmodels

552

15.1 Thesmall-worldmodel....................... 552

15.2 Exponentialrandomgraphs.................... 565

V

Processesonnetworks

589

16

Percolationandnetworkresilience

591

16.1

Percolation..............................

592

16.2

Uniformrandomremovalofvertices...............

594

16.3

Non-uniformremovalofvertices.................

609

16.4 Percolationinreal-worldnetworks................ 615

16.5 Computeralgorithmsforpercolation............... 616

viii

CONTENTS

17

Epidemicsonnetworks

627

17.1

Modelsofthespreadofdisease..................

627

17.2

TheSImodel.............................

628

17.3

TheSIRmodel............................

631

17.4

TheSISmodel............................

636

17.5

TheSIRSmodel...........................

637

17.6

Epidemicmodelsonnetworks...................

639

17.7

Late-timepropertiesofepidemicsonnetworks.........

640

17.8

Late-timepropertiesoftheSIRmodel

..............

642

17.9

Time-dependentpropertiesofepidemicsonnetworks.....

648

17.10Time-dependentpropertiesoftheSImodel...........

648

17.11Time-dependentpropertiesoftheSIRmodel .......... 661

17.12Time-dependentpropertiesoftheSISmodel

..........

669

18

Dynamicalsystemsonnetworks

676

18.1

Dynamicalsystems.........................

677

18.2

Dynamicsonnetworks.......................

686

18.3 Dynamicswithmorethanonevariablepervertex ....... 695

18.4

Synchronization...........................

701

19

Networksearch

705

19.1

Websearch..............................

705

19.2 Searchingdistributeddatabases.................. 709

19.3

Messagepassing...........................

713

References

727

Index 740

ix

PREFACE

Thescientificstudyofnetworks,suchascomputernetworks,biologicalnet-works,andsocialnetworks,isaninterdisciplinaryfieldthatcombinesideasfrommathematics,physics,biology,computerscience,thesocialsciences,andmanyotherareas.Thefieldhasbenefitedenormouslyfromthewiderangeofviewpointsbroughttoitbypractitionersfromsomanydifferentdisciplines,butithasalsosufferedbecausehumanknowledgeaboutnetworksisdispersedacrossthescientificcommunityandresearchersinoneareaoftendonothavereadyaccesstodiscoveriesmadeinanother.Thegoalofthisbookistobringourknowledgeofnetworkstogetherandpresentitinconsistentlanguageandnotation,sothatitbecomesacoherentwholewhoseelementscomplementoneanotherandincombinationteachusmorethananysingleelementcanalone.

Thebookisdividedintofiveparts.Followingashortintroductorychap-ter,PartIdescribesthebasictypesofnetworksstudiedbypresent-dayscienceandtheempiricaltechniquesusedtodeterminetheirstructure.PartIIintro-ducesthefundamentalmathematicaltoolsusedinthestudyofnetworksaswellasmeasuresandstatisticsforquantifyingnetworkstructure.PartIIIde-scribescomputeralgorithmsfortheefficientanalysisofnetworkdata,whilePartIVdescribesmathematicalmodelsofnetworkstructurethatcanhelpuspredictthebehaviorofnetworkedsystemsandunderstandtheirformationandgrowth.Finally,PartVdescribestheoriesofprocessestakingplaceonnet-works,suchasepidemicsonsocialnetworksorsearchprocessesoncomputernetworks.

Thetechnicallevelofthepresentationvariesamongtheparts,PartIrequir-ingvirtuallynomathematicalknowledgeforitscomprehension,whilePartsIIandIIIrequireagraspoflinearalgebraandcalculusattheundergraduatelevel.PartsIVandVaremathematicallymoreadvancedandsuitableforad-vancedundergraduates,postgraduates,andresearchersworkinginthefield.Thebookcouldthusbeusedasthebasisofataughtcourseatmorethanonelevel.AlesstechnicalcoursesuitableforthosewithmoderatemathematicalknowledgemightcoverthematerialofChapters1to8,whileamoretechnicalcourseforadvancedstudentsmightcoverthematerialofChapters6to14and

x

selectedmaterialthereafter.EachchapterfromPartIIonwardisaccompaniedbyaselectionofexercisesthatcanbeusedtotestthereader’sunderstandingofthematerial.

Thisbookhasbeensomeyearsinthemakingandmanypeoplehavehelpedmewithitduringthattime.Imustthankmyever-patienteditorSonkeAdlung,withwhomIhaveworkedonvariousbookprojectsformorethan15yearsnow,andwhoseconstantencouragementandkindwordshavemadeworkingwithhimandOxfordUniversityPressarealpleasure.ThanksarealsoduetoMelanieJohnstone,AlisonLees,EmmaLonie,andAprilWarmanfortheirhelpwiththefinalstagesofbringingthebooktoprint.

Ihavebenefitedgreatlyduringthewritingofthisbookfromtheconver-sation,comments,suggestions,andencouragementofmanycolleaguesandfriends.Theyare,sadly,toonumeroustomentionexhaustively,butspecialthanksmustgotoSteveBorgatti,DuncanCallaway,AaronClauset,BetsyFox-man,LintonFreeman,MichelleGirvan,MartinGould,MarkHandcock,Pet-terHolme,JonKleinberg,AldenKlovdahl,LizaLevina,LaurenMeyers,CrisMoore,LouPecora,MasonPorter,SidneyRedner,PuckRombach,CosmaShal-izi,SteveStrogatz,DuncanWatts,DougWhite,LenkaZdeborova,andBobZiff,aswellastothemanystudents,particularlyMichelleAdan,AlejandroBalbin,ChrisFink,RuthiHortsch,andJaneWang,whosefeedbackhelpedironoutalotofroughspots.IwouldalsoespeciallyliketothankBrianKarrer,whoreadtheentirebookindraftformandgavememanypagesofthoughtfulandthought-provokingcomments,aswellasspottinganumberofmistakesandtypos.Responsibilityforanyremainingmistakesinthebookofcourserestsentirelywithmyself,andIwelcomecorrectionsfromreaders.

Finally,myprofoundthanksgotomywifeCarrieforhercontinualencour-agementandsupportduringthewritingofthisbook.WithoutherthebookwouldstillhavebeenwrittenbutIwouldhavesmiledalotless.

MarkNewman

AnnArbor,Michigan

February24,2010

xi

Thispageintentionallyleftblank

CHAPTER1

INTRODUCTION

Ashortintroductiontonetworks

andwhywestudythem

NETWORKis,initssimplestform,acollectionofpointsjoinedtogetherinpairsbylines.Inthejargonofthefieldthepointsarereferredtoas

vertices1ornodesandthelinesarereferredtoasedges.Manyobjectsofinterestinthephysical,biological,andsocialsciencescanbethoughtofasnetworksand,asthisbookaimstoshow,thinkingoftheminthiswaycanoftenleadtonewandusefulinsights.

Webegin,inthisintroductorychapter,withadiscussionofwhyweareinterestedinnetworksandabriefdescriptionofsomespecificnetworksofnote.Allthetopicsinthischapterarecoveredingreaterdepthelsewhereinthebook.

WHYAREWEINTERESTEDINNETWORKS?

Therearemanysystemsofinteresttoscientiststhatarecomposedofindividualpartsorcomponentslinkedtogetherinsomeway.ExamplesincludetheInter-net,acollectionofcomputerslinkedbydataconnections,andhumansocieties,whicharecollectionsofpeoplelinkedbyacquaintanceorsocialinteraction.

Manyaspectsofthesesystemsareworthyofstudy.Somepeoplestudythenatureoftheindividualcomponents—howacomputerworks,forinstance,orhowahumanbeingfeelsoracts—whileothersstudythenatureoftheconnec-tionsorinteractions—thecommunicationprotocolsusedontheInternetorthedynamicsofhumanfriendships.Butthereisathirdaspecttotheseinteracting

Singular:vertex.

Vertex

Edge

Asmallnetworkcomposedofeightverticesandtenedges.

1

INTRODUCTION

ThemostcommonnetworkvariantsarediscussedindetailinChapter6.

systems,sometimesneglectedbutalmostalwayscrucialtothebehaviorofthesystem,whichisthepatternofconnectionsbetweencomponents.

Thepatternofconnectionsinagivensystemcanberepresentedasanet-work,thecomponentsofthesystembeingthenetworkverticesandthecon-nectionstheedges.Uponreflectionitshouldcomeasnosurprise(althoughinsomefieldsitisarelativelyrecentrealization)thatthestructureofsuchnetworks,