Geometric inhomogeneous random graphs
From MaRDI portal
Abstract: Real-world networks, like social networks or the internet infrastructure, have structural properties such as large clustering coefficients that can best be described in terms of an underlying geometry. This is why the focus of the literature on theoretical models for real-world networks shifted from classic models without geometry, such as Chung-Lu random graphs, to modern geometry-based models, such as hyperbolic random graphs. With this paper we contribute to the theoretical analysis of these modern, more realistic random graph models. Instead of studying directly hyperbolic random graphs, we use a generalization that we call geometric inhomogeneous random graphs (GIRGs). Since we ignore constant factors in the edge probabilities, GIRGs are technically simpler (specifically, we avoid hyperbolic cosines), while preserving the qualitative behaviour of hyperbolic random graphs, and we suggest to replace hyperbolic random graphs by this new model in future theoretical studies. We prove the following fundamental structural and algorithmic results on GIRGs. (1) As our main contribution we provide a sampling algorithm that generates a random graph from our model in expected linear time, improving the best-known sampling algorithm for hyperbolic random graphs by a substantial factor O(n^0.5). (2) We establish that GIRGs have clustering coefficients in {Omega}(1), (3) we prove that GIRGs have small separators, i.e., it suffices to delete a sublinear number of edges to break the giant component into two large pieces, and (4) we show how to compress GIRGs using an expected linear number of bits.
Recommendations
Cites work
- scientific article; zbMATH DE number 410743 (Why is no real title available?)
- scientific article; zbMATH DE number 2079399 (Why is no real title available?)
- scientific article; zbMATH DE number 871936 (Why is no real title available?)
- scientific article; zbMATH DE number 6303023 (Why is no real title available?)
- A Bound for the Diameter of Random Hyperbolic Graphs
- A spatial preferential attachment model with local clustering
- A spatial web graph model with local influence regions
- An approximation theorem for the Poisson binomial distribution
- Bootstrap percolation and the geometry of complex networks
- Bootstrap percolation on geometric inhomogeneous random graphs
- Cliques in hyperbolic random graphs
- Clustering and the hyperbolic geometry of complex networks
- Connected components in random graphs with given expected degree sequences
- Efficient embedding of scale-free graphs in the hyperbolic plane
- Efficient generation of networks with given expected degrees
- Emergence of Scaling in Random Networks
- Exact and efficient generation of geometric random variates and random graphs
- Generating Random Hyperbolic Graphs in Subquadratic Time
- Greedy routing and the algorithmic small-world phenomenon
- Grid methods in simulation and random variate generation
- Hyperbolic random graphs: separators and treewidth
- Models for the Compressible Web
- On a conditionally Poissonian graph process
- On a geometrization of the Chung-Lu model for complex networks
- On the diameter of hyperbolic random graphs
- Random Geometric Graphs
- Random hyperbolic graphs: degree sequence and clustering (extended abstract)
- Scale-free percolation
- Structures in supercritical scale-free percolation
- The average distances in random graphs with given expected degrees
- The geometric protean model for on-line social networks
- The phase transition in inhomogeneous random graphs
- The structure of geographical threshold graphs
- Typical distances in a geometric model for complex networks
Cited in
(44)- Graph distances in scale-free percolation: the logarithmic case
- Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
- Directed random geometric graphs
- Recurrence versus transience for weight-dependent random connection models
- Not all interventions are equal for the height of the second peak
- Cluster-size decay in supercritical long-range percolation
- A random graph model for clustering graphs
- Polynomial growth in degree-dependent first passage percolation on spatial random graphs
- Sampling geometric inhomogeneous random graphs in linear time
- Cliques in geometric inhomogeneous random graphs
- scientific article; zbMATH DE number 5942363 (Why is no real title available?)
- Scale-free percolation in continuous space: quenched degree and clustering coefficient
- Cover and hitting times of hyperbolic random graphs
- From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
- On the second largest component of random hyperbolic graphs
- Spatial Gibbs random graphs
- Spectral gap of random hyperbolic graphs and related parameters
- Greed is good for deterministic scale-free networks
- Penalising transmission to hubs in scale-free spatial random graphs
- Scale-free percolation mixing time
- On the largest component of subcritical random hyperbolic graphs
- Scale-free graphs with many edges
- Exact and efficient generation of geometric random variates and random graphs
- The emergence of a giant component in one-dimensional inhomogeneous networks with long-range effects
- Geometric random intersection graphs with general connection probabilities
- Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds
- On connectivity in random graph models with limited dependencies
- Bounds on the satisfiability threshold for power law distributed random SAT
- Greedy routing and the algorithmic small-world phenomenon
- Lectures on random geometric graphs
- Popularity-similarity random SAT formulas
- Local limits of spatial inhomogeneous random graphs
- The contact process on random hyperbolic graphs: metastability and critical exponents
- Detecting a botnet in a network
- Networks of random trees as a model of neuronal connectivity
- Geometric random graphs vs inhomogeneous random graphs
- On the distances within cliques in a soft random geometric graph
- The impact of heterogeneity and geometry on the proof complexity of random satisfiability
- Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
- Scaling of the clustering function in spatial inhomogeneous random graphs
- Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs.
- Phase transitions and percolation at criticality in enhanced random connection models
- Transience versus recurrence for scale-free spatial networks
- Hyperbolic graph generator
This page was built for publication: Geometric inhomogeneous random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1713405)
