Spectral gap of random hyperbolic graphs and related parameters

DOI10.1214/17-AAP1323MaRDI QIDQ1650095zbMATH OpenWikidataFDO

Authors D. Mitsche, Marcos Kiwi

Publication date 29 June 2018

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.02240, https://projecteuclid.org/euclid.aoap/1523433629

zbMATH Keywords

conductancerandom hyperbolic graphsspectral gap

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: Random hyperbolic graphs have been suggested as a promising model of social networks. A few of their fundamental parameters have been studied. However, none of them concerns their spectra. We consider the random hyperbolic graph model as formalized by [GPP12] and essentially determine the spectral gap of their normalized Laplacian. Specifically, we establish that with high probability the second smallest eigenvalue of the normalized Laplacian of the giant component of and $n$-vertex random hyperbolic graph is $Omega(n^{-(2alpha-1)}/D)$, where $frac12<alpha<1$ is a model parameter and $D$ is the network diameter (which is known to be at most polylogarithmic in $n$). We also show a matching (up to a polylogarithmic factor) upper bound of $n^{-(2alpha-1)}(logn{)}^{1+o(1)}$. As a byproduct we conclude that the conductance upper bound on the eigenvalue gap obtained via Cheeger's inequality is essentially tight. We also provide a more detailed picture of the collection of vertices on which the bound on the conductance is attained, in particular showing that for all subsets whose volume is $O(n^{1-varepsilon})$ the obtained conductance is with high probability $Omega(n^{-(2alpha-1)varepsilon+o(1)})$. Finally, we also show consequences of our result for the minimum and maximum bisection of the giant component.

Recommendations

• A Bound for the Diameter of Random Hyperbolic Graphs
• The spectral gap of random graphs with given expected degrees
• The Spectral Gap of Random Graphs with Given Expected Degrees
• Spectra of random regular hypergraphs
• On the Laplacian Eigenvalues of G_n,p

Cites work

• Bootstrap percolation on geometric inhomogeneous random graphs
• Clustering and the hyperbolic geometry of complex networks
• Geometric bounds for eigenvalues of Markov chains
• Geometric inhomogeneous random graphs
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Law of large numbers for the largest component in a hyperbolic model of complex networks
• On the diameter of hyperbolic random graphs
• On the largest component of a hyperbolic model of complex networks
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Scale-free percolation
• Spectral gap of random hyperbolic graphs and related parameters
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The probability of connectivity in a hyperbolic model of complex networks
• Typical distances in a geometric model for complex networks

Cited in

(22)

• Spectral gap of random hyperbolic graphs and related parameters
• 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
• Clustering in a hyperbolic model of complex networks
• On the largest component of subcritical random hyperbolic graphs
• Penalising transmission to hubs in scale-free spatial random graphs
• Spatial networks and percolation. Abstracts from the workshop held January 17--23, 2021 (hybrid meeting)
• Optimal Cheeger cuts and bisections of random geometric graphs
• Emergence of a spectral gap in a class of random matrices associated with split graphs
• Lack of hyperbolicity in asymptotic Erdős-Renyi sparse random graphs
• Sub-tree counts on hyperbolic random geometric graphs
• Sampling geometric inhomogeneous random graphs in linear time
• The diameter of KPKVB random graphs
• On the second largest component of random hyperbolic graphs
• scientific article; zbMATH DE number 6781574 (Why is no real title available?)
• Scale-free percolation mixing time
• Cover and hitting times of hyperbolic random graphs
• Average distance in a general class of scale-free networks
• Tail bounds for detection times in mobile hyperbolic graphs
• Hamilton cycles and perfect matchings in the KPKVB model
• Hyperbolic random graphs: clique number and degeneracy with implications for colouring
• Statistical mechanics of random hyperbolic graphs within the fermionic maximum-entropy framework

This page was built for publication: Spectral gap of random hyperbolic graphs and related parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1650095)