Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors

DOI10.1002/RSA.20696MaRDI QIDQ4978431zbMATH OpenOpenAlexFDO

Authors Ronen Eldan, Miklós Z. Rácz, Tselil Schramm

Publication date 10 August 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Braess's paradoxgraph Laplacianrandom graphsspectral gap

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study how the spectral gap of the normalized Laplacian of a random graph changes when an edge is added to or removed from the graph. There are known examples of graphs where, perhaps counterintuitively, adding an edge can decrease the spectral gap, a phenomenon that is analogous to Braess's paradox in traffic networks. We show that this is often the case in random graphs in a strong sense. More precisely, we show that for typical instances of ErdH{o}s-R'enyi random graphs $G(n,p)$ with constant edge density $pin(0,1)$, the addition of a random edge will decrease the spectral gap with positive probability, strictly bounded away from zero. To do this, we prove a new delocalization result for eigenvectors of the Laplacian of $G(n,p)$, which might be of independent interest.

Recommendations

• Braess's Paradox in large random graphs
• The spectral gap of a random subgraph of a graph
• Braess's paradox in expanders
• On the Laplacian Eigenvalues of G_n,p
• The Spectral Gap of Random Graphs with Given Expected Degrees

Cites work

• Braess's paradox in expanders
• Braess's Paradox in large random graphs
• Delocalization of eigenvectors of random matrices with independent entries
• Eigenvectors of random graphs: nodal domains
• Entrywise bounds for eigenvectors of random graphs
• Estimates for the concentration function of combinatorial number theory and probability
• scientific article; zbMATH DE number 3099315 (Why is no real title available?)
• On a lemma of Littlewood and Offord
• On the spectra of general random graphs
• Random covariance matrices: universality of local statistics of eigenvalues
• Random matrices: universality of local eigenvalue statistics
• Random matrices: Universality of local eigenvalue statistics up to the edge
• Small ball probabilities for linear images of high-dimensional distributions
• Sparse random graphs: eigenvalues and eigenvectors
• Spectra of random graphs with given expected degrees
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• The eigenvalues of random symmetric matrices
• Über ein Paradoxon aus der Verkehrsplanung

Cited in

(11)

• Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
• Noise sensitivity for the top eigenvector of a sparse random matrix
• On delocalization of eigenvectors of random non-Hermitian matrices
• Braess's Paradox in large random graphs
• Eigenvector delocalization for non‐Hermitian random matrices and applications
• Spectral dynamics of guided edge removals and identifying transient amplifiers for death-birth updating
• Sum-of-squares lower bounds for densest k-subgraph
• Cycle-star motifs: network response to link modifications
• Phase transition for the bottom singular vector of rectangular random matrices
• No-gaps delocalization for general random matrices
• Convergence of the density of states and delocalization of eigenvectors on random regular graphs

This page was built for publication: Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors

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