Random Hyperbolic Graphs: Degree Sequence and Clustering - (Extended 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.

• Publication year

  2012

• Venue

  International Colloquium on Automata, Languages and Programming

• Publication date

  2012-05-07

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-31585-5_51arXiv 1205.1470
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Hyperbolic Geometry of Complex Networks

  2010cited by this paper
• Sustaining the Internet with Hyperbolic Mapping

  2010cited by this paper
• Affiliation networks

  2009cited by this paper
• Models for the Compressible Web

  2009cited by this paper
• Concentration of Measure for the Analysis of Randomized Algorithms

  2009influential reference
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces

  2008influential reference
• First to market is not everything: an analysis of preferential attachment with fitness

  2007cited by this paper
• Geographic Routing Using Hyperbolic Space

  2007cited by this paper
• Clustering in complex networks. I. General formalism.

  2006cited by this paper
• Mathematical results on scale‐free random graphs

  2005cited by this paper
• Graphs over time: densification laws, shrinking diameters and possible explanations

  2005cited by this paper
• On a conjecture related to geometric routing

  2004cited by this paper
• On the curvature of the Internet and its usage for overlay construction and distance estimation

  2004cited by this paper
• Clustering in complex networks

  2004cited by this paper
• A Brief History of Generative Models for Power Law and Lognormal Distributions

  2004cited by this paper
• Popularity based random graph models leading to a scale-free degree sequence

  2004cited by this paper
• Why social networks are different from other types of networks.

  2003cited by this paper
• A general model of web graphs

  2003cited by this paper
• Random geometric graphs.

  2002cited by this paper
• Predicting Internet network distance with coordinates-based approaches

  2002cited by this paper
• Random evolution in massive graphs

  2001cited by this paper
• The degree sequence of a scale‐free random graph process

  2001cited by this paper
• Classes of small-world networks.

  2000cited by this paper
• On power-law relationships of the Internet topology

  1999cited by this paper
• Emergence of Scaling in Random Networks

  1999cited by this paper
• Internet: Diameter of the World-Wide Web

  1999cited by this paper
• Emergence of scaling in random networks

  1999cited by this paper
• Collective dynamics of ‘small-world’ networks

  1998influential reference
• HYPERBOLIC GEOMETRY

  1996cited by this paper
• An Experimental Study of the Small World Problem

  1969cited by this paper
• The Small World Problem

  1967cited by this paper

• Central limit theorem for linear eigenvalue statistics of random geometric graphs

  2026cites this paper
• On Distributed Colouring of Hyperbolic Random Graphs

  2026cites this paper
• Normal approximation for subgraph counts in age-dependent random connection models

  2025cites this paper
• Network renormalization

  2024cites this paper
• Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring

  2024influential citation
• Limit theorems under heavy-tailed scenario in the age-dependent random connection models

  2024cites this paper
• Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models

  2024cites this paper
• Structure and Independence in Hyperbolic Uniform Disk Graphs

  2024cites this paper
• Symmetry-driven embedding of networks in hyperbolic space

  2024influential citation
• Metric structural human connectomes: Localization and multifractality of eigenmodes

  2024cites this paper
• Hyperbolic Benchmarking Unveils Network Topology-Feature Relationship in GNN Performance

  2024cites this paper
• Renormalization of networks with weak geometric coupling.

  2024cites this paper
• Statistical Mechanics of Directed Networks

  2024cites this paper
• Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs

  2023cites this paper
• Four universal growth regimes in degree-dependent first passage percolation on spatial random graphs I

  2023influential citation
• Random graphs and real networks with weak geometric coupling

  2023cites this paper
• Scalable Algorithms for Laplacian Pseudo-inverse Computation

  2023cites this paper
• Recognizing Unit Disk Graphs in Hyperbolic Geometry is ∃R-Complete

  2023cites this paper
• Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs

  2023cites this paper
• On the Giant Component of Geometric Inhomogeneous Random Graphs

  2023cites this paper
• On the Number of Maximal Cliques in Two-Dimensional Random Geometric Graphs: Euclidean and Hyperbolic

  2023cites this paper
• Improved Exact and Heuristic Algorithms for Maximum Weight Clique

  2023cites this paper
• Dynamics of cold random hyperbolic graphs with link persistence

  2022cites this paper
• The PACE 2022 Parameterized Algorithms and Computational Experiments Challenge: Directed Feedback Vertex Set

  2022cites this paper
• Emergence of Geometric Turing Patterns in Complex Networks

  2022cites this paper
• Analysis of the survival time of the SIRS process via expansion

  2022cites this paper
• Unveiling the Sampling Density in Non-Uniform Geometric Graphs

  2022cites this paper
• On Hyperbolic Unit Disk Graphs

  2022cites this paper
• Cover and hitting times of hyperbolic random graphs

  2022cites this paper
• Hyperbolic trees for efficient routing computation

  2022cites this paper
• Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane

  2021influential citation
• An anomalous topological phase transition in spatial random graphs

  2021cites this paper
• The modularity of random graphs on the hyperbolic plane

  2021cites this paper
• p-adic numbers encode complex networks

  2021influential citation
• Horospherical random graphs and lockdown strategies

  2021cites this paper
• Computing Voronoi Diagrams in the Polar-Coordinate Model of the Hyperbolic Plane

  2021cites this paper
• Scale-free percolation mixing time

  2021cites this paper
• Scale-free percolation in continuous space: quenched degree and clustering coefficient

  2021cites this paper
• Dynamics of hot random hyperbolic graphs

  2021cites this paper
• Strongly Hyperbolic Unit Disk Graphs

  2021cites this paper
• Discrete Hyperbolic Random Graph Model

  2021cites this paper
• Latent Space Network Modelling with Continuous and Discrete Geometries.

  2021cites this paper
• Latent Space Network Modelling with Hyperbolic and Spherical Geometries

  2021cites this paper
• Cliques in geometric inhomogeneous random graphs

  2021cites this paper
• An Experimental Study of External Memory Algorithms for Connected Components

  2021cites this paper
• Network geometry

  2020cites this paper
• Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs

  2020cites this paper
• Clustering in a hyperbolic model of complex networks

  2020influential citation
• Beating the Worst-Case: Analysis of a Practical Algorithm for Treewidth

  2020cites this paper
• Hyperbolic Trees in Complex Networks

  2020cites this paper
• Limit theory for isolated and extreme points in hyperbolic random geometric graphs

  2020cites this paper
• Recent Advances in Scalable Network Generation

  2020cites this paper
• On the largest component of subcritical random hyperbolic graphs

  2020cites this paper
• Increasing efficacy of contact-tracing applications by user referrals and stricter quarantining

  2020cites this paper
• Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry

  2020cites this paper
• Normal approximation via non-linear exchangeable pairs

  2020cites this paper
• The contact process on random hyperbolic graphs: Metastability and critical exponents

  2020influential citation
• Not all interventions are equal for the height of the second peak

  2020cites this paper
• Large-scale graph generation: Recent results of the SPP 1736 – Part II

  2020cites this paper
• Degree correlations in scale-free random graph models

  2019cites this paper
• Networks with communities and clustering

  2019cites this paper
• From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)

  2019cites this paper
