Hur utvecklas verkliga grafer med tiden? Vilka är normala tillväxtmönster i sociala, tekniska och informationsnät? Många studier har upptäckt mönster i statiska grafer, identifiera egenskaper i en enda ögonblicksbild av ett stort nätverk eller i ett mycket litet antal ögonblicksbilder; dessa inkluderar tunga svansar för i- och utgrader distributioner, samhällen, små-världen fenomen, och andra. Med tanke på bristen på information om nätutvecklingen under långa perioder har det dock varit svårt att omvandla dessa resultat till uttalanden om trender över tid. Här studerar vi ett brett spektrum av verkliga grafer, och vi observerar några överraskande fenomen. Först, de flesta av dessa grafer densify över tid med antalet kanter som växer superlinjärt i antalet noder. För det andra krymper det genomsnittliga avståndet mellan noderna ofta över tiden i motsats till den konventionella visdomen att sådana avståndsparametrar bör öka långsamt som en funktion av antalet noder (som O(log n) eller O(log(log n)). Befintliga grafgenerering modeller uppvisar inte dessa typer av beteende ens på en kvalitativ nivå. Vi tillhandahåller en ny grafgenerator, baserad på en skogsbrand spridningsprocess som har en enkel, intuitiv motivering, kräver mycket få parametrar (som brandfarlighet noder), och producerar grafer som uppvisar alla de egenskaper som observerats både i tidigare arbete och i den nuvarande studien. Tillstånd att göra digitala eller hårda kopior del eller allt detta arbete för personligt eller klassrum användning beviljas utan avgift förutsatt att kopior inte görs eller distribueras för vinst eller direkta kommersiella fördelar och att kopior visar detta meddelande på första sidan eller första skärmen av en skärm tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Tillstånd kan begäras från publikationsavdelningen., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 ( Vi märker också att skogsbrand modellen uppvisar en skarp övergång mellan glesa grafer och grafer som förtätar. Diagram med minskande avstånd mellan noderna genereras runt denna övergångspunkt. Slutligen analyserar vi sambandet mellan tidsutvecklingen av gradens fördelning och förtätningen av en graf. Vi finner att de två är i grunden relaterade till varandra. Vi observerar också att verkliga nätverk uppvisar denna typ av relation mellan förtätning och examensfördelningen.
Efter att ha jämfört med många tidigare empiriska studier av de storskaliga nätverken gav de en ny grafgenereringsalgoritm, baserad på Skogsbrandens spridningsprocess REF.
Graph evolution: Densification and shrinking diameters
{'venue': 'TKDD', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Physics']}