Hyperbolism är en egenskap hos en graf som kan ses som en "mjuk" version av ett träd, och nyligen empiriskt och teoretiskt arbete har föreslagit att många grafer som uppstår i Internet och relaterade data applikationer har hyperboliska egenskaper. Här tar vi hänsyn till Gromovs uppfattning om δ-hyperbolicity, och vi etablerar flera positiva och negativa resultat för småvärlds- och trädliknande slumpmässiga grafmodeller. Först studerar vi hyperbolismen hos klassen Kleinberg small-world slumpmässiga grafer KSW (n, d, γ), där n är antalet hörn i grafen, d är dimensionen av den underliggande bas rutnät B, och γ är den lilla världen parameter sådan att varje nod u i grafen ansluter till en annan nod v i grafen med sannolikhet proportionell mot 1/d B (u, v) γ med d B (u, v) är rutnätet avstånd från u till v i bas rutnätet B. Vi visar att när γ = d, parametervärdet som möjliggör effektiv decentraliserad routing i Kleinbergs small-world nätverk, med sannolikhet 1 − o(1) är den hyperboliska σ (log n) 1 1.5(d+1)+ε ) för alla ε > 0 oberoende av n. Jämförande med diametern på  till (log n) i detta fall, indikerar det att hyperbolismen inte avsevärt förbättras jämfört med grafdiameter även när långdistansförbindelser avsevärt förbättrar decentraliserad navigering. Vi visar också att för andra värden av γ är den hyperboliska δ antingen på samma nivå eller mycket nära grafdiametern, vilket tyder på dålig hyperbolism i dessa grafer också. Därefter studerar vi en klass av trädliknande grafer som kallas ringformade träd som har konstant hyperbolism. Vi visar att lägga slumpmässiga länkar bland bladen på ett sätt som liknar de små värld graf konstruktioner kan lätt förstöra hyperboliciteten av graferna, utom för en klass av slumpmässiga kanter läggs till med hjälp av en exponentiellt sönderfallande sannolikhetsfunktion baserad på ringavståndet bland bladen. Vår studie ger ett av de första betydande analysresultat på hyperbolismen hos en rik klass av slumpmässiga grafer, som kastar ljus över sambandet mellan hyperbolism och farbarhet av slumpmässiga grafer, liksom över känsligheten för hyperboliska δ för ljud i slumpmässiga grafer.
Mer nyligen, Chen et al. REF beaktade hyperboliciteten hos små världsgrafer och trädliknande slumpmässiga grafer.
On the Hyperbolicity of Small-World and Tree-Like Random Graphs
{'venue': 'ISAAC', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Physics']}