期刊
RANDOM STRUCTURES & ALGORITHMS
卷 50, 期 4, 页码 584-611出版社
WILEY
DOI: 10.1002/rsa.20696
关键词
random graphs; spectral gap; Braess's paradox; graph Laplacian
资金
- NSF [DMS 1106999, DGE 1106400]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据