• Scale-free percolation in continuum space: quenched degree and clustering coefficient

  2019cites this paper
• Limit theory for the number of isolated and extreme points in hyperbolic random geometric graphs

  2019cites this paper
• Hamilton cycles and perfect matchings in the KPKVB model

  2019cites this paper
• Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs

  2019cites this paper
• Efficiently generating geometric inhomogeneous and hyperbolic random graphs

  2019cites this paper
• Anti-concentration for subgraph counts in random graphs

  2019cites this paper
• ETH-tight algorithms for geometric network problems

  2019cites this paper
• Connectivity and mobility in wireless networks

  2019cites this paper
• Communication Optimization by Data Replication for Distributed Graph Algorithms

  2019cites this paper
• Closure coefficients in scale-free complex networks

  2019cites this paper
• Hyperbolic Multiplex Network Embedding with Maps of Random Walk

  2019cites this paper
• Random Graph Modeling

  2019cites this paper
• Scaling up real networks by geometric branching growth

  2019cites this paper
• Link persistence and conditional distances in multiplex networks

  2018cites this paper
• Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry

  2018influential citation
• Towards a Systematic Evaluation of Generative Network Models

  2018cites this paper
• Geometric Inhomogeneous Random Graphs and Graph Coloring Games

  2018cites this paper
• High Performance Algorithms for Quantum Gravity and Cosmology

  2018cites this paper
• N I ] 1 O ct 2 01 8 Spatial networks with wireless applications

  2018cites this paper
• Confined spatial networks with wireless applications

  2018cites this paper
• Updating Dynamic Random Hyperbolic Graphs in Sublinear Time

  2018cites this paper
• Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane

  2018cites this paper
• Hyperbolic intersection graphs and (quasi)-polynomial time

  2018cites this paper
• Scale-free network clustering in hyperbolic and other random graphs

  2018cites this paper
• Sub-tree counts on hyperbolic random geometric graphs

  2018cites this paper
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs

  2018cites this paper
• Spatial networks with wireless applications

  2018cites this paper
• On the Second Largest Component of Random Hyperbolic Graphs

  2017influential citation
• Communication Efficient Algorithms for Generating Massive Networks

  2017cites this paper
• Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory

  2017cites this paper
• Degree correlations in scale-free null models

  2017cites this paper
• University of Birmingham Law of large numbers for the largest component in a hyperbolic model of complex networks

  2017influential citation
• Existence of Small Separators Depends on Geometry for Geometric Inhomogeneous Random Graphs

  2017cites this paper
• Navigability of Random Geometric Graphs in the Universe and Other Spacetimes

  2017cites this paper
• University of Birmingham Typical distances in a geometric model for complex networks

  2017cites this paper
• Communication-Free Massively Distributed Graph Generation

  2017cites this paper
• Hyperbolic grids and discrete random graphs

  2017influential citation
• The diameter of KPKVB random graphs

  2017cites this paper