Sampling Geometric Inhomogeneous Random Graphs in Linear Time

DOI10.4230/LIPIcs.ESA.2017.20zbMath1442.05204OpenAlexW2963760219MaRDI QIDQ5111706

Johannes Lengler, Karl Bringmann, Ralph Keusch

Publication date: 27 May 2020

Full work available at URL: https://dblp.uni-trier.de/db/conf/esa/esa2017.html#BringmannKL17

zbMATH Keywords

compression algorithmsrandom graph modelsreal-world networkssampling algorithmshyperbolic random graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Not all interventions are equal for the height of the second peak, Spatial networks and percolation. Abstracts from the workshop held January 17--23, 2021 (hybrid meeting), The emergence of a giant component in one-dimensional inhomogeneous networks with long-range effects, Local limits of spatial inhomogeneous random graphs, Unnamed Item, Scaling of the clustering function in spatial inhomogeneous random graphs, Unnamed Item, Greed is good for deterministic scale-free networks, Updating Dynamic Random Hyperbolic Graphs in Sublinear Time, Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs, From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial), On the largest component of subcritical random hyperbolic graphs, Degree correlations in scale-free random graph models, Greedy routing and the algorithmic small-world phenomenon, Penalising transmission to hubs in scale-free spatial random graphs, Sampling Geometric Inhomogeneous Random Graphs in Linear Time

Uses Software

• WebGraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scale-free percolation
• Cliques in hyperbolic random graphs
• Bootstrap percolation and the geometry of complex networks
• Spectral gap of random hyperbolic graphs and related parameters
• Structures in supercritical scale-free percolation
• When is a scale-free graph ultra-small?
• Connected components in random graphs with given expected degree sequences
• A Spatial Preferential Attachment Model with Local Clustering
• Clustering and the Hyperbolic Geometry of Complex Networks
• Efficient Generation of Networks with Given Expected Degrees
• The Geometric Protean Model for On-Line Social Networks
• The Structure of Geographical Threshold Graphs
• A Spatial Web Graph Model with Local Influence Regions
• Emergence of Scaling in Random Networks
• Random Hyperbolic Graphs: Degree Sequence and Clustering
• Typical distances in a geometric model for complex networks
• On the Diameter of Hyperbolic Random Graphs
• Generating Random Hyperbolic Graphs in Subquadratic Time
• Random Geometric Graphs
• Bootstrap percolation on geometric inhomogeneous random graphs
• Hyperbolic Random Graphs: Separators and Treewidth
• Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane
• The Average Distance in a Random Graph with Given Expected Degrees
• Sampling Geometric Inhomogeneous Random Graphs in Linear Time
• Models for the Compressible Web
• A Bound for the Diameter of Random Hyperbolic Graphs
• The phase transition in inhomogeneous random graphs
• Exact and Efficient Generation of Geometric Random Variates and Random Graphs
• Greedy Routing and the Algorithmic Small-World Phenomenon
• The average distances in random graphs with given expected degrees
• On a conditionally Poissonian graph process