与えられた期待度を持つランダムグラフのスペクトル

冪法則グラフのスペクトルの研究には、基本的に二つの競合するアプローチがあります。一つはウィグナーの半円法則の類似を証明すること、もう一つは固有値が冪法則分布に従うことを予測することです。半円法則と冪法則は共通点がないものの、適切な行列を考慮すれば、両方のアプローチが本質的に正しいことを示します。特定の条件下で、ランダム冪法則グラフの（正規化された）ラプラス行列の固有値は半円法則に従い、一方の冪法則グラフの隣接行列のスペクトルは冪法則に従います。我々の結果は、与えられた期待度を持つランダムグラフの分析と、いくつかの重要な不変量との関係に基づいています。固有値分布における位相転移が発生する指数_β_のいくつかの（新しい）値が興味深いです。スペクトル分布は、例えば急速に混合するマルコフ連鎖を含むランダム化アルゴリズムのような数多くのグラフアルゴリズムに直接的な影響を与えます。1