《graph theory and complex networks》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
GraphTheoryandComplexNetworksAnIntroductionMaartenvanSteen Copyright©2010MaartenvanSteenPublishedbyMaartenvanSteenISBN:978-90-815406-1-2Edition:1.Printing:01(April2010)AllrightstotextandillustrationsarereservedbyMaartenvanSteen.Thisworkmaynotbecopied,reproduced,ortranslatedinwholeorpartwithoutwrittenpermissionofthepublisher,exceptforbriefexcerptsinreviewsorscholarlyanalysis.Usewithanyformofinformationstorageandretrieval,electronicadaptationorwhatever,computersoftware,orbysimilarordissimilarmethodsnowknownordevelopedinthefutureisstrictlyforbiddenwithoutwrittenpermissionofthepublisher. ToMarielle,Max,andElke¨ CONTENTSPrefaceix1Introduction11.1Communicationnetworks.....................4Historicalperspective........................4FromtelephonytotheInternet..................6TheWebandWikis.........................81.2Socialnetworks...........................9Onlinecommunities........................9Traditionalsocialnetworks....................101.3Networkseverywhere.......................111.4Organizationofthisbook.....................132Foundations172.1Formalities..............................18Graphsandvertexdegrees.....................18Degreesequence...........................23Subgraphsandlinegraphs.....................282.2Graphrepresentations.......................31Datastructures...........................31Graphisomorphism........................332.3Connectivity.............................372.4Drawinggraphs...........................45Graphembeddings.........................45Planargraphs............................503Extensions553.1Directedgraphs...........................57Basicsofdirectedgraphs......................57v Connectivityfordirectedgraphs.................613.2Weightedgraphs..........................653.3Colorings...............................69Edgecolorings............................69Vertexcolorings...........................714Networktraversal794.1Eulertours..............................81ConstructinganEulertour.....................82TheChinesepostmanproblem..................874.2Hamiltoncycles...........................92PropertiesofHamiltoniangraphs.................92FindingaHamiltoncycle......................97OptimalHamiltoncycles......................1005Trees1055.1Background.............................107Treesintransportationnetworks.................107Treesasdatastructures.......................1095.2Fundamentals............................1125.3Spanningtrees............................1165.4Routingincommunicationnetworks...............119Dijkstra’salgorithm.........................120TheBellman-Fordalgorithm....................123Anoteonalgorithmicperformance................1276Networkanalysis1316.1Vertexdegrees............................133Degreedistribution.........................134Degreecorrelations.........................1366.2Distancestatistics..........................1406.3Clusteringcoefficient........................143Someeffectsofclustering.....................143Localview..............................144Globalview.............................1466.4Centrality..............................1507Randomnetworks1557.1Introduction.............................1577.2Classicalrandomnetworks....................158Degreedistribution.........................159Othermetricsforrandomgraphs.................162vi 7.3Smallworlds.............................1667.4Scale-freenetworks.........................172Fundamentals............................172Propertiesofscale-freenetworks.................178Relatednetworks..........................1818Moderncomputernetworks1858.1TheInternet.............................187Computernetworks.........................187MeasuringthetopologyoftheInternet..............1928.2Peer-to-peeroverlaynetworks...................195Structuredoverlaynetworks....................196Randomoverlaynetworks.....................2048.3TheWorldWideWeb........................212TheorganizationoftheWeb....................212MeasuringthetopologyoftheWeb................2149Socialnetworks2239.1Socialnetworkanalysis:introduction..............225Examples...............................225Historicalbackground.......................227Sociogramsinpractice:ateacher’said..............2319.2Somebasicconcepts........................234Centralityandprestige.......................234Structuralbalance..........................240Cohesivesubgroups........................246Affiliationnetworks.........................2529.3Equivalence.............................255Structuralequivalence.......................255Automorphicequivalence.....................258Regularequivalence........................259Conclusions261Mathematicalnotations267Index271Bibliography279vii PREFACEWhenIwasappointedDirectorofEducationfortheComputerSciencede-partmentatVUUniversity,IbecamepartlyresponsibleforrevitalizingourCScurriculum.Atthatpointintime,mathematicswasgenerallyexperi-encedbymoststudentsasdifficult,butevenmoreimportant,asbeingir-relevantforsuccessfullycompletingyourstudies.DespitenumerouseffortsfrommycolleaguesfromtheMathematicsdepartment,thisviewonmath-ematicshasneverreallychanged.ImyselfobtainedamastersdegreeinAppliedMathematics(andinparticularCombinatorics)beforeswitchingtoComputerScienceandgraduallymovingintothefieldoflarge-scaledis-tributedsystems.Myownresearchisbynaturehighlyexperimental,andbeingforcedtohandlelargesystems,bumpingintothetheoryandpracticeofcomplexnetworkswasalmostinevitable.Ialsoneverquitequitenjoyingmaterialon(combinatorial)algorithms,soIdecidedtorunanothertypeofexperiment.Theexperimentthateventuallyledtothistextwastoteachgraphthe-orytofirst-yearstudentsinComputerScienceandInformationScience.Ofcourse,Ineededtoexplainwhygraphtheoryisimportant,soIdecidedtoplacegraphtheoryinthecontextofwhatisnowcallednetworkscience.ThegoalwastoarousecuriosityinthisnewscienceofmeasuringthestructureoftheInternet,discoveringwhatonlinesocialcommunitieslooklike,obtainadeeperunderstandingoforganizationalnetworks,andsoon.Whiledoingso,teachinggraphtheorywasjustpartofthedeal.Noappropriatebookexisted,soIstartedwritinglecturenotes.AswithmostexperimentsthatIparticipatein(thehardworkisactuallydonebymystudents),thingsgotabitoutofhandandIeventuallyfoundmyselfwrit-inganotherbook.Consideringthatmyothertextbooksarereallyon(dis-tributed)computersystemsandbarelycontainanymathematicalsymbols(as,infact,isalsothecaseformostofmyresearchpapers),thisbookistobeconsideredassomewhatexceptional.Infact,becauseIdonotconsiderix myselftobeamathematiciananymore,I’mnotquitesurehowthisbookshouldbeclassified.Isitmath?Isitcomputerscience?Doesitmatter?Thegoalistoprovideafirstintroductionintocomplexnetworks,yetinamoreorlessrigorousway.Afterstudyingthismaterial,astudentshouldhaveaprettygoodideaofwhatmakesreal-worldnetworkscomplexin-steadofcomplicated,andcandoalotmorethanjusthandwavingwhenitcomestoexplainingreal-worldphenomena.Whilegettingtothatpoint,Ialsohopetohaveachievedtwoothergoals:successfullyteachingthefoun-dationsofgraphtheory,andevenmoreimportant,loweringthethresholdforstudyingmathematicalmaterial.Thelattermaynotbeobviouswhenskimmingthroughthetext:itisfullofmathematicalsymbols,theorems,andproofs.Ihavedeliberatelychosenforthisapproach,feelingconfidentthatifenoughandtargetedattentionispaidtothelanguageofmathematicsinthefirstchapters,astudentwillbecomeawareofthefactthatmathematicallanguageissometimesonlyin-timidating:mathematicians’barksareoftenworsethantheirbites.Studentswhohavesofarfollowedmyclasseshaveindeedconfirmedthattheyweresurprisedathowmucheasieritwastoaccessthemathoncetheygotoverthenotations.Ihopethatthisapproachwilllastforlong,makingitatleasteasierformanystudentstonotimmediatelypullbackwhenencounteringmathematicallanguageinothertexts.IntendedreadershipThisbookhasbeenwrittenforfirst-orsecond-yearundergraduateswhohavetakentheusualcoursesinmathematicsastaughtinhighschool.How-ever,althoughIclaimthatthematerialisnotinherentlydifficult,itwillcer-tainlyrequireseriousstudyingbymoststudents,andcertainlythoseforwhichmathdoesnotcomenatural.Asmentioned,Ihavedeliberatelycho-sentousethelanguageofmathbecauseitisnotonlypreciseandcompre-hensive,butaboveallbecauseIbelievethatatthelevelofthisbook,itwilllowerthethresholdforothermathematicaltexts.Itshouldbeclearthatthelecturerusingthismaterialmayneedtopaysomespecialefforttoencour-agestudents.Formoststudents,thelanguagewillturnouttobethehardpart,notthecontent.SupplementarymaterialAssaid,thisbookispartofacourseongraphtheoryandcomplexnet-works.Althoughitcanbeusedforself-study,IencouragestudentsandtheirinstructorstovisittheaccompanyingWebsite:http://www.distributed-systems.net/gtcn/x wherelotsofextramaterialcanbefound,including,mostimportantly,ahugecollectionofexercises(withsolutions).Mygoalistoexpandthissetofexercisescontinuously.Thisisthemostimportantreasonnottohaveincludedanyexercisesinthebook:theycanbereadilyobtainedfromthesite,andalwaysup-to-date.Tomakethematerialmoreaccessible(andfun),butalsotoallowstu-dentstodosomebasicanalysisoflargergraphsandnetworks,wehavebeenusingMathematicaincombinationwithCombinatorica.Allmate-rial,includingMathematicanotebooksanddataongraphsareallavail-ablethroughtheWebsite.Thesitealsohassomeextratoolsforgeneratinggraphs.Ofcourse,slidesandhandoutsareavailable(alloriginatingfromLATEXsources),aswellasallthefiguresfromthebook.Perhapsmostimportantly,anelectronicversionofthebookitselfisalsoavailable.AllmaterialisfreelyaccessibleSometimeswhenyouwriteabook,itmakesalotofsensetothinkbigandactcommercially.Thinkingbiginthissensemeansyouexpectmanypeopletohaveaccesstoyourbook.Actingcommerciallymeansthatyoutrytosuccessfullymarketandsellyourbook.Sometimes,it’senoughtojustthinkbig,knowingthatactingcommerciallywillcertainlykeepeverythingsmall.Whenyouwriteabookcontainingmathematicalsymbols,thinkingbigandactingcommerciallydoesn’tseemtherightcombination.Imerelyhopetoseethematerialtobeusedbymanystudentsandinstructorseverywhereandtoreceivealotofconstructivefeedbackthatwillleadtoimprovements.Actingcommerciallyhasneverbeenoneofstrongpointsanyway.However,freelyaccessibledoesn’tmeanthateveryonehastherighttocopyandspreadthematerial,whichIwouldfindquiteoffensive.Forthisreason,whenrequestinganelectroniccopy,thebookwillbewatermarkedwithyoure-mailaddress.ThewatermarkispartoftheLATEXsource,soit’sprettydifficulttoremove,althoughIdonothavetheillusionthatremovalisimpossible.Finally,forthosewhostillpreferto(also)haveahard-copyversionofthebook(ofcourse,withoutawatermark),suchcanberealizedbyplacinganorderthroughtheWebsite.Furtherinformationcanbefoundthere.Thepriceiscomparabletoprintingityourself.AcknowledgmentsThereareafewpeoplewhodeservetobementioned.SpyrosVoulgarishasbeenresponsibleforcreatinghomeworkassignments,preparingMath-xi ematicanotebooks,andsettingupalltheexerciseclasses.AlbanaGabahasagiftedtalenttoprovideveryconstructivefeedback(nexttothefactthatshehasbeenworkinglikeadogtoprocessallthestudentassignments).AchrafBelmokademhasdoneaterrificjobonsettingupaWeb-basedsubsystemforlettingstudentsself-assesstheirabilitiesforsolvinggraphproblems.Fi-nally,Iwouldliketothankthestudentswhohaveundergonemyteachingforthepasttwoyearsandwhohave,despiteallthemistakes,continuedtoclaimthattheyenjoyedit.MaartenvanSteenAmsterdam,April2010xii CHAPTER1INTRODUCTION On11September2001therewasamaliciousattackontheWTCtowersinNewYorkCity,eventuallyleadingtothetwobuildingscollapsing.Whatisnotknowntomanypeople,isthattherewerethreetransatlanticInter-netcablescomingashoreclosetotheWTCandthatanimportantInternetswitchingstationwasdamaged,alongwithtwootherimportantInternetre-sourcecenters.PeterSalusandJohnQuarterman[2002]hadsincelongbeenmeasuringtheperformanceoftheInternetbycheckingthereachabilityofafairlylargecollectionofservers.Ineffect,theysimplysentmessagesfromdifferentlocationsontheInternettothesespecialcomputersandrecordedwhetherornotserverswouldberesponding.Ifreachabilitywas100%,thismeantthatallserverswereupandrunning.Ifreachabilitywasless,thiscouldmeanthatserverswereeitherout-of-order,orthatthecommunica-tionpathstosomeoftheserverswerebroken.Immediatelyaftertheattackreachabilitydroppedbyabout9%.Within30minutesithadalmostreacheditsoldvalueagain.ThisexampleillustratestwoimportantpropertiesoftheInternet.First,evenwhendisruptingwhatwouldseemasavitallocationintheInternet,suchadisruptionbarelyaffectstheoverallcommunicationcapabilitiesofthenetwork.Second,theInternethasapparentlybeendesignedinsuchawaythatittakesalmostnotimetorecoverfromabigdisaster.Thisrecov-eryisevenmoreremarkablewhenyouconsiderthatnomanualrepairshadevenstarted,butalsothatnodesignerhadeverreallyanticipatedsuchat-tacks(althoughrobustnesswasdefinitelyadesigncriterionfortheInternet).TheInternetdemonstratedemergentself-healingbehavior.1TheInternetisanexampleofwhatisnowcommonlyreferredtoasacomplexnetwork,whichwecaninformallydefineaslargecollectionofinterconnectednodes.Anodecanbeanything:aperson,anorganization,acomputer,abiologicalcell,andsoforth.Interconnectedmeansthattwonodesmaybelinked,forexample,becausetwopeopleknoweachother,twoorganizationsexchangegoods,twocomputershaveacableconnectingthetwoofthem,orbecausetwoneuronsareconnectedbymeansofasynapsesforpassingsignals.Whatmakesthesenetworkscomplexisthattheyaregenerallysohugethatitisimpossibletounderstandorpredicttheiroverallbehaviorbylookingintothebehaviorofindividualnodesorlinks.Asitturnsout,complexnetworksareeverywhere.Or,tobemorepre-cise,itturnsoutthatifwemodelreal-worldsituationsintermsofnetworks,weoftendiscovernewthings.Whatisstriking,isthatmanyreal-worldnet-workslookalike:thestructureoftheInternetresemblestheorganizationofourbrain,butalsotheorganizationofonlinesocialcommunities.Where1Aswe’llencounterinlaterchapters,there’snomagichere:so-calledroutingalgorithmssimplyadjusttheirdecisionswhenpathsbreak.3 thesesimilaritiescomefromisstillamystery,justasitisoftenverydifficulttounderstandhowcertainnetworkswereactuallystructured.Beforewegodeeperintowhatcomplexnetworksactuallyentails,let’sfirstconsiderafewgeneralareaswherenetworksplayavitalrole,startingwithcommuni-cationnetworks.1.1CommunicationnetworksNotevensolongago,settingupaphonecalltosomeoneontheothersideoftheworldrequiredtheinterventionofahumanoperator.Moreover,anestablishedconnectionwasnoguaranteeforbeingabletounderstandeachotherasthequalitycouldbeprettybad.Manywillrecallthesesituationstohappeninthe70sand80softhepreviouscentury—reallynotthatlongago.Today,cellphonesallowustobecontactedvirtuallyanywhereandanytime,andcoveragecontinuestoexpandtoeventhemostremoteareas.Settingupahigh-qualityvoiceconnectionovertheInternetwithpeersanywherearoundtheworldisplainsimple.Alongtheselines,weneedmerelywaitawhileuntilitisalsopossibletohavecheap,high-qualityvideoconnectionsallowingustoexperienceourremotefriendsasbeingvirtuallyinthesameroom.Theworldappearstobebecomingsmaller,andpeoplearebecomingevermoreconnected.Obviously,telecommunicationhasplayedacrucialroleinestablishingthisconnectedworldasitiscommonlyknown,butwiththeconvergenceoftelecommunicationanddatanetworks(andnotablytheInternet),itisdifficultnottobeconnectedanymore.Beingconnectedhasprofoundeffectsforthedisseminationofinformation.Andasweshallsee,howweareconnectedplaysacrucialrolewhenitcomestothespeedandrobustnessofsuchdissemination,amongmanyotherissues.HistoricalperspectiveTohaveaconnectedworlditisobviousthatweneedtocommunicate.Ifwewantthisworldtohavesignificantcoverage,long-distancecommunicationisobviouslyimportant.Unlikewhatmanytendtobelieve,networksthatfacilitatesuchcommunicationhavealonghistory,asdescribedbyHolz-mannandPehrson[1995].Apartfromwell-knownmeansofcommunica-tionsuchassendingmessengersorusingpigeons,long-distancecommuni-cationwithouttheneedtophysicallytransportamessagehasalwayscaughttheattentionofmankind.Typically,suchtelegraphiccommunicationusedtobedonethroughfirebeacons,mirrors(i.e.,heliographiccommunication),drums,andflags.Communicationpathssetupusingsuchmethods,forex-4 amplebyhavingcommunicationpostsorganizedatline-of-sightdistances,areknownfromGreekandRomanhistory.However,itwasn’tuntiltheendofthe18thCenturythatasystem-aticapproachwasdevelopedtoestablishtelegraphiccommunicationnet-works.Suchnetworkswouldconsistofcommunicationposts,ofwhichpairswouldlieineachother’sline-of-sight.Typically,fortheseopticaltelegraphs,distancesbetweentwopostswouldbeintheorderoftensofkilometers,whichwasrealisticgiventhathigh-qualitytelescopescouldbeused.Animportantaspectinthedesignofthesenetworkswasthecommunicationprotocol,whichwouldprescribetheencodingofletters,butalsowhattodoiftherewasatransmissionerror.Tomakemattersmoreconcrete,considerFigure1.1whichshowsamodelofashuttertelegraph.BPNE(a)(b)Figure1.1:(a)Amodelofashutterstationwithsix(open)shuttersand(b)afewexamplesofhowletterswereencoded.AsshowninFigure1.1(b),lettersarerepresentedbyspecificcombina-tionsofopenandclosedshutters.Inthisway,itbecamepossibletotrans-mitmessagesoverlongdistances.Ofcourse,itbecameequallyimportanttothinkaboutencryptionofmessages,handlingtransmissionerrors,syn-chronizationbetweentransmitterandreader(i.e.,senderandreceiver),andsoon.Inotherwords,theseseeminglyprimitivecommunicationnetworkshadtodealwithvirtuallythesameissuesasmodernsystems.Conceptually,thereisreallynodifference.5 Bythemiddleofthe19thCentury,Europehadopticaltelegraphicnet-worksinstalledintheScandinaviancountries,France,England,Germany,andothers.Concerningtopology,thesenetworkswererelativelysimple:therewereonlyrelativelyfewnodes(i.e.,communicationposts),andcyclesdidnotexist.Thatis,betweenanytwonodesmessagescouldtravelonlythroughauniquepath.Suchnetworksarealsoknownastrees.Mattersbecameseriouswhentheelectricaltelegraphsystememerged.Insteadofusingvision,communicationpathswererealizedthroughelec-tricalcables.Themediumprovedtobesuccessful:bythemiddleofthe19thCenturytheelectricaltelegraphspannedmorethan30,000kilometersintheUnitedStates,makingitmorethanjustaseriouscompetitortoopticaltelegraphsystems.Infact,bythenitwascleartomostpeoplethattheop-ticalnetworkswereheadingtowardsadeadend.In1866,networksintheUnitedStatesandEuropeweresuccessfullyconnectedthroughatransat-lanticcable(whereearlierattemptshadfailed).Gradually,theconceptofaworldwidenetworkwasbecomingreality.FromtelephonytotheInternetTheimpactofaworldwidetelephonynetworkcanonlybeunderestimated.Fromanenduser’sperspective,itreallydidn’tmatteranymorewhereyouwere,butonlythattheotherpartywassimultaneouslyonline.Inotherwords,telecommunicationnetworksrealizedlocationindependency.Thisin-dependencycouldberealizedonlybecauseitwaspossibletoestablishacir-cuitbetweenthetwocommunicatingparties:acommunicationpathfromonepartytotheotherwithintermediatenodesoperatingasswitches.Inmostcases,theseswitcheshadfixedlocationsandeveryswitchwasphysi-callylinkedtoafewotherswitches.Thecombinationofswitchesandlinksformacommunicationnetwork,whichcanberepresentedmathematicallybywhatisknownasagraph,theobjectofstudyinthisbook.Aswealreadydiscussed,telecommunicationnetworkswerewellestab-lishedwhenpeoplebegantothinkaboutconnectingcomputersandthusestablishingdatacommunicationnetworks.Ofcourse,themanyexistingnetworksalreadymadeitpossibletosenddata,forexample,asatelegram.Thenewchallengewastoconnectingtheseseparatenetworksintologicallyasingleonethatcouldbeusedbycomputersusingthesameprotocol.Thisledtotheideaofbuildingacommunicationsysteminwhichpossiblylargemessagesweresplitintosmallerunitscalledpackets.Eachpacketwouldbetaggedwiththeaddressofitsdestinationandsubsequentlyroutedthroughthevariousnetworks.Itisimportanttonotethatpacketsfromthesamemessagecouldeachfollowtheirownroutetothedestination,wheretheywouldthenbesubsequentlyusedtoreassembletheoriginalmessage.6 Whenaswitchreceivedapacket,itwouldonlythendecidetowhichnextswitchthepacketwouldbeforwarded.Thispacketswitchingap-proachcontrastssharplywithtelecommunicationnetworksinwhichtwoendpointswouldfirstestablishapathandthensubsequentlyletallcom-municationpassthroughthatpath,alsoreferredtoascircuitswitching.Thefirstpacket-switchingnetworkwasestablishedin1969,calledtheARPANET(AdvancedResearchProjectsAgencyNetwork).ItformedthestartingpointofthepresentInternet.Keytothisnetworkweretheinter-facemessageprocessors(IMPs),specialcomputersthatprovidedasystem-independentinterfaceforcommunication.Inthisway,anycomputerthatwantedtohookuptotheARPANETneededonlytoconformtotheinter-faceofanIMP.IMPswouldthenfurtherhandlethetransferofpackets.Theyformedthefirstgenerationofnetworkswitches,orrouters.Togiveanim-pressionofwhatthisnetworklookedlike,Figure1.2showsalogicalmapofIMPsandtheirconnectedcomputersasofApril1971.LinSRIUtahIllinoisMITCASEcolnUCSBStanSOCCMUfordHarBurUCLARANDBBNvardroughsFigure1.2:AmapoftheARPANETasofApril1971.RectanglesrepresentIMPs;ovalsarecomputers.TheARPANETof1971constitutedanetworkwith15nodesand19links.Itissosmallthatwecaneasilydrawit.We’vepassedthatstagefortheInternet.(Infact,itisfarfromtrivialtodeterminethesizeoftoday’sInter-net.)Ofcourse,thatnetworkwasalsoconnected:itispossibletorouteapacketfromanysourcetoanydestination.Infact,connectivitycouldstillbeestablishedifarandomlyselectedsinglelinkbroke.Animportantde-signcriterionforcommunicationnetworksishowmanylinksneedtofailbeforethenetworkispartitionedintoseveralparts.Forourexamplenet-workofFigure1.2,itisclearthatthisnumberis2.Restassuredthatforthepresent-dayInternet,thisnumberismuchhigher.Likewise,wecanaskourselveshowmanynodes(i.e.,switchesorIMPs)needtofailbeforeconnectivityisaffected.Again,itcanbeseenthatweneed7 toremoveatleast2nodesbeforethenetworkispartitioned.Surprisingly,inthepresent-dayInternetweneednotremovethatmanynodestoestablishthesameeffect.ThisiscausedbythestructureoftheInternet:researchershavediscoveredthattherearerelativelyfewnodeswithverymanylinks.ThesenodesessentiallyformanAchilles’heeloftheInternet.Insubsequentchapters,youwilllearnwhy.TheWebandWikisNexttotheimportanceofe-mailandotherInternetmessagingsystems,thereislittlediscussionabouttheimpactoftheWorldWideWeb.TheWebisanexampleofadigitalinformationspace:acollectionofunitsofin-formation,linkedtogetherintoanetwork.TheWebisperhapsthebiggestinformationspacethatweknowoftoday:bytheendofJanuary2005,itwasestimatedtohaveatleast11.5billionindexablepages[GulliandSignorini,2005],thatis,pagesthatcouldbefoundandindexedbythemajorsearchenginessuchasGoogle.Threeyearslater,differentstudies(usingdifferentmetrics)indicatethatwemaybedealingwith30-50billionpages.Inanycase,weareclearlydealingwithaphenomenalgrowth.WhatmakesinformationspacessuchastheWebinterestingforourstud-ies,isthatagainthesespacesformanetwork.InthecaseoftheWeb,eachpagemay(andgenerallywill)containlinkstootherpagesandcorrespondstoanodeinthenetwork.Whatbecomesinterestingarequestionssuchas:•Ifwetakethenumberoflinkspointingtoapageasameasureofthatpage’spopularity,whatcanwesayaboutthenumberandintensityofpagepopularity(i.e.,whatisthedistributionofpagepopularity)?•DoestheWebalsosharecharacteristicswithwhatareknownassmallworldnetworks:isitpossibletonavigatetoanyotherpagethroughonlyafewlinks?AsweshalldiscussextensivelyinChapter8,theWebindeedhasitsowncharacteristics,someofwhichcorrespondtothoseinsmallworlds.How-ever,therearealsoimportantdifferences.Forexample,itturnsoutthatthedistributionofpagepopularityisveryskewed:therearerelativelyfew,butextremelypopularpages.Incontrast,byfarmostpagesarenotpopular,yettherearemanyofsuchunpopularpages,whichmakesthecollectionofunpopularpagesbyitselfandinterestingsubjectforstudy.AninformationspacerelatedtotheWebisthatoftheonlineencyclo-pediaWikipedia.Bytheendof2007,over7.5millionpageswerecounted,writteninmorethan250differentlanguages.TheEnglishWikipediaisby8 farthelargest,withmorethan2millionarticles.Itisalsothemostpopu-laronewhenmeasuringthenumberofpagerequests:45%ofallWikipediatrafficisdirectedtowardstheEnglishversion[Urdanetaetal.,2009].Again,Wikipediaformsanetworkwithitspagesasnodesandreferencestootherpagesaslinks.LiketheWeb,itturnsoutthattherearefewverypopu-larpages,andmanyunpopularones(butsomanythattheycannotbeig-nored)[Voss,2005].1.2SocialnetworksNexttocommunicationnetworks,networksthatarebuiltaroundpeoplehavesincelongbeensubjectofstudy.Wefirstconsidermodernsocialnet-worksthathavecomeintoplayasonlinecommunitiesfacilitatedbytheInternet.OnlinecommunitiesIntheirlandmarkessay,LickliderandTaylor[1968]foresawthatcomputerswouldformamajorcommunicationdevicebetweenpeopleleadingtotheonlinecommunitiesmuchliketheonesweknowtoday.Indeed,perhapsoneofthebiggestsuccessesoftheInternethasbeentheabilitytoallowpeopletoexchangeinformationwitheachotherbymeansofuser-to-usermessagingsystems[WamsandvanSteen,2004].Thebestknownofthesesystemsise-mail,whichhasbeenaroundeversincetheInternetcametolife.Anotherwell-knownexampleisnetworknews,throughwhichuserscanpostmessagesatelectronicbulletinboards,andtowhichothersmaysubsequentlyreact,leadingtodiscussionthreadsofallsortsandlengths.Morerecentlyinstantmessagingsystemshavebecomepopular,allowinguserstodirectlyandinteractivelyexchangemessageswitheachother,pos-siblyenhancedwithinformationonvariousstatesofpresence.Itisinterestingtoobservethatfromatechnologicalpointofview,mostofthesesystemsarereallynotthatsophisticatedandarestillbuiltwithtech-nologythathasbeenaroundfordecades.Inmanyways,thesesystemsaresimple,andhavestayedsimple,whichallowedthemtoscaletosizesthataredifficulttoimagine.Forexample,ithasbeenestimatedthatin2006al-most2millione-mailmessagesweresenteverysecond,byatotalofmorethan1billionusers.Admittedly,morethan70%ofthesemessageswerespamorcontainedviruses,buteventhenitisobviousthatalotofonlinecommunicationtookplace.Thesenumberscontinuetorise.Morethanthetechnology,itisinterestingtoseewhatthesecommuni-cationfacilitiesdotothepeoplewhousethem.Whatwearewitnessingtodayistheriseofonlinecommunitiesinwhichpeoplewhohavenever9 meteachotherphysicallyaresharingideas,opinions,feelings,andsoon.Infact,Doddsetal.[2003]haveshownthatalsoforonlinecommunitieswearedealingwithwhatisknownasasmallworld.Toputitsimply,asmallworldischaracterizedbythefactthateverytwopeoplecanreacheachotherthroughachainofjustahandfulofmessages.Thisphenomenonisalsoknownasthe“sixdegreesofseparation”[Watts,2003]towhichwewillreturnextensivelylater.Doddsetal.wereinterestedtoseewhethere-mailuserswerecapableofsendingamessagetoaspecificpersonwithoutknowingthatperson’saddress.Inthatcase,theonlythingyoucandoissendthemessagetooneofyouracquaintances,hopingthatheorsheis“closer”tothetargetthanyouare.Withover60,000usersparticipatingintheexperiment,theyfoundthat384outoftheapproximately24,000messagechainsmadeittodesignatedtargetpeople(therewere18targetsfrom13differentcountriesallovertheworld).Ofthese384chains,50%hadalengthsmallerthan5–7,dependingonwhetherthetargetwaslocatedinthesamecountryaswherethechainstarted.Whatwehavejustdescribedisthephenomenonofmessagestravelingthroughanetworkofe-mailusers.Usersarelinkedbyvirtueofknowingeachother,andtheresultingnetworkexhibitspropertiesofsmallworlds,effectivelyconnectingeverypersontotheothersthroughrelativelysmallchainsofsuchlinks.Describingandcharacterizingtheseandothernet-worksformstheessenceofnetworkscience.TraditionalsocialnetworksLongbeforetheInternetstartedtoplayaroleinmanypeople’slives,so-ciologistsandotherresearchersfromthehumanitieshavebeenlookingatthestructureofgroupsofpeople.Inmostcases,relativelysmallgroupswereconsidered,necessarilybecauseanalysisoflargegroupswasoftennotfeasible.AnimportantcontributiontosocialnetworkanalysiscamefromJacobMorenowhointroducedsociogramsinthe1930s.Asociogramcanbeseenasagraphicalrepresentationofanetwork:peoplearerepresentedbydots(calledvertices)andtheirrelationshipsbylinesconnectingthosedots(callededges).AnexamplewewillcomeacrossinChapter9isoneinwhichaclassofchildrenareaskedwhotheylikeanddislike.Itisnothardtoimaginethatwecanuseagraphicalrepresentationtorepresentwholikeswhom,asshowninFigure1.3.Decadeslater,undertheinfluenceofmathematicians,sociogramsandsuchwereformalizedintographs,ourcentralobjectofstudy.Asmen-tioned,graphsaremathematicalobjects,andassuchtheycomealongwith10 -++-+-+-++--++++-Figure1.3:Therepresentationofasociogramexpressingaffectionbetweenpeople.Theabsenceofalinkindicatesneutrality.atheoreticalframeworkthatallowsresearcherstofocusonthestructureofnetworksinordertomakestatementsaboutthebehaviorofanentiresocialgroup.Socialnetworkanalysishasbeenimportantforthefurtherdevelopmentofgraphtheory,forexamplewithrespecttointroducingmetricsforidenti-fyingimportanceofpeopleorgroups.Forexample,apersonhavingmanyconnectionstootherpeoplemaybeconsideredrelativelyimportant.Like-wise,apersonatthecenterofanetworkwouldseemtobemoreinfluentialthansomeoneattheedge.Whatgraphtheoryprovidesusarethetoolstoformallydescribewhatwemeanbyrelativelyimportant,orhavingmoreinfluence.Moreover,usinggraphtheorywecaneasilycomeupwithal-ternativesfordescribingimportanceandsuch.Havingsuchtoolshasalsofacilitatedbeingmorepreciseinstatementsregardingthepositionorrolethatpersonhaswithinacommunity.WewillcomeacrosssuchformalitiesinChapter9.1.3NetworkseverywhereCommunicationnetworksandsocialnetworksaretwoclassesofnetworksthatmanypeopleareawareof.However,therearemanymorenetworksasshowninFigure1.4.Whatshouldimmediatelybecomeclearisthatnet-worksoccurinverydifferentscientificdisciplines:economics,organiza-tionalstudies,socialsciences,biology,logistics,andsoforth.What’smore,theterminologythatisusedtodescribethedifferentnetworksineachdisci-plineislargelythesame,whichmakesitrelativelyeasyformembersofdif-ferentcommunitiestocooperateinunderstandingthefoundationsofcom-plexnetworks.Whatisevenmorestrikingisthefactthatnetworksfromverydifferentdisciplinesoftenlooksomuchalike.Thiscommonterminol-ogyandthestrongresemblanceofnetworksacrossscientificdisciplineshasbeeninstrumentalinboostingnetworkscience.11 NetworkVerticesEdgesDescriptionAirlineairportsflightsConsiderthescheduledflights(ofatrans-specific)carrierbetweentwoairports.portationStreetjunctionsroadAroadsegmentextendsexactlyplanssegmentbetweentwojunctions.Avariationistodistinguishbetweenone-wayandtwo-waysegments.Trainstationsconnec-Twostationsareconnectedonlyiftheretrans-tionisatrainconnectionscheduledthatportationdoesnotpass(possiblywithoutstopping)anyintermediatestations.RailwayjunctionstrackConsidertheactualrailwaytracks.networksegmentWheretracksegmentsmergeorcross,wehavejunctions.BrainneuronssynapsesEachneuroncanbeconsideredtoconsistofinputs(calleddendrites)andoutputs(calledaxon).Synapsescarryelectricalsignalsbetweenneurons.Geneticgenestranscrip-Ingenetic(regulatory)networkswenetworkstionmodelhowgenesinfluenceeachother,factorinparticular,howtheproductofonegenedeterminestherateatwhichanothergeneistranscribed(i.e.,atwhichrateitproducesitsownoutput).Antjunctionsphero-Inorderforantstotelleachotherwherecoloniesmonesourcesoffoodare,theyproducetrailspheromoneswhichisachemicalthatcanbepickedupbyotherants.Pheromonesjointlyconstitutepaths.CitationauthorscitationInscientificliterature,itiscommonnetworkspracticeto(extensively)refertorelatedpublishedworkandsourcesofstatements,inturnleadingtocitationnetworks.Tele-numbercallNetworksofphonecallsreflect(mostly)phonepairsofpeopleexchanginginformation,callsthusformingasocialnetworktechnicallyrepresentedbyphonenumbersandactualcalls.Reputa-peopleratingInelectronictradingnetworkssuchastione-Bay,buyersratetransactions.Asnetworksbuyersinturncanalsobesellers,weobtainanetworkinwhichratesreflectthereputationbetweenpeople.Figure1.4:Examplesofnetworks.12 Understandingcomplexnetworksrequirestherightsetoftools.Inourcase,thetoolsweneedcomefromafieldofmathematicsknownasgraphtheory.Inthisbook,you’lllearnabouttheessentialelementsofgraphthe-oryinordertoobtaininsightintomodernnetworks.Nexttothat,wedis-cussanumberofconceptsthatarenormallynotfoundintraditionaltext-booksongraphtheory,suchasrandomnetworksandvariousmetricsforcharacterizinggraphs.1.4OrganizationofthisbookInthefollowingchapterswe’llgothroughthefoundationsofgraphtheoryandmoveonintopartsthatarenormallydiscussedinmoreadvancedtext-booksonnetworks.Thegoalofthistextistoprovideonlyanawarenessandbasicunderstandingofcomplexnetworks,forwhichreasonnoneoftheadvancedmathematicsthataccompanycomplexnetworksisdiscussed.Tomakematterseasier,specialnotesareincludedthatgenerallyprovidefurtherinformation,suchasthefollowing:Note1.1(Moreinformation)Thisisanexampleofhowadditionalsidenotesarepresented.Textinsuchnotescanalwaysbeskippedasnotesdonotaffecttheflowofthemaintext.Therearedifferenttypesofnotes:Studytips:Studyinggraphtheoryisnotalwayseasy,notbecausethema-terialissodifficult,butbecauseidentifyingthebestapproachtotackleaspecificproblemmaynotbeobvious.Ihavecompiledvarioustipsbasedonexperienceinteaching(andoncemyselflearning)graphthe-ory.Studentsarestronglyencouragedtoreadthesetipsandputthemtotheirownadvantage.Mathematicallanguage:Formanypeople,mathematicsisandremainsabarriertoaccessingotherwiseinterestingmaterial.Thelanguageofmathematiciansaswellasthecommonlyusedtoolsandtechniquesaresometimesevenintimidating.However,therearesomanycasesinwhichthebarrierisonlyvirtual.Theonlythingthatisneededisget-tingacquaintedwithsomebasicsandlearninghowtoapplythem.Innotesfocusingonmathematicallanguage,IgenerallytakeastepbackonpreviouslypresentedmaterialandtranslatethemathintoplainEn-glish,explainmathematicalnotations,andsoforth.Thesenotesaremeanttohelpunderstandthemath,butdonotserveasareplacement.Mathematicssimplyoffersalevelofprecisionthatisdifficulttomatch13 with(informal)English,yetthenotationsshouldnotbesomethingtokeepanyoneawayfromreachingadeeperunderstanding.Prooftechniques:NotablyinChapters2and3sometimeistakentoex-plainabitmoreabouthowtoprovetheorems.Oneofthemaindiffi-cultiesthatIexperiencedwhenfirststudyinggraphtheoryandmoregenerally,combinatorics,wasfindingstructureinproofs.Asinvirtu-allyanyotherfieldofmathematics,graphtheoryusesawholearrayofprooftechniques.Inthesenotes,themostcommonlyusedonesaremadeexplicit,aimingatcreatingabetterawarenessofavailabletech-niquessothatstudentsmayhavelessofafeelingofwalkinginthedarkwhenitcomestosolvingmathematicalproblems.Algorithmics:Graphtheoryinvolvesmanyalgorithms,suchas,forex-ample,findingshortestpaths,identifyingreachablevertices,deter-miningsimilarity,andsoon.Traditionally,algorithmshavealwaysbeendescribedusingmath,butthatlanguageisnotparticularlywell-equippedforexpressingtheflowofcontrolinherenttomostalgo-rithms.Inalgorithmicnotessomeofgraphalgorithmsareexpressedinpseudocode,roughlyfollowingatraditionalprogramminglan-guage.Invirtuallyallcases,thisdescriptionleadstoabettersepa-rationoftheactualmathandthestepscomprisinganalgorithm.Moreinformation:Thesetypeofnotescontainawidevarietyofinforma-tion,rangingfromadditionalbackgroundmaterialtomoredifficultmathematicalmaterialsuchasproofs.Inallcases,thesenotesdonotinterferewiththemaintextandmaybeskippedonfirstreading.Proofsthathavebeenmarked“(*)”maybeskippedatfirstreading:theyaretobeconsideredthetougherpartsofthematerial.Thebookisroughlyorganizedintotwoparts.ThefirstpartscoversChapters2–6.Thesechaptersroughlycoverthesamematerialthatcanusu-allybefoundinstandardtextbooksongraphtheory.ExceptforChapter6,thismaterialistobeconsideredessentialforstudyinggraphtheoryandshouldinanycasebecovered.Chapter6canbeconsideredasacompi-lationofvariousmetricsfromdifferentdisciplinestocharacterizegraphs,theirstructures,andthepositionsthatdifferentnodeshaveinnetworks.ThesecondpartconsistsofChapters7–9anddiscusses(graphmodelsof)real-worldnetworks.NotablyChapter7onrandomnetworkscontainsmaterialthatisoftenpresentedonlyinmoreadvancedtextbooksyetwhichIconsidertobecrucialforraisingscientificinterestinmodernnetworksci-ence.Randomnetworksareimportantfromaconceptualmodelingpointofview,fromananalysispointofview,andareimportantforexplainingtheemergentbehaviorweseeinreal-worldsystems.Bykeepingexplana-14 tionsassimpleaspossibleandattemptingtostickonlytothecoreelements,thismaterialshouldberelativelyeasytoaccessforanyonehavingessen-tiallylearnedonlyhigh-schoolmathematics.Thetwosucceedingchaptersdiscusstheoryandpracticeofreal-worldsystems:computernetworksandsocialnetworks,respectively.15 CHAPTER2FOUNDATIONS Inthepreviouschapterwehaveinformallyintroducedthenotionofanet-workandhavegivenseveralexamples.Inordertostudynetworks,weneedtouseaterminologythatallowsustobeprecise.Forexample,whenwespeakaboutthedistancebetweentwonodesinanetwork,whatdowere-allymean?Likewise,isitpossibletospecifyhowwellconnectedanetworkis?Theseandotherstatementscanbeformulatedaccuratelybyadoptingterminologyfromgraphtheory.Graphtheoryisafieldinmathematicsthatgainedpopularityinthe19thand20thcentury,mainlybecauseitallowedtodescribephenomenafromverydifferentfields:communicationinfrastruc-tures,drawingandcoloringmaps,schedulingtasks,andsocialstructures,justtonameafew.Wewillfirstconcentrateonlyonthefoundationsofgraphtheory.Tothisend,wewillusethelanguageofmathematics,asitallowsustobepreciseandconcise.However,tomanythislanguagewithitsmanysymbolsandoftenpeculiarnotationscaneasilyformanobstacletograsptheessenceforwhatitisbeingused.Forthisreason,wewillgentlyandgraduallyintroducenotationswhileprovidingmoreverbosedescriptionsalongsidethemoreformaldefinitions.Youareencouragedtopayexplicitattentiontotheformalities:intheend,theywillprovetobemuchmoreconvenienttousethanverboseverbaldescriptions.Thelatteroftensimplyfailtobepreciseenoughtocompletelyunderstandwhatisgoingon.Itisalsonotthatdifficult,asmostnotationscomedirectlyfromsettheory.2.1FormalitiesLetusstartwithdiscussingwhatisactuallymeantbyanetwork.Tothisend,wefirstconcentrateonsomebasicformalconceptsandnotationsfromgraphtheory,togetherwithafewfundamentalpropertiesthatcharacterizenetworks.Afterhavingstudiedthissection,youwillhavealreadylearnedalotabouttheworldofgraphsandshouldalsofeelmorecomfortablewithmathematicalnotations.GraphsandvertexdegreesAssaid,thenetworksthathavebeenintroducedsofararemathematicallyknownasgraphs.Initssimplestform,agraphisacollectionofverticesthatcanbeconnectedtoeachotherbymeansofedges.Inparticular,eachedgeofgraphjoinsexactlytwovertices.Usingaformalnotation,agraphisdefinedasfollows.Definition2.1:AgraphGconsistsofacollectionVofverticesandacollectionedgesE,forwhichwewriteG=(V,E).Eachedgee2Eissaidtojointwo18 vertices,whicharecalleditsendpoints.Ifejoinsu,v2V,wewritee=hu,vi.Vertexuandvinthiscasearesaidtobeadjacent.Edgeeissaidtobeincidentwithverticesuandv,respectively.WewilloftenwriteV(G)andE(G)todenotethesetofverticesandedgesassociatedwithgraphG,respectively.Itisimportanttorealizethatanedgecanactuallyberepresentedasanunorderedtupleoftwovertices,thatis,itsendpoints.Forthisreason,wemakenodistinctionbetweenhv,uiandhu,vi:theybothrepresentthefactthatvertexuandvareadjacent.Thisdefinitionmayalreadyraiseafewquestions.Firstofall,isitpos-siblethatanedgejoinsthesamevertices,thatis,cananedgeformaloop?Thereisnothinginthedefinitionthatpreventsthis,andindeed,suchedgesareallowed.Likewise,youmaybewonderingwhethertwoverticesuandvmaybejoinedbymultipleedges,thatis,asetofedgeseachhavinguandvastheirendpoints.Indeed,thisisalsopossible,andweshallbediscussingafewexamplesshortly.Agraphthatdoesnothaveloopsormultipleedgesiscalledsimple.Likewise,thereisnothingthatprohibitsagraphfromhavingnoverticesatall.Ofcourse,inthatcasetherewillalsobenoedges.Suchatrivialgraphiscalledempty.Anotherspecialcaseisformedbyasimplegraphhavingnvertices,witheachvertexbeingadjacenttoeveryothervertex.Thisgraphisalsoknownasacompletegraph.AcompletegraphwithnverticesiscommonlydenotedasKn.Finally,thecomplementofagraphG,denotedasGisthegraphobtainedfromGbyremovingallitsedgesandjoiningexactlythoseverticesthatwerenotadjacentinG.ItshouldbeclearthatifwetakeagraphGanditscomplementG“together,”weobtainacompletegraph.Takingtwographs“together”willbemademorepreciselaterinthischapter.Asanaside,noticethatwhenwewritehu,vi,wecansayonlythatuandvareadajacent,thatis,thatthereisatleastoneedgethatjoinsthetwo.Strictlyspeaking,itisnotpossibleusingthisnotationtodistinguishdiffer-entedgesthatallhappentojoinbothuandv.Ifwewantedtomakethatdis-tinction,wewouldhavetowritesomethinglikee1=hu,viande2=hu,vi.Inotherwords,wewouldhavetoexplicitlyenumeratetheedgesthatjoinuandv.Ofcourse,whendealingwithsimplegraphs,therecanbenomistakeaboutwhichedgeweareconsideringwhenwewritehu,vi.Hereweseeanexamplewheremathematicsallowsustobepreciseandunambiguous.Wewillencountermanymoreofsuchexamples.Asinsomanypracticalsituations,itisoftenconvenienttotalkaboutyourneighbors.Ingraph-theoreticalterms,theneighborsofavertexuareformedbytheverticesthatareadjacenttov,or,inotherwords,thosever-19 ticestowhichvhasbeenjoinedbymeansofanedge.Wecanformulatethispreciselyusingformalmathematicalnotationsasfollows.Definition2.2:ForanygraphGandvertexv2V(G),theneighborsetN(v)ofvisthesetofvertices(otherthanv)adjacenttov,thatisN(v)def=fw2V(G)jv6=w,9e2E(G):e=hu,vigNote2.1(Mathematicallanguage)TheformalnotationisDefinition2.2isveryprecise,yetcanbesomewhatin-timidating.Letusdecypheritabit.First,weusethesymboldef=toexpressthatwhatiswrittenontheleft-handsideisdefinedbywhatiswrittenontheright-handside.Inotherwords,N(v)def=...isnothingbutaccuratelystatingthatN(v)isdefinedbywhatfollowsontherighthandofdef=.Recallthatthesymbol‘9’istheexistentialquantifierusedinsettheorytoexpressstatementslike“thereexistsan...”Keepingthisinmind,youshouldnowbeabletoseethattheright-handsidetranslatesintoEnglishtothefollowingstatement:ThesetofverticeswinG,withwnotequaltov,suchthatthereexistsanedgeeinGthatjoinsvandw.Wewillbeencounteringmanymoreoftheseformalstatements.Ifyouhavetroublecorrectlyinterpretingthem,weencourageyoutomaketranslationslikethepreviousonetoactuallypracticereadingmathematics.Afterawhile,youwillnoticethatthesetranslationscomenaturallybythemselves.Theword“graph”comesfromthefactthatitisoftenveryconvenienttouseagraphicalrepresentation,asshowninFigure2.1.Inthisexample,wehaveagraphGwitheightverticesandatotalof18edges.Eachvertexisrepresentedasablackdotwhereasedgesaredrawnaslines.Whendrawingagraph,itisoftenconvenienttoaddlabels.Bothverticesandedgescanbelabeled.Weshallgenerallynotusesubscriptswhenlabelingverticesandedgesinourdrawingsofgraphs.Thismeansthatalabelsuchase13fromFigure2.1isthesamease13inourtext.Itshouldbeclearthattheremaybemanydifferentwaystodrawagraph.Inthefirstplace,thereisnoreasonwhywewouldsticktojustdotsandlines,althoughitiscommonpracticetodoso.Secondly,thereare,inprin-ciple,norulesconcerningonwheretopositionthedrawnvertices,norarethereanyrulesstatingthatalineshouldbedrawninastraightfashion.However,thewaythatwedrawgraphsisoftenimportantwhenitcomestovisualizingcertainaspects.WereturntothisissueextensivelyinSection2.4.20 v3V(G)=fv1,...,v8ge16E(G)=fe1,...,e18ge5v2e4e1=hv1,v2ie10=hv6,v7ie2=hv1,v5ie11=hv5,v7ie3v4e1e6e3=hv2,v8ie12=hv6,v8ie8e15e4=hv3,v5ie13=hv4,v7ie2v1v5e18v8e5=hv3,v4ie14=hv7,v8ie11e13e6=hv4,v5ie15=hv4,v8ie7e14e7=hv5,v6ie16=hv2,v3ie9e12e17e8=hv2,v5ie17=hv1,v7ie10v7e9=hv1,v6ie18=hv5,v8iv6Figure2.1:Anexampleofagraphwitheightverticesand18edges.Animportantpropertyofavertexisthenumberofedgesthatareinci-dentwithit.Thisnumberiscalledthedegreeofavertex.Definition2.3:Thenumberofedgesincidentwithavertexviscalledthedegreeofv,denotedasd(v).Loopsarecountedtwice.LetusconsiderourexamplefromFigure2.1again.Inthiscase,becausetherearefouredgesincidentwithvertexv1,wehavethatd(v1)=4.Wecancompletethepicturebyconsideringeveryvertex,whichgivesus:VertexDegreeIncidentedgesNeighborsv14hv1,v2i,hv1,v5i,hv1,v6i,hv1,v7iv2,v5,v6,v7v24hv1,v2i,hv2,v3i,hv2,v5i,hv2,v8iv1,v3,v5,v8v33hv2,v3i,hv3,v4i,hv3,v5iv2,v4,v5v44hv3,v4i,hv4,v5i,hv4,v7i,hv4,v8iv3,v5,v7,v8v57hv1,v5i,hv2,v5i,hv3,v5i,hv4,v5i,hv5,v6i,v1,v2,v3,v4,v6,hv5,v7i,hv5,v8iv7,v8v64hv1,v6i,hv5,v6i,hv6,v7i,hv6,v8iv1,v5,v7,v8v75hv1,v7i,hv4,v7i,hv5,v7i,hv6,v7i,hv7,v8iv1,v4,v5,v6,v8v85hv2,v8i,hv4,v8i,hv5,v8i,hv6,v8i,hv7,v8iv2,v4,v5,v6,v7WhenaddingthedegreesofallverticesfromG,wefindthatthetotalsumis36,whichisexactlytwicethenumberofedges.Thisbringsustoourfirsttheorem:Theorem2.1:ForallgraphsG,thesumofthevertexdegreesistwicethenumberofedges,thatis,åd(v)=2jE(G)jv2V(G)21 Proof.WhenwecounttheedgesofagraphGbyenumeratingforeachver-texvofGtheedgesincidentwiththatvertexv,wearecountingeachedgeexactlytwice.Hence,åv2Gd(v)=2jE(G)j.Note2.2(Mathematicallanguage)Again,weencountersomeformalmathematicalnotations.Inthiscase,weusethestandardsymbolåasanabbreviationforsummation.Thus,ånxisthei=1isameasx1+x2+x3++xn.Inmanycases,thesummationissimplyoverallelementsinaspecificset,suchasinourexamplewhereweconsideralltheverticesinagraph.Inthatcase,ifweassumethatV(G)consistsoftheverticesv1,v2,...,vn,thenotationåv2V(G)d(v)istobeinterpretedas:åd(v)def=d(v1)+d(v2)++d(vn)v2V(G)Note,furthermore,thatweusethenotationjSjtodenotethesizeofasetS.Inourexample,jE(G)jthusdenotesthesizeofE(G)or,inotherwords,thetotalnumberofedgesingraphG.Thereisalsoaninterestingcorollarythatfollowsfromthisproperty,namelythatthenumberofverticeswithanodddegreemustbeeven.ThiscanbeeasilyseenifwesplittheverticesVofagraphintotwogroups:Voddcontainingallverticeswithodddegree,andVevenwithallverticeshavingevendegree.Clearly,ifwetakethesumofallthedegreesfromverticesinVodd,andthosefromVeven,wewillhavesummedupallvertexdegrees,thatis,åd(v)+åd(v)=åd(v)v2Voddv2Vevenv2Vwhichiseven.Becausethesumofevenvertexdegreesisobviouslyeven,weknowthatåv2Vevend(v)iseven.Thiscanonlymeanthatåv2Voddd(v)mustalsobeeven.CombiningthiswiththefactthatallvertexdegreesinVoddareodd,weconcludethatthenumberofverticeswithodddegreemustbeeven,thatis,jVoddjiseven.Wehavethusjustproven:Corollary2.1:Foranygraph,thenumberofverticeswithodddegreeiseven.Thevertexdegreeisasimple,yetpowerfulconcept.Asweshallseethroughoutthistext,vertexdegreesareusedinmanydifferentways.Forexample,whenconsideringsocialnetworks,wecanusevertexdegreestoexpresstheimportanceofapersonwithinasocialgroup.Also,whenwediscussthestructureofreal-worldcommunicationnetworkssuchastheIn-ternet,itwillturnoutthatwecanalearnalotbyconsideringthedistributionofvertexdegrees.Morespecifically,bysimplyorderingverticesbytheir22 vertexdegree,wewillbeabletoobtaininsightinhowsuchanetworkisactuallyorganized.DegreesequenceListingthevertexdegreesofagraphgivesusadegreesequence.Thevertexdegreesareusuallylistedindescendingorder,inwhichcasewerefertoanordereddegreesequence.Forexample,ifweconsidertheeightverticesofgraphGfromFigure2.1,wehavethefollowingvertexdegreesvertex:v1v2v3v4v5v6v7v8degree:44347455which,whenorderingthesedegreesindescendingorder,leadstotheor-dereddegreesequence[7,5,5,4,4,4,4,3]Ifeveryvertexhasthesamedegree,thegraphiscalledregular.Inak-regulargrapheachvertexhasdegreek.Asaspecialcase,3-regulargraphsarealsocalledcubicgraphs.Whenconsideringdegreesequences,itiscommonpracticetofocusonlyonsimplegraphs,thatis,graphswithoutloopsandmultipleedges.Aninterestingquestionthatcomestomindiswhenwearegivenalistofnum-bers,istherealsoasimplegraphwhosedegreesequencecorrespondstothatlist?Therearesomeobviouscaseswherewealreadyknowthatagivenlistcannotcorrespondtoadegreesequence.Forexample,wehavejustproventhatthesumofvertexdegreesisalwayseven.Therefore,amini-malrequirementisthatthesumoftheelementsofthatlistshouldbeevenaswell.Likewise,itisnotdifficulttoseethat,forexample,thesequence[4,4,3,3]cannotcorrespondtoadegreesequence.Inthiscase,ifthiswereadegreesequence,wewouldbedealingwithagraphoffourvertices.Thefirstvertexissupposedtohavefourincidentedges.Inthecaseofsimplegraphs,eachoftheseedgesshouldbeincidentwithadifferentvertex.How-ever,thereareonlythreeverticeslefttochoosefrom,so[4,4,3,3]cannevercorrespondtothedegreesequenceofasimplegraph.Ofcourse,takingatrial-and-errorapproachtoseewhetheralistcorre-spondstoadegreesequenceisnotthewaytogo.Fortunately,thereisasystematicwaytoseewhetheragivenlistofnumberscorrespondstothedegreesequenceofasimplegraph,inwhichcasethesequenceissaidtobegraphic.Let’sreturntoourgraphfromFigure2.1,butnowassumethatwearegivenonlythelist[7,5,5,4,4,4,4,3].Weaskourselveswhetherthislistisgraphic.Ifthisisthecase,weshouldbeabletoconstructagraphthathasthisdegreesequence.NotethatthisgraphneednotnecessarilybethesameastheonefromFigure2.1.Thisishowwecanaddressthisissue.23 •Consider[7,5,5,4,4,4,4,3].Ifthissequenceisgraphiccorrespond-ingtoagraph,sayG1,thenweshouldbeabletoconstructG1fromanothergraphG2byaddingavertexv1toG2andjoiningv1tosevenotherverticesfromG2.ThiswouldthenexplainthatG1hasavertexwithhighestdegree7.Notethatforthisconstructiontowork,itisnecessarythatwecanconstructG2.Itshouldbeclearthatifwedonotchangetheorderingofvertexde-grees,thatthedegreesequenceofG2isequalto[4,4,3,3,3,3,2].First,itcontainsoneelementlessthanthedegreesequenceofG1.Second,thefirstelementofthedegreesequenceofG2correspondstothesec-ondelementofG1’sdegreesequence:it’sthedegreeofthesamever-tex,yetforG2itshouldbeonelessthaninG1becausethisvertexisnotyetjoinedtotheaddedvertexv1.Likewise,thesecondelementofG2’sdegreesequencecorrespondstothethirdoneinthedegreesequenceofG1,andsoon.•If[4,4,3,3,3,3,2]isgraphicwecanapplythesametrick:G2shouldbeconstructablefromagraphG3byaddingavertexv2andjoiningv2tofourverticesfromG3.Followingacompletelyanalogousprocedureasbefore,v2isjoinedtotheverticesfromG3suchthattheseverticeswillthenhavevertexdegree4,3,3,and3,respectively.ThiscanonlymeanthatinG3theywillhavedegree3,2,2,and2,respectively,lead-ingtothefollowinglist:[3,2,2,2,3,2].Notethatinthisexample,thefifthelementisthesameasthesixthelementinthedegreesequenceofG2.Thefirstfourelementsrepresentverticesthatwillbejoinedtothenewvertexv2.Theotherelementsrepresentverticesthatremainuntouched,andwillthushavethesamenumberofincidentedgesinG2.•Continuingthislineofreasoning,if[3,3,2,2,2,2]isthe(nowordered)degreesequenceofG3,thenweshouldbeabletoconstructG3fromagraphG4towhichwehaveaddedavertexv3.Thisvertexwouldbejoinedtotheverticeshavingdegree2,1,and1inG4,respectively,yieldingthelist[2,1,1,2,2].Again,notethatthislistcontainsoneelementlessthanthedegreesequenceofG3,butthatnowitsfourthandsubsequentelementsrepresentverticesthathavethesamevertexdegreeinG4andG3.•Wenowhavethatiforderedlist[2,2,2,1,1]isgraphic,thensoshould[1,1,1,1],correspondingtoagraphG5.•Likewise,if[1,1,1,1]isgraphic,thensoshouldthelistofvertexde-grees[0,1,1]correspondtoagraphG6.•Finally,iftheorderedlist[1,1,0]isgraphic,thensoshould[0,0],24 whichistrue:itisagraphG7withtwoverticesandnoedges.Wecansafelyconcludethatthesequence[7,5,5,4,4,4,4,3]indeedcorre-spondstoasimplegraph.TheconstructionofthegraphG1isillustratedinFigure2.2whichshowshoweachgraphG1,G2,...,G6isconstructedbyaddingavertextothepreviousone,startingfromgraphG7.TheanswertowhetherG1isthesameasthegraphfromFigure2.1isaquestionwedeferuntillater.Infact,itturnsouttobequestionthatisgenerallynoteasytoresolve.G7G6G5G4G3G2G1Figure2.2:TheconstructionofgraphG1frompreviousgraphsbasedondegreesequences.Intuitively,itshouldbeclearthatwehavejustintroducedasystematicwayofcheckingwhetheragivenlistofnumberscorrespondstothedegreesequenceofagraph.Italsoformstheessenceoftheproofofthefollowingtheoremthattellsuswhenalistofnumbersisindeedgraphic.Theorem2.2(Havel-Hakimi):Consideralists=[d1,d2,...,dn]ofnnumbersindescendingorder.Thislistisgraphicifandonlyifs=[d,d,...,d]of12n 1n 1numbersisgraphicaswell,where(di+1 1fori=1,2,...,d1di=di+1otherwise25 Note2.3(Mathematicallanguage)Notethatthistheoremconsistsoftwostatements:1.ifsisgraphicthensoiss2.ifsisgraphicthensoissThisisthemeaningof“ifandonlyif,”whichisoftenabbreviatedtoiff.Wewillencountermoreofsuchtheorems,andinordertoprovethemcorrect,proofsinthesecaseswillalwaysconsistoftwoparts.ProofofTheorem2.2.Toprovethistheorem,letusfirstassumethatsisgraphic.Wethenneedtoshowthatsisalsographic.LetGbeasim-plegraphwithdegreesequences.WenowconstructasimplegraphGfromGwithdegreesequencesasfollows(andindoingso,weshowthatsisgraphic).TakeGandaddavertexu.Forreadability,letk=d1andconsiderthekverticesv1,v2,...,vkfromGhavingrespectivelyde-greed,d,...,d.Wethenjointheseverticestothenewlyaddedvertex12ku.Obviously,unowhasdegreek,butalsoeachvertexvinowhasdegreed+1.BecauseallotherverticesofGarenotjoinedwithu,theirvertexidegreeisleftunaffected.Asaconsequence,thenewlyconstructedgraphGhasdegreesequence[k,d+1,d+1,...,d+1,d,...,d],whichis12kk+1n 1preciselys.Letusnowconsidertheopposite:ifsisgraphic,weneedtoshowthatsissoaswell.Inotherwords,weneedtofindagraphGthathasdegreesequences.Tothisend,weconsiderthreedifferentsetsofverticesfromG.Letubeavertexwithdegreek=d1.LetV=fv1,v2,...,vkgbethere-spectiveverticeswiththeknexthighestdegreesd2,d3,...,dk+1.Finally,letW=fw1,w2,...,wn k 1gbetheremainingn k 1verticeswithdegreedk+2,dk+3,...,dn,respectively.ConsiderthegraphGbyremovingufromG,alongwiththekedgesincidentwithu.IfeachoftheseedgesisincidentwithoneoftheverticesfromV,thenobviouslyGisagraphwithdegreesequence(d2 1,d3 1,...,dk+1 1,dk+2,...,dn),whichispreciselys.NowconsiderthesituationthatuisadjacenttoavertexfromW,saywi.Ifforsomevertexvj2V,thedegreeofvjandwiarethesame,i.e.,d(wi)=d(vj),thenwecansimplyswapwiandvjintheoriginalconstructionofthesetsVandW,meaningthathu,wiiisnowanedgeincidentwithavertexfromVinsteadofW.However,ifd(wi)