资源描述：
《Exact solutions for models of evolving networks with addition and deletion of nodes》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
PHYSICALREVIEWE74,0361212006Exactsolutionsformodelsofevolvingnetworkswithadditionanddeletionofnodes1,2,34,53,4CristopherMoore,GourabGhoshal,andM.E.J.Newman1DepartmentofComputerScienceandDepartmentofPhysicsandAstronomy,UniversityofNewMexico,Albuquerque,NewMexico87131,USA2SantaFeInstitute,SantaFe,NewMexico87501,USA3CenterfortheStudyofComplexSystems,UniversityofMichigan,AnnArbor,Michigan48109,USA4DepartmentofPhysics,UniversityofMichigan,AnnArbor,Michigan48109,USA5MichiganCenterforTheoreticalPhysics,UniversityofMichigan,AnnArbor,Michigan,48109,USAReceived11April2006;published28September2006Therehasbeenconsiderablerecentinterestinthepropertiesofnetworks,suchascitationnetworksandtheworldwideweb,thatgrowbytheadditionofvertices,andanumberofsimplesolvablemodelsofnetworkgrowthhavebeenstudied.Intherealworld,however,manynetworks,includingtheweb,notonlyaddverticesbutalsolosethem.Hereweformulatemodelsofthetimeevolutionofsuchnetworksandgiveexactsolutionsforanumberofcasesofparticularinterest.Forthecaseofnetgrowthandso-calledpreferentialattachmentinwhichnewlyappearingverticesattachtopreviouslyexistingonesinproportiontovertexdegreeweshowthattheresultingnetworkshavepower-lawdegreedistributions,butwithanexponentthatdivergesasthegrowthratevanishes.Weconjecturethatthelowexponentvaluesobservedinreal-worldnetworksarethustheresultofvigorousgrowthinwhichtherateofadditionofverticesfarexceedstherateofremoval.Weregrowthtoslowinthefutureforinstance,inamorematurefutureversionofthewebwewouldexpecttoseeexponentsincrease,potentiallywithoutbound.DOI:10.1103/PhysRevE.74.036121PACSnumbers:89.75.Hc,89.20.Hh,05.10.Gg,05.65.bI.INTRODUCTIONdeletionaffectsthecrucialpower-lawbehaviorofthedegreedistribution,whileinothercasesitdoesnot.ThestudyofnetworkshasattractedasubstantialamountInthispaper,westudythegeneralprocessinwhichaofattentionfromthephysicscommunityinthelastfewyearsnetworkgrowsor,potentially,shrinksbytheconstantad-13,inpartbecauseofnetworksbroadutilityasrepresen-ditionandremovalofverticesandedges.Weshowthatatationsofreal-worldcomplexsystemsandinpartbecauseofclassofsuchprocessescanbesolvedexactlyforthedegreethedemonstrablesuccessesofphysicstechniquesinshed-distributionstheygeneratebysolvingdifferentialequationsdinglightonnetworkphenomena.Onetopicthathasbeengoverningtheprobabilitygeneratingfunctionsforthosedis-thesubjectofaparticularlylargevolumeofworkisgrowingtributions.Inparticular,wegivesolutionsforthreeexamplenetworks,suchascitationnetworks4,5andtheworldwideproblemsofthistype,havinguniformorpreferentialattach-web6,7.Perhapsthebest-knownbodyofworkonthismentandhavingstationarysizeornetgrowth.Thecaseoftopicisthatdealingwithpreferentialattachmentmodelsuniformattachmentandstationarysizeisofinterestasa8,9,inwhichverticesareaddedtoanetworkwithedgespossiblemodelforthestructureofpeer-to-peerfilesharingthatattachtopreexistingverticeswithprobabilitiesdepend-networks,whilethepreferential-attachmentstationary-sizeingonthoseverticesdegrees.Whentheattachmentprob-casedisplaysanontrivialstretchedexponentialformintheabilityispreciselylinearinthedegreeofthetargetvertexthetailofthedegreedistribution.OursolutionofthepreferentialresultingdegreesequenceforthenetworkfollowsaYuleattachmentcasewithnetgrowthconfirmsearlierresultsin-distributioninthelimitoflargenetworksize,meaningithasdicatingthatthisprocessgeneratesapower-lawdistribution,apower-lawtail812.Thiscaseisofspecialinterestbe-althoughtheexponentofthepowerlawdivergesasthecausebothcitationnetworksandtheworldwidewebareob-growthratetendstozero,givingdegreedistributionsthatareservedtohavedegreedistributionsthatapproximatelyfollownumericallyindistinguishablefromexponentialforsmallpowerlaws.growthrates.ThissuggeststhattheclearpowerlawseeninThepreferentialattachmentmodelmaybequiteagoodtherealworldwidewebisasignatureofanetworkwhosemodelforcitationnetworks,whichisoneofthecasesforrateofvertexaccrualfaroutstripstherateatwhichverticeswhichitwasoriginallyproposed8,10.Forothernetworks,areremoved.Therelativeratesofadditionandremovalhowever,andespeciallyfortheworldwideweb,itis,ascould,however,changeasthewebmatures,possiblyleadingmanyauthorshavepointedout,necessarilyincompletetoalossofpower-lawbehavioratsomepointinthefuture.1317.Onthewebthereareclearlyotherprocessestakingplaceinadditiontothedepositionofverticesandedges.InII.THEMODELparticular,itisamatterofcommonexperiencethatverticesi.e.,webpagesareoftenremovedfromthewebandwithConsideranetworkthatevolvesbytheadditionandre-themthelinksthattheyhadtootherpages.Modelsofthismovalofvertices.Ineachunitoftime,weaddasingleprocesshavebeentoucheduponoccasionallyintheliteraturevertextothenetworkandremoververtices.Whenavertex1820,andtheevidencesuggeststhatinsomecasesvertexisremoved,sotooarealltheedgesincidentonthatvertex,1539-3755/2006/743/0361218036121-1©2006TheAmericanPhysicalSociety MOORE,GHOSHAL,ANDNEWMANPHYSICALREVIEWE74,0361212006whichmeansthatthedegreesoftheverticesattheotherendsmeansthatthetotalprobabilitythatthegivenedgeattachesofthoseedgeswilldecrease.Nonintegervaluesofrareper-toanyvertexofdegreekissimplykpk.Sinceeachedgemittedandareinterpretedintheusualstochasticfashion.mustattachtoavertexofsomedegree,thisalsoimmediatelyForexample,valuesr1canbeinterpretedastheprobabil-impliesthatthecorrectnormalizationforkisityperunittimethatavertexisremoved.Thevaluer=1correspondstoanetworkoffixedsizeinwhichthereisver-kpk=1.4texturnoverbutnogrowth;valuesr1correspondtogrow-k=0ingnetworks.Inprincipleonecouldalsolookatvaluesr1,whichcorrespondtoshrinkingnetworks,andthemeth-Fortheparticularcaseofkkandr1,whichweconsiderodsderivedhereareapplicabletothatcase.However,weareinSec.IIIC,modelssimilartoourshavebeenstudiedpre-notawareofanyreal-worldexamplesofshrinkingnetworksviouslybySarsharandRoychowdhury18,ChungandLuinwhichtheasymptoticdegreedistributionisofinterest,so19,andCooper,Frieze,andVera20.Whiletheseauthorswewillnotpursuetheshrinkingcasehere.didnotseekanexactsolution,ourresultsonthepower-lawWemaketwofurtherassumptions,whichhavealsobeentailofthedegreedistributioninthiscasecoincidewithmadebymostpreviousauthorsinstudyingthesetypesoftheirs.systems:1thatallverticesaddedhavethesameinitialde-gree,whichwedenotec;2thattheverticesremovedareA.Rateequationselecteduniformlyatrandomfromthesetofallextantver-tices.Note,however,thatwewillnotassumethatthenet-Giventhesedefinitions,theevolutionofthedegreedistri-workisuncorrelatedi.e.,thatitisarandommultigraphbutionisgovernedbyarateequationasfollows.Ifthereareconditionedonitsdegreedistributionasintheso-calledcon-atotalofnverticesinthenetworkatagiventime,thenthefigurationmodel.Ingeneralthenetworksweconsiderwillnumberofverticeswithdegreekisnpk.Oneunitoftimehavecorrelationsamongthedegreesoftheirverticesbutourlaterthisnumberisn+1−rpk,wherepkisthenewvalueofsolutionswillnonethelessbeexact.pk.ThenLetpkbethefractionofverticesinthenetworkatagiventimethathavedegreek.Bydefinition,pkhasthen+1−rpk=npk+kc+ck−1pk−1−ckpk+rk+1pk+1normalization−rkpk−rpk.5ThetermkcinEq.5representstheadditionofavertexofpk=1.1degreectothenetwork.Thetermscpand−cpk−1k−1kkk=0describetheflowofverticesfromdegreek−1tokandfromOurprimarygoalinthispaperwillbetoevaluateexactlythektok+1astheygainextraedgeswhennewlyaddedverticesdegreedistributionpkforvariouscasesofinterest.attachtothem.Thetermsk+1pk+1and−kpkdescribetheAlthoughtheformofpkis,aswewillsee,highlynon-flowfromdegreek+1tokandfromktok−1asverticeslosetrivialinmostcases,themeandegreeofavertex,kedgeswhenoneoftheirneighborsisremovedfromthenet-work.Andtheterm−rprepresentstheremovalwithprob-=k=0kpk,iseasilyderivedintermsoftheparametersrandkc.Themeannumberofverticesaddedtothenetworkperabilityrofavertexwithdegreek.Contributionsfrompro-unittimeis1−r.Themeannumberofedgesremovedwhencessesinwhichavertexgainsorlosestwoormoreedgesinarandomlychosenvertexisremovedfromthenetworkisbyasingleunitoftimevanishinthelimitoflargenandhavedefinitionk.Thusthemeannumberofedgesaddedtothebeenneglected.networkperunittimeisc−rk.ForagraphofmedgesandWewillbeinterestedintheasymptoticformofpkinthenvertices,themeandegreeisk=2m/n.Aftertimetwelimitoflargetimesforagivenk.Settingpk=pkinEq.5haven=1−rtand,assumingthatkhasanasymptoticallygivesconstantvalue,m=c−rkt.Thuskc+ck−1pk−1−ckpk+rk+1pk+1−rkpk−pk=0.c−rk6k=221−rWecanwritethesolutiontoEq.6intermsofgeneratingor,rearranging,functionsasfollows.Letusdefine2ck=.3fz=pzk,7kk1+rk=0Inthespecialcaser=1ofaconstant-sizenetwork,thisgivesk=c,whichisclearlythecorrectanswer.gz=pzk.8Wemustalsoconsiderhowanaddedvertexchoosestheckk=0otherverticestowhichitattaches.Letusdefinetheattach-mentkerneltobentimestheprobabilitythatagivenedgeThen,uponmultiplyingbothsidesofEq.6byzkandsum-kofanewlyaddedvertexattachestoagivenpreexistingver-mingoverkwiththeconventionthatp−1=0,wederiveatexofdegreek.Thefactorofnhereisconvenient,sinceitdifferentialequationforgzthus:036121-2 EXACTSOLUTIONSFORMODELSOFEVOLVING…PHYSICALREVIEWE74,0361212006dgToobtainanexplicitexpressionforthedegreer1−z−gz−c1−zfz+zc=0.9distribution,wemakeuseofdzcmNotealsothatwecaneasilygeneralizeourmodeltothecasexc+1,x=c+1e−x,13wherethedegreesoftheverticesaddedarenotallidenticalm!m=0butareinsteaddrawnatrandomfromsomedistributionrk.Inthatcase,wesimplyreplaceinEq.6withrandzcinkckkxmEq.9withthegeneratingfunctionhz=krkz.ex=,14InthefollowingsectionswesolveEq.9foranumberofm=0m!differentchoicesoftheattachmentkernelk.Notethat,sincethedefinitionsofbothfzandgzincorporatetheunknowndistributionpk,wemustingeneralsolveimplicitly1−z−1=zk,15forgzintermsoffz.Inallofthecasesofinteresttousk=0here,however,itturnsouttobestraightforwardtoderiveantowriteexplicitequationforgzasaspecialcaseofEq.9.cmczgz=c−c+1zkc+1III.SOLUTIONSFORSPECIFICCASESk=0m=0m!mInthissectionwestudythreespecificexamplesofthecz−c+1,c.16classofmodelsdefinedintheprecedingsection:namely,m!m=0linearpreferentialattachmentmodelskkforbothgrow-ingandfixed-sizenetworksanduniformattachmentThezdependenceinthefirsttermofthisexpressioncanbek=constantforfixedsize.Aswewillsee,eachoftheserewrittencasesturnsouttohaveinterestingfeatures.cmcmczczk=zkk=0m=0m!m=0k=mm!A.Uniformattachmentandconstantsizemink,cmc„mink,c+1,c…Forthefirstofourexamplemodelswestudythecase=zk=eczk,wherethesizeofthenetworkisconstantr=1andinwhichk=0m=0m!k=0„mink,c+1…eachvertexaddedchoosesthecotherstowhichitattaches17uniformlyatrandom.Thismeansthatkisconstant,inde-pendentofk,andcombiningEqs.1and4,weimmedi-wheremink,cdenotesthesmallerofkandcandwehaveatelyseethatthecorrectnormalizationfortheattachmentagainemployedEq.13.Asimilarsequenceofmanipula-kernelisk=1forallk.Thenwehavekpk=pksothattionsleadstoanexpressionforthesecondtermalso,thus:fz=gzinEq.9,whichgivesczmk+1,czk=eczk.181dgzcc+gz−=.10k=0m=0m!k=0k+11−zdz1−zCombiningtheseidentitieswithEq.16,itisthenasimpleNotingthat1−ze−czisanintegratingfactorandthatgzkmattertoreadoffthetermingzinvolvingz,whichisbymustobeytheboundaryconditiong1=1,wereadilydefinitionourpk.Wefindtwoseparateexpressionsforthedeterminethatcasesofkaboveandbelowc:ecz1eck+1,cgz=tce−ctdtpk=c+1c+1−c+1,c,forkc,1−zzck+1ecz19=c−c+1c+1,cz−c+1,c,111−zandwhereeck+1,cpk=c+1c+1,c1−,forkc.20ck+1c+1,x=tce−tdt12Notethatthequantityk+1,c/k+1appearinginbothxtheseexpressionsistheprobabilitythataPoisson-distributedistheincompletefunction.variablewithmeancislessthanorequaltok.ThustheOnecaneasilycheckthatthisgivesameandegreedegreedistributionhasatailthatdecaysasthecumulativeg1=c,asitmust,andthatthevarianceofthedegreedistributionofsuchaPoissonvariable,implyingthatitfallsg1+g1−c2isequalto2c,indicatingatightlypeaked3offrapidly.Toseethismoreexplicitly,wenotethatforfixeddegreedistributionwhencislarge.candkc036121-3 MOORE,GHOSHAL,ANDNEWMANPHYSICALREVIEWE74,036121200610021.ItisstraightforwardtoseethatifonestartswithsuchagraphandrandomlyaddsandremovesverticeswithPoisson--1distributeddegrees,thegraphremainsanuncorrelatedran-10domgraphwiththesamedegreedistribution,andhencethisdistributionisnecessarilythefixedpointoftheevolution-2k10Pprocess,asthesolutionabovedemonstrates.-310B.PreferentialattachmentandconstantsizeProbability-4Ournextexampleaddsanextradegreeofcomplexityto10thepicture:weconsiderverticesthatattachtoothersinpro--5portiontotheirdegree,theso-calledpreferentialattach-10mentmechanism9.Thisimpliesthatourattachmentker--6nelkislinearinthedegree:k=AkforsomeconstantA.10110Thenormalizationrequirement4thenimpliesthatDegreekkpk=Akpk=Ak=1,25FIG.1.ColoronlineThedegreedistributionofourmodelfork=0k=0thecaseofuniformattachmentk=constantwithfixedsizen=50000andc=10.ThepointsrepresentdatafromnumericalandhenceA=1/k.Forthemoment,letuscontinuetofocussimulationsandthesolidlineistheanalyticsolution.onthecaser=1ofconstantnetworksize,inwhichcasek=cEq.3andmc+1,ccc+1,cp=ck−c,21kkcc+1m!k+2k=.26m=k+1csincethesumisstronglydominatedinthislimitbyThenitsfirstterm.ApplyingStirlingsapproximation,x
x/ex2/x,thisgives1zfz=kpzk=gz,27c+1,ckckc−3/2kck=0pkcke,22ckandEq.9becomeswhichdecayssubstantiallyfasterasymptoticallythananygzdgzcexponential.−=.28Asacheckonthesecalculations,wehaveperformedex-1−z2dz1−z2tensivecomputersimulationsofthemodel.InFig.1weTheappropriateintegratingfactorinthiscaseise−1/1−z,showresultsforthecasec=10,alongwiththeexactsolutionfromEqs.19and20.Asthefigureshows,theagreementwhich,inconjunctionwiththeboundaryconditiong1=1,betweenthetwoisexcellent.givesBeforemovingontootherissues,wenoteadifferentand1ctparticularlysimplecaseofagrowingnetworkwithuniformgz=e1/1−ze−1/1−tdt.291−t2attachment,thecaseinwhichtheverticesaddedhaveaPois-zsondegreedistributioncke−c/k!withmeanc.InthatcasethefactorofzcinEq.10isreplacedwiththegeneratingChangingthevariableofintegrationtoy=1/1−tthisfunctionhzforthePoissondistribution:expressioncanbewrittenk−c1ccekcz−1gz=e1/1−ze−ydyhz=z=e,231−k=0k!1/1−zyc−yandthesolution,Eq.11,becomesce=e1/1−z−1sdycz1syses=01/1−zgz=hte−ctdt=ecz−1,241−zzcc1=1+e1/1−z−1s1−s,.30whichisitselfthegeneratingfunctionforaPoissondistribu-s=1s1−ztion.Thusweseeparticularlyclearlyinthiscasethatthewhere1−s,x=e−yy−sdyisagaintheincompleteequilibriumdegreedistributioninthesteady-stateuniformxattachmentnetworkissharplypeakedwithaPoissontail.Infunction,hereappearingwithanegativefirstargument.fact,thenetworkinthiscaseissimplyanuncorrelatedran-Ausefulidentifyforthecases1canbederivedbydomgraphofthetypefamouslystudiedbyErdősandRényiintegratingbypartsthus:036121-4 EXACTSOLUTIONSFORMODELSOFEVOLVING…PHYSICALREVIEWE74,03612120061e−x010−s,x=s−1−s,x.31sx10-1Iteratingthisexpressionthengives10-2s−1-3−1s−1mm−1!k10−xP1−s,x=−0,x+em.10-4s−1!m=1x-53210Probability-60,x=e−y/ydyisalsoknownastheexponentialinte-10x-7gralfunction−Ei−x.ApplyingthisidentitytoEq.3010gives-810c-9c110gz=1−110100s=1ss−1!Degreeks−11e1/1−z0,+−1mm−1!1−zmFIG.2.ColoronlineThedegreedistributionforourmodelin1−zm=1thecaseoffixedsizen=50000andc=10withlinearpreferentialattachment.Thepointsrepresentdatafromournumericalsimula-1=qz−Ae1/1−z0,tions,andthesolidlineistheanalyticsolutionforkc.Notethatc,331−zthetailofthedistributiondoesnotfollowapowerlawasingrow-ingnetworkswithpreferentialattachment,butinsteaddecaysfasterwhereqzisapolynomialofdegreec−1andthanapowerlaw,asastretchedexponential.ccAc=s−1!Whilethecoefficientsakcanbeexpressedexactlyusings=1shypergeometricfunctions,amoreinformativeapproachistoemployasaddle-pointexpansion.TheintegrandofEq.39dependsonlyonc.Forkc,then,thedegreekisunimodalintheintervalbetween1andandpeaksatxdistributionpkisgivenbythecoefficientsofz1in−Ae1/1−z(0,1/1−z).Wedeterminethesecoefficients=1+4k+1
k.Approximatingtheintegrandasac2asfollows.ChangingthevariableofintegrationtoGaussianaroundthispoint,weobtainask→,x=y−z/1−z,wefindaek−3/4e−2k40k1e−x−e1/1−z0,=−edx.34andpk=Acakforkcasstatedabove.1−z1x+z/1−zFigure2showstheformofthissolutionforthecasec=10.AlsoshowninthefigureareresultsfromcomputerThenweexpandtheintegrandtogetsimulationsofthemodelonsystemsofsizen=50000withk−1kc=10,whichagreewellwiththeanalyticresults.Theappear-111z=−1−2.35anceofthestretchedexponentialinEq.40isworthyofx+z/1−zxk=1xxnote.Weareawareofonlyafewcasesofgraphswithstretchedexponentialdegreedistributionsthathavebeendis-Commutingthesumandtheintegral,weobtaincussedpreviouslyforinstance,ingrowingnetworkswithsublinearpreferentialattachment22aswellasinempirical1−e1/1−z0,=azk,36networkdata23.k1−zk=0whereC.Preferentialattachmentinagrowingnetworke−xWenowcometothethirdandmostcomplexofourex-a0=−edx=−e0,1,37amplenetworks,inwhichwecombinepreferentialattach-1xmentwithnetgrowthofthenetwork,r1.Logically,weandfork1,shouldperhapsfirstsolvethecaseofagrowingnetworkwithoutpreferentialattachment,whichinfactwehavedone.1k−1e−xButthesolutionturnsouttohavenoqualitativelynewfea-ak=e1−2dx.381xxturestodistinguishitfromtheconstantsizecaseandismathematicallytediousbesides.GiventhelargeamountofIntegratingbyparts,weobtainaslightlysimplerexpressioneffortitrequiresanditsmodestrewards,therefore,wepreferktoskipthiscaseandmoveontomorefertileground.e1a=1−e−xdx.39Asbefore,perfectlinearpreferentialattachmentimplieskk1xk=k/kor036121-5 MOORE,GHOSHAL,ANDNEWMANPHYSICALREVIEWE74,03612120061k−z1−−z/1−us+−2k=1+r,41du2c1−z01+uwherewehavemadeuseofEq.3.Thens+−1=−1s+1fz=1+rzgz/2candEq.9becomess1dg1−z1−−z/1−u−1gz−1−zr−1+rz=zc.422dz1−z1+udu0Anintegratingfactorfortheleft-handsideinthiscases−1mm−2/1−r−1−zis−z/1−zwhere=2r/1+r.Notethat+.471whenr1.Unfortunately,thisintegratingfactorism=1+m1−znonanalyticatz=,whichmakesintegralstraversingthisThefinalsumcanbeevaluatedinclosedformintermsofthepointcumbersome.Tocircumventthisdifficulty,weobserveincompletefunction,butourprimaryfocushereisonthethatthesecondterminEq.42vanishesatz=,givingprecedingterm.SubstitutingintoEq.45,weseethatgzg=c.Thisprovidesuswithanalternativeboundarycon-=qz+Ac,rhz,whereditionongz,allowingustofixtheintegratingconstantwhileonlyintegratinguptoz=.Itisthenstraightforward−z1−−z/1−u−1toshowthathz=−du,481−z01+u2−z−2/1−r−t2/1−rtcdtgz=,c1+r1−zz1−t1−t−t2cs−1c−s+s−1Ac,r=1−,49431+rs=0ssforz.Sincethedegreedistributionisentirelydeterminedandqzisapolynomialoforderc−1inz.bythebehaviorofgzattheorigin,itisadequatetorestrictSinceAc,rdependsonlyoncandrandqzhasnotermsinzoforderzcorhigher,thedegreedistributionforkcis,oursolutiontothisregime.Changingvariablestou=−t/1−,wefindtowithinamultiplicativeconstant,givenbythecoefficientsintheexpansionofhzaboutzero.Makingthechangeof2−z1−variablesgz=1−−11+r1−zy−z/1−u=,50ucdu1−z/−z−y−1−u2,4401+uuwefindthatwhere=3−r/1−r.Ifweexpandthelastfactorinthe1y−1dyintegrand,thisbecomeshz=−,5101−z/−z−yc2scs−1c−sandexpandingtheintegrandinpowersofzweobtaingz=−11−k1+rs=0shz=k=0akzwith−z1−−z/1−us+−211−yk−1du.45ak=1−y−1dy1−z1+u1−yk+100Weobservethefollowingusefulidentity:−111−yk=y−2dy,52xxk01−yuudu=1+u−du1+u1+ufork1,wherethesecondequalityfollowsviaan00integrationbyparts.xAsinthecaseofconstantsize,wecanexpressthese=−+11+x−1coefficientsinclosedformusingspecialfunctions,butifwex−1areprimarilyinterestedintheformofthetailofthedegreeu−du,46distribution,thenamorerevealingapproachistomakea−+101+ufurthersubstitutiony=x/k,givingwherethesecondequalityisderivedviaintegrationbyparts.k1−x/kka=−1k−x−2dx.53Setting=s+−2andx=−z/1−andnotingthatthek1−x/kk0lastintegralhasthesameformasthefirst,wecanemploythisidentityiterativelys−1timestogetInthelimitoflargekthisbecomes036121-6 EXACTSOLUTIONSFORMODELSOFEVOLVING…PHYSICALREVIEWE74,0361212006100consideredcaseofadditionofvertices,wealsoincludevertexremoval.Wehavegivenexactsolutionsforcasesinwhichverticesareaddedandremovedatthesamerate,a-110potentialmodelforsteady-statenetworkssuchaspeer-to-peernetworks,andcasesinwhichtherateofadditionkexceedstherateofremoval,whichweregardasaP-210simplemodelforthegrowthof,forexample,theworldwideweb.10-3Wefindverydifferentbehaviorsinthesevariouscases.ProbabilityForasteady-statenetworkinwhichnewlyaddedverticesattachtoothersatrandomwefindadegreedistribution,Eqs.-41019and20,whichissharplypeakedaboutitsmaximumandhasarapidlydecayingPoissontail.Thisdistributionisquiteunliketheright-skeweddegreedistributionsfoundin-510manyreal-worldnetworks,butasapossibleformforade-110100signednetworksuchasapeer-to-peernetworkitmightbeDegreekpreferableoverskewedforms,beingmorehomogeneousandhencedistributingtrafficmoreevenly.FIG.3.ColoronlineDegreedistributionforagrowingnet-1Ifnewlyappearingverticesattachtoothersusingalinearworkwithlinearpreferentialattachmentandr=,c=10.Thesolid2preferentialattachmentmechanism,wherebyverticesgainlinerepresentstheanalyticsolution,Eqs.49and52,forkc,newedgesinproportiontothenumbertheyalreadypossess,andthepointsrepresentsimulationresultsforsystemswithfinalwefindthatthedegreedistributionbecomesastretchedex-sizen=100000vertices.ponential,Eqs.39and40,asubstantiallybroaderdistri-butionthanthatoftherandomattachmentcase,thoughstillmorerapidlydecayingthanthepowerlawsoftenseenina
−1k−e−1−xx−2dx=k−,54k1−−1growingnetworks.0Andinthecasewherethenetworkshowsnetgrowth,andpk=Ac,rakforkcasstatedabove.addingverticesfasterthanitlosesthem,wefindthattheThusthetailofthedegreedistributionfollowsapowerdegreedistributionfollowsapowerlaw,Eqs.52and54,lawwithexponentwithanexponentthatassumesvaluesintherange3,divergingasthegrowthratetendstozero.3−rThislastresultisofinterestforanumberofreasons.=.551−rFirst,itshowsthatpower-lawbehaviorcanberigorouslyestablishedinnetworksthatgrowbutalsolosevertices.Notethatthisexponentdivergesasr→1sothatthepowerMostpreviousanalyticmodelsofnetworkgrowthhavefo-lawbecomeseversteeperasthegrowthrateslows,eventu-cusedsolelyonvertexaddition.Andwhiletherealworld-allyassumingthestretchedexponentialformofEq.40widewebandothernetworksappeartohavedegreedistri-steeperthananypowerlawinthelimitr=1.Inthelimitbutionsthatcloselyfollowpowerlaws,thesenetworksalsor→0werecovertheestablishedpower-lawbehaviorclearlyloseverticesaswellasgainingthem.Theresultsak−3forgrowinggraphswithpreferentialattachmentandpresentedheredemonstratethatthewidelystudiedmecha-knovertexremoval811.nismofpreferentialattachmentforgeneratingpower-lawInFig.3weshowtheformofthedegreedistributionforbehavioralsoworksinthisregime.thismodelforthecaser=1,c=10,alongwithnumericalOntheotherhand,thelargevaluesoftheexponent2resultsfromsimulationsofthemodelonnetworksoffinalgeneratedbyourmodelappearnottobeinagreementwithsizen=100000vertices.Thepower-lawbehaviorisclearlythebehaviorobservedinreal-worldnetworks,mostofwhichvisibleonthelogarithmicscalesusedasastraightlineinthehaveexponentsintherangefrom2to313.Therearetailofthedistribution.Onceagaintheanalyticsolutionandwell-knownmechanismsthatcanreducetheexponentfromsimulationsareinexcellentagreement.3tovaluesslightlylowerspecificallythegeneralizationofWenotethatSarsharandRoychowdhury18and,subse-thepreferentialattachmentmodeltothecaseofadirectedquently,ChungandLu19andCooper,Frieze,andVeranetwork8,11,whichisinanycaseamoreappropriate20independentlydemonstratedpower-lawbehaviorinthemodelfortheworldwideweb.Inthelimitoflowgrowthdegreedistributionofnetworksinthecaser1.Theirre-rate,however,ourmodelpredictsadivergingexponentand,sultsfocusonthetailofthedistributionratherthanonexactwhiletheexactvaluemaynotbeaccuratebecauseofahostsolutions,buttheyfindthesamedependenceoftheexponentofcomplicatingfactors,itseemslikelythatthedivergenceonthegrowthrate.itselfisarobustphenomenon;asotherauthorshavecom-mented,therearegoodreasonstobelievethatnetgrowthisoneofthefundamentalrequirementsforthegenerationofpower-lawdegreedistributionsbythekindofmechanismsIV.DISCUSSIONconsideredhere.InthispaperwehavestudiedmodelsofthetimeThusthefactthatwedonotobserveverylargeexponentsevolutionofnetworksinwhich,inadditiontothewidelyinrealnetworksappearstoindicatethatmostnetworksarein036121-7 MOORE,GHOSHAL,ANDNEWMANPHYSICALREVIEWE74,0361212006aregimewheregrowthdominatesoververtexlossbyawideticallyanticipateseeingbehaviorofthistypeanytimeinthemargin.Itispossible,however,thatthiswillnotalwaysbenearfuture.thecase.Theweb,forexample,hascertainlybeingenjoyingaperiodofveryvigorousgrowthsinceitsappearanceintheACKNOWLEDGMENTSearly1990s,butitcouldbethatthisisasignprimarilyofitsyouthandthatasthenetworkmaturesitssizewillgrowThisworkwasfundedinpartbytheNationalSciencemoreslowly,theverticesaddedbeingmorenearlybalancedFoundationunderGrantNos.DMS-0405348andPHY-bythosetakenaway.Werethistohappen,wewouldexpect0200909andbytheJamesS.McDonnellFoundation.C.M.toseetheexponentofthedegreedistributiongrowlarger.AthankstheUniversityofMichiganandtheCenterforthesufficientlylargeexponentwouldmakethedistributionin-StudyofComplexSystemsfortheirhospitalitywhilepartofdistinguishableexperimentallyfromanexponentialorthisworkwascarriedoutandTracyConradandRosemarystretchedexponentialdistribution,althoughwedonotrealis-Moorefortheirsupport.1R.AlbertandA.-L.Barabási,Rev.Mod.Phys.74,472002.Struct.Algorithms18,2792001.2S.N.DorogovtsevandJ.F.F.Mendes,Adv.Phys.51,107913S.N.DorogovtsevandJ.F.F.Mendes,Europhys.Lett.52,332002.2000.3M.E.J.Newman,SIAMRev.45,1672003.14R.AlbertandA.-L.Barabási,Phys.Rev.Lett.85,52344D.J.deS.Price,Science149,5101965.2000.5S.Redner,Eur.Phys.J.B4,1311998.15P.L.KrapivskyandS.Redner,Comput.Netw.39,2612002.6R.Albert,H.Jeong,andA.-L.Barabási,NatureLondon401,16B.Tadić,PhysicaA314,2782002.1301999.17A.Grönlund,K.Sneppen,andP.Minnhagen,Phys.Scr.71,7J.M.Kleinberg,S.R.Kumar,P.Raghavan,S.Rajagopalan,6802005.andA.Tomkins,inProceedingsofthe5thAnnualInterna-18N.SarsharandV.Roychowdhury,Phys.Rev.E69,026101tionalConferenceonCombinatoricsandComputing,editedbyT.Asano,H.Imai,D.T.Lee,S.-I.Nakano,andT.Tokuyama,2004.LectureNotesinComputerScienceSpringer,Berlin,1999,19F.ChungandL.Lu,InternetMathematics1,4092004.Vol.1627,pp.118.20C.Cooper,A.Frieze,andJ.Vera,InternetMathematics1,4638D.J.deS.Price,J.Am.Soc.Inf.Sci.27,2921976.2004.9A.-L.BarabásiandR.Albert,Science286,5091999.21P.ErdősandA.Rényi,Publ.Math.Inst.Hung.Acad.Sci.5,10P.L.Krapivsky,S.Redner,andF.Leyvraz,Phys.Rev.Lett.171960.85,46292000.22P.L.KrapivskyandS.Redner,Phys.Rev.E63,06612311S.N.Dorogovtsev,J.F.F.Mendes,andA.N.Samukhin,Phys.2001.Rev.Lett.85,46332000.23M.E.J.Newman,S.Forrest,andJ.Balthrop,Phys.Rev.E66,12B.Bollobás,O.Riordan,J.Spencer,andG.Tusnády,Random035101R2002.036121-8
