Braess's Paradox for the Spectral Gap in Random Graphs and Delocalization of Eigenvectors
Braess's Paradox for the Spectral Gap in Random Graphs and Delocalization of Eigenvectors
复制标题
DOI：
10.1002/rsa.20696
复制
发表时间：
2017-07-01
影响因子：
1
通讯作者：
Schramm, Tselil
中科院分区：
文献类型：
--
作者：
Eldan, Ronen;Racz, Miklos Z.;Schramm, Tselil
我们研究随机图的归一化拉普拉斯算子的谱间隙在向图中添加或删除边时如何变化。在一些已知的图表示例中，添加边缘可能会减少频谱间隙，这可能与直觉相反，这种现象类似于交通网络中的布雷斯悖论。我们证明，在强烈意义上，随机图中经常出现这种情况。更准确地说，我们证明了对于 Erdos-Renyi 随机图 G(n, p) 的典型实例，边密度 p 恒定。 (0, 1)，添加随机边缘将以正概率减小光谱间隙，严格限制在远离零的范围内。为此，我们证明了 G(n, p) 拉普拉斯算子特征向量的新离域结果，这可能具有独立意义。 (C) 2016 年 Wiley 期刊公司。
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 counter-intuitively, 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 Erdos-Renyi random graphs G(n, p) with constant edge density p. (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. (C) 2016 Wiley Periodicals, Inc.