Probability of graphs with large spectral gap by multicanonical Monte Carlo

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.

3pages 4figures

References in corpus (4)

• Extreme Value Statistics of Eigenvalues of Gaussian Random Matrices
• Performance of networks of artificial neurons: The role of clustering
• Large Deviations of the Maximum Eigenvalue in Wishart Random Matrices
• Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that

Cited by in corpus (7)

• Emergence of cooperative bistability and robustness of gene regulatory networks
• Sampling motif-constrained ensembles of networks
• Multicanonical MCMC for Sampling Rare Events
• Evolution enhances mutational robustness and suppresses the emergence of a new phenotype: A new computational approach for studying evolution
• Robustness Leads Close to the Edge of Chaos in Coupled Map Networks: toward the understanding of biological networks
• Evolution of Genetic Redundancy : The Relevance of Complexity in Genotype-Phenotype Mapping
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks