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

Ronen Eldan, Miklós Z. Rácz, Tselil SchrammRandom Struct. Algorithms 2017 · OpenReview

TL;DR

This paper investigates Braess's paradox – where adding a road can increase traffic congestion – in the context of random graphs. The authors demonstrate that, counterintuitively, adding a random edge to a typical Erdős-Rényi random graph is likely to decrease its spectral gap, a measure of graph connectivity. This phenomenon is linked to the delocalization of eigenvectors of the graph's Laplacian.

What Problem Does This Paper Address?

The spectral gap of a graph's Laplacian is a crucial property related to its connectivity and how efficiently information (or random walks) can spread through it. Intuitively, adding edges to a graph should improve its connectivity and thus increase its spectral gap. However, there are known counterexamples, like the "barbell graph," where adding an edge can paradoxically decrease the spectral gap. This is analogous to Braess's paradox in traffic networks, where adding a new road can lead to increased congestion. The authors aim to understand how prevalent this "Braess's paradox" phenomenon is in random graphs, specifically Erdős-Rényi random graphs, and to connect it to the behavior of the graph's eigenvectors.

Methods

The paper's core contribution lies in proving that for typical Erdős-Rényi random graphs $G(n,p)$ with constant edge probability $p$, adding a random edge will decrease the spectral gap with a probability bounded away from zero. This is achieved by:

  1. Establishing a general condition for spectral gap decrease: They derive a condition based on the second eigenvector of the graph Laplacian. If this eigenvector has a smaller Rayleigh quotient in the graph with the added edge, the spectral gap decreases.
  2. Proving a delocalization result for eigenvectors: A key technical contribution is proving that for typical random graphs, the second eigenvector of the normalized Laplacian is "delocalized." This means its mass is spread out across many vertices, rather than concentrated on a few. Specifically, a constant fraction of the eigenvector's entries have magnitudes of a similar order. This is a novel result for eigenvectors beyond the first one.
  3. Connecting delocalization to Braess's paradox: The delocalization of the second eigenvector is shown to be a sufficient condition for the spectral gap to decrease when a random edge is added.

The proofs involve sophisticated techniques from random matrix theory, including concentration inequalities (Littlewood-Offord type), union bounds, and detailed analysis of graph properties for typical random graph instances.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of random graph models.

Key Insights and Ideas

  • Braess's Paradox is common in random graphs: The paper provides strong theoretical evidence that the counterintuitive phenomenon of adding an edge decreasing connectivity is not an anomaly but a common occurrence in random graphs.
  • Eigenvector delocalization is key: The surprising result is that the delocalization of eigenvectors (specifically, the second one) is what drives the spectral gap decrease. This is a departure from the intuition that more "spread out" eigenvectors might imply better connectivity.
  • New delocalization results: The paper establishes a new type of delocalization result for eigenvectors of the normalized Laplacian of random graphs, which is crucial for their main theorem and may be of independent interest.

Key Results

  • Theorem 1: For fixed $p \in (0,1)$, the probability that adding a random edge to a random graph $G(n,p)$ decreases its spectral gap is bounded away from zero as $n \to \infty$.
  • Theorem 2: For fixed $p \in (0,1)$ and $\eta > 0$, a constant fraction of entries of the second eigenvector of the normalized Laplacian of $G(n,p)$ have magnitudes at least $\frac{1}{\sqrt{n} (\log n)^{\eta}}$ with high probability. This quantifies the delocalization.
  • Corollary 1: This implies a weaker version of a conjecture by Fan Chung, stating that the probability of an edge removal increasing the spectral gap is bounded away from zero.

Limitations and Future Work

  • Constant edge density: The results are proven for constant edge density $p \in (0,1)$. The authors note that their proofs might extend to $p = n^{-\epsilon}$ for small $\epsilon > 0$, but they did not optimize for this. Extending to sparser or denser graphs could be a future direction.
  • Focus on the second eigenvector: While the paper proves delocalization for the second eigenvector, it suggests that similar results might hold for other eigenvectors corresponding to eigenvalues not too close to 0 or 1. Further investigation into the delocalization of the entire spectrum is a natural extension.
  • General graphs: The paper focuses on random graphs. Investigating the prevalence of Braess's paradox and eigenvector delocalization in other classes of graphs (e.g., graphs with specific community structures) would be valuable.

Summary updated

BibTeX
@inproceedings{eldan2017braess,
  author = {Ronen Eldan and Miklós Z. Rácz and Tselil Schramm},
  title = {{Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors}},
  booktitle = {Random Struct. Algorithms},
  year = {2017},
  url = {https://openreview.net/forum?id=uXC2DZLqs2},
}
Figure