论文标题
从图形取样的大图的拉普拉斯频谱
The Laplacian Spectrum of Large Graphs Sampled from Graphons
论文作者
论文摘要
本文研究了从图形子中采样的拉普拉斯频谱和（大）图的平均有效性。从广义上讲，我们的主要发现是，可以使用相应的图形函数有效地近似大型图形的拉普拉斯特征值。更具体地说，我们展示了如何近似Laplacian特征值的分布以及该图的平均有效性（Kirchhoff指数）。在所有情况下，我们都会在近似错误上提供明确的界限，并得出当节点数量到Infinity时，误差为零的渐近率。我们的主要结果证明了图形分段lipschitz并远离零的条件。
This paper studies the Laplacian spectrum and the average effective resistance of (large) graphs that are sampled from graphons. Broadly speaking, our main finding is that the Laplacian eigenvalues of a large dense graph can be effectively approximated by using the degree function of the corresponding graphon. More specifically, we show how to approximate the distribution of the Laplacian eigenvalues and the average effective resistance (Kirchhoff index) of the graph. For all cases, we provide explicit bounds on the approximation errors and derive the asymptotic rates at which the errors go to zero when the number of nodes goes to infinity. Our main results are proved under the conditions that the graphon is piecewise Lipschitz and bounded away from zero.
