Random hyperbolic graphs: degree sequence and clustering (extended abstract)
From MaRDI portal
Abstract: In the last decades, the study of models for large real-world networks has been a very popular and active area of research. A reasonable model should not only replicate all the structural properties that are observed in real world networks (for example, heavy tailed degree distributions, high clustering and small diameter), but it should also be amenable to mathematical analysis. There are plenty of models that succeed in the first task but are hard to analyze rigorously. On the other hand, a multitude of proposed models, like classical random graphs, can be studied mathematically, but fail in creating certain aspects that are observed in real-world networks. Recently, Papadopoulos, Krioukov, Boguna and Vahdat [INFOCOM'10] introduced a random geometric graph model that is based on hyperbolic geometry. The authors argued empirically and by some preliminary mathematical analysis that the resulting graphs have many of the desired properties. Moreover, by computing explicitly a maximum likelihood fit of the Internet graph, they demonstrated impressively that this model is adequate for reproducing the structure of real graphs with high accuracy. In this work we initiate the rigorous study of random hyperbolic graphs. We compute exact asymptotic expressions for the expected number of vertices of degree k for all k up to the maximum degree and provide small probabilities for large deviations. We also prove a constant lower bound for the clustering coefficient. In particular, our findings confirm rigorously that the degree sequence follows a power-law distribution with controllable exponent and that the clustering is nonvanishing.
Recommendations
Cited in
(50)- Spectral gap of random hyperbolic graphs and related parameters
- Geometric inhomogeneous random graphs
- Law of large numbers for the largest component in a hyperbolic model of complex networks
- The contact process on random hyperbolic graphs: metastability and critical exponents
- Limit theory for isolated and extreme points in hyperbolic random geometric graphs
- Clustering in a hyperbolic model of complex networks
- On the largest component of subcritical random hyperbolic graphs
- Greedy routing and the algorithmic small-world phenomenon
- Penalising transmission to hubs in scale-free spatial random graphs
- Not all interventions are equal for the height of the second peak
- Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
- Solving vertex cover in polynomial time on hyperbolic random graphs
- The probability of connectivity in a hyperbolic model of complex networks
- Clustering and the hyperbolic geometry of complex networks
- Typical distances in a geometric model for complex networks
- On the diameter of hyperbolic random graphs
- Hyperbolicity, degeneracy, and expansion of random intersection graphs
- On the diameter of hyperbolic random graphs
- Updating dynamic random hyperbolic graphs in sublinear time
- Scale-free percolation in continuous space: quenched degree and clustering coefficient
- Sub-tree counts on hyperbolic random geometric graphs
- Scale-free network clustering in hyperbolic and other random graphs
- Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs.
- From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
- Sampling geometric inhomogeneous random graphs in linear time
- The diameter of KPKVB random graphs
- Degree correlations in scale-free random graph models
- On the second largest component of random hyperbolic graphs
- Hyperbolic graph generator
- Non-hyperbolicity of random graphs with given expected degrees
- Clustering and the hyperbolic geometry of complex networks
- Towards a Systematic Evaluation of Generative Network Models
- scientific article; zbMATH DE number 7662451 (Why is no real title available?)
- A random graph model for clustering graphs
- Scale-free percolation mixing time
- Cliques in high-dimensional geometric inhomogeneous random graphs
- Cover and hitting times of hyperbolic random graphs
- Polynomial growth in degree-dependent first passage percolation on spatial random graphs
- Four universal growth regimes in degree-dependent first passage percolation on spatial random graphs
- Average distance in a general class of scale-free networks
- Limit theorems under heavy-tailed scenario in the age-dependent random connection models
- The PACE 2022 parameterized algorithms and computational experiments challenge: directed feedback vertex set
- Tail bounds for detection times in mobile hyperbolic graphs
- Hamilton cycles and perfect matchings in the KPKVB model
- Cliques in hyperbolic random graphs
- Hyperbolic random graphs: clique number and degeneracy with implications for colouring
- Structure and independence in hyperbolic uniform disk graphs
- Statistical mechanics of random hyperbolic graphs within the fermionic maximum-entropy framework
- Enumeration of graphs with a heavy-tailed degree sequence
- Bootstrap percolation and the geometry of complex networks
This page was built for publication: Random hyperbolic graphs: degree sequence and clustering (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167045)
