approach to measure preferential attachment in net

arXiv:cond-mat/0512117v2[cond-mat.stat-mech]25Apr2006Aself-consistentapproachtomeasurepreferentialattachmentinnetworksanditsapplicationtoaninherentstructurenetworkClaireP.MassenandJonathanP.K.Doye∗UniversityChemicalLaboratory,LensfieldRoad,CambridgeCB21EW,UnitedKingdom(Dated:February2,2008)Preferentialattachmentisonepossiblewaytoobtainascale-freenetwork.Wedevelopaself-consistentmethodtodeterminewhetherpreferentialattachmentoccursduringthegrowthofanetwork,andtoextractthepreferentialattachmentruleusingtime-dependentdata.Modelnet-worksaregrownwithknownpreferentialattachmentrulestotestthemethod,whichisseentoberobust.Themethodisthenappliedtoascale-freeinherentstructurenetwork,whichrepresentstheconnectionsbetweenminimaviatransitionstatesonapotentialenergylandscape.Eventhoughthisnetworkisstatic,wecanexaminethegrowthofthenetworkasafunctionofathresholdenergy(ratherthantime),whereonlythosetransitionstateswithenergieslowerthanthethresholdenergycontributetothenetwork.Forthesenetworksweareabletodetectthepresenceofpreferentialattachment,andthishelpstoexplaintheubiquityoffunnelsonenergylandscapes.However,thescale-freedegreedistributionshowssomedifferencesfromthatofamodelnetworkgrownusingtheobtainedpreferentialattachmentrules,implyingthatotherfactorsarealsoimportantinthegrowthprocess.I.INTRODUCTIONScale-freenetworksareubiquitousinnature[1,2],technology[3,4]andsociety[5,6].Itiswellknownthatagrowthmechanisminvolvingpreferentialattach-mentcanleadtoscale-freenetworks[7].IntheoriginalBarab´asi-Albert(BA)model[7],anewnodeisaddedateachtimesteptogetherwithmnewedges.Thesenewedgesaremorelikelytoattachtooldnodeswithhighdegree,thusthehigherthedegreeofanode,thefasteritsdegreeincreases,leadingtothepower-lawdegreedis-tributionthatischaracteristicofscale-freenetworks.Forlinearpreferentialattachment,nodesgainedgeswithaprobabilityΠthatisproportionaltotheirdegreek.Foramoreflexiblepower-lawform,Π∝kα,ithasbeenshownthatascale-freenetworkisonlyproducedbytheBAmodeliftheexponentα=1[8].Forα1,thedegreedistributionfollowsastretchedexponential,andforα1asinglesiteconnectstoallthenodes.However,inmorecomplexmodels,theresultingnetworkscanbescale-freeevenifα6=1[9–14].Previously,wehaveanalysedthepropertiesofinher-entstructure(IS)networks[15–17],andherewewanttotestwhetherthepreferentialattachmentmodelcanhelptoexplainthescale-freecharacterofthesenetworks.ISnetworksrepresentpotentialenergylandscapesbytak-inglocalminimainthepotentialenergy,orinherentstructures,tobenodesinthenetwork,andedgeslinkthoseminimathataredirectlyconnectedbyatransitionstate.Thisnetworkprovidesadynamicallyrelevantrep-resentationofthelandscape,sincethelow-temperaturedynamicsofasystemcanbeconsideredintermsofahoppingbetweenbasinsofattractionsurroundingtheminimaviatransitionstates[18].ISnetworksforsmall∗Electronicaddress:[e-mail]-Jonesclustershavebeenshowntobescale-free[15].Furthermore,indirectevidencethatthistopologyismoregeneralhascomefromthepropertiesofthebasinsofattractionsurroundingminimaforsupercooledliquids[19],andfromthetopologyofmorecoarse-grainedde-scriptionsoftheenergylandscapesofproteins[20,21].UnderstandingtheoriginofthetopologyoftheISnet-worksisaparticularchallengebecause,unlikemanynet-works,theyarestatic.Thetopologyisdeterminedjustbytheinterparticlepotentialandthesizeofthesystem.Therefore,apreferentialattachmentapproachmight,atfirstsight,seemtotallyinappropriatetothesenetworksbecausetheydonotgrowintime.However,herewewishtoexplorewhethertheISnetworkscanbeunderstoodintermsofaquasi-growthprocess.Inparticular,wewillexaminehowthenetworkevolvesasafunctionofathresholdenergy,whereonlythosetransitionstatesthatliebelowthatenergygiverisetoedgesinthenetwork.Inthisquasi-growthprocessthelow-energyminimacorre-spondtothe‘older’nodesinthenetwork.Wehavepre-viouslyshownthatthereisastrongcorrelationbetweentheenergyofaminimumanditsdegreewiththe‘older’lower-energyminimahavinghigherdegree[15],thussug-gestingthatapreferentialattachmentmodelmightbefruitful.Sofar,preferentialattachmenthasonlybeentestedempiricallyinrelativelyfewcases[9–14,22,23].Thisispartlyduetothelackoftime-resolveddataforgrowingnetworks,butareliablemethodfordeterminingtheformofthepreferentialattachmentisalsolacking.Themainproblemisthattheprobabilityofanodewithgivende-greegaininganedge,Π(k,t)=kα/Pikαi,dependsonthesizeofthenetworkthroughthedenominatorofthisexpression.Amethodthathasbeenusedpreviouslyistoconsidertwosnapshotsofthenetworkacertaintimeapart[10–13].Therelationshipbetweenthenumberofedgesgainedbyanodeinthistimeanditsdegreeintheinitialnetwork2canbedetermined.Thedegreeofeachnode,andhencePikαi,isassumedtoremainconstantoverthistimepe-riod.Theconsequencesofthisapproximationarenotclear.Furthermore,theresultswilldependonthesizeofthetimeperiodused.Actor,scientificcollaborationandproteininteractionnetworkshavebeenstudiedusingthismethod,findingexponentsbetween0.75and1.1.Newmanstudiedtime-resolveddataforscientificcol-laborationnetworks[9],comparingtheprobabilitythatanodewithgivendegreegainsanedge(asmeasuredfromthedata)withthatexpec