经典(无标度网络)Emergence-of-scaling-in-random-networks

arXiv:cond-mat/9910332v1[cond-mat.dis-nn]21Oct1999EmergenceofScalinginRandomNetworksAlbert-L´aszl´oBarab´asi∗andR´ekaAlbertDepartmentofPhysics,UniversityofNotre-Dame,Notre-Dame,IN46556Systemsasdiverseasgeneticnetworksortheworldwidewebarebestdescribedasnetworkswithcomplextopology.Acommonpropertyofmanylargenetworksisthatthevertexconnectivitiesfollowascale-freepower-lawdistribution.Thisfeatureisfoundtobeaconsequenceofthetwogenericmechanismsthatnetworksexpandcontinuouslybytheadditionofnewvertices,andnewverticesattachpreferentiallytoalreadywellconnectedsites.Amodelbasedonthesetwoingredientsreproducestheobservedstationaryscale-freedistributions,indicatingthatthedevelopmentoflargenetworksisgovernedbyrobustself-organizingphenomenathatgobeyondtheparticularsoftheindividualsystems.∗[e-mail]1Theinabilityofcontemporarysciencetodescribesystemscomposedofnon-identicalelementsthathavediverseandnonlocalinteractionscurrentlylimitsadvancesinmanydis-ciplines,rangingfrommolecularbiologytocomputerscience(1).Thedifficultyindescribingthesesystemsliespartlyintheirtopology:manyofthemformrathercomplexnetworks,whoseverticesaretheelementsofthesystemandedgesrepresenttheinteractionsbetweenthem.Forexample,livingsystemsformahugegeneticnetwork,whoseverticesareproteinsandgenes,theedgesrepresentingthechemicalinteractionsbetweenthem(2).Atadifferentorganizationallevel,alargenetworkisformedbythenervoussystem,whoseverticesarethenervecells,connectedbyaxons(3).Butequallycomplexnetworksoccurinsocialsci-ence,whereverticesareindividualsororganizations,andtheedgescharacterizethesocialinteractionbetweenthem(4),ordescribetheworldwideweb(),whoseverticesareHTMLdocumentsconnectedbylinkspointingfromonepagetoanother(5,6).Duetotheirlargesizeandthecomplexityoftheinteractions,thetopologyofthesenetworksislargelyunknown.Traditionally,networksofcomplextopologyhavebeendescribedusingtherandomgraphtheoryofErd˝osandR´enyi(ER)(7),butintheabsenceofdataonlargenetworksthepredictionsoftheERtheorywererarelytestedintherealworld.However,drivenbythecomputerizationofdataacquisition,suchtopologicalinformationisincreasinglyavailable,raisingthepossibilityofunderstandingthedynamicalandtopologicalstabilityoflargenetworks.Inthispaperwereportontheexistenceofahighdegreeofself-organizationcharacterizingthelargescalepropertiesofcomplexnetworks.Exploringseverallargedatabasesdescribingthetopologyoflargenetworksthatspanasdiversefieldsasthe(k)thatavertexinthenetworkinteractswithkotherverticesdecaysasapower-law,followingP(k)∼k−γ.Thisresultindicatesthatlargenetworksself-organizeintoascale-freestate,afeatureunexpectedbyallexistingrandomnetworkmodels.Tounderstandtheoriginofthisscaleinvariance,weshowthatexistingnetworkmodelsfailto2incorporategrowthandpreferentialattachment,twokeyfeaturesofrealnetworks.Usingamodelincorporatingthesetwoingredients,weshowthattheyareresponsibleforthepower-lawscalingobservedinrealnetworks.Finally,wearguethattheseingredientsplayaneasilyidentifiableandimportantroleintheformationofmanycomplexsystems,implyingthatourresultsarerelevanttoalargeclassofnetworksobservedinNature.Whiletherearealargenumberofsystemsthatformcomplexnetworks,detailedtopo-logicaldataisavailableonlyforafew.Thecollaborationgraphofmovieactorsrepresentsawelldocumentedexampleofasocialnetwork.Eachactorisrepresentedbyavertex,twoactorsbeingconnectediftheywerecasttogetherinthesamemovie.Theprobabilitythatanactorhasklinks(characterizinghisorherpopularity)hasapower-lawtailforlargek,followingP(k)∼k−γactor,whereγactor=2.3±0.1(Fig.1A).Amorecomplexnetworkwithover800millionvertices(8)isthe’sconnectivityand,consequently,oureffectivenessinlocatinginformationonthe(5).InformationaboutP(k)canbeobtainedusingrobots(6),indicatingthattheprobabilitythatkdocumentspointtoacertainwebpagefollowsapower-law,withγ=2.1±0.1(Fig.1B)(9).AnetworkwhosetopologyreflectsthehistoricalpatternsofurbanandindustrialdevelopmentistheelectricalpowergridofwesternUS,theverticesrepresentinggenerators,transformersandsubstations,theedgescorrespondingtothehighvoltagetransmissionlinesbetweenthem(10).Duetotherelativelymodestsizeofthenet-work,containingonly4941vertices,thescalingregionislessprominent,butisneverthelessapproximatedwithapower-lawwithanexponentγpower≃4(Fig.1C).Finally,aratherlarge,complexnetworkisformedbythecitationpatternsofthescientificpublications,theverticesstandingforpaperspublishedinrefereedjournals,theedgesrepresentinglinkstothearticlescitedinapaper.RecentlyRedner(11)hasshownthattheprobabilitythatapaperiscitedktimes(representingtheconnectivityofapaperwithinthenetwork)followsapower-lawwithexponentγcite=3.Theaboveexamples(12)demonstratethatmanylargerandomnetworkssharethecom-3monfeaturethatthedistributionoftheirlocalconnectivityisfreeofscale,followingapower-lawforlargek,withanexponentγbetween2.1and4whichisunexpecte