Probability of graphs with large spectral gap by multicanonical Monte Carlo

DOI10.1016/J.CPC.2010.06.039MaRDI QIDQ546962zbMATH OpenOpenAlexFDO

Authors Nen Saito, Yukito Iba

Publication date 30 June 2011

Published in Computer Physics Communications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.1023

zbMATH Keywords

large deviationmulticanonical Monte CarloRamanujan graphrandom graphspectral gap

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Applications of graph theory (05C90)

Abstract: Graphs with large spectral gap are important in various fields such as biology, sociology and computer science. In designing such graphs, an important question is how the probability of graphs with large spectral gap behaves. A method based on multicanonical Monte Carlo is introduced to quantify the behavior of this probability, which enables us to calculate extreme tails of the distribution. The proposed method is successfully applied to random 3-regular graphs and large deviation probability is estimated.

Recommendations

• The Spectral Gap of Random Graphs with Given Expected Degrees
• On the spectra of large sparse graphs with cycles
• The spectral gap of random graphs with given expected degrees
• Asymptotic spectral analysis of growing graphs: a quantum probabilistic approach
• Spectral techniques applied to sparse random graphs

Cites work

• A Guide to Monte Carlo Simulations in Statistical Physics
• Eigenvalues and expanders
• Equation of state calculations by fast computing machines
• scientific article; zbMATH DE number 2115090 (Why is no real title available?)
• scientific article; zbMATH DE number 2193965 (Why is no real title available?)
• Large deviations of the maximum eigenvalue in Wishart random matrices
• Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that
• Ramanujan graphs

Cited in

(2)

• Multicanonical MCMC for sampling rare events: an illustrative review
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks

This page was built for publication: Probability of graphs with large spectral gap by multicanonical Monte Carlo

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